Franklin's Notes


Chajoth's Theorem

Chajoth's Theorem states, informally, that any infinite ordered set can be changed to a different order type by relocating a single element. The following lemma is needed for the proof:

Lemma 1. If $\alpha$ is an arbitrary order type, then there exists a unique decomposition of the form $\alpha=\beta+\gamma$ where $\beta$ is an ordinal and $\gamma$ is an order type with no first element.

Proof. Let $A$ be an ordered set of type $\alpha$. There must exist some ordinal which is not the order type of any initial segment of $A$, so we may consider the smallest such ordinal, which we will denote $\beta'$. Notice that for any set of well-ordered initial segments of an ordering, their union is also a well-ordered initial segment (which follows from the theorems proven here ), meaning that $\beta'$ cannot be a limit ordinal - for if all ordinals less than $\beta'$ were the order type of some initial segment of $A$, then their union would be an initial segment of type $\beta'$, contradicting the definition of $\beta'$ as the first ordinal which is not the order type of some initial segment of $A$.

Since $\beta'$ is not a limit ordinal, it is a successor ordinal, so we may let $\beta$ be its predecessor, so that $\beta'=\beta+1$. Let $B\subset A$ be the initial segment of $A$ of order type $\beta$, and consider $A\backslash B$. If $A\backslash B$ had a least element, then that element could be appended to $B$ to form an initial segment of order type $\beta+1=\beta'$, which is impossible. Thus, we have that $A\backslash B$ has no first element. If we let $\gamma$ be the order type of $A\backslash B$, then $\alpha=\beta+\gamma$ is the desired decomposition.

To see why this decomposition is unique, first notice that the ordinal $\beta$ is uniquely determined by our construction. Then note that no two distinct initial segments of $B$ can both have order type $\beta$, since ordinals cannot be isomorphic to a proper segment of themselves, as follows from Theorem 2 proven here . This means that $A=B+A\backslash B$ is the unique decomposition of $A$ into an ordinal and an ordering with no first element, and $\alpha=\beta+\gamma$ is the unique decomposition of $\alpha$ of the specified type. $\blacksquare$

Now we are ready to prove the desired theorem:

Chajoth's Theorem. In any infinite ordered set, it is possible to change the place of one element in such a way that changes the order type of the set.

Proof. If $A$ is an infinite ordered set, let $A=B+A\backslash B$ be the unique decomposition of $A$ into a well-ordered initial segment and an ordered set with no least element, as provided for by the previous lemma. If $B$ has the order type of a finite ordinal $\beta$, then we may move any element of $A\backslash B$ to the beginning of $A$, so that the resulting ordered set $A'$ has an initial segment with order type $\beta+1$, making it distinct from $A$ by the uniqueness of decomposition described by the previous lemma. If $B$ has the order type of an infinite ordinal $\beta$, then we may remove the first element of $B$ (which does not change its order type, since $\omega=1+\omega$) and append it to the end of $B$, so that $A$ has an initial segment of order type $\beta+1$, making it distinct from $A$ by the uniqueness of the decomposition. In either case, we have relocated one element of $A$ and thereby produced a distinct order type. $\blacksquare$

set-theory

order-theory

ordinals

back to home page