"Ill-founded Recursion" without Fund

Question

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.

Answer 1

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$.

Answer 2

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$.