0
$\begingroup$

It seems obvious to me that if for any domino (it is known that all previous dominos fell than this domino will also fell) than it is true that all dominos will fell. It should not matter if there is an infinity of dominos before any domino. Why then the PTI is not true on sets that are not well ordered? It seems to me I understood the proof which indeed shows that PTI is not true when the property in PTI is that x does not belong to B (set that is not well ordered). But is PTI true in my domino example? Is there a way to show that PTI may not be true in domino example? It seems to me that domino example covers all cases.

$\endgroup$
1
  • 1
    $\begingroup$ Consider the real line with the usual ordering, and let $P(x)$ denote the statement $x\le0$. Note that, if $P(y)$ holds for all $y\lt x$, then $P(x)$ also holds. $\endgroup$
    – bof
    Oct 21, 2020 at 7:12

2 Answers 2

2
$\begingroup$

Every linearly ordered set has a largest well-ordered initial segment (which may as well be empty). Call this segment $S$, and consider the property $x\in S$.

Take any point outside of $S$, if such point exists, $y$, then it holds for every $x<y$ $$\forall u(u<x\to u\in S)\to x\in S,$$ because $S$ is an initial segment, and if $x\notin S$, then there is some $u<x$ such that $u\notin S$ as well. Because $S$ is the largest well-ordered initial segment.

Therefore, if PTI holds, $S$ must be everything, and so well-ordered.


Of course, this talks about linear orders. We can talk about partial orders, and the same idea works out with a well-founded downwards-closed subset. So we get that well-foundedness to be equivalent to having a recursion property.

$\endgroup$
19
  • $\begingroup$ "Every linearly ordered set has a largest well-ordered initial segment"? A set of all integers is linealy ordered but does not have a largest well-ordered segment (with minimal element). What do you mean by initial segment? $\endgroup$ Oct 21, 2020 at 12:32
  • $\begingroup$ The empty set, as I said. $\endgroup$
    – Asaf Karagila
    Oct 21, 2020 at 12:33
  • $\begingroup$ But empty set is not the largest well-ordered segment of linearly ordered set, such as Z. Segment of a set is just a subset of a set? It looks like you state that if PTI holds than the set is well-ordered. But it is not true - I gave you the domino example with infinite numbers of dominos at the left of any domino. $\endgroup$ Oct 21, 2020 at 12:46
  • $\begingroup$ It is the largest initial segment. Any other initial segment contains infinitely many negative integers and is therefore not well-ordered. $\endgroup$
    – Asaf Karagila
    Oct 21, 2020 at 12:46
  • $\begingroup$ the set with only number 1 is larger than empty set, but well-ordered $\endgroup$ Oct 21, 2020 at 12:51
0
$\begingroup$

The induction principle for well-ordered sets is the following theorem: Let $(X,<)$ be a well-ordered set and let $P(x)$ be a statement pertaining to elements $x$ of $X$. (It can be itentified with the subset $P(X):=\{ x \in X \ | \ P(x)\}$ of $X$). Assume that the following statement holds:

$\forall x(\forall y(y<x\Longrightarrow P(y)) \Longrightarrow P(x))$

Then $\forall z P(z)$ holds. In other words, if $P(x)$ holds for $x$ whenever $P(y)$ holds for all $y<x$, then $P(z)$ holds for all $z$.

Consider a linearly ordered set $(X,<)$ which is not well-ordered. So there is a non-empty subset $Y \subseteq X$ which has no minimum. Consider the statement $P(x): \forall y \in Y,x<y$. Let $x \in X$ such that for all $z\in X$ we have $z<x\Longrightarrow P(z)$. I claim that $P(x)$ holds. Indeed assume for contradiction that there is $y \in Y$ with $y\leq x$. Since $Y$ has no minimum, we may assume that $y<x$. So $P(y)$ holds by our hypothesis. In particular we have $y<y$: a contradiction. We deduce that $P(x)$ holds.

But of course the statement $\forall z P(z)$ is false since $P(y)$ is false when $y \in Y$ and $Y$ is non-empty. So the induction principle fails for $(X,<)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .