2
$\begingroup$

Assume the axioms of Extensionality, Empty Set, and Adjunction (meaning that $S\cup\{x\}$ forms a set for any $S,x$). Notice that we do not have Specification as an axiom, which makes this theory very sparse and hard to work with. My question is simple: can we define an infinite collection which is wellordered by the $\in$ relation? By infinite, I mean that the collection is nonempty and admits no maximum element.

I already know that this theory cannot define an infinite wellorder with the full wellfoundedness schema, since otherwise it would be able to interpret Peano Arithmetic. Instead, I'm interested in whether we can get the first-order wellfoundedness schema which quantifies over sets. Namely, can we prove $\forall S, (\exists x, x\in S)\implies \exists x, (x\in S \land \forall(y\in S), x\leq y)$? Since this is a single first-order statement, it's much more reasonable that we might interpret it.

$\endgroup$

1 Answer 1

5
$\begingroup$

Yes, and in fact a very minor modification to the definition of ordinals will still allow us to prove that the ordinals are wellordered. Without Specification to form subsets, the wellfoundedness condition is substantially weaker, but we can still do a lot without Specification. Define the function $x^+ = x\cup\{x\}$, and define the class $\mathbf{Ord}$ so that $\alpha\in\mathbf{Ord}$ precisely when: $\alpha$ is a transitive set, and $\alpha$ is wellordered by the $\in$ relation, and moreover the following condition holds. $$\forall(S\subseteq \alpha), \forall C, \exists Z, \forall x, x\in Z \iff (x\in S \land x\notin C)$$

The above condition simply asserts that, given any subset $S\subseteq \alpha$ and any set $C$, the subtraction $S\setminus C$ is well defined. Since $\alpha\subseteq \alpha$, we also find $S\setminus(\alpha\setminus C) = S\cap C$ existing as a set. Now, our intent is to show that $\mathbf{Ord}$ is wellordered by membership, that $\emptyset\in\mathbf{Ord}$, and moreover that all $\alpha\in\mathbf{Ord}$ have $\alpha^+\in\mathbf{Ord}$. That will prove $\mathbf{Ord}$ is nonempty and unbounded, as required. For convenience, we write $x<y$ to mean that there exists $\alpha\in\mathbf{Ord}$ with $x\in y\in \alpha$.


Lemma: $\forall(\alpha,\beta,\gamma\in\mathbf{Ord}), \alpha\in\beta\in\gamma \implies \alpha\in\gamma$

Lemma: $\forall(\alpha\in\mathbf{Ord}), \alpha\notin \alpha$

proof: Having $\alpha\in\alpha$ would imply $\alpha<\alpha$, which contradicts the ordering of $\alpha$. $\square$

Lemma: $\forall(\alpha\in\mathbf{Ord}), \forall(\beta\in \alpha), \beta\in\mathbf{Ord}$

proof: Immediately $\beta$ is transitive, and since $\beta\subseteq \alpha$ then $\beta$ is wellordered by membership. Finally, every $S\subseteq \beta$ has $S\subseteq \alpha$ and thus $S\setminus C$ exists for any $C$. $\square$

Theorem: $\emptyset\in\mathbf{Ord}$

proof: It's vacuously true that $\emptyset$ is transitive and wellordered by membership, and all $S\subseteq \emptyset$ obey $S=\emptyset$ and thus $S\setminus C=\emptyset$. $\square$

Theorem: $\forall(\alpha\in\mathbf{Ord}), \alpha^+\in\mathbf{Ord}$

proof: All $\beta\in \alpha^+$ either have $\beta=\alpha$ or $\beta\in\alpha$, and either way $\beta\in\mathbf{Ord}$ so that $\beta\notin \beta$. It similarly follows that $\beta$ is a transitive set, hence $\delta\in\gamma\in\beta \implies \delta\in \beta$. Moreover, all $\beta,\gamma\in\alpha^+$ must have one of $\beta\in\gamma$ or $\gamma\in \beta$ or $\gamma=\beta$, which follows by some simple case analysis, hence $\alpha^+$ is totally ordered. Moreover, any nonempty $S\subseteq \alpha^+$ either has $S=\{\alpha\}$ so that $\alpha$ is minimal in $S$, or else we find minimal $x\in(S\cap \alpha)$ so that $x\in S$ is also minimal in $\alpha^+$, hence $\alpha^+$ is wellordered. Finally, every $S\subseteq \alpha^+$ obeys $S\setminus C = ((\alpha\cap S)\setminus C)\cup(S\cap\{\alpha\}\setminus C)$, which exists in any case. $\square$

Theorem: $\forall(\alpha,\beta\in\mathbf{Ord}), \alpha\in \beta \lor \alpha=\beta \lor \beta\in \alpha$

proof: In pursuit of contradiction, suppose not. We cannot simultaneously have $(\alpha\setminus \beta)=\emptyset$ and $(\beta\setminus \alpha)=\emptyset$, since otherwise that would imply $\alpha=\beta$ via Extensionality, so without loss of generality let's assume $(\alpha\setminus \beta)\neq \emptyset$. Because of this, we find $x=\min(\alpha\setminus\beta)$, and since all $t\in x$ have $t\in \beta$ due to minimality of $x$, necessarily $x\subseteq \beta$. Since $x\in \alpha$ then $x\neq \beta$, so it follows that $(\beta\setminus x)\neq \emptyset$, so we can find $y=\min(\beta\setminus x)$ so that $y\subseteq x$ for the same reason as why $x\subseteq \beta$. Finally, all $t\in x$ have $t\neq y$ since $y\notin x$, and also $y\notin t$ for the same reason, but since both $t,y\in \beta$ then necessarily $t\in y$ due to the ordering of $\beta$. Therefore $x\subseteq y$ so that $x=y$, but this is impossible since $y\in \beta$ and $x\notin \beta$, a contradiction as expected. $\square$

This shows that $\mathbf{Ord}$ is totally ordered under membership. To show that it's wellordered (in the sense that every nonempty set contains a minimum), we just consider the intersection of a set with some ordinal.

Theorem: $\forall S, (\exists(\alpha\in \mathbf{Ord}), \alpha\in S) \implies (\exists(\alpha\in S), \alpha\cap S = \emptyset)$

proof: Fix some $\alpha_0\in \mathbf{Ord}$ having $\alpha_0\in S$. Since $\alpha_0$ is an ordinal, we can construct $S_0=\alpha\cap S$. In case $S_0=\emptyset$, then simply let $\alpha=\alpha_0$ and we are done. Otherwise if $S_0\neq\emptyset$, we instead let $\alpha=\min(S_0)$ which obeys $\alpha\cap S = \emptyset$. This works because $\alpha\cap S = (\alpha\cap\alpha_0)\cap S = \alpha\cap (\alpha_0\cap S) = \alpha\cap S_0 = \emptyset$, hence $\alpha=\min(S)$. $\square$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .