1. Limited time only! Sign up for a free 30min personal 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 problems from Hrbacek, Jech

  1. May 15, 2012 #1
    1. The problem statement, all variables and given/known data

    I'm attempting some self-study in set theory using the text mentioned above. The exercises here are quite different from those in previous texts which I've used, so I was hoping I could present some of my attempts (so far, only from the first problem set) and receive some feedback as to whether it seems I am performing them correctly.

    2. Relevant axioms

    Axiom of existence:
    There exists a set which has no elements.

    Axiom of extensionality:
    If every element of X is an element of Y and every element of Y is an element of X, then X = Y.

    Axiom Schema of Comprehension:
    Let P(x) be a property of x. For any set A, there is a set B such that x ∈ B iff x ∈ A and P(x).

    Axiom of pair:
    For any A and B, there is a set C such that x is an element of C iff x = A or x = B.

    Axiom of union:
    For any set S, there exists a set U such that x ∈ U iff x ∈ A for some A ∈ S.

    Axiom of Power set:
    For any set S, there exists a set P such that X ∈ P iff X ⊆ S.



    3. The attempt at a solution


    3.1: Show that the set of all x such that x ∈ A and x ∉ B exists.
    3.1 solution: Let P(x, A, B) be the property x ∈ A and x ∉ B. Then W = {x ∈ A | P(x, A, B)} exists by the axiom schema of comprehension.


    3.4 Let A and B be sets. Show there exists a unique set C such that x ∈ C iff either (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A).
    3.4 solution: By the axiom of pair, there is some set D such that x ∈ D iff x = A or x = B. Let P(x, A, B) be the property (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A). Then W = {x
    ∈ D | P(x, A, B)} exists by the axiom schema of comprehension. If K is another set which satisfies x ∈ K iff either (x ∈ A and x B) or (x ∈ B and x A)
    , then x ∈ K iff x ∈ C, and so by extensionality K = C.

    3.5 a)Given A, B, and C, there is a set P such that x ∈ P iff x = A or x = B or x = C.
    b) generalize to four elements
    3.5 a) solution: Using A and B along with the axiom of pair provides us with a new set D such that x ∈ D iff x = A or x = B. Now use the axiom of pair again, this time with C alone to obtain the set E such that x ∈ E iff x = C. Now use the axiom of pair one last time, with D and E, to create the set F such that x ∈ F iff x = D or x = E. Finally, apply the axiom of union to F, which yields the set P, where x ∈ P iff x ∈ H for some H ∈ F. Thus, P = {x | x ∈ D or x ∈ E} = {x | x = A or x = B or x = C}.
    3.5 b) I'll wait to do this one until someone can verify part a).
     
  2. jcsd
  3. May 15, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Note that A and B are fixed, so it should actually be "Let P(x) be the property [itex]x\in A~\text{and}~x\in B[/itex]. What you wrote isn't wrong, but there is no reason to let A and B be parameters.
    Also note that if you let P(x) be [itex]x\in B[/itex], then you would also get the right answer!!
    Indeed:

    [tex]A\cap B=\{x\in A~\vert~x\in B\}[/tex]


    I'm not sure what you mean with "x B" and "x A".

    That is ok.
     
  4. May 15, 2012 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Ok, I see you corrected it. But right now you have formed the set

    [tex]\{x\in \{A,B\}~\vert~(x\in A~\text{and}~x\notin B)~\text{or}~ (x\in B~\text{and}~x\notin A)\}[/tex]

    Thus x can only be A and B right now. So your set C can only contain A and B. This is not what you want.

    Hint, you want to form the set

    [tex]\{x\in A~\vert~x\notin B\}\cup \{x\in B~\vert ~x\notin A\}[/tex]
     
  5. May 15, 2012 #4
    Thank you for your quick response micromass! Does this proof look a little better?

    3.4 Let A and B be sets. Show there exists a unique set C such that x ∈ C iff either (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A).
    3.4 solution: By the axiom of pair, there is some set D such that x ∈ D iff x = A or x = B. Next apply the axiom of union to D to obtain the set S, where x ∈ S iff x ∈ K for some K ∈ D. Let P(x, A, B) be the property (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A). Then W = {x ∈ S | P(x, A, B)} exists by the axiom schema of comprehension. If K is another set which satisfies x ∈ K iff either (x ∈ A and x B) or (x ∈ B and x A), then x ∈ K iff x ∈ C, and so by extensionality K = C.
     
  6. May 15, 2012 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That looks ok.
     
  7. May 15, 2012 #6
    I am having some trouble with this one:

    3.2: Replace the axiom of existence by the following weaker postulate: Weak axiom of existence- some set exists. Prove the axiom of existence using the weak axiom of existence and the comprehension schema [hint: Let A be a set known to exist; consider {x ∈ A | x ≠ x}].



    We want to prove that the empty set exists. The weak axiom of existence guarantees some set (here, A) exists. Let P(x) be the property x ≠ x. Then by the comprehension schema there exists a set B such that x ∈ B iff x ∈ A and P(x).

    My question is, is the proof finished by simple noting that nothing exists which is not equal/identical to itself, thus making B empty?
     
    Last edited: May 15, 2012
  8. May 16, 2012 #7

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, that is indeed the idea. If x is in your set B, then x≠x. This is impossible, thus B is empty.
     
  9. May 16, 2012 #8
    Here's another one:

    3.3a) Prove that a set of all sets does not exist [hint: if V is a set of all sets, consider { x ∈ V | x ∉ x}].
    b) Prove that for any set A, there is some x ∉ A.


    a) This one seems pretty simple. If a set of all sets, V, exists, then let P(x) be the property x ∉ x. By the comprehension schema then, we can form the set B = {x ∈ V | x ∉ x}. But this set is impossible to form by Russel's paradox. Thus, V fails to exist.

    b) At first I proposed this: Let A be an arbitrary set. Then we can apply the axiom of pair to A to obtain {A}, where {A} ∉ A. [while I was at first convinced of this, I later wondered if there was a more rigorous way of showing that {A} ∉ A? In addition, is there a way to prove that any subset of A is not a memeber of A?
     
  10. May 16, 2012 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    This is correct.

    Aah, now we come to an interesting point. From the 6 properties you listed, we can not prove that {A} ∉ A. That is, if we only accept those 6 properties, then it might be that there exists a set A such that {A} ∈ A.
    You can not just say that {A} ∉ A because it violates your intuition. Because, in fact, it might not even be true.

    Of course, we want that for each set {A} ∉ A holds. But in order to achieve this, we need a further axiom that specifically prohibits this and other such constructions. The impossibility of {A} ∈ A does not follow from the 6 axioms.

    OK, so how do we prove (b) then?? Well, you'll have to apply (a). Assume that (b) is not true, that is: for all sets x we have that x ∈ A. Then A is the set of all sets.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Set theory problems from Hrbacek, Jech
  1. Set Theory Problem (Replies: 11)

  2. 2 set theory problems (Replies: 3)

Loading...