Set theory problems from Hrbacek, Jech

[Syrus]

Homework Statement

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.

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).

 

[micromass]

Homework Statement

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.

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.

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]

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.

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

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}.

That is ok.

 

[micromass]

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.

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]

 

[Syrus]

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.

 

[micromass]

That looks ok.

 

[Syrus]

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?

 

[micromass]

Yes, that is indeed the idea. If x is in your set B, then x≠x. This is impossible, thus B is empty.

 

[Syrus]

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?

 

[micromass]

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.

This is correct.

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?

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.