1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set Theory: Prove a function is injective

Tags:
  1. Aug 28, 2015 #1
    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 [tex]P(E)\rightarrow P(A) X P(B)[/tex] be defined by
    [tex]f(X)=(A\cap X,B\cap X)[/tex]

    Show that f is injective if and only if [tex]A\cup B=E[/tex]
    Show that f is surjective if and only if [tex]A\cap B=\varnothing[/tex]

    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. jcsd
  3. Aug 28, 2015 #2

    Geofleur

    User Avatar
    Science Advisor
    Gold Member

    For starters, do you understand the terms in the problem and what it's asking for?
     
  4. Aug 28, 2015 #3
    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
     
  5. Aug 28, 2015 #4

    Geofleur

    User Avatar
    Science Advisor
    Gold Member

    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?
     
  6. Aug 28, 2015 #5

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
     
  7. Aug 29, 2015 #6
    Can you tell me what the "X" is in [tex]f(X)=(A\cap X, B\cap X)[/tex] ?

    is X a subset of E where [tex]X \in A[/tex] or [tex]X \in B[/tex]?

    or is X a subset of P(E)?
     
  8. Aug 29, 2015 #7

    Geofleur

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  9. Aug 29, 2015 #8
    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 [tex]A \cup B=E[/tex]

    Most proofs start out with something like:

    Let [tex] a,b \in E[/tex] and I would need to show [tex]f(a)=f(b)[/tex] implies [tex]a=b[/tex]
     
  10. Aug 29, 2015 #9

    Geofleur

    User Avatar
    Science Advisor
    Gold Member

    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 ##.
     
  11. Aug 29, 2015 #10
    Okay, so I would have:

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

    So can I say that ordered pair [tex](A \cap X,B \cap X) \in C_1[/tex] ?
     
  12. Aug 29, 2015 #11

    Geofleur

    User Avatar
    Science Advisor
    Gold Member

    ## 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.
     
  13. Aug 29, 2015 #12
    Thanks for your time Geofleur, Ill do some more problems.
     
  14. Aug 29, 2015 #13

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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)##.
     
  15. Aug 29, 2015 #14
    ahh, that clears quite a bit up! Thanks vela!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Set Theory: Prove a function is injective
Loading...