# If the axiom of induction were extended to include imaginary numbers...

• A
If the axiom of induction was extended to include imaginary numbers, what effect would this have?

The axiom of induction currently only applies to integers. If this axiom and/or the well ordering principle was extended to include imaginary numbers, would this cause any currently true statements to become false?

I am aware that the well-ordering principle requires a concept of "next", but if each multiple of I was treated as the "next", it seems to me that this would fit in perfectly well with common axiomatic systems and would not lead to any contradiction.

fresh_42
Mentor
If the axiom of induction was extended to include imaginary numbers, what effect would this have?

The axiom of induction currently only applies to integers. If this axiom and/or the well ordering principle was extended to include imaginary numbers, would this cause any currently true statements to become false?

I am aware that the well-ordering principle requires a concept of "next", but if each multiple of I was treated as the "next", it seems to me that this would fit in perfectly well with common axiomatic systems and would not lead to any contradiction.
I'm not quite sure whether I understand this. An induction needs a base point and therefore cannot go from ## -\infty ## to ## +\infty ##.
One could regard inductions on ## \mathbb{Z} [ i ] ## either according to some ordering or as a double induction along ##\mathbb{Z}## and ## n_0 + \mathbb{Z} \cdot i ## starting at a certain point. But neither would be a proper generalization, but rather an induction as it is: split and / or nested.
I'm afraid you will have to define what you mean more rigorously.

Axiomatically, induction is just the Peano Axiom for natural numbers. you may change their counting, shift them or whatever. But you need the natural numbers somehow.

mfb
Mentor
You can map every countable infinite set to the natural numbers, and run a normal induction over it (at least in principle). You cannot do induction over uncountable sets as you'll never reach all elements by going from one element to the next - that is the definition of uncountable.

• FactChecker
You can map every countable infinite set to the natural numbers, and run a normal induction over it (at least in principle). You cannot do induction over uncountable sets as you'll never reach all elements by going from one element to the next - that is the definition of uncountable.
Sure, but https://en.wikipedia.org/wiki/Transfinite_induction

• mfb
mfb
Mentor
Is there any non-trivial proof that uses transfinite induction over the real (or complex) numbers? A well-ordering relies on the axiom of choice, so you cannot even explicitly write down the ordering you use in the induction.

Are there are proofs of results of ##\mathbb{R}## that do transfinite induction over uncountable sets? Yes, plenty.
1) Note that the proof of Zorn's lemma itself often relies on transfinite recursion/induction
2) There exists a measurable set in ##\mathbb{R}## that is not a Borel set can be proved most easily with transfinite recursion and induction over an uncountable set.
3) The Cantor-Bendixon theorem can be proved by transfinite recursion/induction: every uncountable closed subset of ##\mathbb{R}## is the union of a perfect set and a countable set.

As for transfinite recursion/induction over the real numbers (like you asked), one can use it to provide a counterexample to the following version of Cantor-Bendixon: there is an uncountable set without perfect subset.

• fresh_42 and mfb
fresh_42
Mentor
Is there any non-trivial proof that uses transfinite induction over the real (or complex) numbers? A well-ordering relies on the axiom of choice, so you cannot even explicitly write down the ordering you use in the induction.
I also only have found Zermelo's well-ordering theorem and Tuckey's Lemma as applications (in two books). Since all those statements (Tukey's Lemma, Hausdorff's Maximality Priciple, Zorn's Lemma, Zermelo's well-ordering theorem) are equivalent to the axiom of choice, it seems to me as circling around. (I would like to mention an analogue of one of my favorite sports here, but it might be misunderstood and Wiki doesn't have an English name for it. I should ask someone how Froome, Evans or LeMond call it.)
Maybe one could use it to prove the existence of Hamel bases. But this would again only substitute the axiom of choice.
However, I admit that I find transfinite induction pretty elegant and am a fan of it, since I've read it for the first time.

How exactly would you do that?

The concept of induction does not originate with the natural numbers, the natural numbers originate with induction. Induction simply means a logical process by which the truthfulness of one statement implies the truthfulness of another statement, using specific statements to construct more general statements (as opposed to deduction, which works in the opposite direction). What exactly would it mean for, say, the √(-1)th statement out of a list of propositions to be true?

That does not mean that induction is not useful or valid in proofs involving complex numbers. You could easily run into situations where it might be productive to, for instance, use induction on the imaginary part of a complex number, where proposition n involves the number z = a + in, from which proposition n+1 could somehow be reached by adding i1 to z to get a + i(n+1). That could be a valid proof.

To answer the question: sure you can do induction on ##\mathbb{Z}##, and you can do it on ##\mathbb{Z}## and ##\mathbb{Q}## also. The only problem is that the ordering of the induction won't agree with the natural ordering, and that's a big problem.

For example, for ##\mathbb{Z}## I can prove ##P(z)## for all ##z\in \mathbb{Z}## by following this rather weird scheme:
1) ##P(0)## and ##P(1)## are true.
2) If ##z>0## and ##P(z)## is true, then ##P(-z)## is true.
3) If ##z<0## and ##P(z)## is true, then ##P(-z+1)## is true.

So to proceed by this induction, we prove ##P(0)## and ##P(1)## to be true. Then we prove ##P(1)\Rightarrow P(-1)\Rightarrow P(2)\Rightarrow P(-2)\Rightarrow P(3)\Rightarrow ...##.

This is possible in principle, but I don't know of any natural statement that is proven this way. Similar schemes can be done on ##\mathbb{Q}## and ##\mathbb{Z}## but are even more complex (and never used).

As for ##\mathbb{Z}##, the following double induction scheme seems more natural (but I still don't really know an application).
1) ##P(0)## is true.
2) If ##P(z)## is true, then ##P(z+1)## is true.
3) If ##P(z)## is true, then ##P(-z)## is true.
4) If ##P(z)## is true, then ##P(z + i)## is true.

(1) proves the statement for ##0##. (2) proves it for all positive integers. (3) proves it for all integers. (4) proves it for the upper half plane. (3) proves it for the entire plane.

mfb
Mentor
There are so many different ways to combine several induction steps. A nice one is the forward-backward induction to prove arithmetic mean > geometric mean:
P(1) -> P(2) -> P(4) -> P(8) -> ... for P(2n)
P(n) -> P(n-1) to cover the cases in between.