Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've run into a small problem while working through Enderton's Elements of Set Theory. I'm doing the following problem:

Call a natural number even if it has the form $2\cdot m$ for some $m$. Call it odd if it has the form $(2\cdot p)+1$ for some $p$. Show that each natural number number is either even or odd, but never both.

I've shown most of this, and along the way I've derived many of the results found in Arturo Magidin's great post on addition, so any of the theorems there may be used. It is the 'never both' part with which I'm having trouble. This is some of what I have:

Let $$ B=\{n\in\omega\ |\neg(\exists m(n=2\cdot m)\wedge\exists p(n=2\cdot p+1))\}, $$ the set of all natural numbers that are not both even and odd. Since $m\cdot 0=0$, $0$ is even. Also $0$ is not odd, for if $0=2\cdot p+1$, then $0=(2\cdot p)^+=\sigma(2\cdot p)$, but then $0\in\text{ran}\ \sigma$, contrary to the first Peano postulate. Hence $0\in B$. Suppose $k\in B$. Suppose $k$ is odd but not even, so $k=2\cdot p+1$ for some $p$. Earlier work of mine shows that $k^+$ is even. However, $k^+$ is not odd, for if $k^+=2\cdot m+1$ for some $m$, then since the successor function $\sigma$ is injective, we have $$ k^+=2\cdot m+1=(2\cdot m)^+\implies k=2\cdot m $$ contrary to the fact that $k$ is not even.

Now suppose $k$ is even, but not odd. I have been able to show that $k^+$ is odd, but I can't figure a way to show that $k^+$ is not even. I suppose it must be simple, but I'm just not seeing it. Could someone explain this little part? Thank you.

share|cite|improve this question
up vote 3 down vote accepted

HINT $\ $ Here's the inductive step: $\rm\ 2m \ne 2n+1\ \Rightarrow\ 2m+1 \ne 2(n+1)$

share|cite|improve this answer
@yunone: $\rm\ a^{+} = b^{+}\ \Rightarrow\ a = b\ $ is a Peano axiom. – Bill Dubuque Jan 10 '11 at 4:30
Sorry, my last comment was at the post before the edit. I believe I see now. So suppose $k=2m\neq 2n+1$. Then since $\sigma$ is injective, $k^+=(2m)^+\neq(2n+1)^+\Rightarrow k^+=2m+1\neq 2n+1^+=2n+2=2(n+1)$. So $k^+$ is odd, but not even. Thanks! – yunone Jan 10 '11 at 4:33

Suppose there exists some $n \in \mathbb{N}$ which is both even and odd. Then $n= 2m = 2p+1$. So $2m = 2p+1$ or $2(m-p) = 1$. Contradiction.

share|cite|improve this answer
I suspect he hasn't yet defined subtraction (or proved that addition is cancellable). – Bill Dubuque Jan 10 '11 at 4:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.