Proving Properties of Natural Numbers

Watch this thread

Announcements

Stuck between two unis for your firm and insurance choice? Get help here! >>

start new discussion reply

Page 1 of 1

Go to first unread

Skip to page:

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Hi Guys

Basically, I'm working through the Analysis I Textbook by Terence Tao. For those who aren't familiar with it, basically it begins by starting with the Peano axioms and using these to deduce other properties of the natural numbers. I believe the idea is to get used to handling proofs by first proving things which seem obvious so that we can handle proving results in analysis which won't seem so obvious.

So, anyway, enough of my rambling. I was wondering if anyone could assist me in proving these statements and also advise whether I'm structuring my proofs in the correct way.

Below are the axioms, propositions, lemmas, etc. which we may assume:

Spoiler:

Show

Below are the exercises:

Spoiler:

Show

I'll include my working on each exercise in a different post to avoid crowding this one out

Thanks for your time

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Exercise 2.2.1

Let

be the proposition that

for all natural numbers

$\begin{array}{rlll} (0 + b) + c & = & b + c & \text{ because } 0 + b = b \text{ by definition 2.2.1} \\ & = & 0 + (b + c) & \text{ by definition 2.2.1} \end{array}$
Therefore P(0) is true.

$\begin{array}{rlll} ( (a++) + b) + c) & = & ((a+b)++) + c & \text{ by definition 2.2.1} \\ & = & ((a + b) + c)++ & \text{ by definition 2.2.1} \\ & = & (a + (b + c))++ & \text{ supposing that P(a) is true} \\ & = & (a++) + (b + c) & \text{ by definition 2.2.1} \end{array}$
Which is P(a++)

Therefore by the principle of mathematical induction (axiom 2.5), P(a) is true for all natural numbers, a.

---

Is this a valid structure for a proof?

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

I'm not sure how to approach exercise 2.2.2

I know it says to use induction but I'm not sure on what, a or b? :confused:

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Exercise 2.2.3. a)

$a \geq a$ iff

, for some natural number n.

by lemma 2.2.2 and 0 is a natural number according to axiom 2.1.

Therefore $a \geq a$ . QED

Is this a valid structure?

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Exercise 2.2.3 b

$a \geq b$ iff

, for some natural number

(definition 2.2.11)

and $b \geq c$ iff

, for some natural number

(definition 2.2.11)

Therefore,
$\begin{array}{rlll} a & = & (c + m) + n & \\ & = & c + (m + n) & \text{ because addition is associative (proposition 2.2.5)} \end{array}$

So

has the form

where

is some natural number

Therefore it follows that $a \geq c$ from definition 2.2.11

QED.

Is this ok?

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Exercise 2.2.3 c

$a \geq b$ iff

for some natural number n

$b \geq b$ iff

for some natural number m

Therefore, $a \geq b$ and $b \geq a$ iff $\begin{array}{rlll} a & = & (a + m) + n & \\ & = & = a + (m + n) & \text{ because addition is associative (Proposition 2.2.5)} \end{array}$
iff

because of the cancellation law (proposition 2.2.6)
iff m = 0 and n = 0 by corollary 2.2.9

Therefore

by lemma 2.2.2 and

by lemma 2.2.2

QED

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Exercise 2.2.3 d

$a \geq b$ iff

for some natural number

iff
$\begin{array}{rll} a + c & = & (b + n) + c \\ & = & (b + c) + n \end{array}$
because addition is commutative and associative (propositions 2.2.4 and 2.2.5)

Therefore, it follows that, $a + c \geq b + c$ by definition 2.2.11

QED

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Exercise 2.2.3 e

iff

for some natural number n and $b \neq a$

$b \neq a$ implies $n \neq 0$ because

lemma 2.2.2

So we can write,

for some natural number m (I'm not sure if I've justified this enough?)

$\begin{array}{rlll} b & = & a + (m++) & \\ & = & (a + m)++ & \text{ by lemma 2.2.3} \\ & = & (a++) + m & \text{ by definition 2.2.1} \end{array}$

iff $a++ \leq b$ by definition 2.2.11

QED

LogicGoat

Badges: 8

Rep:

Report Thread starter 8 years ago

Exercise 2.2.4

This is the proof provided by the book:

Spoiler:

Show

$0 \leq b$ iff

for some natural number n (from definition 2.2.11)

by definition 2.2.1
and we know that b is a natural number therefore $0 \leq b$ for all natural numbers

QED
(is this ok, or would I need to use induction?)

iff

and $a \neq b$

iff

(I'm not sure if this step is actually justified? Since axiom 2.4 just says n++ = m++ => n=m, not the other way around)

by lemma 2.2.3
axiom says if n is a natural number then so is n++ so

for some natural number m
iff $a++ \geq b$

Axiom 2.3 says 0 is not the successor of any natural number and since we know

this means $m \neq 0$
iff $a++ \neq b + 0$
iff $a++ \neq b$ by lemma 2.2.2

So if $a++ \geq b$ and $a++ \neq b$ then

QED

iff

by lemma 2.2.2
iff

by definition 2.2.1
iff

by lemma 2.2.3
iff

(by definition 2.1.3)
iff $a++ \geq b$ by definition 2.2.11

suppose that

iff

by the cancellation law (proposition 2.2.6)
but

and axiom 2.3 says that 0 is not the successor of any natural numbers
therefore $1 \neq 0$
so $b +1 \neq b$
so $a++ \neq b$

We have $a++ \geq b$ and $a++ \neq b$
therefore

definition 2.2.11

QED