Proving Properties of Natural Numbers Watch

Announcements

Everything you need to know about applying to uni through Clearing >>

Applying to uni? Find your uni group chat here >>

LogicGoat

Badges: 8

Rep:

Report Thread starter 5 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 5 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 5 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 5 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 5 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 5 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 5 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 5 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 5 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

LogicGoat

Badges: 8

Rep:

#10

Report Thread starter 5 years ago

#10

Anyone willing to look at these proofs and comment? :puppyeyes:

start new discussion

Page 1 of 1

Go to first unread

Quick Reply

Submit reply

Attached files

Replying is easier on our app - Click here to download for FREE!

Write a reply...

new posts

University open days

Manchester Metropolitan University

Undergraduate Open Day Undergraduate

Wed, 19 Jun '19

find out more
University of West London

Undergraduate Open Day - West London Campus Undergraduate

Wed, 19 Jun '19

find out more
University of Warwick

Undergraduate Open Day Undergraduate

Fri, 21 Jun '19

find out more

Poll

Join the discussion

How did your AQA A-level Biology Paper 3 go?

Loved the paper - Feeling positive (241)

14.86%

The paper was reasonable (905)

55.8%

Not feeling great about that exam... (356)

21.95%

It was TERRIBLE (120)

7.4%

Quick Reply

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room

Today on TSR

University open days

Poll

How did your AQA A-level Biology Paper 3 go?

Watched Threads

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room

TSR Support Team

Get Started

Using TSR

Info

TSR Group

Connect with TSR

Proving Properties of Natural Numbers Watch

Not what you're looking for? Try…

Quick Reply

Related discussions

Related articles

Related university courses

Oops, nobody has postedin the last few hours.

Oops, nobody is replying to posts.

See more of what you like onThe Student Room

Today on TSR

University open days

Poll

How did your AQA A-level Biology Paper 3 go?

Watched Threads

Spotlight

Oops, nobody has postedin the last few hours.

Oops, nobody is replying to posts.

See more of what you like onThe Student Room

TSR Support Team

Get Started

Using TSR

Info

TSR Group

Connect with TSR

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room