1
$\begingroup$

I have recently begun self studying Real Analysis 1 by Tao. Such proofs are new to me and the solutions are not provided in the book. That is why I'm asking this question. Any feedback is welcome, thank you very much for your time!

There are two other questions about this lemma on here. However, they both used symbolic logic and hence remain inaccessible to me.

Axiom 2.4: Different natural numbers must have different successors; i.e., if $n,m$ are natural numbers and $n≠m,$ then $n++≠m++.$ Equivalently, if $n++=m++,$ then we must have $n=m.$

Axiom 2.5: Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n)$ is true for every natural number $n.$

I am trying to prove:

Lemma 2.2.10: Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++=a.$

Proof: Let $P(n)$ be a property pertaining to a natural number $n.$ Assume that $P(0)$ is true and that $P(n)$ being true implies that $P(n++)$ is true. By axiom 2.5, $P(n)$ is true for all natural numbers $n.$ Assume that there exists a positive natural number $a$ such that $b++\not=a$ for any natural number $b.$ However, the existence of such a number would mean that $P(a)$ isn't necessarily true. This is a contradiction and hence there must exist a natural number $b$ such that $b++=a.$ Next, assume that $c$ is also a natural number such that $c++=a.$ Hence, $b++=c++.$ By axiom 2.4, this implies that $b=c.$ Consequently, there exists a unique natural number $b$ such that $b++=a$ for all positive natural numbers $a.$ $\square$

$\endgroup$
  • 3
    $\begingroup$ Does this answer your question? Proof Check Lemma 2.2.10 in Tao $\endgroup$ – Mauro ALLEGRANZA Feb 26 at 13:09
  • $\begingroup$ I read that discussion. However, the question does not prove existence. The first answer does attempt to prove existence but the second answer says that the first one is incomplete and uses symbolic logic (which I don't understand). I am more concerned about existence. Doesn't existence follow directly from the way induction is defined? Essentially, if some number didn't have a predecessor, then how does the property hold for that number? $\endgroup$ – TheGeometer Feb 27 at 2:06
  • $\begingroup$ But what is property $P$ in your proof? It seems that you haven't specified it. $\endgroup$ – Mauro ALLEGRANZA Feb 27 at 8:48
2
$\begingroup$

Long comment

Let $P(n)$ be a property pertaining to a natural number $n$. [...] Assume that there exists a positive natural number a such that $b++≠a$ for any natural number $b$. However, the existence of such a number would mean that $P(a)$ isn't necessarily true.

But you have only restated Induction axiom, without defining the property $P(n)$ to which apply it.

In order to apply Induction, we have to define a suitable property $P(n)$:

"if $n$ is positive, there is a number $b$ such that $n=b++$".

Base step: $a=0$.

According to Definition 2.2.7 (Positive natural numbers) $0$ is not positive. Thus, using Ex Falso Quodlibet we have:

"if $a=0$, then (if $a$ is positive, there is a number $b$ such that $a=b++$)".

The result ($P(0)$) follows by Modus ponens.

Induction step: assume that the property $P(n)$ defined above holds for $a$ and consider $a++$.

We have that: $a++=a++$ (law of equality; see Appendix.7 Equality, page 329). Thus,

"there is a number $b$ such that $a++=b++$"

holds. But then it holds also: "if $a++$ is positive, there is a number $b$ such that $a++=b++$", i.e. $P(a++)$.

Having proved $P(a++)$, we have also that "if $P(a)$, then $P(a++)$" holds.

Now we have all the ingredients needed for applying Axiom 2.5 (Principle of mathematical induction): we have proved $P(0)$ and we have proved that whenever $P(a)$ is true, $P(a++)$ is also true.

Then we can conclude that $P(a)$ is true for every natural number $a$, i.e. that:

"if $a$ is positive, there is a number $b$ such that $a=b++$".


The previous result grabs the key role of Induction: every natural number is "achievable" starting from $0$ and applying the successor operation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, that helped! I just have 2 questions about it. 1) For the base case, is your reasoning similar to the following? Let's say that we want to show that the empty set is a subset of an arbitrary set $A$. The requirement for it to be a subset is that every element in the empty set must also be an element of $A.$ However, there are no elements in the empty set so all the elements in the empty set are in $A$ and hence it is a subset of A. 2) Why do I have to specify some property $P,$ can't I just let $P$ be some property? $\endgroup$ – TheGeometer Feb 29 at 21:41
  • 1
    $\begingroup$ @TheGeometer - to 1) Yes. "if not-($x \in \emptyset$), then (if $x \in \emptyset$, then Q)", for a formula Q whatever is valid, and thus, due to the fact that "not-($x \in \emptyset$)" holds, we conclude by Modus Ponens. $\endgroup$ – Mauro ALLEGRANZA Mar 1 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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