Set Theory: Prove a function is injective

[DeldotB]

Homework Statement

Hello,
I need some help on the following. I am BRAND new to set theory and this was in my first HW assignment and I am 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

Homework Equations

None

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: I am new to set theory.

 

[Geofleur]

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

 

[DeldotB]

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

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 don't know the terms of the problem

 

[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?

 

[vela]

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 don't know the terms of the problem

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.

 

[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)?

 

[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.

 

[DeldotB]

P(E) is all 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.

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 haven't seen a function like this. I know what it "does" but I am 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

 

[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$.

 

[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 ?

 

[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.

 

[DeldotB]

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

 

[vela]

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)$.

 

[DeldotB]

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)$.

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