# Proof of “well-founded iff there is no sequence $x_n$ s.t. $(x_{n+1}, x_n) \in R$”

I tried to do the following exercise from a book I'm reading, can you tell me if my solution is correct? Thanks!

Theorem 2: Let $R$ be a binary relation on a set $X$. Then $R$ is strictly well-founded iff there is no sequence $(x_n)_{n \in \mathbb N}$ of elements of $X$ such that $(x_{n+1}, x_n) \in R$ for all $n \in \mathbb N$.

Exercise:

(i) Formulate an analogue of Theorem 2 for well-founded relations.

(ii) Prove Theorem 2.

(i) Theorem 2': Let $R$ be a binary relation on a set $X$. Then $R$ is well-founded iff there is no sequence $(x_n)_{n \in \mathbb N}$ of elements of $X$ such that $(x_{n+1}, x_n) \in R$ and $x_n \neq x_{n+1}$ for all $n \in \mathbb N$.

(ii)

$\implies$: Assume there is a sequence $x_n$ with $(x_{n+1},x_n) \in R$ for all $n \in \mathbb N$. Then the set $Y = \{x_n \mid n \in \mathbb N\}$ and hence $R$ is not well-founded since for every element $x_n$ there is $x_{n+1} \in Y$ with $(x_{n+1},x_n) \in R$.

$\Longleftarrow$: Let $R$ be strictly well-founded. Assume we have a sequence $x_n$ with $(x_{n+1},x_n) \in R$ for all $n \in \mathbb N$. Then by the same argument as above $R$ is not well-founded, hence there cannot be such a sequence.

I must be missing something but I can't seem to figure out what.

-

In (ii) $\Rightarrow$ I think that you meant to say something like this:

Then let $Y=\{x_n:n\in\Bbb N\}$ and observe that $Y$ has no $R$-minimal element, so that $R$ is not strictly well-founded.

You’re actually proving the contrapositive of $\Rightarrow$ here, which is fine, but then in what you’ve labelled $\Leftarrow$ you set out to prove the same thing, this time directly. Thus, you’re still in want of a proof of $\Leftarrow$. I suggest trying to prove the contrapositive: assume that $R$ is not strictly well-founded, and construct an infinite strictly $R$-decreasing sequence. (You’ll need the axiom of dependent choice.)

Added: Suppose that $R$ is not strictly well-founded, and let $Y$ be a non-empty subset of $X$ such that for each $y\in Y$ there is a $z\in Y$ such that $\langle z,y\rangle\in R$. Then $R_Y=R\cap(Y\times Y)$ is an entire relation on $Y$, so the axiom of dependent choice guarantees that there is a sequence $\langle y_n:n\in\omega\rangle$ in $Y$ such that $\langle y_{n+1},y_n\rangle\in R$ for all $n\in\omega$.

Added2: If you want to use AC directly, let $\mathscr{A}=\big\{\langle A,y\rangle\in\wp(Y)\times Y:y\in A\text{ and }|Y\setminus A|<\omega\big\}$. By hypothesis for each $\langle A,y\rangle\in\mathscr{A}$ there is a $z\in A$ such that $\langle z,y\rangle\in R$. Let $$P=\prod_{\langle A,y\rangle\in\mathscr{A}}A\;;$$ this is a product of non-empty sets, so by AC it’s non-empty. Let $\varphi\in P$, and choose $y_0\in Y$ arbitrarily. Given $\{y_k:k\le n\}$, let $A_n=Y\setminus\{y_k:k\le n\}$, and let $y_{n+1}=\varphi(\langle A_n,y_n\rangle)$.

-
@MattN.: Yes, if my guess at their distinction between well-founded relation and strictly well-founded relation is correct. –  Brian M. Scott Oct 23 '12 at 15:01
@MattN.: Then yes, it looks fine to me. The proof for the other direction is okay, though it could be written a bit better. –  Brian M. Scott Oct 23 '12 at 15:04
@MattN.: Not a problem; give me a few minutes, and I’ll add to my answer. –  Brian M. Scott Oct 23 '12 at 15:07
@MattN.: Yes, you could use AC, but it’s a bigger hammer than you need. –  Brian M. Scott Oct 23 '12 at 15:19
@MattN.: Exactly. –  Brian M. Scott Oct 23 '12 at 15:29

You have proven the same implication twice. To show "$\Longleftarrow$", take an arbitrary non-empty set without minimal element and consecutively pick smaller and smaller elements. If this process terminates, you have a minimal element which cannot be. If it doesn't terminate, you get your sequence (to make this precise, you have to use the axiom of choice).

-