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 $\displaystyle A \subseteq U$ and suppose $\displaystyle f_A : \wp (U) \rightarrow \wp (U)$, where $\displaystyle \wp (U)$ is the power set of U, and defined by $\displaystyle f_A(S) = A - S$, is one-one..

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

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

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

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

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

Now suppose $\displaystyle f_A (S) = A \backslash S$ is one-to-one. If $\displaystyle A \ne U$ then $\displaystyle \left( {\exists b \in A^c } \right)$.
Thus $\displaystyle \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 $\displaystyle f_A$ is one-to-one.
That is a contradiction. So $\displaystyle 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 $\displaystyle A = U$ then clearly $\displaystyle f_U (B) = U \backslash B = B^c$ is one-to-one. Because $\displaystyle B^c = C^c \; \Rightarrow \;B = C$.
I get $\displaystyle A = U$, $\displaystyle f_U (B) = U \backslash B = B^c$ but what is $\displaystyle 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 $\displaystyle f_A (S) = A \backslash S$ is one-to-one. If $\displaystyle A \ne U$ then $\displaystyle \left( {\exists b \in A^c } \right)$.
Thus $\displaystyle \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 $\displaystyle f_A$ is one-to-one.
That is a contradiction. So $\displaystyle A = U$.
Okay so "$\displaystyle \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, $\displaystyle 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 $\displaystyle 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 $\displaystyle f_A$ is one-to-one.
So suppose that
$\displaystyle \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