Is it necessary to use the axiom of Regularity to prove the successor function being injective?

1.3k Views Asked by At

Basically the problem is that given an inductive set $X$ we can define the successor function on $X$ such that $S:X\longrightarrow X$ and for all $x\in X$, $S(x)=x\cup \{x\}$. So, one of Peano axioms says that such a function is injective on $\omega$. My attempt in trying to prove that $S$ is injective uses the axiom of regularity:

Let's suppose that for some $x$ and $y$ in $X$ we have $S(x)=S(y)$, meaning $x\cup \{x\}=y\cup \{y\}$. As $x\in x\cup \{x\}$ then $x\in y$ or else $x=y$. If $x=y$ then $S$ is injective. If $x\in y$ but $x\neq y$ then since $y\in y\cup \{y\} $ and $y\cup \{y\}=x\cup \{x\}$, so $y\in x$. Then $x\in y$ and $y\in x$, which is a contradiction. Therefore $S$ is injective.

Another attempt that I'm trying is by means of induction since $X$ is inductive but till now the only thing that comes to my mind is using the same argument.

How can I prove it without using the axiom of regularity? Is it possible?

2

There are 2 best solutions below

2
On BEST ANSWER

In the comments Daniela mentions that the goal is to show that indeed the successor function is injective on $\omega$. As Hagen shows, if we take an arbitrary inductive set then the axiom of regularity is needed.

But if we reduce to linearly ordered inductive sets, i.e. $X$ is inductive and for every $x,y\in X$ either $x=y$ or $x\in y$ or $y\in x$, then we can prove that $S$ is injective without an appeal to the axiom of regularity. (Note that we are talking about a sharp linear order, i.e. irreflexive, transitive and total. These properties imply that the order is strongly antisymmetric: $\forall x\forall y(\lnot(x<y\land y<x))$. However the following proof can be easily modified to accommodate the case where we take reflexive, antisymmetric and transitive.)

Suppose that $X$ is linearly ordered and inductive, and $x,y\in X$ such that $x\cup\{x\}=y\cup\{y\}$, if $x=y$ we are done, otherwise $x\in y$ and $y\in x$, however since $(X,\in)$ is [strongly] antisymmetric this cannot happen so it is a contradiction.

0
On

If we abandon regularity, we may indeed face some weird sets $a\ne b$ such that $a=\{b\}$ and $b=\{a\}$. Then if $a,b\in X$ (e.g. $X=\omega\cup\{a,b\}$), injectivity fails indeed. But if you want to work only with the case $X=\omega$ (the smallest infinite ordinal), all is fine: Ordinals are regular automatically.