What's Wrong with This Proof About Unions? (A Statement in Halmos)

[middleCmusic]

Hi everyone,

So I'm finally reading through Naive Set Theory (Halmos) and I'm trying to prove one of the statements that he leaves for the reader. But in my attempt to prove it, I seem to have disproven it. Clearly, I've made a mistake somewhere, but I can't figure out where. I'm betting it's in my understanding of one of his previous statements, so I'm including a little background here. [strike]Can someone help me find the flaw(s)?[/strike]

Problem solved! (I think)

Solution: I was being sloppy with Axiom 2.19: it forms the union of the elements of the sets of the collection, not the union of the sets of the collection. The fixed proof is found below.

some background:


Axiom 2.10 (Axiom of Specification).
To every set A and every condition S(x), there corresponds a set B whose elements are exactly those elements x of A for which S(x) holds. The set B is denoted by \{x \in A : S(x)\}.

Axiom 2.15 (Axiom of pairing)
If a and b are sets, there exists a set A for which a \in A and b \in A. (Edited after error pointed out by HallsofIvy)

Theorem 2.16 (Existence of duple sets).
If a and b are sets, there exists a (unique) set B which has as members only a and b.

Proof. By the axiom of pairing (2.15), we know that there exist a set A containing a and b. Then, apply the axiom of specification (2.10) to obtain the set B = \{x \in A : x=a \text{ or } x=b\}. Clearly, this set contains just a and b. We denote this set by \{a, b\}. (The uniqueness of this set is guaranteed by the axiom of extensionality, for if any set contains different members than \{a, b\}, it will not satisfy the construction above.) \square

Theorem 2.17 (Existence of singleton sets)
If a is a set, then there exists a set containing only the set a, which is denoted by \{a\}.

Proof. Since a is a set, there exists a set denoted by \{a, a\} which contains only a (and a) by Theorem 2.16. We choose to denote this set by \{a\}. \square

Axiom 2.19 (Axiom of unions).
For every collection \mathscr{C} of sets, there exists a set V that contains all the elements that belong to at least one set of the given collection.

Theorem 2.20 (Existence of unions).

For every collection \mathscr{C} of sets, there exists a set that contains only all the elements that belong to at least one set of the given collection. We call this set the union of the sets in \mathscr{C}, and we denote the above set by \bigcup \mathscr{C} or \bigcup \{X : X \in \mathscr{C}\} or \bigcup\limits_{X \in \mathscr{C}}X.

Proof. Let us be given some collection \mathscr{C} of sets. By applying the axiom of unions (2.19), we have some set V which contains all of the sets in \mathscr{C}. Then, we use the axiom of specification to obtain the set U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \mathscr{C}\}. It is clear that this set contains only all the elements that belong to at least one set of the collection \mathscr{C}. \square

the proof in question:


[strike]Theorem 2.22 (Union of the elements of the set of a set). Let A be a nonempty set. Then \bigcup\limits_{X \in \{A\}} X = A.

Proof. Let A be some nonempty set. Then, by the axiom of unions, there exists a set V which contains all the elements of \{A\}. Further, by Theorem 2.20, there exists a set U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \{A\}\}. But what is \{A\}? By Theorem 2.17, it is the set containing only A. Thus, the only possible X in the definition of U above is A itself. So we have U = \{x: x \in V \text{ and } x \in A\}. But we also find that x \in V \Rightarrow x = A. But since A \in A is a contradiction, as no set can be a member of itself, we have that U = \varnothing. \square[/strike]

Theorem 2.22 (Union of the elements of the set of a set). Let A be a nonempty set. Then \bigcup\limits_{X \in \{A\}} X = A.

Proof. Let A be some nonempty set. Then, by the axiom of unions, there exists a set V which contains all the elements of \{A\}. Further, by Theorem 2.20, there exists a set U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \{A\}\}. But what is \{A\}? By Theorem 2.17, it is the set containing only A. Thus, the only possible X in the definition of U above is A itself. So we have U = \{x: x \in V \text{ and } x \in A\}. But since A \in \mathscr{C} and V contains all elements of sets in \mathscr{C}, the condition "x \in V" is implied by the condition "x \in A", so we have U = \{x: x \in A\}, and thus

\bigcup\limits_{X \in \{A\}} X = U = \{x: x \in A\} = \text{ the set containing only the elements of } A = A. \square​

EDIT: It would perhaps be prudent to write up two little lemmas for use in this proof:

1) If X = \{x: P(x) \text{ and } R(x)\}, and P(x) \Rightarrow R(x), then X = \{x: P(x)\}, and

2) \{x: x \in A\} = A.

 

[HallsofIvy]

