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

  • #1
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 [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:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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 [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 B[/itex].

You mean [itex]b \in A[/itex], don't you?

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].
[/QUOTE]
 
  • #3
You mean [itex]b \in A[/itex], don't you?
Good catch! Thanks. I'll fix that.
 

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

  • Last Post
Replies
9
Views
2K
Replies
4
Views
2K
Replies
11
Views
3K
Replies
0
Views
3K
  • Last Post
Replies
16
Views
4K
Replies
1
Views
2K
Replies
41
Views
2K
Replies
0
Views
4K
  • Last Post
Replies
4
Views
1K
Replies
13
Views
2K
Top