# Arithmetic systems without Induction

It's often said that AC is a controversial axiom and so often in my math classes when it is used a brief comment is made to the effect of "we can prove this without Zorn's Lemma but it's more work". And the attitude is that it doesn't matter, after all we can get the result by other means and the subject is geometry, analysis, etc. and not foundations (so it's not a big deal really).

However, Induction and the Well-Ordering Principle (its equivalent) are more common axioms however if we subtract these the same results seem to be true but at the same time I am not sure how to prove them.

So my question is: If we toss out WOP/Induction does it follow that everything falls apart? Robinson arithmetic is an example of such a system and it is essentially undecidable. I'm wanting clarification on what this means by way of examples (from Peano arithmetic); specifically, I'm wondering if in cases where we would have used Induction (or the equivalent) if we can't write a proof of the result do we conclude the result is unprovable or do we need a separate proof that it is "unprovable" (whatever that means). Do results have definite truth or false values or is it possible to be neither. If we can prove that the result is provable (i.e. that the result is either true or false and not neither) but we don't have an explicit proof of the result itself, does it follow that the result in our weaker system must be the same as it was in the stronger system (when we used Induction or whatever). If the result is "neither" can we tack on whatever we want the result to be as a new axiom in a consistent manner? I realize there are many questions here... here are some examples to help.

(1) "$$\sum_{j=1}^n j= \frac{n(n+1)}{2}$$"; this result is often how induction is introduced though induction is not required therefore it is clear the result would still hold in Robinson.

(2) "Any $$n\in N$$ has a unique expression $$n=c_11!+c_22!+\cdots +c_kk!$$ for some $$k\ge1$$, each $$0\le c_j\le j$$ and $$c_k\neq0$$."

When I proved this, I used induction and the proof was rather messy and detailed; so while the result appears to always hold I cannot imagine proving it without induction. So it seems that induction is necessary... but I'm not sure of its truth value in Robinson arithmetic.

(3) "Every subset of $$\mathbb{N}$$ is countable":Infinite sets with cardinality less than the natural numbers

It seems here that you either use AC (making the proof trivial) or you use the Well-Ordering Principle and then the proof is still easy but a little more work. But if we toss out these axioms then I'm not sure how to it prove the result. What's really interesting about this case, is that unlike the previous example where the result seems true (because we can test it for various cases) there is no way to test it here. It seems on par with the Continuum Hypothesis in terms of weirdness; I'm guessing in the absence of Induction there is no positive truth value to (3) but I'm not sure... and I'm guessing we could simply make an axiom about the existence of smaller infinities in a perfectly consistent way... though this is offensive to all intuition.

• Your question is very unclear to me. Is it about induction or about choice? is it about arithmetic or about set theory? Jan 26, 2019 at 20:42
• Neither AC or induction per se but rather (1) do usual theorems fail to obtain in any sense whatsoever if we subtract our favorite axioms (induction, for example (but not necessarily induction)). (2) If we fail to be able to prove our old theorems should we then prove they cannot be proven in a weaker system and therefore they are neither true nor false? (3) If something is neither true nor false can we add it as an axiom and (4) If we can prove something has a proof but cannot prove it directly, does it follow that its value is the same as in the stronger system? Jan 26, 2019 at 21:15
• @Squirtle This is all over the place, but (1) Sure, subtract axioms and you can prove fewer things. For instance, Robinson arithmetic cannot even prove $\forall x,y(x+y=y+x).$ In general it is bad at proving universal statements, although it can often prove every instance separately. (2) We often can prove that the weaker system cannot prove a given statement, as is true with my previous example. It makes no sense to say something is true or false in a system, only provable, refutable (i.e. negation is provable) or neither. Truth is about structures (e.g. $\mathbb N$), not formal systems. Jan 27, 2019 at 0:43
• @Squirtle (3) If something is not refutable in a system, it is consistent to add it as an axiom. For instance, it's well known that (assuming PA is consistent), Con(PA) is not provable in PA, so it follows that PA + $\lnot$Con(PA) is a consistent system. (4) Not sure what you mean here. Prove something has a proof where? Jan 27, 2019 at 0:54
• I don't understand your example (1): what do you mean when you claim that it's clear induction isn't needed? At a glance, I don't even think Q can prove "For all $n$, $\sum_{i=1}^ni$ exists." Keep in mind that even expressing this statement in the language of arithmetic is nontrivial - to define $\sum_{i=1}^ni$ we need to talk about finite sequences of natural numbers (that is, $\sum_{i=1}^ni$ is the unique number $x$ such that there is a sequence of length $n$ whose first term is $1$, whose $n$th term is $x$, and such that the $j+1$th term is the $j$th term plus $j+1$ for all $j<n$). Feb 8, 2019 at 19:01

If we toss out WOP/Induction does it follow that everything falls apart?

The answer is basically, yes.

There is very little that can be proved genuinely without induction. Robinson arithmetic, for example, cannot prove that addition is commutative, or that every number is either even or odd. More subtly, it cannot even prove that "$$\sum_{i=1}^ni$$" is always well-defined - that is, it cannot prove the statement "for all $$n$$ there is a unique sequence $$s$$ of length $$n$$ such that $$s_1=1$$ and for each $$1 we have $$s_k=s_{k=1}+k$$" (the final term $$s_n$$ would then be $$\sum^n_{i=1}i$$). Neither can Robinson arithmetic prove that every bounded subset of $$\mathbb{N}$$ is finite (which again has to be phrased in terms of sequences to even be expressible in the language of arithmetic).

The main "freedom" which dropping induction entirely permits is the existence of computable models (see Tennenbaum's theorem). For example, the set of polynomials in one variable with integer coefficients and positive leading term (fine, also including $$0$$) forms a computable nonstandard model of Robinson arithmetic which is fairly interesting in its own right. However, nobody would propose it as a satisfactory universe within which mathematics can properly be conducted (since for example it can't make sense of basic combinatorics).

That said, dropping most induction is more interesting. The system $$I\Sigma_1$$ (= the ordered semiring axioms + induction for $$\Sigma_1$$ formulas) is drastically weaker than PA but still proves many of the results of classical number theory. Additionally, it's strong enough that we can meaningfully ask how much additional induction is needed to prove the things it can't - this is part of reverse mathematics (which also studies the role of set existence axioms and their computability-theoretic content in proving higher-type statements), and I've said a bit about this here. Robinson arithmetic is just too weak for "reverse mathematics over Robinson arithmetic" to work properly (although we can go substantially below $$I\Sigma_1$$).

If you are interested in weak theories of arithmetic, I strongly recommend the book Metamathematics of first-order logic (which is freely and legally available online!). For even weaker systems, I don't know of a similarly good source but a good phrase to google is "bounded arithmetic."

Meanwhile, the situation in set theory is dramatically different. ZF (= set theory without choice) can still prove a huge amount of mathematics, so it's "usable" in a way that Robinson arithmetic is not. Additionally, there are natural principles contradicting choice, so there's a positive reason to consider ZF; by contrast I don't know of any natural arithmetic principles contradicting induction (although it would be really cool to find some).

• Awesome response! Thank you. Can you comment on my concern, "If we can prove that the result is provable (i.e. that the result is either true or false and not neither) but we don't have an explicit proof of the result itself, does it follow that the result in our weaker system must be the same as it was in the stronger system (when we used Induction or whatever)." I think my guess is correct... but maybe not. An analogy of why it might fail, in topology we have nets that can converge to multiple limits but if we "upgrade" the space then the net can converge to at most one thing. Feb 22, 2020 at 21:58
• @Squirtle I think so, although it's vague. A stronger system can't "change its mind" (without being inconsistent); if a weak theory $T_0$ can prove some sentence $\varphi$, then a stronger theory $T_1$ can also prove $\varphi$ (and cannot prove $\neg\varphi$ unless $T_1$ is inconsistent). But keep in mind that "provable" isn't unambiguous, you have to specify provability with respect to what theory (and I think "the result is either true or false and not neither" is intended to mean "the result is decidable in our weaker system" - if not, it's not really meaningful). Feb 22, 2020 at 23:18
• Thanks for attempting to understand what I mean rather than dismissing it as nonsense. I'm taking a few years off to teach myself these topics before going to grad school so there is at times a (technical) disconnect with the material... I have to kinda grasp at these weird concepts. Feb 23, 2020 at 0:54