Back to home

A Proof in Set Theory

Exercise 9(c) in chapter 3.3 of O'Leary's The Structure of Proof: With Logic and Set Theory asks the reader to prove that $\{0\} \times \mathbb{Z} \ne \mathbb{Z}$ . The set theory in the book is fairly simple and naive; numbers are not sets, and $\mathbb{Z}$ is never properly defined. The answer to the exercise is something like " $(0, 0) \in \set{0} \times \mathbb{Z}$ but $(0, 0) \notin \mathbb{Z}$ ." This exercise made me wonder, though, whether it is possible to define $\mathbb{Z}$ in such a way that $\{0\} \times \mathbb{Z} = \mathbb{Z}$ . My investigations led me to the following theorem and proof, which, though seemingly trivial and probably useless, I find pretty interesting.

Here we use the "short" definition of the ordered pair, that is $\mathbb{Z}$ . An object is anything that can be a member of a set.

THEOREM: If is an object and is a nonempty set, $\{a\} \times A \ne A$ .

PROOF: Suppose, for the sake of contradiction, that $\{a\} \times A = A$ . since is nonempty, let x_1 be an element of . Now, for each natural number $i \ge 2$ , let x_i be the element of such that $x_{i-1} = (a, x_i)$ , i.e. $x_1 = \set{a, \set{a, x_2}}$ , $x_2 = \set{a, \set{a, x_3}}$ , etc. Now define the set as follows: $B = \set{x_i \mid i=1, 2, 3, \cdots} \cap \set{\set{a, x_i} \mid i=1,2,3, \cdots}$ , i.e. $B = \set{x_1, \set{a, x_1}, x_2, \set{a, x_2}, \cdots}$ . For each natural $i \ge 1$ , we have $\set{a, x_{i+1}} \in B \cap x_i$ and $x_i \in B \cap \set{a, x_i}$ . That is, each element of is not disjoint with , contradicting the Axiom of Regularity. By contradiction, $\{a\} \times A = A$ must be false. ☐

This theorem clearly indicates that it is impossible to define $\mathbb{Z}$ such that $\{0\} \times \mathbb{Z} = \mathbb{Z}$ . The proof leans heavily on the use of the "short" definition of the ordered pair. I believe that this proof could be altered to use the more standard Kuratowski definition, or any other "reasonable" definition, but I have not yet tried.