Naive Set Theory: The Natural Numbers

Transitive Sets


A set $A$ is transitive if every element of every element of $A$ is itself an element of a $A$. Formally, a transitive set is a set $S$ such that $x \in y \in A \implies x \in A$. Transitive sets are said to have the property of transitivity.

For example, consider the set $S=\{0, 1, 2\}$. The element $1$ is an element of $2$, and $1$ is also an element of $S$. Ditto for the element $0$, which is also an element of $1$. $S$ is therefore a transitive set. Conversely, consider the set $T=\{0, 2\}$. We see that $1 \in 2$, but $1 \notin T$, so $T$ is not a transitive set.

Transitivity is not typically a concept we think of when we think of the natural numbers. We're more apt to think about things like arithmetic. However, transitivity is a very useful "in between" property, as it is crucial for proving those more familiar properties of arithmetic (and more!).

Upon further reflection, transitivity also turns out to be philosophically pleasing. Consider what it "means" for each natural number to be a member of all of the ones that come after it. When counting elements, the concept of the "third" element belongs to all sets that have $3$ or more elements. For example, if you count to $4$, you must always count to $3$ along the way, and likewise for any time you count to $5$, $12$, $100$, or beyond. Likewise, the fact that smaller numbers are also subsets of bigger numbers makes sense, as having $3$ things is certainly part, but not all, of having $4$ things.


Problems

  1. Show that $\bigcup S \subseteq S$ is an equivalent definition of transitivity. 

    Assume $\bigcup S \subseteq S$. Then

    $\bigcup S \subseteq S \\ \{ x : x \in y \text{ and } y \in S \} \subseteq \{ x : x \in S \} \\ $

    Thus $x \in y \text{ and } y \in S$ implies $x \in S$.

    Conversely, assume $x \in y \text{ and } y \in S$ implies $x \in S$. Then

    $ \{ x : x \in y \text{ and } y \in S \} \subseteq \{ x : x \in S \} \\ \bigcup S \subseteq S \\ $

    Show Answer
  2. Show that $x \in S \implies x \subseteq S$ is an equivalent definition of transitivity.

    Assume $x \in S$ implies $x \subseteq S$. Let $y \in x$. Then by definition of subset, $y \in S$. Thus $y \in x \in S \implies y \in S$.

    Conversely, assume $y \in x \in S$ implies $y \in S$. Let $a \in S$. Then for all $b \in a$, $b \in S$. Therefore $a \subseteq S$. Thus $a \in S \implies a \subseteq S$.

    Show Answer
  3. Prove that if $S$ is a transitive set, then $\bigcup (S^+) = S$.

    $ \bigcup (S^+) = \bigcup \{ S, \{S\} \} \\ \bigcup (S^+) = \bigcup S \cup \bigcup \{S\} \\ \bigcup (S^+) = \bigcup S \cup S \\ \bigcup (S^+) = S \cup S \\ \bigcup (S^+) = S \\ $

    Show Answer
  4. Prove that if $a^+ = b^+$, then $a=b$.

    Given $a^+ = b^+$, we can take the union of both sides to get $\bigcup a^+ = \bigcup b^+$. Because $a$ and $b$ are transitive, $\bigcup a^+ = a$ and $\bigcup b^+ = b$, therefore $a = b$.

    Show Answer
  5. Prove that every natural number is a transitive set.

    Hint: Use induction.

    We'll walk through this first proof by induction with extra caution. Subsequent proofs of induction can then be afforded less exposition.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : n \text{ is transitive} \}$. If we can show that $S = \mathbb{N}$, we will prove that every $n \in \mathbb{N}$ is transitive. In order to demonstrate this fact, we must prove the base case, where we show that $0 \in S$, and the inductive step, where we show that $n \in S$ implies $n^+ \in S$.

    Base case: $0 = \varnothing$ is vacuously transitive. It is true that $\varnothing$ is transitive because all of the elements of its elements are themselves elements of $\varnothing$. Stated differently, there are no elements in $\varnothing$ to violate the condition of transitivity. Therefore $0$ is transitive, so $0 \in S$.

    Inductive step: Assume $k \in S$. By construction, $k^+ = k \cup \{k\}$, so $k \subseteq k^+$. Because $k$ is transitive, then by the above theorem $\bigcup (k^+) = k$. Therefore $\bigcup (k^+) \subseteq k^+$, which by the equivalent definition of transitivity above shows that $k^+$ is transitive. Therefore $k^+ \in S$.

    Since $0 \in S$ and $k \in S$ implies $k^+ \in S$, and $S$ is a subset of $\mathbb{N}$, we conclude by the Principle of Mathematical Induction that $S = \mathbb{N}$, and therefore that every $n \in \mathbb{N}$ is transitive.

    Show Answer
  6. Prove that $\mathbb{N}$ is a transitive set.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : n \subseteq \mathbb{N} \}$.

    Base case: $0 = \varnothing$, and the empty set is a subset of every set, so $0 \subseteq \mathbb{N}$. Because $0 \in \mathbb{N}$ by definition of $\mathbb{N}$, we see that $0 \in S$.

    Inductive step: Assume $k \in S$. Then by definition $k \in \mathbb{N}$, so by definition of a subset, $\{k\} \subseteq \mathbb{N}$. Likewise, by the inductive hypothesis, $k \subseteq \mathbb{N}$. Because the union of two subsets is itself a subset, we have $k \cup \{k\} \subseteq \mathbb{N}$. By definition, $k^+ = k \cup \{k\}$, so $k^+ \in S$. Thus $S = \mathbb{N}$, and the result follows by induction.

    Show Answer