0
$\begingroup$

I found a statement said that the proposition "Mathematical induction can be applied on any total order set" is False.

(The place I found the statement might not be believable.)

This means that there is a counterexample where cannot the math induction be applied. I didn't find out much information about the relation of Mathematical induction and total-ordered set. So I guess somewhere I thought wrong.

I have no robust concept about them though, however I thought that any total-ordered set can be applied math induction, stated with my naive intuition below:

Because Mathematical induction is based on well-ordering principle, which is applied on $\mathbb{Z^+}$, I'd consider that any total-ordered set is isomorphic to $\mathbb{Z^+}$. By applying a topological sort on the total-ordered set, we can get a chain. The chain is actually the longest path of the total ordered set, so it preserves the order property. The isomorphism $f$ can be defined by: For all elements $x$ in the total-ordered set, $f(x)=$ " $x$'s order number in the chain".

Hence, I "guess" that math induction can be applied on the total-ordered set, based on the assumption that "If any set is isomorphic to $\mathbb{Z^+}$, and that isomorphism preserves the order information, then math induction can be applied on it", which I cannot tell is correct or not.

Thanks for any hint and correction!

$\endgroup$
8
  • 5
    $\begingroup$ "total ordering" and "well-ordering" are not at all the same. $\endgroup$ Commented Jan 31, 2019 at 9:11
  • 6
    $\begingroup$ Try the real numbers. They are totally ordered. What is the "next real number" after $1$? $\endgroup$
    – Arthur
    Commented Jan 31, 2019 at 9:11
  • $\begingroup$ This will work only with ordered group that is countable $\endgroup$
    – Shaq
    Commented Jan 31, 2019 at 9:22
  • 1
    $\begingroup$ @Shaq Yeah, the rational numbers would like to have a word with you. (Technically it's possible, but it's rare to see it in action. Most often it's something like induction on the denominator instead of on the actual rational number.) $\endgroup$
    – Arthur
    Commented Jan 31, 2019 at 9:30
  • 1
    $\begingroup$ @Shaq "To put them ( the rationals) in chain" still is not well-ordering them. We "can put them" in chain (i.e., in a sequence) because we know they're countable, but we've no idea what a well order of them is and that's what we need to apply induction in a reasonable way. $\endgroup$
    – DonAntonio
    Commented Jan 31, 2019 at 10:18

2 Answers 2

1
$\begingroup$

One very general form of induction is well-founded induction. Suppose $\le$ well-founds $S$. Since any non-empty subset of $S$ has a $\lt$-minimal element, contrapositively $$(\forall x\in S(x\lt y\to\phi(x))\to\phi(y))\to\forall y\in S(\phi(y)).$$

One can't generalise this to total ordering, which doesn't guarantee an analogous property of $S$'s non-empty subsets.

However, one can sometimes induct without knowing how to well-found a set. For example, real induction relies on the fact that subsets of $\Bbb R$ have infima and suprema.

$\endgroup$
3
  • $\begingroup$ "Real induction" is essentially just that a real interval is a connected space in the order topology ( because $\Bbb R$ is order-dense in itself and any bounded non-empty subset has a $\sup$ and $\inf.$ E.g. if $C$ is an open cover of $[0,1]$ let $x\in A$ iff $x\in [0,1]$ and $[0,x]$ can be covered by a finite subset of $C.$ We show that $A$ is open-and-closed in the connected space $[0,1],$ and since $A$ is not empty (because $0\in A$), therefore $A=[0,1].$...............+1 $\endgroup$ Commented Jan 31, 2019 at 11:21
  • $\begingroup$ Only problem with the answer is that the phrase "mathematical induction" OP uses doesn't conventionally mean either of the forms of induction you mention. $\endgroup$ Commented Apr 15 at 23:43
  • $\begingroup$ Really nice link though! $\endgroup$ Commented Apr 16 at 0:31
0
$\begingroup$

"I thought that any total-ordered set can be applied math induction"

"I'd consider that any total-ordered set is isomorphic to $\mathbb{Z}^+$"

You thought wrong, possibly because you have unconventional ideas of "total-ordered set" and "math induction".

The conventional meaning of totally ordered set (usual phrase) is the field of a total order when that field is a set (together with the total order itself).

A total order is a particular kind of binary relation (the same concept can be expressed in terms relations that are not binary, but a binary relation is sufficient). Something is in the field of a relation if it's one of the things related in some instance of the relation. For instance if Alfred is the brother of Betty, then both Alfred and Betty are in the field of the binary relation "is the brother of".

A binary relation $<$ is of the particular form referred to if it's

  1. transitive i.e. for all $x, y, z$ in the field of $<$, $x<z$ if $x<y$ and $y<z$.
  2. asymmetric i.e. for all $x, y$ in the field of $<$, $x<y$ and $y<x$ don't both hold.
  3. "connected" i.e. for all $x, y$ in the field of $<$, if $x\neq y$ then $x<y$ and $y<x$ don't both not hold.

and a binary relation of that form corresponds with most people's understanding of $x$ comes before $y$ in a total order of it's field.

The same term may be conventionally used to denote a binary relation $\leqslant$ of a similar form but with condition 2. replaced by

  1. asymmetric i.e. for all $x, y$ in the field of $\leqslant$, $x\leqslant y$ and $y\leqslant x$ hold if, and only if, $x=y$.

This is just a slight touch of schizophrenia in the conventional usage of the terms total order and asymmetric, not materially affecting the argument.

If $<$ is a total order as defined above, then so is it's converse. (The converse $\breve{B}$ of a binary relation $B$ is the relation in which $x\breve{B}y$ if, and only if, $yBx$.) The three conditions then apply equally to $\breve{<}$ (normally denoted $>$ when $<$ is used to denote the original relation). Also the fields of $B$ and $\breve B$ are identical so if the field is a totally ordered set under $<$ it is also under $>$.

Now consider the totally ordered set $\mathbb{Z}^+$ under $<$ and suppose there is, as the second of your statements I quoted above maintains, an order isomorphism $\phi$ of $\mathbb{Z}^+$ under $>$ onto this set. Then

Let $\phi(0)=n$

Then $n<n+1$ therefore $\phi^{-1}(n)>\phi^{-1}(n+1)$

i.e. $0>\phi^{-1}(n+1)$, contradicting the assumption that $\phi$ is a bijection from $\mathbb{Z}^+$ to $\mathbb{Z}^+$. So there can be no such order isomorphism $\phi$ in that case, which invalidates your general statement.

According to your question, the first of your statements I quoted above is, you say, based on the intuitions subsequently described, which include the second one I mentioned that is false on any normal reading, so that may answer the question.

My interpretation of "can be applied" in the first statement (possibly not what was intended) would be that given any totally ordered set (by $<$) and property $\phi$ then if you can prove

  1. $\phi(m)$ for a minimum element of $<$ (i.e. $m<x$ for all $x\neq m$ in the field of $<$).
  2. $\phi(x)\implies\phi(s)$ for any immediate successor of $x$ (i.e $x<s$ and there is no $t$ such that $x<t<s$.)

then you can conclude $\phi(x)$ for all elements of the field of $<$.

You could "apply" this to the example $\mathbb{Z}^+$ under $>$ and it would strictly speaking hold, because you couldn't prove 1. since there is no minimum element, so the antecedent would be false whatever $\phi$ were.

On the other hand neither could you use it to prove anything in that case.

If you consider the non negative real numbers $\mathbb{R}_{\geqslant 0}$ under $<$ then it doesn't hold. It would allow you to prove all real numbers $\geqslant 0$ are integers, because

  1. 0 is an integer (and a minimum element)
  2. $x$ is an integer$\implies s$ is an integer for any immediate successor of $x$ (vacuously true since all real numbers have no immediate successor under $<$).

On the other hand, "If any set is isomorphic to $\mathbb{Z}^+$ , and that isomorphism preserves the order information, then math induction can be applied on it" is closer to being correct.

$\mathbb{Z}^+$ is just a set so to make it a totally ordered set you need a total order on the set. Normally the usual $<$.

Any order isomorphism preserves the order information, because that's what an order isomorphism is. (Perhaps the unusual phrasing was intended to convey what I said in the last paragraph.)

If that's what you mean and $<$ is the usual order then it's trivially true to prove by induction in $\mathbb{Z}^+$ under $<$ assuming my previous interpretation of "can be applied".

Let $\phi$ be an isomorphism of $<$ on $\mathbb{Z}^+$ onto the binary relation $\prec$ on the set $Y$, that is a 1-1 correspondence between fields of $<$ and $\prec$ ($Y$ in the latter case) such that $x<y$ if, and only if, $\phi(x)\prec\phi(y)$.

$\prec$ is a total order (though the fact doesn't come into the proof).

  1. If $x\prec y$ and $y\prec z$ then for some $l,m,n$ in $\mathbb{Z}^+$, $x=\phi(l),y=\phi(m),z=\phi(n)$ and $l<m$ and $m<n$, hence $l<n$ so $x\prec z$. So $\prec$ is transitive.
  2. If $x\prec y$ and $y\prec x$ then for some $l,m$ in $\mathbb{Z}^+$, $x=\phi(l),y=\phi(m)$ and $l<m$ and $m<l$ which is impossible. So $\prec$ is asymmetric.
  3. If $x\neq y$ are $Y$ then for some $l\neq m$ in $\mathbb{Z}^+$, $x=\phi(l)$ and $y=\phi(m)$ and one of $l<m$ and $m<l$ holds, so one of $x\prec y$ and $y\prec x$ holds. So $\prec$ is connected.

$\phi(0)$ is a minimum element of $Y$ under $\prec$ because any element $y$ of $Y$ is $\phi(n)$ for some $n$ in $\mathbb{Z}^+$ (because $\phi$ is onto) and $n\neq 0$ if $y\neq\phi(0)$ (because $\phi$ is 1-1). Then $0<n$, so $\phi(0)\prec\phi(n)=y$ (because $\phi$ is an isomorphism).

$\phi(n+1)$ is an immediate successor of $y$ in $Y$ under $\prec$ if and only if $y=\phi(n)$. If $y=\phi(n)$, $n<n+1$ so $y\prec\phi(n+1)$, but if $y\prec z\prec\phi(n+1)$ then $\phi^{-1}(y)<\phi^{-1}(z)<\phi^{-1}(\phi(n+1))$ or $n<\phi^{-1}(z)<n+1$ which is impossible. If $y\neq\phi(n)$, then $y=\phi(m)$ for some $m\neq n$. Then if $\phi(n+1)$ is an immediate successor of $y$, $m<n+1$ so $m<n$, but then $y\prec\phi(n)\prec\phi(n+1)$ contradicting the assumption that $\phi(n+1)$ is the immediate successor of $y$.

Now suppose you have proved for some property $\psi$

  1. $\psi(m)$ for the minimal element of $\prec$
  2. $\psi(x)\implies\psi(s)$ for any immediate successor of $x$ (in $\prec$)

then you've proved the required antecedents assumed in my interpretation of your phrase "can be applied" above.

But you've also proved $\psi(\phi(0))$ and for all $n$ in $\mathbb{Z}^+$, $\psi(\phi(n))\implies \psi(\phi(n+1))$). So by induction (in $\mathbb{Z}^+$ under $<$) $\psi(\phi(n))$ for all $n$ in $\mathbb{Z}^+$.

But also each $x$ in $Y$ is $\phi(n)$ for some $n$ in $\mathbb{Z}^+$, so $\psi(x)$ for each $x$ in $Y$, which is to say the consequent, in this case follows.

It doesn't necessarily follow if the usual ordering of $\mathbb{Z}^+$ is not assumed. For example if you order all the even numbers in their usual order but before all the odd numbers in their usual order and consider the identity map as the isomorphism $\phi$, then you can prove that the minimum element $(0)$ is even and whenever $n$ is even so is its immediate successor in that ordering $(n+2)$, but you can't then conclude that all members of $\mathbb{Z}^+$ are even.

$\endgroup$

You must log in to answer this question.

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