Prove that every natural number is either even or odd.

[ruip]

Hello,

I'm re-studying calculus using Spivak's Calculus 4ed and I'm stuck in one of the problems. Any help is appreciated.

Homework Statement

The theorem to prove is "every natural number is either even or odd".

The definition of even given by Spivak is the following: A natural number n is even if there exists an integer k such that n = 2k. Similarly, for an odd natural number n, there exists an integer k such that 2 = 2k+1.

I can also use the basic facts about natural numbers and integers, such as associativity, commutativity, existence of identity, and distributivity.

The other property of the natural numbers I can use is the principle of mathematical induction.

2. The attempt at a solution

First, my understanding of the "either or" is that I must prove that every natural n is even or odd _and not both_. A general argument by induction will look like:

• The number 1 is odd because there exists a k = 0, such that 2*0 + 1 = 1
• Suppose n is either even or odd. If even then there exists a k such that n = 2k, and n+1 = 2k+1 and so, n+1 is odd. The case for n odd is similar. And so, if n is even or odd, then n+1 is even or odd.

By the principle of mathematical induction, all natural numbers are even or odd.

The problem (one of the problems?) with this proof is that I don't show that a natural number can't be even and odd at the same time.

I can't even start to show that 1 is not even. I need to prove that there are no integer k such that 1 = 2k. I understand that the only "number" that satisfy the equation is 1/2 and 1/2 is not an integer, but I can't state that in a proof with the principles that were given.

Any help? :)

Thanks!

 

[Office_Shredder]

Are you allowed to use inequality properties? For example if a>b and c>0 then ac>bc. Then i 2k>2 if k is a positive integer (and if k is negative 2k<0)

 

[ruip]

Yes, I can use inequality properties: a number n is positive, n = 0, or -n is positive; if n and m are positive then n+m and n*m are also positive. The example you give was proved from the previous properties and so I can use that and similar properties too.

Following your example with the 2k>2, let me try to use it.

So, to show that 1 is not even, I assume that if 1 is even then there exists a k such that 2k = 1. Now I have three cases:
a) If k = 0, then 2k = 0 (already proven) and 0 ≠ 1 and so I get a contradiction.
b) if k > 0, then 2k > 2 and 2 > 1, so 2k> 1, and so 2k ≠ 1.
c) if k < 0, similar to the previous case.
By contradiction, there is no integer k such that 2k = 1, and so 1 is not even.

Is this correct?

EDIT: this doesn't seem correct. I can't show that if k > 0, then 2k > 2.

Now I'm not sure if showing that 1 is odd and not even is enough to prove the general case. In the induction step, I'm assuming that n is either even or odd. When even, I show that n+1 is odd but I don't prove that n+1 is not even.

 

[I like Serena]

Assume there is a number x that is both even and odd.

So there must be a k with x=2k, and also an m with x=2m+1.
That is, 2k=2m+1

Can you rewrite this?
And use inequalities?
(No induction necessary.)

 

[ruip]

I can rewrite it as 2(k-m) = 1 and make a similar argument as in the post above.

If k-m = 0, then 2(k-m) = 0
if k-m < 0, then 2(k-m) < 0
The problem is with k-m > 0. 2(k-m) > 0 and 1 > 0 so everything looks fine and I don't get a contradiction. I'm missing something. :\

 

[Office_Shredder]

EDIT: this doesn't seem correct. I can't show that if k > 0, then 2k > 2.

k isn't just positive, it's also an integer, so k>=1.

EDIT: Similar argument finishes up what you want in your previous post

 

[ruip]

k isn't just positive, it's also an integer, so k>=1.

EDIT: Similar argument finishes up what you want in your previous post

Sorry, but I don't know how to prove that if k > 0 and k is an integer, then k >= 1. I don't see how can I show that there aren't integers between 0 and 1.

 

[I like Serena]

What kind of definition do you have for an inequality?
And how are your whole numbers defined?

I expect something like x < x + 1 for any x.
And that the whole numbers are 1 plus a repeated number of additions of 1, combined with 1 plus a repeated number of subtractions of 1.

This means that any number is less than x, equal to x, equal to x+1, or greater than x+1.
So there is no number between x and x+1.

 

[ruip]

Hello,

I have the following three basic properties regarding inequalities:
1. Trichotomy law. For every number a, one and only one of the following holds:

• a = 0
• a is in collection of positive numbers P
• -a is in collection of positive numbers P

2. If a and b are in P, then a + b is in P
3. If a and b are in P, then a * b is in P

The "a > b" is defined as "a - b in P".

I have no additional information about the "construction" of numbers, only the basic properties they respect. If I understood your question correctly, the numbers aren't defined starting with 1 and then adding 1's like in natural numbers. I don't think numbers are defined beyond the properties they respect.

Besides the three properties above, I have:
a + (b + c) = (a + b) + c
a + b = b + a
a + 0 = a
a + (-a) = 0 (this one doesn't apply to natural numbers)
a*(b*c) = (a*b)*c
a*b = b*a
a*1 = a
1 ≠ 0
a*a^-1 = 1 for a ≠ 0 (this property doesn't apply to integers, obviously).
a(b + c) = ab + ac

I also have the principle of mathematical induction/well-ordering principle for natural numbers and that's it.

EDIT: removed comment about my whole numbers.

 

[I like Serena]

Your definitions allow real numbers.
But the term "natural number" means that it is a whole number,which is not negative (and may be zero depending on your definition).

Now I'm confused.
Are we talking real numbers, whole numbers, or natural numbers?
When you mentioned well-ordering you were again talking about natural numbers and your problem statement also refers consistently to natural numbers...

 

[ruip]

Sorry, I misunderstood you when you said "whole numbers". You were referring to the integers. Ignore my comment "My "whole numbers" are the real numbers and so," and consider the rest. I remove that from the previous post.

 

[I like Serena]

Sorry, I referred to whole numbers (integers) and gave a definition for that, when I should have defined the natural numbers.

Just to be clear, should we ignore every reference to the word "natural" in your problem statement, and just read "number" wherever it says "natural number"?
Or else, what is your definition of a natural number?

 

[ruip]

Just to be clear, should we ignore every reference to the word "natural" in your problem statement, and just read "number" wherever it says "natural number"?

No, in fact the problem is about natural numbers. Prove that a natural number is either even or odd. Sorry about the confusion. I have no definition for natural number besides the properties they respect.

Quoting Spivak
"The simplest numbers are the "counting numbers"
1,2,3,...
The fundamental significance of this collection of numbers is emphasized by its
symbol N (for natural numbers). A brief glance at P1-P12 will show that our
basic properties of "numbers" do not apply to N—for example, P2 and P3 do not
make sense for N. From this point of view the system N has many deficiencies."

The properties P1-P12 are the ones I gave above. P2 and P3 are specifically the 0 identity (since the naturals are defined in this book starting with 1) and the -a inverse existence.

 

[I like Serena]

Well, I don't have Spivak, but if I understand correctly he defines the natural numbers as the numbers 1,2,3,...
In particular that is 1, and counting up by adding 1 every time (although he doesn't explicitly say so).

In particular the trichotomy law is not entirely well defined in this case, since -a is not defined for natural numbers.
And also your definition of "a > b" is not well defined, since a-b does not exist within the natural numbers.

 

[ruip]

Well, I don't have Spivak, but if I understand correctly he defines the natural numbers as the numbers 1,2,3,...
In particular that is 1, and counting up by adding 1 every time (although he doesn't explicitly say so).

In particular the trichotomy law does not hold, since -a is not defined for natural numbers.
And also you definition of "a > b" is not well defined, since a-b does not exist within the natural numbers.

I guess you are right. But I must add that the even definition talks about integer numbers also, namely, a natural number n is even if there exists _an integer k_ so that n = 2k. So I think I can use the trichotomy law for the integer 'k' in this definition. Maybe this isn't enough anyway.

 

[I like Serena]

It's enough as far as I'm concerned.

To get back to your problem (now that the definition stuff is out of the way), I believe the last thing you needed is that if k-m>0, that then also k-m≥1...

 

[ruip]

It's enough as far as I'm concerned.

To get back to your problem (now that the definition stuff is out of the way), I believe the last thing you needed is that if k-m>0, that then also k-m≥1...

Let me restate the argument from the beginning. If an integer n is even then there is an integer k so that n = 2k. Also, if n is odd then there is an integer m so that n = 2m+1.

Now, if that is true then 2k = 2m+1 and so 2(k-m) = 1.

When (k-m)<= 0, I can easily get a contradiction.
When (k-m) > 0 and (k-m) being an integer, let me assume for now that k-m >= 1 (I don't know how to prove this yet).
If (k-m) ≥ 1 then 2(k-m) ≥ 2 and 2 > 1 so 2(k-m) > 1 and so 2(k-m) ≠ 1. By contradiction, a number n can't be even and odd.

I believe this is correct but I can't see how to get the "if k-m>0 and (k-m) is an integer, then (k-m)≥1".

 

[I like Serena]

Good! :)

What you need is that ...<-1<0<1<2<3<...
From this inequality it follows that there can be no integers between 0 and 1.

Can you proof that?

 

[ruip]

Well, for any number a, if a is positive then a*a > 0 (by definition).
Also if a < 0, then (-a) > 0 and (-a)*(-a) > 0. Since (-a)(-a) = a*a[1], then a*a > 0.

So, for any number a ≠ 0, a² > 0, and in particular 1² = 1 > 0.

Given that 1 > 0, then -1 < 0. Also 1 + 1 > 0 + 1, that is 2 > 1. Also 1 - 1 > 0 - 1, and so 0 > -1.
And so ... < -1 < 0 < 1 < 2 < ...

From here I don't see how can we conclude that there aren't any integers between 0 and 1. Any hints?

--

[1] For any numbers a, b
ab + a(-b) = a(b + -b) = a*0 = 0
ab + a(-b) = 0
-(ab) + ab + a(-b) = -(ab)
a(-b) = -(ab)

And also, for any numbers a, b

(-a)(-b) + a(-b) = (-a + a)(-b) = 0(-b) = 0
(-a)(-b) + -ab = 0 (using previous result)
(-a)(-b) + (-ab) + ab = ab
(-a)(-b) = ab

 

[I like Serena]

You've lost me there.

You wrote: "a > b" is defined as "a - b in P".

So where do all your products factor in?
There's only addition (actually subtraction) involved as far as I can tell.

Let's start with x+1>x (for any integer x).
Can you proof that?

 

[ruip]

You've lost me there.

You wrote: "a > b" is defined as "a - b in P".

So where do all your products factor in?

One of the properties I gave was "if a and b in P, then a*b is also in P", and so if a*a in P for any a ≠ 0 (as shown in previous post), then a*a - 0 is in P, and by definition a*a > 0. Since 1*1 = 1 and 1*1 > 0 then 1 > 0.

There's only addition (actually subtraction) involved as far as I can tell.

Let's start with x+1>x (for any integer x).
Can you proof that?

To prove this I depend on the fact that 1 > 0 as proved previously.

Considering that 1 > 0, that is 1 - 0 in P, then
(1 - 0) + 0 in P
(1 - 0) + (x + -x) in P, and so
(1 + x) - (x + 0) is in P
1 + x > x

 

[I like Serena]

Okay.
That looks correct.

Let me give a shorter version.
We have: "a > b" is defined as "a - b in P".

Now fill in a=x+1, and b=x, then we get:
(x+1)-x=-x + (x+1)=(-x+x)+1=0+1=1, which is in P.
So x+1 > x.

In particular we have 0<1.
How about other numbers?
Say we pick a number y.
What are the possibilities relative to 0 and 1?

Note that ">" has a transitive property.
Oh wait. You did not mention the properties of an inequality yet...

 

[ruip]

Okay.
That looks correct.

Let me give a shorter version.
We have: "a > b" is defined as "a - b in P".

Now fill in a=x+1, and b=x, then we get:
(x+1)-x=-x + (x+1)=(-x+x)+1=0+1=1, which is in P.
So x+1 > x.

In particular we have 0<1.

Sorry, but I don't understand how is this "shorter". It looks exactly the same, since you depend on the fact that 1 is in P to conclude that (x+1)-x = 1 is in P.

Since 1 in P is the same as 1-0 in P, that is 1 > 0, then we need to prove first that 1 > 0.

The way you wrote it, looks like that you started with (x + 1) - x in P and than concluded as a specific case that 1 in P. Maybe I misunderstood it?

How about other numbers?
Say we pick a number y.
What are the possibilities relative to 0 and 1?

Note that ">" has a transitive property.
Oh wait. You did not mention the properties of an inequality yet...

Anyway, regarding transitivity of the >, I can say the following.

If a-b in P and b-c in P, then (a-b) + (b-c) in P, and therefore (a-c) in P.

And I still don't get it. Don't know what to say about any number y. A number y could be equal to 0, 1, 0 < y < 1, above 1, or below 0.

I'm a little lost in all this, but I'm trying to follow your reasoning (and having some fun doing it!). More hints please? :)

 

[I like Serena]

Sorry, but I don't understand how is this "shorter". It looks exactly the same, since you depend on the fact that 1 is in P to conclude that (x+1)-x = 1 is in P.

Since 1 in P is the same as 1-0 in P, that is 1 > 0, then we need to prove first that 1 > 0.

The way you wrote it, looks like that you started with (x + 1) - x in P and than concluded as a specific case that 1 in P. Maybe I misunderstood it?

If I understood you correctly the definition of "a>b" is based on the set P.
I am assuming that all natural numbers are in the set P.

You seem to use ">" to deduce that a number is in P, but that would be a circular argument.

Anyway, regarding transitivity of the >, I can say the following.

If a-b in P and b-c in P, then (a-b) + (b-c) in P, and therefore (a-c) in P.

And I still don't get it. Don't know what to say about any number y. A number y could be equal to 0, 1, 0 < y < 1, above 1, or below 0.

I'm a little lost in all this, but I'm trying to follow your reasoning (and having some fun doing it!). More hints please? :)

I believe we decided that the natural numbers consist of 1 and multiple addititions of 1 to it.
Did we?

If we did than 1<1+1<1+1+1<...
Any natural number y must be one of these numbers.
By transitivity, y is either 1,2, or a bigger number.
In particular it cannot be a number between 1 and 2, because it has to be one of these other numbers.

 

[jgens]

If you really want a definition of the natural numbers and integers in [itex]\mathbb{R}[/itex], then this definition is adequate: Define a set [itex]A[/itex] to be inductive if and only if [itex]1 \in A[/itex] and [itex]k+1 \in A[/itex] whenever [itex]k \in A[/itex]. Let [itex]\mathbb{N}[/itex] be the intersection of every inductive subset of [itex]\mathbb{R}[/itex] and let [itex]\mathbb{Z} = \mathbb{N} \cup \{0\} \cup -\mathbb{N}[/itex]. You will have to go through some work to show that these sets have the desired properties, but if you are insistent on a definition of [itex]\mathbb{N}[/itex], then this suffices.

 

[Office_Shredder]

You don't even really need to know how the natural numbers are defined as long as you know the property of induction works on them to solve this problem. Clearly 1>=1, and we proved that if x>=1, x+1>=1.

 

[ruip]

If I understood you correctly the definition of "a>b" is based on the set P.
I am assuming that all natural numbers are in the set P.

You seem to use ">" to deduce that a number is in P, but that would be a circular argument.

The set P is the set of positive numbers but , from the given properties, the only information we have about P is the trichotomy law, the close of addition over P, and the close of multiplication over P. I understand now that you assumed that 1 is in P but in reality that must be proved first. Only then I can say that 1 > 0. After this, we can conclude that 1+1 is in P, 1+1+1 is in P, etc.

I didn't use ">" to deduce anything. In fact, as defined, "a>b" is just syntax for "a-b in P".

I believe we decided that the natural numbers consist of 1 and multiple addititions of 1 to it.
Did we?

If we did than 1<1+1<1+1+1<...
Any natural number y must be one of these numbers.
By transitivity, y is either 1,2, or a bigger number.
In particular it cannot be a number between 1 and 2, because it has to be one of these other numbers.

Ah! I think I have a way to say that formally but I'm not sure. I'll try it.

Since we want to show that 2(k-m) ≠ 1 when (k-m) > 0 and (k-m) is an integer let me consider the set A = {p in N: 2p = 1}, using p = (k-m).

If A is not empty then A has a minimum element x so that 2x = 1 (by the well ordering principle).

The minimum x isn't 1 because 2*1 = 2 ≠ 1, and so x > 1.
Since x > 1, then 2x > 2 and 2 > 1, therefore 2x > 1 and so 2x ≠ 1. Since we want a minimum 2x = 1 but 2x > 1, by contradiction, the set A is empty and so there is no natural p so that 2p = 1.

I'm not entirely convinced but this doesn't look that bad. What do you think?

EDIT: I saw the other answers to use induction. Thanks. I guess I'm not that far away, but my current proof is a mess. :)

 

[ruip]

If you really want a definition of the natural numbers and integers in [itex]\mathbb{R}[/itex], then this definition is adequate: Define a set [itex]A[/itex] to be inductive if and only if [itex]1 \in A[/itex] and [itex]k+1 \in A[/itex] whenever [itex]k \in A[/itex]. Let [itex]\mathbb{N}[/itex] be the intersection of every inductive subset of [itex]\mathbb{R}[/itex] and let [itex]\mathbb{Z} = \mathbb{N} \cup \{0\} \cup -\mathbb{N}[/itex]. You will have to go through some work to show that these sets have the desired properties, but if you are insistent on a definition of [itex]\mathbb{N}[/itex], then this suffices.

That's problem 25 of chapter 2. I'll try to do that one too. :)