Discrete Mathematics - Determine if the following function is onto, one to one or both.

Question

I have a test next week and im going through a sample test. One of the questions involves determining if the function is one-to-one, onto or both. I managed to proof its not one-to-one but am stuck on onto.

The question is in terms of sets where the domain is the cross product of two power sets A and B and the range is the power set of a union of two sets A and B.

I understand the definition of onto and am able to do math related questions fine but this question has completely thrown me because of the sets. i really need some help on proofing that its onto.

1) Determine whether the following function is one-to-one, onto or both.

F: P(A) X P(B) = P(A U B)

F((X,Y)) = X U Y

where A={a,b}, B={c,d}

any help is appreciated.

Answer 1

To prove that the function is onto you need to show that given an arbitrary value in the range there's an argument in the domain that gives this value.

Now repeat with specifics:

To prove that $F$ is onto you need to show that given an arbitrary value $T \in P(A \cup B)$ there's an argument $S \in P(A) \cup P(B)$ such that $F(S)=T$.

This looks scary but mostly because of all the powersets. Always remember that to belong to a powerset of $X$ is just the same thing as to be a subset of $X$, no more and no less. So let's unpack the $P$'s:

$T$ is some subset of $A \cup B$, while you need to find $S$, which is a pair $(X,Y)$ of a subset $X \subset A$ and a subset $Y \subset B$. You need to find $X$ and $Y$ so that $T = X \cup Y$.

Intuitively, you're given something from $A$ and something from $B$, but all packed together into $T$. You need to divide this $T$ into two parts, one part $X$ includes everything that comes from $A$ and the other $Y$ everything that comes from $B$. Then their union will be exactly $T$ which is what you want.

By now the solution (of how to define $X$ and $Y$ given $T$) should sort of seem obvious to you, and if not, try to reread the above and focus on understanding what every sentence says, exactly.

Answer 2

Onto:

imagine 5 apples and 3 boxes. now each box must have at least one apple. i.e it can have 1 or 2 or more as long as there's enough to put in the other boxes too.

One to One:

imagine again 5 apples and 3 boxes. here you don't have to fill every box with apples but if you do, you can only put one apple.

hope it helps

Answer 3

To see that $F$ is one-to-one, we need to show that for any $C, S \subseteq A$ and for any $D, T \subseteq B$, if $C \cup D = S \cup T$, then $C = S$ and $D = T$. This can be established by showing that four subset inclusions hold. I'll just prove one of them; the rest follow by symmetry.

We want to show that $C \subseteq S$. To this end, choose any $x \in C$. We claim that $x \in S$. Otherwise, if we suppose towards a contradiction that $x \notin S$, then since $x \in S \subseteq S \cup T$, it follows that $x \in T \subseteq B$. But since $x \in S \subseteq A$, it follows that $x \in A \cap B = \varnothing$, a contradiction. Hence, $C \subseteq S$, as desired.