Proving Properties of Natural Numbers Watch

LogicGoat
Badges: 8
Rep:
?
#1
Report Thread starter 5 years ago
#1
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
0
reply
LogicGoat
Badges: 8
Rep:
?
#2
Report Thread starter 5 years ago
#2
Exercise 2.2.1

Let P(a) be the proposition that (a +b) + c = a + (b + c) for all natural numbers a

\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?
0
reply
LogicGoat
Badges: 8
Rep:
?
#3
Report Thread starter 5 years ago
#3
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:
0
reply
LogicGoat
Badges: 8
Rep:
?
#4
Report Thread starter 5 years ago
#4
Exercise 2.2.3. a)

a \geq a iff a = a + n, for some natural number n.

a = a + 0 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?
0
reply
LogicGoat
Badges: 8
Rep:
?
#5
Report Thread starter 5 years ago
#5
Exercise 2.2.3 b

a \geq b iff a = b + n, for some natural number n (definition 2.2.11)

and b \geq c iff b = c + m, for some natural number m (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 a has the form a = c + k where k is some natural number k= m + n

Therefore it follows that a \geq c from definition 2.2.11

QED.

Is this ok?
0
reply
LogicGoat
Badges: 8
Rep:
?
#6
Report Thread starter 5 years ago
#6
Exercise 2.2.3 c

a \geq b iff a = b + n for some natural number n

b \geq b iff b = a +m 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 m + n = 0 because of the cancellation law (proposition 2.2.6)
iff m = 0 and n = 0 by corollary 2.2.9

Therefore a = b + 0 = b by lemma 2.2.2 and b = a + 0 = a by lemma 2.2.2

QED
0
reply
LogicGoat
Badges: 8
Rep:
?
#7
Report Thread starter 5 years ago
#7
Exercise 2.2.3 d

 a \geq b iff a = b + n for some natural number n
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
0
reply
LogicGoat
Badges: 8
Rep:
?
#8
Report Thread starter 5 years ago
#8
Exercise 2.2.3 e

a < b iff  b = a + n for some natural number n and b \neq a

b \neq a implies n \neq 0 because a + 0 = a lemma 2.2.2

So we can write, b = a + (m++) 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
0
reply
LogicGoat
Badges: 8
Rep:
?
#9
Report Thread starter 5 years ago
#9
Exercise 2.2.4

This is the proof provided by the book:
Spoiler:
Show


0 \leq b iff b = 0 + n for some natural number n (from definition 2.2.11)
b = n by definition 2.2.1
and we know that b is a natural number therefore 0 \leq b for all natural numbers b QED
(is this ok, or would I need to use induction?)

a > b iff a = b + n and a \neq b

iff a++ = (b+n)++
(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)
a++ = b + (n++) by lemma 2.2.3
axiom says if n is a natural number then so is n++ so
a++ = b + m 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 m = n++
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 a++ > b QED

a = b iff a++ = b++
iff a++ = (b++) + 0 by lemma 2.2.2
iff a++ = (b + 0)++ by definition 2.2.1
iff a++ = b + (0++) by lemma 2.2.3
iff a++ = b + 1 (by definition 2.1.3)
iff a++ \geq b by definition 2.2.11

suppose that b + 1 = b
iff 1 = 0 by the cancellation law (proposition 2.2.6)
but 1 = 0++ 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 a++ > b definition 2.2.11

QED
0
reply
LogicGoat
Badges: 8
Rep:
?
#10
Report Thread starter 5 years ago
#10
:bump:

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

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • Manchester Metropolitan University
    Undergraduate Open Day Undergraduate
    Wed, 19 Jun '19
  • University of West London
    Undergraduate Open Day - West London Campus Undergraduate
    Wed, 19 Jun '19
  • University of Warwick
    Undergraduate Open Day Undergraduate
    Fri, 21 Jun '19

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%

Watched Threads

View All