Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
@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
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. –  Brian M. Scott Oct 23 '12 at 15:04
1  
@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
1  
@MattN.: Yes, you could use AC, but it’s a bigger hammer than you need. –  Brian M. Scott Oct 23 '12 at 15:19
1  
@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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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