Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is a basic fact of set theory that the following holds:

Let $(X,\leq)$ be a linear ordered set. Then it holds that, for each finite sequence $y_{1}$,...,$y_{n}$ of sets and each formula $\phi(x,y_{1},...,y_{n})$ of set theory, we have

$$\forall{y_{1},...,y_{n}}(\forall{x\in X}(\forall{z}\lt x\phi(z,y_{1},...,y_{n})\rightarrow\phi(x,y_{1},...,y_{n}))\rightarrow\forall{x\in X}\phi(x,y_{1},...,y_{n}))$$

iff $(X,\leq)$ is a well-ordering. Hence induction works on $(X,\leq)$ iff $(X,\leq)$ is a well-ordering.

We can ask the same question for the recursion principle:

Let $(X,\leq)$ be a linear ordering such that, for each function $F:V\times V\times V\rightarrow V$, and each parameter $p$, there is a unique function $f:X\rightarrow V$ such that $f(x)=F(x,f|X_{x},p)$ for all $x\in X$, where $X_{x}$ is the subset of $X$ consisting of all elements strictly smaller than $x$ and $f|A$ is the restriction of $f$ to $A$.

Does it then follow that $(X,\leq)$ is a well-ordering?

This is obviously true if we assume the axiom of foundation. E.g. we could otherwise use $F(x,y)=y$ to construct an ill-founded set.

However, the first fact about induction seems to be more 'logical' in nature and does not depend on the axiom of foundation. I would therefore be interested in knowing whether the second fact can also be deduced without assuming foundation.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

Define $F(x,f,p)$ to be the smallest ordinal not in the range of $f$ (so the variables $x$ and $p$ are just dummy variables, to match the notation in the question). Suppose there exists a solution $f$ of the recursion $f(x)=F(x,f|X_x,p)$. Then $f$ embeds $X$ (with its given ordering) strictly monotonically into the ordinals (with their standard well-ordering). It follows that the given ordering of $X$ is a well-ordering.

Addendum (the next day, without jet lag, I hope): The choiceless version of the proof from uniqueness isn't actually hard; it's very close to what Peter Komjáth wrote, but, for the record, here it is. Suppose $A$ is a nonempty subset of $X$; I must show that it has a smallest element. Define $F(x,f,p)$ to be 1 if $x\in A$ and some $y<x$ has $f(y)=1$, and to be 0 otherwise. Then the identically 0 function satisfies the recursion $f(x)=F(x,f|X_x,p)$. The function $g$ that is identically 1 on $A$ and 0 on $X-A$ is different from $f$ (as $A\neq\emptyset$) and therefore must not satisfy the recursion. If $x$ is a point where the recursion equation $g(x)=F(x,g|X_x,p)$ is violated, then $x\in A$ (otherwise the value $g(x)=0$ satisfies the recursion) and no element of $A$ is $<x$ (otherwise the value $g(x)=1$ satisfies the recursion). So $x$ is the smallest element of $A$.

Let me also mention another proof from existence, a proof that doesn't need ordinals and in fact uses only (recursive definitions of) functions with values in $\{0,1\}$. For nonempty $A\subseteq X$, define $F(x,f,p)$ to be 1 if $x\in A$ and no $y<x$ has $f(y)=1$, and to be 0 otherwise. Suppose $f$ satisfies this recursion. If it were identically zero, then the recursion equation would say that it should be 1 at points in $A$; since $A\neq\emptyset$, this is a contradiction. So $f(x)=1$ for some $x$. The recursion equation then requires that $x\in A$. Suppose, toward a contradiction, that $A$ had an element $x'<x$. By the recursion equation and the fact that $f(x)=1$, we know that $f(y)=0$ for all $y<x$, hence in particular for all $y<x'$. But then the recursion equation makes $f(x')=1$, which is absurd as $x'$ is one of the $y$'s that are $<x$ and are therefore mapped to 0 by $f$. This contradiction completes the proof that $x$ is the smallest element in $A$.

share|improve this answer
1  
Note that this argument uses only the existence, not the uniqueness, of $f$. Peter Komjáth's answer used only the uniqueness, not the existence. Note also that my answer avoids the axiom of choice as well as foundation. I believe there is also a choiceless version of the argument from uniqueness, but I'll need to think about it (and I'm jet-lagged at the moment). –  Andreas Blass May 14 '12 at 20:31
    
Great, thanks to both of you. I had only thought about existence, it is nice to see that both existence and uniqueness are sufficient –  M Carl May 15 '12 at 8:24
add comment

Let $x_0>x_1>\cdots$ be a strictly decreasing sequence in $(X,<)$. We can define an $F$ which gives two solutions: $f_0$ which is 0 everywhere, and $f_1$, which has $f_1(y)=0$ if $y\le x_n$ for every $n$ and $f_1(y)=1$ if $y\ge x_n$ for some $n$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.