Infinite induction

78 Views Asked by At

$1$- We can prove by induction that If $\preceq$ is a total ordering on $A$, every non-empty $\color{blue}{finite}$ subset $S$ of $A$ has a least element and a greatest element.

$2$- But how to prove that If $\preceq$ is a total ordering on $A$, every non-empty $\color{red}{countable}$ subset $S$ of $A$ has a least element and a greatest element.

Here we can't use induction anymore.

Edit:

I've seen this question "Suppose $A$ has the property that every non-empty countable subset has a least element. Show that $A$ is well ordered. (Hint: show first that A is totally ordered.)". So I'm wondering could we prove the second paragraph?

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the set of all integers, which is totally ordered, countable, with neither a maximum nor a minimum element.

What you need is well ordering, not total ordering. That's what makes induction work. See the wikipedia page.