1
$\begingroup$

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.

2 Answers 2

2

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

  • 0
    Is my answer to (i) correct?2012-10-23
  • 1
    @MattN.: Yes, if my guess at their distinction between *well-founded relation* and *strictly well-founded relation* is correct.2012-10-23
  • 0
    They defined strictly well-founded as well-founded and for all $x$, $(x,x) \notin R$ ($R$ is irreflexive).2012-10-23
  • 0
    For the other direction: Assume $R$ is not well-founded. Then there is a set $Y\subset X$ such that for every $y$ \in $Y$ there is $z\in Y$ such that $(z,y) \in R$. Construct a sequence $y_n$ as follows: define $y_1 = y$ for any $y$ in $Y$. Then $y_2 = z$ for some $z \in Y$ with $(z,y_1)$. And so on.2012-10-23
  • 1
    @MattN.: Then yes, it looks fine to me. The proof for the other direction is okay, though it could be written a bit better.2012-10-23
  • 0
    @MattN.: You’re welcome!2012-10-23
  • 0
    Wait -- I can't use DC. DC is a statement about an entire binary relation. But I don't necessarily assume my $R$ to be entire. Or am I missing something?2012-10-23
  • 1
    @MattN.: Not a problem; give me a few minutes, and I’ll add to my answer.2012-10-23
  • 0
    Thank you! (I could just use AC, no? AC lets me pick an element from my non-empty set $Y$ at each step, right?)2012-10-23
  • 1
    @MattN.: Yes, you could use AC, but it’s a bigger hammer than you need.2012-10-23
  • 0
    But I'm trying to understand where I use what: assume I wanted to prove the missing direction with AC, would the following be correct? Assume $R$ is not well-founded. Then there is a set $Y\subset X$ such that for every $y \in Y$ there is $z\in Y$ such that $(z,y)\in R$. Construct a sequence $y_n$ as follows: $Y$ is non-empty hence by AC we can pick an element $y_1 = y$. Since $Y$ contains infinitely many elements, $Y \setminus \{y_1\}$ is still non-empty so that again by AC we can pick $y_2$ such that $(y_2, y_1) \in R$. We repeat this to obtain the desired sequence.2012-10-23
  • 1
    @MattN.: Exactly.2012-10-23
  • 0
    Aces, thank you very much for your patience!2012-10-23
  • 0
    Actually, I'm sorry to bother you again: the collection of sets we're making a choice over doesn't exist in its entirety at the time of applying the choice function. Rather, the $n$-th application of $f$ looks like $f^n (Y) = f(f(\dots f(Y)\dots))$, so depends on itself recursively. But AC is about an existing collection of sets. How can we justify the validity of this choice process nonetheless, if we assume AC?2012-10-23
  • 0
    I can answer my own question: an equivalent formulation of AC is that "For any set A, the power set of A (with the empty set removed) has a choice function." and $f^n (Y) \in \mathcal{P}(Y)$.2012-10-23
  • 1
    @MattN.: Yep: standard trick. I just added a slightly different way to do it to my answer.2012-10-23
  • 0
    Thank you! Why do you make the restriction $|Y \setminus A|< \omega$ in the definition of curly $A$?2012-10-23
  • 0
    Funny me. The reason I took a day to digest your **Added:** paragraph is that I kept thinking "but the fact that such a sequence exists is "obvious", why do we need to apply DC?". But of course that's just the same as AC: there it's also "obvious" that if we have a bunch of non-empty sets, then we can pick an element from each.2012-10-24
  • 0
    I'm sorry, but did you mean to write $$P=\prod_{\langle A,y\rangle\in\mathscr{A}}z\;;$$ where you wrote $$P=\prod_{\langle A,y\rangle\in\mathscr{A}}A\;;$$?2012-10-24
  • 0
    @MattN.: No, I meant what I wrote.2012-10-24
  • 0
    But then $y_{n+1}=\varphi(\langle A_n,y_n\rangle) = A$ on the very last line. No? Because $\varphi \in P = A \times A \times \dots \times A $...2012-10-24
  • 0
    @MattN.: No. A point $\varphi$ of $P$ is a function whose domain is the index set $\mathscr{A}$ and whose value at a given index $\langle A,y\rangle$ is an element of that $A$. Thus, $\varphi(\langle A_n,y_n\rangle)$ is an element of $A_n$, which is exactly what we want it to be.2012-10-24
2

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