$6.1$ LEMMA. If $\langle A,R \rangle $ is a well-ordering, then for all $x\in A, \langle A,R\rangle \ncong \langle \text{pred}(A,x,R),R\rangle .$

order-theorywell-orders

The following is from Kenneth Kunen's book Set Theory : An Introduction to Independent Proofs

Whenever $R$ and $S$ are relations, and $A,B$ are sets, we say $\langle A,R\rangle \cong \langle B,S\rangle$ iff there is a bijection $f: A\rightarrow B$ such that $\forall x, y\in A \left(x Ry \iff f(x)Sf(y)\right).$ $f$ is called an isomorphism from $\langle A, R\rangle$ to $\langle B, S\rangle.$

We say $R$ well-orders $A,$ or $\langle A,R\rangle$ is a well-ordering iff $\langle A,R\rangle$ is a total ordering and every non-empty subset of $A$ has an $R$– least element.

if $x\in A,$ let $\text{pred}(A,x,R) = \{y\in A:yRx\}$

$6.1$ LEMMA. If $\langle A,R \rangle $ is a well-ordering, then for all $x\in A, \langle A,R\rangle \ncong \langle \text{pred}(A,x,R),R\rangle .$

PROOF. If $f : A \rightarrow \text{pred}(A,x,R)$ were an isomorphism, derive a contradiction by considering the $R$-least element of $\{y\in A :f(y)\ne y\}.$

So if $C =\{y\in A :f(y)\ne y\}$ has $x_0$ as it's $R$-least element then $f(C)$ has $f(x_0)$ as it's $R$-least element. We also observe that if $x\notin C$ then $f(x) = x$ which in turn implies that $f(x)\notin \text{pred}(A,x,R).$ Thus $A = C.$ Thus $x_0$ is the least element of $A$ and $f(x_0)$ is the least element of $\text{pred}(A,x,R).$ But both $A$ and $\text{pred}(A,x,R)$ should have the same least element. Hence $f(x_0)\neq x_0$ is the contradiction here.

Is this the contradiction the author speaks about?

Best Answer

I also don't understand from where you derive the "Thus $A=C$" in your question.

I would proceed as follows using the $C$ you defined.

$C$ is not empty as by hypothesis on $f$, $f(x) R x$ and therefore $x \in C$ as $R$ is irreflexive. As $R$ well-orders $A$, $C$ has a $R$-least element that we denote by $x_0$. We have $f(x_0) \neq x_0$ and $\langle A, R \rangle$ being a total ordering, either $f(x_0) R x_0$ or $x_0 R f(x_0)$. $f(x_0) R x_0$ would be in contradiction with the definition of $x_0$.

Now if $x_0 R f(x_0)$, $\text{pred}(A,x_0,R) \subseteq \text{pred}(A,f(x_0),R)$. Let's have a look at the restriction of $f^{-1}$ to $\text{pred}(A,f(x_0),R)$:

  1. $f^{-1}$ is $R$-increasing, i.e. $x R y \iff f^{-1}(x) R f^{-1}(y)$ and one-to-one.
  2. The image of $\text{pred}(A,f(x_0),R)$ under $f^{-1}$ is included in $\text{pred}(A,x_0,R)$.
  3. The restriction of $f^{-1}$ to $\text{pred}(A,x_0,R)$ is the identity map. Indeed, by definition of $x_0$ for $y \in \text{pred}(A,x_0,R)$ we have $yRx_0$ and therefore $f(y) = y \iff y = f^{-1}(y)$.

Let's consider $z=f^{-1}(x_0)$. According to point 2. above $z R x_0$ and $z=f^{-1}(z)$ according to point 3. in contradiction with $f^{-1}$ injective.

Related Question