4
$\begingroup$

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:

enter image description here

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

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

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.

$\endgroup$
  • $\begingroup$ I corrected my question, thank you. Although having $(x_{n+1},x_n) \in R$ still looks like a sequence to me... $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 15:53
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 24 '12 at 16:01
  • $\begingroup$ 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. $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 16:29
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very well spotted! But your eyes have skipped the strictly, which means that $(x,x) \notin R$ for all $x \in X$. $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 18:04
  • 1
    $\begingroup$ @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$. $\endgroup$ – Henning Makholm Oct 24 '12 at 18:08
  • $\begingroup$ 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. $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 18:40
  • $\begingroup$ @Matt: Is it possible that your source is using a nonstandard notion of "well-founded" that allows reflexive relations to satisfy it? $\endgroup$ – Henning Makholm Oct 24 '12 at 18:42
  • $\begingroup$ Yep, I just double-checked the definition. Let me add it to the question. $\endgroup$ – Rudy the Reindeer Oct 24 '12 at 18:43
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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