Can we prove every number is even or odd without induction?

[lugita15]

It is a simple exercise to prove using mathematical induction that if a natural number n > 1 is not divisible by 2, then n can be written as m + m + 1 for some natural number m. (Depending on your definition of odd number, this can either be stated as "every number is even or odd", or as "every odd number is one greater than an even number". My question is, can this be proven without induction? In other words, can this be proven in Robinson arithmetic? If not, what is example of a nonstandard model of Robinson arithmetic that doesn't have this property?

The reason I'm asking this is that the proof of the irrationality of the square root of 2 is usually presented with only one use of induction (or an equivalent technique). But the proof depends on the fact if k^2 is even, then k is even, and that fact in turn depends on the fact that the square of a number not divisible by 2 is a number not divisible by 2. And that fact is, as far as I can tell, is a result of the proposition above. (I'm open to correction on that point.) So if that proposition depended on induction, then the proof that sqrt(2) is irrational would depend on two applications of induction. (The reason that the ancient Greeks wouldn't have been aware of this is that Euclid implicitly assumes the proposition above, when he defines an odd number as "that which is not divisible into two equal parts, or that which differs by a unit from an even number".)

Any help would greatly appreciated.

Thank You in Advance.

 

[CompuChip]

I guess you could say something like: let n = 2k + r, where we assume that $n, k, r \ge 0$.
If r = 0 the number is even, by definition. We can also assume $r < 2$, because as long as $r \ge 2$ we can consider $n = 2k' + r'$ with k' = k + 1, r' = r - 2 and still satisfy our initial non-negativity assumptions. So if 0 < r < 2 then the only other possibility is r = 1.

The thing is, while writing this, I am wondering whether the argument for talking r below 2 is valid, or this is a argument by induction in disguise :)

On the other hand, even the very definition of the natural numbers (from Peano's axioms) is inductive. So even if you start from there, I would think the "best" you can do is prove that every even number is followed by an odd one and vice versa; which again sounds like an informal way of doing induction.

 

[lugita15]

I guess you could say something like: let n = 2k + r, where we assume that $n, k, r \ge 0$.
If r = 0 the number is even, by definition. We can also assume $r < 2$, because as long as $r \ge 2$ we can consider $n = 2k' + r'$ with k' = k + 1, r' = r - 2 and still satisfy our initial non-negativity assumptions. So if 0 < r < 2 then the only other possibility is r = 1.

The thing is, while writing this, I am wondering whether the argument for talking r below 2 is valid, or this is a argument by induction in disguise :)

It is indeed induction in disguise, because you're assuming that if you keep iterating the operation k' = k + 1, r' = r - 2, you'll eventually get an r value less than 2. In other words, you're assuming that you can't have an infinite descending sequence of natural numbers, which is an assumption equivalent to induction.

On the other hand, even the very definition of the natural numbers (from Peano's axioms) is inductive.

Well, there are systems of arithmetic weaker than Peano arithmetic that don't use induction. In particular, Robinson arithmetic is basically what you get when you take out induction out of Peano arithmetic (and add one minor axiom, namely that every number other than 0 is the successor of some number). You can prove quite a lot in Robinson arithmetic, and even in systems much weaker than Robinson arithmetic. In fact, Harvey Friedman made the conjecture that pretty much all "naturally occurring" theorems of number theory can be proven in a very weak system known as EFA.

In any case, my question was about whether Robinson arithmetic suffices to prove the statement.

 

[verty]

You can have a sequence of proofs: $P(0), P(1), ...$ for each natural number.
You can have $P(0), P(0) \land P(1), P(0) \land P(1) \land P(2), ...$ for each natural number.
You can prove that every natural number is either even or odd, but you can't prove $\forall x P(x)$.
It's about what one can deduce in the language. But we all know that those two sequences of proofs work for all natural numbers.

 

[lugita15]

You can prove that every natural number is either even or odd, but you can't prove $\forall x P(x)$.

There are plenty of propositions of the form $\forall x P(x)$ that can be proven in Robinson arithmetic, i.e. without using induction. There are also propositions of that form that require induction to prove them. What makes you think that the proposition we're dealing with is in the second category rather than the first?

 

[Jolb]

I've been following this post because I too fell into the trap CompuChip got into. [Luckily I was able to delete my post when I realized I was making a logical fallacy.] Since I am no expert on number theory or "Robinson arithmetic" (first time I've heard of that), I am not sure if verty's answer makes sense but I believe it must be making a similar logical error.

To me, it seems obvious that in order to define natural numbers, you must have the axiom of induction [it is one of the Peano axioms]. If you are using some sort of alternative definition for a natural number in some sort of Robinson arithmetic, you must define what you mean by a natural number. In other words, without induction, you must be using some nonstandard definition of natural number. To be able to determine whether all natural numbers are "even" or "odd" (or any other property for that matter), we must first know what your definition of natural number is--and most people assume induction as an axiom for natural numbers.

 

[chiro]

Another technique is to form equivalence classes for both even and odd numbers and then show that these classes partition all numbers and cover the set.

 

[lugita15]

Since I am no expert on number theory or "Robinson arithmetic" (first time I've heard of that)

Robinson arithmetic is basically Peano arithmetic minus induction (plus a minor axiom that every number greater than 0 has a predecessor).

To me, it seems obvious that in order to define natural numbers, you must have the axiom of induction [it is one of the Peano axioms]. If you are using some sort of alternative definition for a number in some sort of Robinson arithmetic, you must define what you mean by a number. In other words, without induction, you must be using some nonstandard definition of natural number. To be able to determine whether all numbers are "even" or "odd" (or any other property for that matter), we must first know what your definition of natural number is--and most people assume induction as an axiom for numbers.

It depends on what you mean by "define". In mathematics, we can either define things explicitly, like "an even number is a natural number which is divisible by 2", or axiomatically, like "the natural numbers system is a system that satisfies the axioms of Peano arithmetic". If you use Peano arithmetic, you're defining the natural numbers axiomatically. So if you want to know how can you define natural numbers in Robinson arithmetic, the answer is exactly the same way: we say "the system of natural numbers is a system that satisfies the axioms of Robinson arithmetic".

There's also another sense of the word "define": you may want to define a system using a set of axioms that ONLY the system you're talking about satisfies. But that's too hard a condition to literally satisfy, because if the set {1,2,3,...} satisfies any set of axioms, then surely the set {1',2',3',...}, where everything stays the same but you just put a prime symbol after each number, also satisfies the same set of axioms. But here's what we can do: we can require that if two systems satisfy our set of axioms, then the two systems must be isomorphic to each other; i.e. they're basically the same system, except the elements have been "relabeled". To put it another way, we want a set of axioms that characterizes our system "upto isomorphism".

Unfortunately, it turns out that we can't really characterize the natural number in this manner: there exists no recursive axiom system which characterizes the natural numbers upto isomorphism. (Recursive means a computer program can do it.) To put it another way, there's no set recursive set of axioms and rules of inference that ONLY systems isomorphic to the natural numbers satisfy. (So neither Peano arithmetic nor Robinson arithmetic suffice.) But there is one piece of good news: you CAN characterize the natural numbers upto isomorphism if you use second-order logic. All you need to do is replace the usual induction schema with the full second-order induction axiom. (The induction schema, which is what we use in first-order Peano arithmetic, states for each particular formula ψ(n), that if ψ(0) and ψ(n) implies ψ(n+1) for all n, then ψ(n) for all n. The second-order induction axiom, on the other hand says that for all sets of natural numbers X, even sets that can never be defined by any formula, if 0 is in X and n is in X implies that n+1 is in X for all n, then n is in X for all n.") How is this possible? Because you can never make a recursive axiom system that fully captures second-order logic. In other words, you can never make a computer program that can find all the consequences of the second-order Peano axioms.

 

[lugita15]

Another technique is to form equivalence classes for both even and odd numbers and then show that these classes partition all numbers and cover the set.

Your approach is basically the same as CompuChip's. The question becomes, how do you know that there are only two equivalence classes modulo 2, i.e. how do you know that ever natural number leaves a remainder of 0 or 1 when divided by 2? What if it leaves a remainder r ≥ 2? You may say "then r-2 will be less than 2." But what if it's not? What if you keep subtracting 2 forever, i.e. you do r-2, r-4, r-6, etc., but you never get it under 2? You may say "that's impossible, because you can't have an infinite descending sequence of natural numbers", but that assumption is equivalent to induction.

 

[verty]

I've been following this post because I too fell into the trap CompuChip got into. [Luckily I was able to delete my post when I realized I was making a logical fallacy.] Since I am no expert on number theory or "Robinson arithmetic" (first time I've heard of that), I am not sure if verty's answer makes sense but I believe it must be making a similar logical error.

To me, it seems obvious that in order to define natural numbers, you must have the axiom of induction [it is one of the Peano axioms]. If you are using some sort of alternative definition for a natural number in some sort of Robinson arithmetic, you must define what you mean by a natural number. In other words, without induction, you must be using some nonstandard definition of natural number. To be able to determine whether all natural numbers are "even" or "odd" (or any other property for that matter), we must first know what your definition of natural number is--and most people assume induction as an axiom for natural numbers.

A natural number is 1, or S(1), or S(S(1)), or S(S(S(1))), or..., a sequence of definitions. No induction needed.

 

[lugita15]

A natural number is 1, or S(1), or S(S(1)), or S(S(S(1))), or..., a sequence of definitions. No induction needed.

Actually, you're implicitly smuggling in assumptions with the "...". The "..." you're using is called the "ancestral". It's called that because it's a concept we use when we define the word ancestor: "your ancestor is your parent, or your parent's parent, or your parent's parent's parent, or ...". One way to define the "..." is by using numbers: you can say an ancestor is the nth iteration of the parent function for some natural number n. This works fine for ancestors, but obviously if you use it for natural numbers, it would be circular.

Your definition can be made precise in another way though: a hereditary set is a set that contains S(n) whenever it contains n. When you say a natural number is 1, or S(1), or S(S(1)), or ..., what the "..." really means is, "a natural number is something that belongs to all hereditary sets containing 1." (If you think about it enough, you'll find that it works. For instance, you should be able to see that the only real numbers that belong to all the hereditary sets containing 1 are the natural numbers.) But then things become tricky, because it depends on what "all sets" mean, and that depends on second-order logic. And as I explained to Jolb, there is no recursive axiom system that fully captures second-order logic, so a computer program could never figure out what is and isn't a valid chain of reasoning according to second-order logic.

So long story short, your definition doesn't really suffice to uniquely pick out the natural numbers, at least in a way that could be used to teach a computer what natural numbers are.