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

Basic Set theory question

  1. Sep 14, 2008 #1

    I am having trouble constructing the sentences in this proof.

    Its very simple, proof that [tex]A \cup \left( B \cap C \right) = \left( A \cup B \right) \cap \left( A \cup B \right) [/tex]

    So basically I need to show that if [tex] x \in A \cup \left( B \cap C \right)[/tex] then [tex]x \in \left( A \cup B \right) \cap \left( A \cup B \right)[/tex]

    Here is what I got:

    If [tex] x \in A \cup \left( B \cap C \right)[/tex] then [tex] x \in A[/tex] or [tex] x \in \left( B \cap C \right)[/tex]. Which means that either [tex] x \in A[/tex], or [tex] x \in B[/tex] and [tex] x \in C[/tex]...

    First Question,

    I feel like there is ambiguity here. "Either x in A, or x in B and x in C " can be interpreted two ways right? You could read it: [tex] x \in \left( A \cup B \right) \cap C [/tex] or you could read it as intended [tex] x \in A \cup \left( B \cap C \right)[/tex] How can I make the sentence clear that I want the latter?

    Second question,

    From here is it ok for me to make the jump to x in A or B, and x in A or C? It seems clear to me that this is the case, but I am not sure if something is left to be said before I make this claim.

    Thanks for help!
  2. jcsd
  3. Sep 14, 2008 #2
    I'll do my best to answer.
    First off while yes you need to show what you say you need to show, but you also have to show that if [tex]x \in \left( A \cup B \right) \cap \left( A \cup B \right)[/tex] then [tex] x \in A \cup \left( B \cap C \right)[/tex]. This is because = is essentially a bi-conditional statement, so you need to show that the left side is a subset of the right side but also that the right side is a subset of the left side. If that is true, then they are equal.

    Secondly, I would simply write "x is a member of A or x is a member of the intersection of B and C." Do you have to write that part in words? Seems like symbolic would be better.

    I think you can make that jump, but you should clarify why you are making the jump.
  4. Sep 15, 2008 #3
    Thanks that helps, I have finished it and I think made it perfectly clear. And yes I am aware that I have to show it both ways. If I can get it one way going backwards is usually very easy.

    I have another one, that I am stuck on at the moment and maybe you would be so kind to help. Latex was taking too long so I am going to try to write it out using no Latex.

    Show that (A - B) x C = (A x C) - (B x C)

    So I start the same way

    let (x, y) /in (A - B) x C.

    This is the set {(x,y) | x in A and x not in B, y in C}

    I Want to be able to say the following:

    This is the same as saying all x in A and y in C, and all x not in B and y not in C.

    But I am not sure I can make this leap, does this need justification?
  5. Sep 16, 2008 #4
    Ok things were a bit more complicated than I thought they would be...

    But that was because I didn't understand what the complement of BxC was until I drew myself a picture.

    But I solved it, and now I am moving on, thanks!
  6. Sep 16, 2008 #5
    WOULD you care to give a short proof of the above i am just curious

  7. Sep 19, 2008 #6
    One direction is:
    (A - B) x C = (A x C) - (B x C)

    Let (a,c) in (A - B) x C then a in A - B and c in C.

    a in A - B -> a in A and A not in B.

    a in A and c in C -> (a,c) in A x C.

    a not in B -> (a , x) not in B x C for all x. (in particular our c).

    therefore (a, c) in (A x C) - (B x C) as (a, c) in A x C and (a, c) not in B x C.
  8. Sep 19, 2008 #7
    According to what theorem axiom or law of logic do you get and i quote;

    .........a not in B -> (a , x) not in B x C for all x. (in particular our c)..........................

    I am sorry i can make no justification for that step
  9. Sep 19, 2008 #8
    Let A and B be a set.
    Assume for some a, a is not contained in A.

    AxB = all (x, y) such that x in A and y in B.

    since a is not in A (a, y) can not be in AxB for any y.
  10. Sep 19, 2008 #9
    Yeah what Diffy said. In other more formal terms:
    By definition A x B = { (a,b) | a in A and b in B }

    For a given (x, y) to be in A x B, x must be in A and y must be in B, so if (x , y) is not in A x B, then either x not in A or y not in B, or both of course, but we take that for granted :)
  11. Sep 19, 2008 #10
    Each step in amathematical proof is justified by either a theorem ,an axiom,a definition or a law of logic words like because.......but of course.......obviously.............can you see ..............its easy e.t.c have no place at all.

    Things that you may understand or you think you understand other people may not, so how are you going to convince them ?
  12. Sep 20, 2008 #11


    User Avatar
    Science Advisor

    The justification is the definition of "B x C".

    B x C is defined as the set of all pairs (x, y) such that x is in B and y is in C. If a is not in B, then there is no pair in B x C with first member a- i.e. (a, x) is not in B x C for any x.
  13. Sep 20, 2008 #12


    User Avatar
    Science Advisor

    Which post was this in response to? No one has said any thing like that.
  14. Sep 20, 2008 #13
    so how do we prove:

    ~aεB ====> ~(a,x)ε(B x C) ,for all x?

    your reasoning is rather intuitive is just like saying can 2+2 be other than 4?

    but this can be proved too
  15. Sep 20, 2008 #14
    Are you ok with the following statement?
    If a is not in B, then there is no pair in B x C with first member a.

    I would say it's by definition, but suppose there exists a c such that (a, c) in B x C, then
    a in B and c in C by definition.

    Contradition because we said a not in B by assumption. I bolded the 2 contradictory things.
    The c was chosen as any arbitraty element of C, therefore no c in C works.

    That's where I got the statement:
    (a, x) is not in B x C for any x. (and in particular, the x's in C since x not in C would be "even more" not in B x C).
  16. Oct 3, 2008 #15

    after all there is a proof by contradiction.

    another way to show that ~(a,c)ε(BxC) i.e (a,c)does not belong to BxC IS THE following:

    ~aεΒ ===> ~aεB v ~cεC ( BY disjunction introduction) ===> ~( aεA^ cεC ) ( BY de morgan) ====> ~(a,c)ε(ΒxC)
  17. Oct 3, 2008 #16


    User Avatar
    Homework Helper

    (x,y) & \in (A-B) \times C \quad \text{means}\\
    x \in A-B, & y \in C \quad \text{so}\\
    x \in A, x \not \in B & y \in C \quad \text{so}\\
    (x,y) & \in A \times C, (x,y) \not \in B \times C \quad \text{so}\\
    (A-B) \times C & \subseteq (A \times C) - (B \times C)

    To go the other way

    (x,y) & \in (A \times C) - (B \times C) \quad \text{means}\\
    (x,y) \in A \times C, & (x,y) \not \in B \times C \quad \text{so} \\
    \left(x \in A \text{ and } y \in C \right) & \text{ and } \left(x \not \in B \text{ and } y \in C\right) \quad \text{so}\\
    x \in A-B & \text{ and } y \in C \quad \text{which gives}\\
    x \in (A-B) \times C

    so that

    (A \times C) - (B \times C) \subseteq (A-B) \times C

    These two give the equality of the sets - no need for reference to quantifiers or symbolic logic - just the definitions of Cartesian product, set equality, and subsets.
  18. Oct 3, 2008 #17
    Nearly all proofs in set theory after dropping quantifiers are based on proofs in symbolic logic .

    And in our example this can be shown in the following way.

    (A-B)xC= (AxC)-(BxC) <===> {(x,y)ε[(A-B)xC] <====> {(x,y)ε[(AxC)-(BxC)]} <====>

    { [(xεA & ~xεB) & yεC] <=====> [ ( xεA & yεC) & ~(xεB & yεC)]},and if we put now, xεA=P , xεB=q, yεC=r the above becomes.

    p & ~q & r <====> p & r & ~( q & r) and this is problem in propositional calculus

    Hence a virtuoso in symbolic logic will not miss a proof in set theory,after dropping quantifiers that is
  19. Oct 4, 2008 #18


    User Avatar
    Homework Helper

    "Hence a virtuoso in symbolic logic"

    If I ever see anything written by one I'll be impressed.
    I am aware (probably more than you) of the relationships. However, I am also aware that people who ask for guidance in one area are typically not interested in showmanship, which is all you seem intent on offering.

    If this post is "beyond the pale" as our locale saying goes, I expect the moderators will delete it; I accept their decision in advance.
  20. Oct 4, 2008 #19
    I am sorry for the sentence "hence a virtuoso in sumbolic................."

    My intentions are not showmanship.

    But is not a fact that in the heart of the proof of each set problem is symbolic logic??
  21. Oct 4, 2008 #20


    User Avatar
    Homework Helper

    Thank you for your apology - I owe a larger one to you.
    There is no doubt that set theory and symbolic logic are deeply intertwined - I stress the similarities when I teach our only class (unfortunately a survey class) that covers both topics.
    The point I wanted make (and which, re-reading, bollixed tremendously) is that elegant as it may be, a brief proof of the result written in the language and notation of logic might not provide a glimpse at the mechanics a person studying an introduction to set theory needs.
    It wasn't a comment on ability, or elegance, but on suitability at this level.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook