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

Elementary Set Theory Proof

  1. Jul 15, 2011 #1
    Hello,

    I am teaching myself Set Theory, and in doing some exercises I came across the problem:

    Given sets A and B, prove that [itex]A \subseteq B[/itex] if and only if [itex]A \cap B = A[/itex].

    My proof, in natural language, is in two parts:

    1) Prove that if [itex]A \subseteq B[/itex], [itex]A \cap B = A[/itex].

    By the definition of subsets, all elements [itex]x \in A[/itex] are also [itex]x \in B[/itex]. By definition, [itex]A \cap B = \left\{x: x \in A \wedge x \in B \right\}[/itex]. Since all elements of A are also elements of B, but not all elements of B are necessarily elements of A, the intersection fo the two is A.

    2) Prove that if [itex]A \cap B \neq A[/itex], it is not true that [itex]A \subseteq B[/itex].

    If the intersection of A and B is not A, then there are necessarily elements of A that are not elements of B, therefore A is not a subset of B.

    Therefore, [itex]A \subseteq B[/itex] if and only if [itex]A \cap B = A[/itex]. Q.E.D.

    Is this a sufficient proof?

    If it is, could someone help me translate it into the language of formal language?

    Edit: Fixed wrong logical connective, set notation.
     
    Last edited: Jul 15, 2011
  2. jcsd
  3. Jul 15, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Hi WisheDeom! :smile:

    Here you probably mean [itex]\wedge[/itex] and not [itex]\vee[/itex].

    This only proves that [itex]A\subseteq A\cap B[/itex]? What about the other inclusion?

    You again use that [itex]A\cap B\subseteq A[/itex], you may want to prove this.

    The proof looks good except for the remarks I posted.

    I like the style of the proof. What do you mean with "formal language"? You mean with symbols like [itex]\Rightarrow,~\forall,~\wedge[/itex] and stuff?
     
  4. Jul 15, 2011 #3
    Unless I'm missing something, this theorem isn't true. It's almost true, but consider the case where A = B.
     
  5. Jul 15, 2011 #4
    The theorem is true even in the case where A=B
     
  6. Jul 15, 2011 #5
    Thank you for the responses.

    Yes, of course.

    This is what I was trying to do in the second part, but see below.

    Would you be able to go into a little more detail? I know this is very basic, but I am just starting. :smile:

    Yeah, that's what I meant. I guess my approach in learning the subject is a bit of a mix of "naive" and "axiomatic" set theory.

    Yes, of course, I should have written "a subset of or equal to". I fixed the notation in the OP.
     
  7. Jul 15, 2011 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    You say

    But the only thing I can infer from the statement "If the intersection of A and B is not A" is that there either is an element in A but not in [itex]A\cap B[/itex] or there is an element in [itex]A\cap B[/itex], but not in A. One of these possibilities cannot happen, namely that there is an element in [itex]A\cap B[/itex] but not in A. But for that you need to show first that [itex]A\cap B\subseteq A[/itex]
     
  8. Jul 15, 2011 #7
    Ah! I understand now.

    So by definition [itex]A \cap B = \left\{x:x \in A \wedge x \in B } [/itex] and [itex]C \subseteq A \leftrightarrow \forall x (x \in C \rightarrow x \in A)[/itex]. Since the intersection of A and B contains elements from A but no elements not in A, [itex](A \cap B) \subseteq A[/itex].

    Is this valid? Does it complete the proof?

    Thanks for your patience, by the way.
     
  9. Jul 15, 2011 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, this is ok :smile:
     
  10. Jul 26, 2011 #9
    Here is the formalization (ignoring tex):
    Key:
    A. for [itex]\forall[/itex]
    -> for [itex]\rightarrow[/itex]
    e. for [itex]\in[/itex]
    i^i for [itex]\cap[/itex]
    C_ for [itex]\subseteq[/itex]

    1 A C_ B <-> A. x ( x e. A -> x e. B )
    2 ( A i^i B ) = A <-> A. x ( ( x e. A /\ x e. B ) <-> x e. A )
    3 ( A C_ B <-> ( A i^i B ) = A ) <-> ( A. x ( x e. A -> x e. B ) <-> A. x ( ( x e. A /\ x e. B ) <-> x e. A ) ) ) (By 1 and 2)
    4 ( ( x e. A /\ x e. B ) -> x e. A ) [case of a and b -> a]
    5 ( x e. A -> x e. B ) -> ( x e. A -> ( x e. A /\ x e. B ) )
    6 ( x e. A -> x e. B ) -> ( ( x e. A /\ x e. B ) <-> x e. A ) (By 4 and 5)
    7 ( ( x e. A /\ x e. B ) <-> x e. A ) -> ( x e. A -> ( x e. A /\ x e. B ) )
    8 ( x e. A -> ( x e. A /\ x e. B ) ) -> ( x e. A -> x e. B )
    9 ( ( x e. A /\ x e. B ) <-> x e. A ) -> ( x e. A -> x e. B ) ( by 7 and 8)
    10 ( x e. A -> x e. B ) <-> ( ( x e. A /\ x e. B ) <-> x e. A ) ( by 6 and 9)
    11 A. x ( x e. A -> x e. B ) <-> A. x ( ( x e. A /\ x e. B ) <-> x e. A ) (by 10)
    12 A C_ B <-> ( A i^i B ) = A (by 11 and 3)

    Too much detail, but it is very spelled out.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Elementary Set Theory Proof
  1. Set theory proof (Replies: 2)

  2. Elementary set theory (Replies: 2)

Loading...