# Proof of every binary relation with a rank function is well-founded

I proved the following claim (source image), can you tell me if my proof is correct? Thanks:

Claim 4: Let $R$ be a binary relation on a set $X$, and suppose $\langle Y, \prec \rangle$ is a strict w.o. If there exists a function $rk : X \to Y$ such that $$\forall x, y \in X (x \neq y \land \langle x, y \rangle \in R \to rk(x) \prec rk(y)), \tag{*}$$ then the relation $R$ is wellfounded.

where we use the following definition of wellfounded:

$\newcommand{\pair}[2]{\langle#1,#2\rangle}$

Definition 3: Let $R$ be a binary relation on a set $X$. We say that $R$ is wellfounded, if for every nonempty subset $Y \subseteq X$ there exists a $z \in Y$ such that $\pair yz \notin R$ for all $y \in Y\setminus \{z\}$. A relation $R$ is strictly wellfounded if it is wellfounded and irreflexive.

Proof:

Assume $R$ is not well-founded. Then there exists an infinite $R$-descending sequence $(x_n)$ such that $(x_{n+1}, x_n) \in R$, $n \in \mathbb N$, so that $S = \{x_n \mid n \in \mathbb N\}$ does not have an $R$-minimal element. Then $f(S)$ is a subset of $Y$ containing an infinite $R$-descending sequence $(f(x_{n+1}), f(x_n)) \in \prec$ which is a contradiction to $(Y,\prec)$ being well-founded.

• Yep, that'll do. – Kevin Arlin Oct 24 '12 at 14:58
• The title mismatches the excerpt from the book. Well-founded need not be a well-order. – Asaf Karagila Oct 24 '12 at 15:08
• @KevinCarlson Aces:) Thank you! – Rudy the Reindeer Oct 24 '12 at 15:48
• @AsafKaragila What title would you suggest? – Rudy the Reindeer Oct 24 '12 at 15:49
• Well founded. – Asaf Karagila Oct 24 '12 at 15:52

First, a notational error: $(x_{n+1},x_n)\in R$ does not describe a describe a sequence. What you mean is that there is a sequence $\langle x_n:n\in\Bbb N\rangle$ in $X$ such that $\langle x_{n+1},x_n\rangle\in R$ for each $n\in\Bbb N$. There’s no need for the scare quotes; just call it an $R$-descending sequence, or a descending sequence with respect to $R$. Similarly, there’s no good reason for the scare quotes on minimal: just say $R$-minimal.

Thus substance of the argument is correct, but it’s unnecessarily complicated. Let $A$ be any non-empty subset of $X$. Then $rk[A]$ is a non-empty subset of $Y$, so it has a $\prec$-least element $y$. Let $a\in A$ be such that $rk(a)=y$. If $\langle x,a\rangle\in R$ for some $x\in X$, then $rk(x)<y$, and therefore $x\notin A$. Thus, $a$ is an $R$-minimal element of $A$, and $R$ is well-founded.

• I corrected my question, thank you. Although having $(x_{n+1},x_n) \in R$ still looks like a sequence to me... – Rudy the Reindeer Oct 24 '12 at 15:53
• @MattN.: Having $\langle x_{n+1},x_n\rangle\in R$ for each $n\in\Bbb N$ is certainly a possible property of a sequence in $X$, but that’s not what you originally wrote. You spoke of a ‘sequence $(x_{n+1},x_n)\in R,n\in\Bbb N$’, which doesn’t actually make sense. For each $n\in\Bbb N$ $(x_{n+1},x_n)$ is a two-term sequence in $X$ that when viewed as an ordered pair is in $R$, but that’s clearly not what you were trying to say. – Brian M. Scott Oct 24 '12 at 16:01
• Thank you. No, I was trying to say that if I have $(x_{n+1}, x_n) \in R$ for all $n \in \mathbb N$ then $x_n$ is a sequence. – Rudy the Reindeer Oct 24 '12 at 16:29

I would say the claim is not true at all. For any nonempty $X$, the equality relation $$R=\{(x,x)\mid x\in X\}$$ vacuously satisfies the $(*)$ condition for any rank function $\mathit rk$. But it is not well-founded because of the infinitely descending chain $$\cdots \mathrel R x \mathrel R \cdots \mathrel R x \mathrel R x \mathrel R x$$

• Very well spotted! But your eyes have skipped the strictly, which means that $(x,x) \notin R$ for all $x \in X$. – Rudy the Reindeer Oct 24 '12 at 18:04
• @Matt: The only "strict" I see in the claim is a condition on $(Y,\prec)$ -- and everything about $\mathit rk$ and $Y$ is irrelevant because the lhs $x\ne y\land \langle x,y\rangle\in R$ of the implication in $(*)$ is never true for this $R$. – hmakholm left over Monica Oct 24 '12 at 18:08
• Dear @Henning, you are absolutely right. Now I am not sure what to say. I am very impressed with how you noticed that this claim is false. – Rudy the Reindeer Oct 24 '12 at 18:40
• @Matt: Is it possible that your source is using a nonstandard notion of "well-founded" that allows reflexive relations to satisfy it? – hmakholm left over Monica Oct 24 '12 at 18:42
• Yep, I just double-checked the definition. Let me add it to the question. – Rudy the Reindeer Oct 24 '12 at 18:43

The proof is fine. It is common to take $Y$ to be an ordinal, by the way.

• I'm shocked that you didn't provide an alternative proof not relying on AC. :-) – Michael Greinecker Oct 24 '12 at 15:00
• @Michael: I don't bother, when things are not needed. The previous questions by Matt show that AC is used through and through anyway. – Asaf Karagila Oct 24 '12 at 15:01