# Homework Help: Set Theory: Prove a function is injective

Tags:
1. Aug 28, 2015

### DeldotB

1. The problem statement, all variables and given/known data

Hello,
I need some help on the following. Im BRAND new to set theory and this was in my first HW assignment and Im not sure where to start.
The question is as follows:

Let A and B be parts of a set E
Let $$P(E)\rightarrow P(A) X P(B)$$ be defined by
$$f(X)=(A\cap X,B\cap X)$$

Show that f is injective if and only if $$A\cup B=E$$
Show that f is surjective if and only if $$A\cap B=\varnothing$$

notation: P(A) denotes the set of all parts of A

2. Relevant equations

None

3. The attempt at a solution

I do not have anything in my notes that remotely resembles this. Any pointers on how I should get started? Remember: Im new to set theory.

2. Aug 28, 2015

### Geofleur

For starters, do you understand the terms in the problem and what it's asking for?

3. Aug 28, 2015

### DeldotB

Well, I know the definition of injectivity and surjectivity. Does it say that the parts of E are mapping to ordered pairs (a,b) where a is in P(A) and b is in P(B)?
Im not sure about "defined by" f(X)=(A intersect X, B intersect X)

So basically: no, I dont know the terms of the problem

4. Aug 28, 2015

### Geofleur

Think of a function as a machine that eats one thing and spits another thing out. The first line, $P(E) \rightarrow P(A) \times P(B)$ is saying that the function will eat a subset (or "part") of E and spit out an ordered pair, the first item of which is a subset of A and the second item of which is a subset of B. The second line, $f(X) = (A \cap X, B \cap X)$ is telling you specifically which subsets of A and B will go in the ordered pair. You seem to intuitively have understood this.

Start with just the injectivity. Take some easier to understand function, like $f(x) = x^3$, defined on the real numbers, and see if you can prove that it is injective. What assumption do you have to start with in order to do this? How does the proof end?

5. Aug 28, 2015

### vela

Staff Emeritus
I don't know if it was a typo, but I suspect the problem says "Let $f: P(E) \to P(A)\times P(B)$ be defined by $f(X) = (A \cap X, B \cap X)$. So you're right in thinking it maps subsets of E to the ordered pair (a, b) where a and b are, respectively, subsets of A and B.

6. Aug 29, 2015

### DeldotB

Can you tell me what the "X" is in $$f(X)=(A\cap X, B\cap X)$$ ?

is X a subset of E where $$X \in A$$ or $$X \in B$$?

or is X a subset of P(E)?

7. Aug 29, 2015

### Geofleur

P(E) is the collection of all subsets of E. X is an element of P(E), which means that it is a subset of E. A and B are also subsets of E. It does not make sense to say that X is an element of A or of B. It could be a subset of either, but it doesn't have to be.

8. Aug 29, 2015

### DeldotB

Okay, so given this, how would I start? I guess the function is confusing me. All worked examples work with a function like f(x)=2x+1 or f(x)=x^2 and so on...
I havent seen a function like this. I know what it "does" but Im confused about how to actually prove its injective using the information $$A \cup B=E$$

Most proofs start out with something like:

Let $$a,b \in E$$ and I would need to show $$f(a)=f(b)$$ implies $$a=b$$

9. Aug 29, 2015

### Geofleur

To show that a function is injective, you have to show that f(a) = f(b) implies that a = b. In this case, the function takes sets as arguments, so you will want to start with $f(C_1) = f(C_2)$, where $C_1$ and $C_2$ are subsets of E. Then you'll have to find a way to show that $C_1 = C_2$, using the information that $A \cup B = E$. Note that the problem asks you to prove that f is injective if and only if $A \cup B = E$. So you'll also have to assume that f is injective and show that this implies $A \cup B = E$.

10. Aug 29, 2015

### DeldotB

Okay, so I would have:

Let $$C_1,C_2 \in E$$,
Since f is injective , this implies $$f(C_{1})=f(C_2)$$.

So can I say that ordered pair $$(A \cap X,B \cap X) \in C_1$$ ?

11. Aug 29, 2015

### Geofleur

$C_1$ and $C_2$ are subsets of E, not elements of E. f is injective means: $f(C_1)=f(C_2)$ implies $C_1 = C_2$. Before tackling this problem, it might be a good idea to do some simpler problems that are just about sets, set membership, and subsets, without involving the additional complication of a function.

12. Aug 29, 2015

### DeldotB

Thanks for your time Geofleur, Ill do some more problems.

13. Aug 29, 2015

### vela

Staff Emeritus
It might help you to look at a specific example of E, A, and B to see how everything fits together. Let E = {1,2,3}, A={1,2}, and B={2,3}. Then you have
\begin{align*}
P(E) &= \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\} \\
P(A) &= \{\emptyset, \{1\}, \{2\}, \{1,2\}\} \\
P(B) &= \{\emptyset, \{2\}, \{3\}, \{2,3\}\}
\end{align*} The domain of $f$ is P(E). The codomain of $f$ is the set
\begin{align*}
P(A)\times P(B) = \left\{ \begin{array}{cccc}
(\emptyset, \emptyset), & (\{1\}, \emptyset), & (\{2\}, \emptyset), & (\{1,2\}, \emptyset), \\
(\emptyset, \{2\}), & (\{1\}, \{2\}), & (\{2\}, \{2\}), & (\{1,2\}, \{2\}), \\
(\emptyset, \{3\}), & (\{1\}, \{3\}), & (\{2\}, \{3\}), & (\{1,2\}, \{3\}), \\
(\emptyset, \{2,3\}), & (\{1\}, \{2,3\}), & (\{2\}, \{2,3\}), & (\{1,2\}, \{2,3\}) \\
\end{array}\right\}
\end{align*} Suppose $X = \{1, 3\} \in P(E)$. Note $X$ is a set, not an element of E. Then
\begin{align*}
f(X) &= (A \cap X, B \cap X) \\
&= (\{1,2\} \cap \{1,3\}, \{2,3\} \cap \{1,3\}) \\
&= (\{1\}, \{3\})
\end{align*} which is an element of $P(A) \times P(B)$.

14. Aug 29, 2015

### DeldotB

ahh, that clears quite a bit up! Thanks vela!!