1. Function Question

Hello,

I've been having trouble with the following question:

I'm having a tough time understand whats really going on... I feel I know what a function is, how it's defined, and when its one to one, but this question, I dont understand...

Say U is, {1,3,5}
Say A is 3
Say S is 5

F{3}(5) = {3} - 5
= 3
??

But how is that not one to one then?

Can anybody shed some light on this problem for me? :-S

Thanks for any help,

2. Originally Posted by kcp133
Hello,

I've been having trouble with the following question:

I'm having a tough time understand whats really going on... I feel I know what a function is, how it's defined, and when its one to one, but this question, I dont understand...

Say U is, {1,3,5}
Say A is 3
Say S is 5

F{3}(5) = {3} - 5
= 3
??

But how is that not one to one then?

Can anybody shed some light on this problem for me? :-S

Thanks for any help,

as you should see, S must be in the power set.. hence it should be the set {5}.. also, note that the function gives you an element of the power set..

my proof might be completely wrong because i proved it the way i know when proving something like this..

proof:
let $A \subseteq U$ and suppose $f_A : \wp (U) \rightarrow \wp (U)$, where $\wp (U)$ is the power set of U, and defined by $f_A(S) = A - S$, is one-one..

Let $X \in \wp (U)$.. since $f_A(S) = A - S$ is one-one for $S \in \wp (U)$, then $f_A(X) = A - X \implies f_A(X) + X = A$..
by definition, $f_A(X) , X \in \wp {U} (\implies f_A(X) , X \subseteq U)$, hence $f_A(X) + X \subseteq U$ and also $f_A(X) + X \subseteq A$..

since $X$ was arbitrary and we started with $X \in \wp (U)$ or $X \subseteq U$, then $A=U$.

Let A=U and suppose for $X,Y \subseteq A$, $f_A(X) = f_A(Y)$.. clearly, $f_A(X) = A - X = A - Y = f_A(Y) \implies X=Y$..

therefore, $f_A$ is one-one.. QED

3. If $A = U$ then clearly $f_U (B) = U \backslash B = B^c$ is one-to-one. Because $B^c = C^c \; \Rightarrow \;B = C$.

Now suppose $f_A (S) = A \backslash S$ is one-to-one. If $A \ne U$ then $\left( {\exists b \in A^c } \right)$.
Thus $\left. \begin{gathered} f_A \left( {\{ b\} } \right) = A\backslash \{ b\} = A \hfill \\ f_A \left( \emptyset \right) = A\backslash \emptyset = A \hfill \\ \end{gathered} \right\}\; \Rightarrow \;\left\{ b \right\} = \emptyset$ because $f_A$ is one-to-one.
That is a contradiction. So $A = U$.

4. forgive me here, but this is for my first course in discrete math and i still feel a bit new to it all...

Originally Posted by Plato
If $A = U$ then clearly $f_U (B) = U \backslash B = B^c$ is one-to-one. Because $B^c = C^c \; \Rightarrow \;B = C$.
I get $A = U$, $f_U (B) = U \backslash B = B^c$ but what is $C^c$? Where does it come from, how does that help you conclude that the function is one-to-one?

--
Originally Posted by Plato
Now suppose $f_A (S) = A \backslash S$ is one-to-one. If $A \ne U$ then $\left( {\exists b \in A^c } \right)$.
Thus $\left. \begin{gathered} f_A \left( {\{ b\} } \right) = A\backslash \{ b\} = A \hfill \\ f_A \left( \emptyset \right) = A\backslash \emptyset = A \hfill \\ \end{gathered} \right\}\; \Rightarrow \;\left\{ b \right\} = \emptyset$ because $f_A$ is one-to-one.
That is a contradiction. So $A = U$.
Okay so " $\left( {\exists b \in A^c } \right)$" just says its not empty, which you prove is false, correct?
But someone like me, might not know that this is the way to do the proof... For example, I would have approached this part trying to prove that A is not a subset of U and vice versa... which would have wasted my exam-taking time and likely landed me no where?

How can someone realize these kinds of tricks? Just experience?

Then, $f_A ( {\{ b\} } ) = A\backslash \{ b\} = A$ -- This part i dont really get either? your plugging in this set for S, but how do you know that A-S will still be A?

I appreciate the help :-)

5. That operation A-S or A\S is called set minus. In other words, You are removing from A any element that A has in common with S. So basically $A\backslash S = A \cap S^c$ , A intersect the complement of S.
Look at a couple of examples.
A={1,2,3,4,5,6}, S={2,4,6,8,0}: A\S={1,3,5}, S\A={8,0}, A\A is empty.
So if b is not in A then A\{b}=A because nothing is taken away from A.

For your first question, we want to show that if A=U then $f_A$ is one-to-one.
So suppose that
$\begin{gathered}
f_A (B) = f_A (C) \hfill \\
U\backslash B = U\backslash C \hfill \\
B^c = C^c \hfill \\
B = C \hfill \\
\end{gathered}$
.
If the complements of two set are equal then the set are equal.
This is the standard way of proving a function is one-to-one.
Say f(x)=f(y) and prove that x=y.

6. :-D

thanks for the help, the proof makes sense now