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

1. May 22, 2013

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

Last edited: May 22, 2013
2. May 22, 2013

HallsofIvy

Staff Emeritus

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]

3. May 22, 2013

middleCmusic

Good catch! Thanks. I'll fix that.