- #1
middleCmusic
- 74
- 0
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 [itex]A[/itex] and every condition [itex]S(x)[/itex], there corresponds a set [itex]B[/itex] whose elements are exactly those elements [itex]x[/itex] of [itex]A[/itex] for which [itex]S(x)[/itex] holds. The set [itex]B[/itex] is denoted by [itex]\{x \in A : S(x)\}[/itex].
Axiom 2.15 (Axiom of pairing)
If [itex]a[/itex] and [itex]b[/itex] are sets, there exists a set [itex]A[/itex] for which [itex]a \in A[/itex] and [itex]b \in A[/itex]. (Edited after error pointed out by HallsofIvy)
Theorem 2.16 (Existence of duple sets).
If [itex]a[/itex] and [itex]b[/itex] are sets, there exists a (unique) set [itex]B[/itex] which has as members only [itex]a[/itex] and [itex]b[/itex].
Proof. By the axiom of pairing (2.15), we know that there exist a set [itex]A[/itex] containing [itex]a[/itex] and [itex]b[/itex]. Then, apply the axiom of specification (2.10) to obtain the set [itex]B = \{x \in A : x=a \text{ or } x=b\}[/itex]. Clearly, this set contains just [itex]a[/itex] and [itex]b[/itex]. We denote this set by [itex]\{a, b\}[/itex]. (The uniqueness of this set is guaranteed by the axiom of extensionality, for if any set contains different members than [itex]\{a, b\}[/itex], it will not satisfy the construction above.) [itex]\square[/itex]
Theorem 2.17 (Existence of singleton sets)
If [itex]a[/itex] is a set, then there exists a set containing only the set [itex]a[/itex], which is denoted by [itex]\{a\}[/itex].
Proof. Since [itex]a[/itex] is a set, there exists a set denoted by [itex]\{a, a\}[/itex] which contains only [itex]a[/itex] (and [itex]a[/itex]) by Theorem 2.16. We choose to denote this set by [itex]\{a\}[/itex]. [itex]\square[/itex]
Axiom 2.19 (Axiom of unions).
For every collection [itex]\mathscr{C}[/itex] of sets, there exists a set [itex]V[/itex] 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 [itex]\mathscr{C}[/itex] 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 [itex]\mathscr{C}[/itex], and we denote the above set by [itex]\bigcup \mathscr{C}[/itex] or [itex]\bigcup \{X : X \in \mathscr{C}\}[/itex] or [itex]\bigcup\limits_{X \in \mathscr{C}}X[/itex].
Proof. Let us be given some collection [itex]\mathscr{C}[/itex] of sets. By applying the axiom of unions (2.19), we have some set [itex]V[/itex] which contains all of the sets in [itex]\mathscr{C}[/itex]. Then, we use the axiom of specification to obtain the set [itex]U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \mathscr{C}\}.[/itex] It is clear that this set contains only all the elements that belong to at least one set of the collection [itex]\mathscr{C}[/itex]. [itex]\square[/itex]
the proof in question:
[strike]Theorem 2.22 (Union of the elements of the set of a set). Let [itex]A[/itex] be a nonempty set. Then [itex]\bigcup\limits_{X \in \{A\}} X = A.[/itex]
Proof. Let [itex]A[/itex] be some nonempty set. Then, by the axiom of unions, there exists a set [itex]V[/itex] which contains all the elements of [itex]\{A\}[/itex]. Further, by Theorem 2.20, there exists a set [itex]U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \{A\}\}.[/itex] But what is [itex]\{A\}[/itex]? By Theorem 2.17, it is the set containing only [itex]A[/itex]. Thus, the only possible [itex]X[/itex] in the definition of [itex]U[/itex] above is [itex]A[/itex] itself. So we have [itex]U = \{x: x \in V \text{ and } x \in A\}[/itex]. But we also find that [itex]x \in V \Rightarrow x = A[/itex]. But since [itex]A \in A[/itex] is a contradiction, as no set can be a member of itself, we have that [itex]U = \varnothing[/itex]. [itex]\square[/itex][/strike]
Theorem 2.22 (Union of the elements of the set of a set). Let [itex]A[/itex] be a nonempty set. Then [itex]\bigcup\limits_{X \in \{A\}} X = A.[/itex]
Proof. Let [itex]A[/itex] be some nonempty set. Then, by the axiom of unions, there exists a set [itex]V[/itex] which contains all the elements of [itex]\{A\}[/itex]. Further, by Theorem 2.20, there exists a set [itex]U = \{x: x \in V \text{ and } x \in X \text{ for some } X \in \{A\}\}.[/itex] But what is [itex]\{A\}[/itex]? By Theorem 2.17, it is the set containing only [itex]A[/itex]. Thus, the only possible [itex]X[/itex] in the definition of [itex]U[/itex] above is [itex]A[/itex] itself. So we have [itex]U = \{x: x \in V \text{ and } x \in A\}[/itex]. But since [itex]A \in \mathscr{C}[/itex] and [itex]V[/itex] contains all elements of sets in [itex]\mathscr{C}[/itex], the condition "[itex]x \in V[/itex]" is implied by the condition "[itex]x \in A[/itex]", so we have [itex]U = \{x: x \in A\}[/itex], and thus
[itex]\bigcup\limits_{X \in \{A\}} X = U = \{x: x \in A\} = \text{ the set containing only the elements of } A = A. \square [/itex]
EDIT: It would perhaps be prudent to write up two little lemmas for use in this proof:
1) If [itex]X = \{x: P(x) \text{ and } R(x)\}[/itex], and [itex]P(x) \Rightarrow R(x)[/itex], then [itex]X = \{x: P(x)\}[/itex], and
2) [itex]\{x: x \in A\} = A[/itex].
Last edited: