The Richness of the Lattice of Natural Number Sets (2021)

Based on the writings of Joel David Hamkins

Let us venture into the expansive and densely packed territory of the power set lattice $\langle P(\mathbb{N}), \subseteq \rangle$, which encompasses every possible collection of natural numbers.

1. Fundamental Lattice Properties

In this mathematical structure, we examine sets $A \subseteq \mathbb{N}$ through the lens of the subset relation. This configuration constitutes a lattice because it possesses a defined least upper bound and greatest lower bound for any two elements:

• Least Upper Bound (LUB): The union $A \cup B$.
• Greatest Lower Bound (GLB): The intersection $A \cap B$.

Because it satisfies the identity $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, it is a distributive lattice. More specifically, as a power set algebra, it functions as a Boolean algebra.

The Hierarchy of the Lattice

The structure can be visualized as a vertical expanse with distinct regions:

Conceptual Note: We often imagine finite sets as clustering near the "Earthly" bottom ($\emptyset$), while cofinite sets soar near the "heavenly" top ($\mathbb{N}$).

---

2. Exploring Suborders

A primary question arises: Which familiar ordering systems can be embedded as suborders within $\langle P(\mathbb{N}), \subseteq \rangle$?

The Natural Number Order $\langle \mathbb{N}, \leq \rangle$

We can construct a "ladder" using initial segments: $\emptyset \subseteq \{0\} \subseteq \{0, 1\} \subseteq \{0, 1, 2\} \subseteq \dots$

This sequence is fascinating because every individual rung is a finite set (clinging to Earth), yet the ladder itself reaches the heavens; there is no upper bound for this chain other than $\mathbb{N}$ itself.

Conversely, we can find a "knotted rope" dangling from the top using complements: $\dots \subseteq \mathbb{N} \setminus \{0, 1, 2\} \subseteq \mathbb{N} \setminus \{0, 1\} \subseteq \mathbb{N} \setminus \{0\} \subseteq \mathbb{N}$ Here, every element is cofinite (near the top), yet the chain descends all the way to the bottom ($\emptyset$).

The Integer Order $\langle \mathbb{Z}, \leq \rangle$

To find a copy of the integers, we can imagine a "sky crane" suspended in the lattice. Starting with the set of all odd numbers:

1. Ascend: Add even numbers one by one.
2. Descend: Remove odd numbers one by one.

This creates a discrete chain isomorphic to $\mathbb{Z}$, unbounded except by the absolute limits of $\emptyset$ and $\mathbb{N}$.

---

3. The Quest for Density and Universality

Can we embed a dense order, such as the rational numbers $\langle \mathbb{Q}, \leq \rangle$?

At first glance, this seems impossible unlikely. One might assume the lattice is fundamentally discrete because the "nearest neighbors" of a set are simply those created by adding or removing a single element.

However, the reality is surprising: Not only can we embed $\mathbb{Q}$, but $P(\mathbb{N})$ is universal for all countable orders. Any order relation on a countable domain is isomorphic to a suborder of $\langle P(\mathbb{N}), \subseteq \rangle$.

The Proof of Universality

To prove that any order $\langle L, \preccurlyeq \rangle$ is isomorphic to a collection of sets under $\subseteq$, we use the concept of down-sets.

The Algorithm:

def embed_order(L):
    # For every element q in the order L
    # Define the down-set q_down as the set of all predecessors
    embedding = {q: {p for p in L if p <= q} for q in L}
    return embedding

The Formal Logic: For each $q \in L$, let $q\downarrow = \{p \in L \mid p \preccurlyeq q\}$. We claim that: $p \preccurlyeq q \iff p\downarrow \subseteq q\downarrow$

• Forward ($\implies$): If $p \preccurlyeq q$, then any element below $p$ is necessarily below $q$. Thus, $p\downarrow \subseteq q\downarrow$.
• Backward ($\impliedby$): If $p\downarrow \subseteq q\downarrow$, then since $p \in p\downarrow$, it must be that $p \in q\downarrow$, meaning $p \preccurlyeq q$.

Since $L$ is countable, the power set $P(L)$ is isomorphic to $P(\mathbb{N})$.

Visualizing the Embedding Logic

---

4. Summary and Gallery

Our exploration reveals that the power set of natural numbers is far from a simple discrete structure; it is a rich environment capable of hosting any countable ordering.

Exploration Checklist:

• Identify Lattice Properties (Distributive/Boolean)
• Map the Hierarchy (Atoms to Coatoms)
• Embed $\mathbb{N}$ (The Ladder)
• Embed $\mathbb{Z}$ (The Sky Crane)
• Prove Universality for all countable orders

Visual Appendix