I am going through some online lecture notes which prove equivalence between:
- a relation $R$ on a set $X$ is well-founded
By which I mean: every non-empty subset of $X$ has an $R$-least element
- well-founded induction holds in $(X,R)$
By which I mean: $\big[\forall x\in X\,\big(\forall y\in X\,y\,R\,x\implies y\in P\big)\implies x\in P\big]\implies P=X$
What I am puzzled by is that one direction falls naturally: if $R$ is well-founded and $P$ some non-empty subset of $X$ such that for each $x$ and all $y\in P$ with $y\,R\,x$ we have $x\in P$ then $X\setminus P$ cannot have a least element so $X\setminus P=\emptyset$.
But the other direction requires some weak form of choice in every proof I've seen.
- are these two notions no longer equivalent in the absence of choice?
- if so, is there a reason this is often glossed over/not mentioned?
The other direction does not require any choice: you can just prove it by reversing the argument you gave. Suppose well-founded induction holds in $(X,R)$ and let $Q$ be a subset of $X$. If $Q$ has no least element, that means that for each $x\in Q$, there is some $y\in Q$ such that $y \mathbin{R} x$. Letting $P=X\setminus Q$, this means that if $P$ contains all $y$ such that $y \mathbin{R} x$, then $P$ contains $x$. So, by induction, $P=X$, so $Q$ is empty.