Hi everyone,

So I'm finally reading through Naive Set Theory (Halmos) and I'm trying to prove one of the statements that he leaves for the reader. But in my attempt to prove it, I seem to have disproven it. Clearly, I've made a mistake somewhere, but I can't figure out where. I'm betting it's in my understanding of one of his previous statements, so I'm including a little background here. [strike]Can someone help me find the flaw(s)?[/strike]

Problem solved! (I think)

Solution: I was being sloppy with Axiom 2.19: it forms the union of the elements of the sets of the collection, not the union of the sets of the collection. The fixed proof is found below.

some background:


Axiom 2.10 (Axiom of Specification).
To every set A and every condition S(x), there corresponds a set B whose elements are exactly those elements x of A for which S(x) holds. The set B is denoted by \{x \in A : S(x)\}.

Axiom 2.15 (Axiom of pairing)
If a and b are sets, there exists a set A for which a \in A and b \in B.

You mean b \in A, don't you?

Theorem 2.16 (Existence of duple sets).
If a and b are sets, there exists a (unique) set B which has as members only a and b.

Proof. By the axiom of pairing (2.15), we know that there exist a set A containing a and b. Then, apply the axiom of specification (2.10) to obtain the set B = \{x \in A : x=a \text{ or } x=b\}. Clearly, this set contains just a and b. We denote this set by \{a, b\}. (The uniqueness of this set is guaranteed by the axiom of extensionality, for if any set contains different members than \{a, b\}, it will not satisfy the construction above.) \square

Theorem 2.17 (Existence of singleton sets)
If a is a set, then there exists a set containing only the set a, which is denoted by \{a\}.

Proof. Since a is a set, there exists a set denoted by \{a, a\} which contains only a (and a) by Theorem 2.16. We choose to denote this set by \{a\}. \square

Axiom 2.19 (Axiom of unions).
For every collection \mathscr{C} of sets, there exists a set V that contains all the elements that belong to at least one set of the given collection.

Theorem 2.20 (Existence of unions).

For every collection \mathscr{C} of sets, there exists a set that contains only all the elements that belong to at least one set of the given collection. We call this set the union of the sets in \mathscr{C}, and we denote the above set by \bigcup \mathscr{C} or \bigcup \{X : X \in \mathscr{C}\} or \bigcup\limits_{X \in \mathscr{C}}X.

Proof. Let us be given some collection \mathscr{C} of sets. By applying the axiom of unions (2.19), we have some set V which contains all of the sets in \mathscr{C}. Then, we use the axiom of specification to obtain the set U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \mathscr{C}\}. It is clear that this set contains only all the elements that belong to at least one set of the collection \mathscr{C}. \square

the proof in question:


[strike]Theorem 2.22 (Union of the elements of the set of a set). Let A be a nonempty set. Then \bigcup\limits_{X \in \{A\}} X = A.

Proof. Let A be some nonempty set. Then, by the axiom of unions, there exists a set V which contains all the elements of \{A\}. Further, by Theorem 2.20, there exists a set U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \{A\}\}. But what is \{A\}? By Theorem 2.17, it is the set containing only A. Thus, the only possible X in the definition of U above is A itself. So we have U = \{x: x \in V \text{ and } x \in A\}. But we also find that x \in V \Rightarrow x = A. But since A \in A is a contradiction, as no set can be a member of itself, we have that U = \varnothing. \square[/strike]

Theorem 2.22 (Union of the elements of the set of a set). Let A be a nonempty set. Then \bigcup\limits_{X \in \{A\}} X = A.

Proof. Let A be some nonempty set. Then, by the axiom of unions, there exists a set V which contains all the elements of \{A\}. Further, by Theorem 2.20, there exists a set U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \{A\}\}. But what is \{A\}? By Theorem 2.17, it is the set containing only A. Thus, the only possible X in the definition of U above is A itself. So we have U = \{x: x \in V \text{ and } x \in A\}. But since A \in \mathscr{C} and V contains all elements of sets in \mathscr{C}, the condition "x \in V" is implied by the condition "x \in A", so we have U = \{x: x \in A\}, and thus

\bigcup\limits_{X \in \{A\}} X = U = \{x: x \in A\} = \text{ the set containing only the elements of } A = A. \square​

EDIT: It would perhaps be prudent to write up two little lemmas for use in this proof:

1) If X = \{x: P(x) \text{ and } R(x)\}, and P(x) \Rightarrow R(x), then X = \{x: P(x)\}, and

2) \{x: x \in A\} = A.[/QUOTE]

 

[middleCmusic]

You mean b \in A, don't you?

Good catch! Thanks. I'll fix that.