Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete mathematics, bijections between disjoint unions

  1. Oct 24, 2012 #1
    Hi,
    So I am trying to show the following:
    ##(A \cup B)\sqcup(A \cap B) \leftrightarrow A \sqcup B##

    The proof that I am trying to understand starts with:
    ##A \leftrightarrow (A \backslash B) \sqcup (A\cup B) \qquad (1)##,
    and
    ##A \cup B \leftrightarrow (A\backslash B)\sqcup B \qquad (2)##

    These two both make sense, in the first one we see that ##(A \backslash B) ## with ## (A\cup B)## is a partition of A, and thus there are bijections from ##(A \backslash B) ## to ## \{ (x,0) : x \in (A \backslash B) \}## and from ##A \cap B## to ##\{ (y,1) : y \in A \cap B \}##, and the same argument for ##(2)##

    The next step in the proof says that:
    ##(A \cup B)\sqcup(A \cap B) \leftrightarrow (A\backslash B)\sqcup B \sqcup (A \cap B) ## which (apparently) follows from ##(2)##
    and then, ##(1)## apparently means that
    ##(A\backslash B)\sqcup B \sqcup (A \cap B) \leftrightarrow A \sqcup B## which proves it.
    But I don't understand how ##(1)## and ##(2)## helps us in these steps, can you just exchange terms like that? Anyone care to explain? Thanks..
     
    Last edited: Oct 24, 2012
  2. jcsd
  3. Oct 25, 2012 #2
    What the"##\sqcup##" stand for??
     
  4. Oct 25, 2012 #3
    ##A \sqcup B## is the disjoint union of ##A## and ##B##, defined by:
    ##A \sqcup B = \{(x,0):x \in A \} \cup \{(y,1):y \in B \}##
     
  5. Oct 25, 2012 #4

    Erland

    User Avatar
    Science Advisor

    And ##\leftrightarrow## ? Does that simlpy mean equality (=) here?
     
  6. Oct 25, 2012 #5
    I thought this was standard notation in (discrete) mathematics, but anyway,
    ##A \leftrightarrow B## means that there exists a bijection between ##A## and ##B##.
     
  7. Oct 26, 2012 #6
    So there is not a single person on the board who knows about this? It is from a first course in discrete mathematics for 2nd year students.
     
  8. Oct 26, 2012 #7
    I can't get your example to work when using this definition. I don't get it at all.
     
  9. Oct 26, 2012 #8
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Discrete mathematics, bijections between disjoint unions
Loading...