0
$\begingroup$

Consider a countable set like $\mathbb{Q}$. Let $f : \mathbb{N} \rightarrow \mathbb{Q}$ be any bijection witnessing the equinumerosity of $\mathbb{Q}$ And $\mathbb{N}$. Then for each predicate $\phi$, the induction principle for $\mathbb{N}$ implies that $(\forall p \in \mathbb{Q})\phi(p)$ whenever $\phi(f(0))$ and $(\forall n \in \mathbb{N})(\phi(f(n)) \rightarrow \phi(f(n + 1)))$. More generally, each such $f$ induces a well-ordering on the relevant set, from which an induction principle for that set can be derived.

Is there an interesting example of a property true of some set like $\mathbb{Q}$ or $\mathbb{Z}$, the proof of which proceeds by induction in the manner described? It's quite easy to construct trivial examples to illustrate the possibility. However, I've never seen and can't seem to find any real examples.

$\endgroup$
2
  • $\begingroup$ Of course, well-ordering does not equate with standard induction. What you really mean is an order isomorphism to $\mathbb N$. One can do induction on any well-ordering more generally. $\endgroup$
    – Thomas Andrews
    Nov 5, 2015 at 23:42
  • $\begingroup$ @Thomas: I was under the impression that the well-ordering principle and the principle of mathematical induction are equivalent. In any case, the motivating example was the well-ordering obtained from an order isomorphism with the natural numbers. That is, unless I'm misunderstanding something about your comment. $\endgroup$
    – emi
    Nov 6, 2015 at 5:21

1 Answer 1

Reset to default
1
$\begingroup$

Essentially you're using a wellordering of $\mathbb{Q}$ (of length $\omega$) and proving the statement by induction on the wellordering. In this particular case we can actually construct, effectively specify, the wellordering.

For general infinite sets, we can't, and we have to appeal to the Axiom of Choice (AC). Sierpinski wrote a monograph Hypothese du Continu (1934) (The Continuum Hypothesis, CH), which explores consequences of CH. If I recall correctly, some proofs and/or constructions therein proceed from a wellordering of the reals of length $\omega_1$, guaranteed by AC + CH. Such a wellordering has the nice property that every initial segment is countable.

Though I can't recall further examples right now, I have seen early 20th century proofs which use a wellordering of the set under consideration, where in more recent times one would use a different form of AC — Zorn's lemma or the like.

$\endgroup$
2
  • $\begingroup$ I'll check out your references. They look promising, although I'm more interested in the case for countable sets without the axiom of choice, since the topic arose in my discrete math class. Thanks for the answer! $\endgroup$
    – emi
    Nov 6, 2015 at 5:25
  • $\begingroup$ Also look at Hausdorff's magnum opus. The wikipedia article I just cited is literally translated from the Klingon or something, it's barely English, .. but one can manage. (Hausdorff's work has definitely been translated into English many moons ago :) and it's much easier to read than that wikipedia article! Sierpinski's book remains, I think, French only. So, accessibility depends on what languages you "have". But "mathematical French" isn't a high bar: "espace topologique" et al :) $\endgroup$
    – BrianO
    Nov 6, 2015 at 7:19

You must log in to answer this question.

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