Mixing
Understanding and proving prop 2.1.16 in Tao's Analysis I concerning recursive definitions
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
Notes: Tao's axioms and original proposition statement and proof are given below. Similar questions have been asked here and here, but I was not able to resolve my issues. In particular, I have realized, it seems, there is a great deal of set theory going on "underneath the hood", and I find it rather conceptually and logically problematic that Tao introduces this proposition in a chapter before any set theory is even discussed. He remarks in a footnote how the proposition can be formulated more rigorously in the language of set theory, but he leaves that as the last exercise in a section in the chapter on set theory. This seems pretty sloppy to me, but I'm doing the best I can to follow what he's trying to communicate and the how/why of his proof. I found this blog post from Keith Devlin to be interesting but a little over my head. Is there any real good way to understand Tao's proposition without a thorough grounding in axiomatic set theory?
EDIT: I have reformulated my question as largely a request for people to comment on or critique my attempt at "a more fleshed out inductive proof." Since the proof is by induction, I'll try to outline my thoughts according to the typical way an induction proof works. Any comments as to where I am going wrong or what needs to be fixed would be greatly appreciated.
Proof attempt:
Base case: The procedure gives a single value to $a_0$, namely $c$. My understanding is that we basically assume a natural number $c$ exists due to Assumption 2.6, and we simply make the definition $a_0colon=c$. None of the other definitions $a_n++colon=f_n(a_n)$ will redefine the value of $a_0$ because the way in which a natural number $a_n$ is assigned to another natural number $n$ is by the assignment $a_n++colon=f_n(a_n)$ which involves the successor, and Axiom 2.3 tells us that $n++neq0$ for every natural number $n$. Hence, it's impossible to define (again) $a_0$ once the procedure has begun.
Inductive step: Suppose inductively that the procedure gives a single value to $a_n$. We want to show that a single value is then given to $a_n++$, namely $a_n++colon=f_n(a_n)$. We should first note that $a_n$ being single-valued is critical because $a_n++$ is going to be defined to be $a_n++colon=f_n(a_n)$, and it would not be sensible to start thinking about $a_n++$ being single-valued if $a_n++$ were defined in terms of a function whose argument was multi-valued (i.e., if $a_n$ were multi-valued, then we could reasonably expect $f_n(a_n)$ to return multiple distinct values as well). It may seem as though we can now safely rely on $a_n++$ being single-valued, but there is a concern we must address, namely the possibility that for a later natural number $m$ the corresponding definition $a_m++colon=f_m(a_m)$ could somehow cause $a_n++$ to be multi-valued. How?
If we came across an $m$ for which $n++=m++$ but $f_n(a_n)neq f_m(a_m)$, then we would have an issue because $n++=m++$ implies that $a_n++=a_m++$. Why would this be a problem? Well, with $a_n++colon= f_n(a_n)$ and $a_m++colon= f_m(a_m)$, we would have $a_n++=f_n(a_n),f_m(a_m)$ even though $f_n(a_n)neq f_m(a_m)$, indicating that $a_++$ would not have a single value assigned to it, as desired. How do we resolve this potential issue?
Suppose that later in the process we came across an $m$ corresponding to the definition $a_m++colon= f_m(a_m)$, where we also had $n++=m++$. Since $n++=m++$, it must be the case that $n=m$ by Axiom 2.4. Hence, we must also have $f_n(a_n)=f_m(a_m)$, thus showing that none of the other definitions $a_m++colon= f_m(a_m)$ will redefine the value of $a_n++$, and hence only a single value is assigned to $a_n++$.
This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
Content by Tao:
Axiom 2.1. $0$ is a natural number.
Axiom 2.2. If $n$ is a natural number, then $n++$ is also a natural number.
Axiom 2.3. $0$ is not the successor of any natural number ; i.e., we have $n++ ne 0$ for every natural number $n$.
Axiom 2.4. Different natural numbers must have different successors ; i.e., if $n, m$ are natural numbers and $n ne m$, then $n++ ne m++$. Equivalently, if $n++ = m++$, then we must have $n=m$.
Axiom 2.5. (Principle of mathematical induction). 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$.
Assumption 2.6. (Informal) There exists a number system $mathbbN$, whose elements we will call natural numbers, for which Axioms 2.1-2.5 are true.
Proposition 2.1.16 (Recursive definitions). Suppose for each natural number $n$, we have some function $f_n : mathbbN rightarrow mathbbN$ from the natural numbers to the natural numbers. Let $c$ be a natural number. Then we can assign a unique natural number $a_n$ to each natural number $n$, such that $a_0 = c$ and $a_n++ = f_n (a_n)$ for each natural number $n$.
Proof. (Informal) We use induction. We first observe that this procedure gives a single value to $a_0$, namely $c$. (None of the other definitions $a_n++:= f_n (a_n)$ will redefine the value of $a_0$, because of Axiom 2.3.) Now suppose inductively that the procedure gives a single value to $a_n$. Then it gives a single value to $a_n++$, namely $a_n++:= f_n (a_n)$. (None of the other definitions $a_m++:= f_m (a_m)$ will redefine the value of $a_n++$, because of Axiom 2.4.) This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
real-analysis elementary-set-theory logic induction peano-axioms
edited yesterday
Andrés E. Caicedo
63k7150235
asked yesterday
Jessica
264
 |Â
show 1 more comment
up vote
5
down vote
favorite
Notes: Tao's axioms and original proposition statement and proof are given below. Similar questions have been asked here and here, but I was not able to resolve my issues. In particular, I have realized, it seems, there is a great deal of set theory going on "underneath the hood", and I find it rather conceptually and logically problematic that Tao introduces this proposition in a chapter before any set theory is even discussed. He remarks in a footnote how the proposition can be formulated more rigorously in the language of set theory, but he leaves that as the last exercise in a section in the chapter on set theory. This seems pretty sloppy to me, but I'm doing the best I can to follow what he's trying to communicate and the how/why of his proof. I found this blog post from Keith Devlin to be interesting but a little over my head. Is there any real good way to understand Tao's proposition without a thorough grounding in axiomatic set theory?
EDIT: I have reformulated my question as largely a request for people to comment on or critique my attempt at "a more fleshed out inductive proof." Since the proof is by induction, I'll try to outline my thoughts according to the typical way an induction proof works. Any comments as to where I am going wrong or what needs to be fixed would be greatly appreciated.
Proof attempt:
Base case: The procedure gives a single value to $a_0$, namely $c$. My understanding is that we basically assume a natural number $c$ exists due to Assumption 2.6, and we simply make the definition $a_0colon=c$. None of the other definitions $a_n++colon=f_n(a_n)$ will redefine the value of $a_0$ because the way in which a natural number $a_n$ is assigned to another natural number $n$ is by the assignment $a_n++colon=f_n(a_n)$ which involves the successor, and Axiom 2.3 tells us that $n++neq0$ for every natural number $n$. Hence, it's impossible to define (again) $a_0$ once the procedure has begun.
Inductive step: Suppose inductively that the procedure gives a single value to $a_n$. We want to show that a single value is then given to $a_n++$, namely $a_n++colon=f_n(a_n)$. We should first note that $a_n$ being single-valued is critical because $a_n++$ is going to be defined to be $a_n++colon=f_n(a_n)$, and it would not be sensible to start thinking about $a_n++$ being single-valued if $a_n++$ were defined in terms of a function whose argument was multi-valued (i.e., if $a_n$ were multi-valued, then we could reasonably expect $f_n(a_n)$ to return multiple distinct values as well). It may seem as though we can now safely rely on $a_n++$ being single-valued, but there is a concern we must address, namely the possibility that for a later natural number $m$ the corresponding definition $a_m++colon=f_m(a_m)$ could somehow cause $a_n++$ to be multi-valued. How?
If we came across an $m$ for which $n++=m++$ but $f_n(a_n)neq f_m(a_m)$, then we would have an issue because $n++=m++$ implies that $a_n++=a_m++$. Why would this be a problem? Well, with $a_n++colon= f_n(a_n)$ and $a_m++colon= f_m(a_m)$, we would have $a_n++=f_n(a_n),f_m(a_m)$ even though $f_n(a_n)neq f_m(a_m)$, indicating that $a_++$ would not have a single value assigned to it, as desired. How do we resolve this potential issue?
Suppose that later in the process we came across an $m$ corresponding to the definition $a_m++colon= f_m(a_m)$, where we also had $n++=m++$. Since $n++=m++$, it must be the case that $n=m$ by Axiom 2.4. Hence, we must also have $f_n(a_n)=f_m(a_m)$, thus showing that none of the other definitions $a_m++colon= f_m(a_m)$ will redefine the value of $a_n++$, and hence only a single value is assigned to $a_n++$.
This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
Content by Tao:
Axiom 2.1. $0$ is a natural number.
Axiom 2.2. If $n$ is a natural number, then $n++$ is also a natural number.
Axiom 2.3. $0$ is not the successor of any natural number ; i.e., we have $n++ ne 0$ for every natural number $n$.
Axiom 2.4. Different natural numbers must have different successors ; i.e., if $n, m$ are natural numbers and $n ne m$, then $n++ ne m++$. Equivalently, if $n++ = m++$, then we must have $n=m$.
Axiom 2.5. (Principle of mathematical induction). 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$.
Assumption 2.6. (Informal) There exists a number system $mathbbN$, whose elements we will call natural numbers, for which Axioms 2.1-2.5 are true.
Proposition 2.1.16 (Recursive definitions). Suppose for each natural number $n$, we have some function $f_n : mathbbN rightarrow mathbbN$ from the natural numbers to the natural numbers. Let $c$ be a natural number. Then we can assign a unique natural number $a_n$ to each natural number $n$, such that $a_0 = c$ and $a_n++ = f_n (a_n)$ for each natural number $n$.
Proof. (Informal) We use induction. We first observe that this procedure gives a single value to $a_0$, namely $c$. (None of the other definitions $a_n++:= f_n (a_n)$ will redefine the value of $a_0$, because of Axiom 2.3.) Now suppose inductively that the procedure gives a single value to $a_n$. Then it gives a single value to $a_n++$, namely $a_n++:= f_n (a_n)$. (None of the other definitions $a_m++:= f_m (a_m)$ will redefine the value of $a_n++$, because of Axiom 2.4.) This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
real-analysis elementary-set-theory logic induction peano-axioms
edited yesterday
Andrés E. Caicedo
63k7150235
asked yesterday
Jessica
264
Tao's book is titled Analysis and not Set Theory: this is the reason why he do not spend many page regarding set theory topics and try to recap only the basic concepts and results needed in his exposition.
– Mauro ALLEGRANZA
yesterday
1
@MauroALLEGRANZA I get that Tao is concerned with analysis and not set theory proper, but it seems disjointed and inconsistent with some of his explicitly stated goals early on in the text, namely "We will try to introduce these concepts one at a time and identify explicitly what our assumptions are as we go along--and not allow ourselves to use more "advanced" tricks such as the rules of algebra until we have actually proven them" [p. 14]. It seems disjointed is all. Also, my question is now not identical to the linked questions, given my latest edit of actually trying to furnish a proof.
– Jessica
yesterday
Base case : Ok.
– Mauro ALLEGRANZA
yesterday
Inductive step: the i nitial discussion about multi-valued is superfluous: $f_n$ is a function and this it cannot have more than one-value for input $a_n$. This is slightly different with respect to : assuming that $a_n$ has been defined (and thus it is a single specific value) it is not possible that subsequently we can re-define it. This is waht you have discussed in thenext paragraphs, where we want to enusre that there is no $m$ for which $n++=m++$ but $f_n(a_n)≠f_m(a_m)$.
– Mauro ALLEGRANZA
yesterday
@MauroALLEGRANZA Thanks for the clarification! It's starting to make more sense now. Final question: where in your proof sketch do you explicitly use the inductive hypothesis $P(n)$ in proving that's $P(n++)$ follows? I'm so used to explicitly referencing how $P(n++)$ follows from $P(n)$ Andrew $P(0)$ that Iran throwing me off a bit. Is it simply the ability to even define $a_n++$, since it depends on $a_n$, that the inductive hypothesis is being explicitly used?
– Jessica
yesterday
 |Â
show 1 more comment
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Notes: Tao's axioms and original proposition statement and proof are given below. Similar questions have been asked here and here, but I was not able to resolve my issues. In particular, I have realized, it seems, there is a great deal of set theory going on "underneath the hood", and I find it rather conceptually and logically problematic that Tao introduces this proposition in a chapter before any set theory is even discussed. He remarks in a footnote how the proposition can be formulated more rigorously in the language of set theory, but he leaves that as the last exercise in a section in the chapter on set theory. This seems pretty sloppy to me, but I'm doing the best I can to follow what he's trying to communicate and the how/why of his proof. I found this blog post from Keith Devlin to be interesting but a little over my head. Is there any real good way to understand Tao's proposition without a thorough grounding in axiomatic set theory?
EDIT: I have reformulated my question as largely a request for people to comment on or critique my attempt at "a more fleshed out inductive proof." Since the proof is by induction, I'll try to outline my thoughts according to the typical way an induction proof works. Any comments as to where I am going wrong or what needs to be fixed would be greatly appreciated.
Proof attempt:
Base case: The procedure gives a single value to $a_0$, namely $c$. My understanding is that we basically assume a natural number $c$ exists due to Assumption 2.6, and we simply make the definition $a_0colon=c$. None of the other definitions $a_n++colon=f_n(a_n)$ will redefine the value of $a_0$ because the way in which a natural number $a_n$ is assigned to another natural number $n$ is by the assignment $a_n++colon=f_n(a_n)$ which involves the successor, and Axiom 2.3 tells us that $n++neq0$ for every natural number $n$. Hence, it's impossible to define (again) $a_0$ once the procedure has begun.
Inductive step: Suppose inductively that the procedure gives a single value to $a_n$. We want to show that a single value is then given to $a_n++$, namely $a_n++colon=f_n(a_n)$. We should first note that $a_n$ being single-valued is critical because $a_n++$ is going to be defined to be $a_n++colon=f_n(a_n)$, and it would not be sensible to start thinking about $a_n++$ being single-valued if $a_n++$ were defined in terms of a function whose argument was multi-valued (i.e., if $a_n$ were multi-valued, then we could reasonably expect $f_n(a_n)$ to return multiple distinct values as well). It may seem as though we can now safely rely on $a_n++$ being single-valued, but there is a concern we must address, namely the possibility that for a later natural number $m$ the corresponding definition $a_m++colon=f_m(a_m)$ could somehow cause $a_n++$ to be multi-valued. How?
If we came across an $m$ for which $n++=m++$ but $f_n(a_n)neq f_m(a_m)$, then we would have an issue because $n++=m++$ implies that $a_n++=a_m++$. Why would this be a problem? Well, with $a_n++colon= f_n(a_n)$ and $a_m++colon= f_m(a_m)$, we would have $a_n++=f_n(a_n),f_m(a_m)$ even though $f_n(a_n)neq f_m(a_m)$, indicating that $a_++$ would not have a single value assigned to it, as desired. How do we resolve this potential issue?
Suppose that later in the process we came across an $m$ corresponding to the definition $a_m++colon= f_m(a_m)$, where we also had $n++=m++$. Since $n++=m++$, it must be the case that $n=m$ by Axiom 2.4. Hence, we must also have $f_n(a_n)=f_m(a_m)$, thus showing that none of the other definitions $a_m++colon= f_m(a_m)$ will redefine the value of $a_n++$, and hence only a single value is assigned to $a_n++$.
This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
Content by Tao:
Axiom 2.1. $0$ is a natural number.
Axiom 2.2. If $n$ is a natural number, then $n++$ is also a natural number.
Axiom 2.3. $0$ is not the successor of any natural number ; i.e., we have $n++ ne 0$ for every natural number $n$.
Axiom 2.4. Different natural numbers must have different successors ; i.e., if $n, m$ are natural numbers and $n ne m$, then $n++ ne m++$. Equivalently, if $n++ = m++$, then we must have $n=m$.
Axiom 2.5. (Principle of mathematical induction). 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$.
Assumption 2.6. (Informal) There exists a number system $mathbbN$, whose elements we will call natural numbers, for which Axioms 2.1-2.5 are true.
Proposition 2.1.16 (Recursive definitions). Suppose for each natural number $n$, we have some function $f_n : mathbbN rightarrow mathbbN$ from the natural numbers to the natural numbers. Let $c$ be a natural number. Then we can assign a unique natural number $a_n$ to each natural number $n$, such that $a_0 = c$ and $a_n++ = f_n (a_n)$ for each natural number $n$.
Proof. (Informal) We use induction. We first observe that this procedure gives a single value to $a_0$, namely $c$. (None of the other definitions $a_n++:= f_n (a_n)$ will redefine the value of $a_0$, because of Axiom 2.3.) Now suppose inductively that the procedure gives a single value to $a_n$. Then it gives a single value to $a_n++$, namely $a_n++:= f_n (a_n)$. (None of the other definitions $a_m++:= f_m (a_m)$ will redefine the value of $a_n++$, because of Axiom 2.4.) This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
real-analysis elementary-set-theory logic induction peano-axioms
edited yesterday
Andrés E. Caicedo
63k7150235
asked yesterday
Jessica
264
Notes: Tao's axioms and original proposition statement and proof are given below. Similar questions have been asked here and here, but I was not able to resolve my issues. In particular, I have realized, it seems, there is a great deal of set theory going on "underneath the hood", and I find it rather conceptually and logically problematic that Tao introduces this proposition in a chapter before any set theory is even discussed. He remarks in a footnote how the proposition can be formulated more rigorously in the language of set theory, but he leaves that as the last exercise in a section in the chapter on set theory. This seems pretty sloppy to me, but I'm doing the best I can to follow what he's trying to communicate and the how/why of his proof. I found this blog post from Keith Devlin to be interesting but a little over my head. Is there any real good way to understand Tao's proposition without a thorough grounding in axiomatic set theory?
EDIT: I have reformulated my question as largely a request for people to comment on or critique my attempt at "a more fleshed out inductive proof." Since the proof is by induction, I'll try to outline my thoughts according to the typical way an induction proof works. Any comments as to where I am going wrong or what needs to be fixed would be greatly appreciated.
Proof attempt:
Base case: The procedure gives a single value to $a_0$, namely $c$. My understanding is that we basically assume a natural number $c$ exists due to Assumption 2.6, and we simply make the definition $a_0colon=c$. None of the other definitions $a_n++colon=f_n(a_n)$ will redefine the value of $a_0$ because the way in which a natural number $a_n$ is assigned to another natural number $n$ is by the assignment $a_n++colon=f_n(a_n)$ which involves the successor, and Axiom 2.3 tells us that $n++neq0$ for every natural number $n$. Hence, it's impossible to define (again) $a_0$ once the procedure has begun.
Inductive step: Suppose inductively that the procedure gives a single value to $a_n$. We want to show that a single value is then given to $a_n++$, namely $a_n++colon=f_n(a_n)$. We should first note that $a_n$ being single-valued is critical because $a_n++$ is going to be defined to be $a_n++colon=f_n(a_n)$, and it would not be sensible to start thinking about $a_n++$ being single-valued if $a_n++$ were defined in terms of a function whose argument was multi-valued (i.e., if $a_n$ were multi-valued, then we could reasonably expect $f_n(a_n)$ to return multiple distinct values as well). It may seem as though we can now safely rely on $a_n++$ being single-valued, but there is a concern we must address, namely the possibility that for a later natural number $m$ the corresponding definition $a_m++colon=f_m(a_m)$ could somehow cause $a_n++$ to be multi-valued. How?
If we came across an $m$ for which $n++=m++$ but $f_n(a_n)neq f_m(a_m)$, then we would have an issue because $n++=m++$ implies that $a_n++=a_m++$. Why would this be a problem? Well, with $a_n++colon= f_n(a_n)$ and $a_m++colon= f_m(a_m)$, we would have $a_n++=f_n(a_n),f_m(a_m)$ even though $f_n(a_n)neq f_m(a_m)$, indicating that $a_++$ would not have a single value assigned to it, as desired. How do we resolve this potential issue?
Suppose that later in the process we came across an $m$ corresponding to the definition $a_m++colon= f_m(a_m)$, where we also had $n++=m++$. Since $n++=m++$, it must be the case that $n=m$ by Axiom 2.4. Hence, we must also have $f_n(a_n)=f_m(a_m)$, thus showing that none of the other definitions $a_m++colon= f_m(a_m)$ will redefine the value of $a_n++$, and hence only a single value is assigned to $a_n++$.
This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
Content by Tao:
Axiom 2.1. $0$ is a natural number.
Axiom 2.2. If $n$ is a natural number, then $n++$ is also a natural number.
Axiom 2.3. $0$ is not the successor of any natural number ; i.e., we have $n++ ne 0$ for every natural number $n$.
Axiom 2.4. Different natural numbers must have different successors ; i.e., if $n, m$ are natural numbers and $n ne m$, then $n++ ne m++$. Equivalently, if $n++ = m++$, then we must have $n=m$.
Axiom 2.5. (Principle of mathematical induction). 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$.
Assumption 2.6. (Informal) There exists a number system $mathbbN$, whose elements we will call natural numbers, for which Axioms 2.1-2.5 are true.
Proposition 2.1.16 (Recursive definitions). Suppose for each natural number $n$, we have some function $f_n : mathbbN rightarrow mathbbN$ from the natural numbers to the natural numbers. Let $c$ be a natural number. Then we can assign a unique natural number $a_n$ to each natural number $n$, such that $a_0 = c$ and $a_n++ = f_n (a_n)$ for each natural number $n$.
Proof. (Informal) We use induction. We first observe that this procedure gives a single value to $a_0$, namely $c$. (None of the other definitions $a_n++:= f_n (a_n)$ will redefine the value of $a_0$, because of Axiom 2.3.) Now suppose inductively that the procedure gives a single value to $a_n$. Then it gives a single value to $a_n++$, namely $a_n++:= f_n (a_n)$. (None of the other definitions $a_m++:= f_m (a_m)$ will redefine the value of $a_n++$, because of Axiom 2.4.) This completes the induction, and so $a_n$ is defined for each natural number $n$, with a single value assigned to each $a_n$.
real-analysis elementary-set-theory logic induction peano-axioms
edited yesterday
Andrés E. Caicedo
63k7150235
asked yesterday
Jessica
264
edited yesterday
Andrés E. Caicedo
63k7150235
edited yesterday
Andrés E. Caicedo
63k7150235
edited yesterday
Andrés E. Caicedo
63k7150235
63k7150235
asked yesterday
Jessica
264
asked yesterday
Jessica
264
asked yesterday
Jessica
264
264
Tao's book is titled Analysis and not Set Theory: this is the reason why he do not spend many page regarding set theory topics and try to recap only the basic concepts and results needed in his exposition.
– Mauro ALLEGRANZA
yesterday
1
@MauroALLEGRANZA I get that Tao is concerned with analysis and not set theory proper, but it seems disjointed and inconsistent with some of his explicitly stated goals early on in the text, namely "We will try to introduce these concepts one at a time and identify explicitly what our assumptions are as we go along--and not allow ourselves to use more "advanced" tricks such as the rules of algebra until we have actually proven them" [p. 14]. It seems disjointed is all. Also, my question is now not identical to the linked questions, given my latest edit of actually trying to furnish a proof.
– Jessica
yesterday
Base case : Ok.
– Mauro ALLEGRANZA
yesterday
Inductive step: the i nitial discussion about multi-valued is superfluous: $f_n$ is a function and this it cannot have more than one-value for input $a_n$. This is slightly different with respect to : assuming that $a_n$ has been defined (and thus it is a single specific value) it is not possible that subsequently we can re-define it. This is waht you have discussed in thenext paragraphs, where we want to enusre that there is no $m$ for which $n++=m++$ but $f_n(a_n)≠f_m(a_m)$.
– Mauro ALLEGRANZA
yesterday
@MauroALLEGRANZA Thanks for the clarification! It's starting to make more sense now. Final question: where in your proof sketch do you explicitly use the inductive hypothesis $P(n)$ in proving that's $P(n++)$ follows? I'm so used to explicitly referencing how $P(n++)$ follows from $P(n)$ Andrew $P(0)$ that Iran throwing me off a bit. Is it simply the ability to even define $a_n++$, since it depends on $a_n$, that the inductive hypothesis is being explicitly used?
– Jessica
yesterday
 |Â
show 1 more comment
Tao's book is titled Analysis and not Set Theory: this is the reason why he do not spend many page regarding set theory topics and try to recap only the basic concepts and results needed in his exposition.
– Mauro ALLEGRANZA
yesterday
1
@MauroALLEGRANZA I get that Tao is concerned with analysis and not set theory proper, but it seems disjointed and inconsistent with some of his explicitly stated goals early on in the text, namely "We will try to introduce these concepts one at a time and identify explicitly what our assumptions are as we go along--and not allow ourselves to use more "advanced" tricks such as the rules of algebra until we have actually proven them" [p. 14]. It seems disjointed is all. Also, my question is now not identical to the linked questions, given my latest edit of actually trying to furnish a proof.
– Jessica
yesterday
Base case : Ok.
– Mauro ALLEGRANZA
yesterday
Inductive step: the i nitial discussion about multi-valued is superfluous: $f_n$ is a function and this it cannot have more than one-value for input $a_n$. This is slightly different with respect to : assuming that $a_n$ has been defined (and thus it is a single specific value) it is not possible that subsequently we can re-define it. This is waht you have discussed in thenext paragraphs, where we want to enusre that there is no $m$ for which $n++=m++$ but $f_n(a_n)≠f_m(a_m)$.
– Mauro ALLEGRANZA
yesterday
@MauroALLEGRANZA Thanks for the clarification! It's starting to make more sense now. Final question: where in your proof sketch do you explicitly use the inductive hypothesis $P(n)$ in proving that's $P(n++)$ follows? I'm so used to explicitly referencing how $P(n++)$ follows from $P(n)$ Andrew $P(0)$ that Iran throwing me off a bit. Is it simply the ability to even define $a_n++$, since it depends on $a_n$, that the inductive hypothesis is being explicitly used?
– Jessica
yesterday
Tao's book is titled Analysis and not Set Theory: this is the reason why he do not spend many page regarding set theory topics and try to recap only the basic concepts and results needed in his exposition.
– Mauro ALLEGRANZA
yesterday
Tao's book is titled Analysis and not Set Theory: this is the reason why he do not spend many page regarding set theory topics and try to recap only the basic concepts and results needed in his exposition.
– Mauro ALLEGRANZA
yesterday
1
1
@MauroALLEGRANZA I get that Tao is concerned with analysis and not set theory proper, but it seems disjointed and inconsistent with some of his explicitly stated goals early on in the text, namely "We will try to introduce these concepts one at a time and identify explicitly what our assumptions are as we go along--and not allow ourselves to use more "advanced" tricks such as the rules of algebra until we have actually proven them" [p. 14]. It seems disjointed is all. Also, my question is now not identical to the linked questions, given my latest edit of actually trying to furnish a proof.
– Jessica
yesterday
@MauroALLEGRANZA I get that Tao is concerned with analysis and not set theory proper, but it seems disjointed and inconsistent with some of his explicitly stated goals early on in the text, namely "We will try to introduce these concepts one at a time and identify explicitly what our assumptions are as we go along--and not allow ourselves to use more "advanced" tricks such as the rules of algebra until we have actually proven them" [p. 14]. It seems disjointed is all. Also, my question is now not identical to the linked questions, given my latest edit of actually trying to furnish a proof.
– Jessica
yesterday
Base case : Ok.
– Mauro ALLEGRANZA
yesterday
Base case : Ok.
– Mauro ALLEGRANZA
yesterday
Inductive step: the i nitial discussion about multi-valued is superfluous: $f_n$ is a function and this it cannot have more than one-value for input $a_n$. This is slightly different with respect to : assuming that $a_n$ has been defined (and thus it is a single specific value) it is not possible that subsequently we can re-define it. This is waht you have discussed in thenext paragraphs, where we want to enusre that there is no $m$ for which $n++=m++$ but $f_n(a_n)≠f_m(a_m)$.
– Mauro ALLEGRANZA
yesterday
Inductive step: the i nitial discussion about multi-valued is superfluous: $f_n$ is a function and this it cannot have more than one-value for input $a_n$. This is slightly different with respect to : assuming that $a_n$ has been defined (and thus it is a single specific value) it is not possible that subsequently we can re-define it. This is waht you have discussed in thenext paragraphs, where we want to enusre that there is no $m$ for which $n++=m++$ but $f_n(a_n)≠f_m(a_m)$.
– Mauro ALLEGRANZA
yesterday
@MauroALLEGRANZA Thanks for the clarification! It's starting to make more sense now. Final question: where in your proof sketch do you explicitly use the inductive hypothesis $P(n)$ in proving that's $P(n++)$ follows? I'm so used to explicitly referencing how $P(n++)$ follows from $P(n)$ Andrew $P(0)$ that Iran throwing me off a bit. Is it simply the ability to even define $a_n++$, since it depends on $a_n$, that the inductive hypothesis is being explicitly used?
– Jessica
yesterday
@MauroALLEGRANZA Thanks for the clarification! It's starting to make more sense now. Final question: where in your proof sketch do you explicitly use the inductive hypothesis $P(n)$ in proving that's $P(n++)$ follows? I'm so used to explicitly referencing how $P(n++)$ follows from $P(n)$ Andrew $P(0)$ that Iran throwing me off a bit. Is it simply the ability to even define $a_n++$, since it depends on $a_n$, that the inductive hypothesis is being explicitly used?
– Jessica
yesterday
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
2
down vote
The key characteristic of a function is that for every input it produces a single output, i.e.
$ text for every x,y : text if f(x) ne f(y), text then x ne y$.
Thus, the step-by-step construction described by Tao is aimed at satisfying this property.
We start with $a_0 := c$ for some $c$ and, as you noted, the procedure will never re-define $a_0$.
Regarding the inductive step, that defines : $a_n++ := f_n(a_n)$; so, how can we be sure that there is no "previous" $m$ such that $a_n++=a_m$ ?
Assume that there is such an $m$.
Two cases : $m=0$. In this case : $a_n++=a_0$ contradicting what we have said above.
Second case : $m ne 0$. This means that $a_m$ is a successor of some $r$, i.e. $a_m=a_r++$.
But then $a_r++=a_m=a_n++$, and this can be so only if $r=n$.
Thus $a_r++=a_n++$ and we are done.
Note also Tao's comment :
Note how all of the axioms had to be used here. In a system which had some sort of wrap-around, recursive definitions would not work because some elements of the sequence would constantly be redefined. For instance, in Example 2.1.5, in which $3++ = 0$, then there would be (at least) two conflicting definitions for $a_0$, either $c$ or $f_3(a_3))$. In a system which had superfluous elements such as $0.5$, the element $a_0.5$ would never be defined.
For the definition of addition of natural numbers in a standard textbook, see : George Tourlakis, Lectures in Logic and Set Theory. Volume 2 : Set Theory, Cambridge UP (2003), page 246.
Another way of formulating the above proof is [see Landau, page 4] :
Let $a_y$ and $b_y$ be defined for all $y$ as follows :
$$a_1=c text and b_1=c,$$
$$a_y++ = f_y(a_y) text and b_y++=f_y(b_y), text for every y.$$
Let $A = text the set of all y text for which a_y=b_y$.
Clearly $a_1=c=b_1$ and thus $1 in A$.
If $y in A$, then $a_y=b_y$, and therefore : $f_y(a_y)=f(b_y)$.
Thus : $a_y++=f_y(a_y)=f(b_y)=b_y++$ and so $y++ in A$.
Hence - by induction - $A$ is the set of all natural numbers, i.e. for every $y$ we have $a_y = b_y$.
answered yesterday
Mauro ALLEGRANZA
60.6k346105
Thanks for the (long) comment and link--I just ordered Landau's classic work as well. Your sketch seems to more explicitly address the potential "looping problem" (I'll have to try to digest it a bit more)--is there anything majorly wrong with my own attempt at the inductive step? Thanks for your patient help.
– Jessica
yesterday
Thank you for adding the additional detail! Is there any chance you could glance over my attempted proof of the inductive step? I realize it may not be necessary given your current answer, but my own attempted proof was, in many ways, inspired by your own comments on those linked posts at the beginning of this question. I just think it would help me a good bit to know of any error I've committed. Regardless, thanks again for the added detail, especially the bit from Landau.
– Jessica
yesterday
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
The key characteristic of a function is that for every input it produces a single output, i.e.
$ text for every x,y : text if f(x) ne f(y), text then x ne y$.
Thus, the step-by-step construction described by Tao is aimed at satisfying this property.
We start with $a_0 := c$ for some $c$ and, as you noted, the procedure will never re-define $a_0$.
Regarding the inductive step, that defines : $a_n++ := f_n(a_n)$; so, how can we be sure that there is no "previous" $m$ such that $a_n++=a_m$ ?
Assume that there is such an $m$.
Two cases : $m=0$. In this case : $a_n++=a_0$ contradicting what we have said above.
Second case : $m ne 0$. This means that $a_m$ is a successor of some $r$, i.e. $a_m=a_r++$.
But then $a_r++=a_m=a_n++$, and this can be so only if $r=n$.
Thus $a_r++=a_n++$ and we are done.
Note also Tao's comment :
Note how all of the axioms had to be used here. In a system which had some sort of wrap-around, recursive definitions would not work because some elements of the sequence would constantly be redefined. For instance, in Example 2.1.5, in which $3++ = 0$, then there would be (at least) two conflicting definitions for $a_0$, either $c$ or $f_3(a_3))$. In a system which had superfluous elements such as $0.5$, the element $a_0.5$ would never be defined.
For the definition of addition of natural numbers in a standard textbook, see : George Tourlakis, Lectures in Logic and Set Theory. Volume 2 : Set Theory, Cambridge UP (2003), page 246.
Another way of formulating the above proof is [see Landau, page 4] :
Let $a_y$ and $b_y$ be defined for all $y$ as follows :
$$a_1=c text and b_1=c,$$
$$a_y++ = f_y(a_y) text and b_y++=f_y(b_y), text for every y.$$
Let $A = text the set of all y text for which a_y=b_y$.
Clearly $a_1=c=b_1$ and thus $1 in A$.
If $y in A$, then $a_y=b_y$, and therefore : $f_y(a_y)=f(b_y)$.
Thus : $a_y++=f_y(a_y)=f(b_y)=b_y++$ and so $y++ in A$.
Hence - by induction - $A$ is the set of all natural numbers, i.e. for every $y$ we have $a_y = b_y$.
answered yesterday
Mauro ALLEGRANZA
60.6k346105
Thanks for the (long) comment and link--I just ordered Landau's classic work as well. Your sketch seems to more explicitly address the potential "looping problem" (I'll have to try to digest it a bit more)--is there anything majorly wrong with my own attempt at the inductive step? Thanks for your patient help.
– Jessica
yesterday
Thank you for adding the additional detail! Is there any chance you could glance over my attempted proof of the inductive step? I realize it may not be necessary given your current answer, but my own attempted proof was, in many ways, inspired by your own comments on those linked posts at the beginning of this question. I just think it would help me a good bit to know of any error I've committed. Regardless, thanks again for the added detail, especially the bit from Landau.
– Jessica
yesterday
add a comment |Â
up vote
2
down vote
The key characteristic of a function is that for every input it produces a single output, i.e.
$ text for every x,y : text if f(x) ne f(y), text then x ne y$.
Thus, the step-by-step construction described by Tao is aimed at satisfying this property.
We start with $a_0 := c$ for some $c$ and, as you noted, the procedure will never re-define $a_0$.
Regarding the inductive step, that defines : $a_n++ := f_n(a_n)$; so, how can we be sure that there is no "previous" $m$ such that $a_n++=a_m$ ?
Assume that there is such an $m$.
Two cases : $m=0$. In this case : $a_n++=a_0$ contradicting what we have said above.
Second case : $m ne 0$. This means that $a_m$ is a successor of some $r$, i.e. $a_m=a_r++$.
But then $a_r++=a_m=a_n++$, and this can be so only if $r=n$.
Thus $a_r++=a_n++$ and we are done.
Note also Tao's comment :
Note how all of the axioms had to be used here. In a system which had some sort of wrap-around, recursive definitions would not work because some elements of the sequence would constantly be redefined. For instance, in Example 2.1.5, in which $3++ = 0$, then there would be (at least) two conflicting definitions for $a_0$, either $c$ or $f_3(a_3))$. In a system which had superfluous elements such as $0.5$, the element $a_0.5$ would never be defined.
For the definition of addition of natural numbers in a standard textbook, see : George Tourlakis, Lectures in Logic and Set Theory. Volume 2 : Set Theory, Cambridge UP (2003), page 246.
Another way of formulating the above proof is [see Landau, page 4] :
Let $a_y$ and $b_y$ be defined for all $y$ as follows :
$$a_1=c text and b_1=c,$$
$$a_y++ = f_y(a_y) text and b_y++=f_y(b_y), text for every y.$$
Let $A = text the set of all y text for which a_y=b_y$.
Clearly $a_1=c=b_1$ and thus $1 in A$.
If $y in A$, then $a_y=b_y$, and therefore : $f_y(a_y)=f(b_y)$.
Thus : $a_y++=f_y(a_y)=f(b_y)=b_y++$ and so $y++ in A$.
Hence - by induction - $A$ is the set of all natural numbers, i.e. for every $y$ we have $a_y = b_y$.
answered yesterday
Mauro ALLEGRANZA
60.6k346105
Thanks for the (long) comment and link--I just ordered Landau's classic work as well. Your sketch seems to more explicitly address the potential "looping problem" (I'll have to try to digest it a bit more)--is there anything majorly wrong with my own attempt at the inductive step? Thanks for your patient help.
– Jessica
yesterday
Thank you for adding the additional detail! Is there any chance you could glance over my attempted proof of the inductive step? I realize it may not be necessary given your current answer, but my own attempted proof was, in many ways, inspired by your own comments on those linked posts at the beginning of this question. I just think it would help me a good bit to know of any error I've committed. Regardless, thanks again for the added detail, especially the bit from Landau.
– Jessica
yesterday
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The key characteristic of a function is that for every input it produces a single output, i.e.
$ text for every x,y : text if f(x) ne f(y), text then x ne y$.
Thus, the step-by-step construction described by Tao is aimed at satisfying this property.
We start with $a_0 := c$ for some $c$ and, as you noted, the procedure will never re-define $a_0$.
Regarding the inductive step, that defines : $a_n++ := f_n(a_n)$; so, how can we be sure that there is no "previous" $m$ such that $a_n++=a_m$ ?
Assume that there is such an $m$.
Two cases : $m=0$. In this case : $a_n++=a_0$ contradicting what we have said above.
Second case : $m ne 0$. This means that $a_m$ is a successor of some $r$, i.e. $a_m=a_r++$.
But then $a_r++=a_m=a_n++$, and this can be so only if $r=n$.
Thus $a_r++=a_n++$ and we are done.
Note also Tao's comment :
Note how all of the axioms had to be used here. In a system which had some sort of wrap-around, recursive definitions would not work because some elements of the sequence would constantly be redefined. For instance, in Example 2.1.5, in which $3++ = 0$, then there would be (at least) two conflicting definitions for $a_0$, either $c$ or $f_3(a_3))$. In a system which had superfluous elements such as $0.5$, the element $a_0.5$ would never be defined.
For the definition of addition of natural numbers in a standard textbook, see : George Tourlakis, Lectures in Logic and Set Theory. Volume 2 : Set Theory, Cambridge UP (2003), page 246.
Another way of formulating the above proof is [see Landau, page 4] :
Let $a_y$ and $b_y$ be defined for all $y$ as follows :
$$a_1=c text and b_1=c,$$
$$a_y++ = f_y(a_y) text and b_y++=f_y(b_y), text for every y.$$
Let $A = text the set of all y text for which a_y=b_y$.
Clearly $a_1=c=b_1$ and thus $1 in A$.
If $y in A$, then $a_y=b_y$, and therefore : $f_y(a_y)=f(b_y)$.
Thus : $a_y++=f_y(a_y)=f(b_y)=b_y++$ and so $y++ in A$.
Hence - by induction - $A$ is the set of all natural numbers, i.e. for every $y$ we have $a_y = b_y$.
answered yesterday
Mauro ALLEGRANZA
60.6k346105
The key characteristic of a function is that for every input it produces a single output, i.e.
$ text for every x,y : text if f(x) ne f(y), text then x ne y$.
Thus, the step-by-step construction described by Tao is aimed at satisfying this property.
We start with $a_0 := c$ for some $c$ and, as you noted, the procedure will never re-define $a_0$.
Regarding the inductive step, that defines : $a_n++ := f_n(a_n)$; so, how can we be sure that there is no "previous" $m$ such that $a_n++=a_m$ ?
Assume that there is such an $m$.
Two cases : $m=0$. In this case : $a_n++=a_0$ contradicting what we have said above.
Second case : $m ne 0$. This means that $a_m$ is a successor of some $r$, i.e. $a_m=a_r++$.
But then $a_r++=a_m=a_n++$, and this can be so only if $r=n$.
Thus $a_r++=a_n++$ and we are done.
Note also Tao's comment :
Note how all of the axioms had to be used here. In a system which had some sort of wrap-around, recursive definitions would not work because some elements of the sequence would constantly be redefined. For instance, in Example 2.1.5, in which $3++ = 0$, then there would be (at least) two conflicting definitions for $a_0$, either $c$ or $f_3(a_3))$. In a system which had superfluous elements such as $0.5$, the element $a_0.5$ would never be defined.
For the definition of addition of natural numbers in a standard textbook, see : George Tourlakis, Lectures in Logic and Set Theory. Volume 2 : Set Theory, Cambridge UP (2003), page 246.
Another way of formulating the above proof is [see Landau, page 4] :
Let $a_y$ and $b_y$ be defined for all $y$ as follows :
$$a_1=c text and b_1=c,$$
$$a_y++ = f_y(a_y) text and b_y++=f_y(b_y), text for every y.$$
Let $A = text the set of all y text for which a_y=b_y$.
Clearly $a_1=c=b_1$ and thus $1 in A$.
If $y in A$, then $a_y=b_y$, and therefore : $f_y(a_y)=f(b_y)$.
Thus : $a_y++=f_y(a_y)=f(b_y)=b_y++$ and so $y++ in A$.
Hence - by induction - $A$ is the set of all natural numbers, i.e. for every $y$ we have $a_y = b_y$.
answered yesterday
Mauro ALLEGRANZA
60.6k346105
edited yesterday
answered yesterday
Mauro ALLEGRANZA
60.6k346105
answered yesterday
Mauro ALLEGRANZA
60.6k346105
answered yesterday
Mauro ALLEGRANZA
60.6k346105
60.6k346105
Thanks for the (long) comment and link--I just ordered Landau's classic work as well. Your sketch seems to more explicitly address the potential "looping problem" (I'll have to try to digest it a bit more)--is there anything majorly wrong with my own attempt at the inductive step? Thanks for your patient help.
– Jessica
yesterday
Thank you for adding the additional detail! Is there any chance you could glance over my attempted proof of the inductive step? I realize it may not be necessary given your current answer, but my own attempted proof was, in many ways, inspired by your own comments on those linked posts at the beginning of this question. I just think it would help me a good bit to know of any error I've committed. Regardless, thanks again for the added detail, especially the bit from Landau.
– Jessica
yesterday
add a comment |Â
Thanks for the (long) comment and link--I just ordered Landau's classic work as well. Your sketch seems to more explicitly address the potential "looping problem" (I'll have to try to digest it a bit more)--is there anything majorly wrong with my own attempt at the inductive step? Thanks for your patient help.
– Jessica
yesterday
Thank you for adding the additional detail! Is there any chance you could glance over my attempted proof of the inductive step? I realize it may not be necessary given your current answer, but my own attempted proof was, in many ways, inspired by your own comments on those linked posts at the beginning of this question. I just think it would help me a good bit to know of any error I've committed. Regardless, thanks again for the added detail, especially the bit from Landau.
– Jessica
yesterday
Thanks for the (long) comment and link--I just ordered Landau's classic work as well. Your sketch seems to more explicitly address the potential "looping problem" (I'll have to try to digest it a bit more)--is there anything majorly wrong with my own attempt at the inductive step? Thanks for your patient help.
– Jessica
yesterday
Thanks for the (long) comment and link--I just ordered Landau's classic work as well. Your sketch seems to more explicitly address the potential "looping problem" (I'll have to try to digest it a bit more)--is there anything majorly wrong with my own attempt at the inductive step? Thanks for your patient help.
– Jessica
yesterday
Thank you for adding the additional detail! Is there any chance you could glance over my attempted proof of the inductive step? I realize it may not be necessary given your current answer, but my own attempted proof was, in many ways, inspired by your own comments on those linked posts at the beginning of this question. I just think it would help me a good bit to know of any error I've committed. Regardless, thanks again for the added detail, especially the bit from Landau.
– Jessica
yesterday
Thank you for adding the additional detail! Is there any chance you could glance over my attempted proof of the inductive step? I realize it may not be necessary given your current answer, but my own attempted proof was, in many ways, inspired by your own comments on those linked posts at the beginning of this question. I just think it would help me a good bit to know of any error I've committed. Regardless, thanks again for the added detail, especially the bit from Landau.
– Jessica
yesterday
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2872344%2funderstanding-and-proving-prop-2-1-16-in-taos-analysis-i-concerning-recursive-d%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Tao's book is titled Analysis and not Set Theory: this is the reason why he do not spend many page regarding set theory topics and try to recap only the basic concepts and results needed in his exposition.
– Mauro ALLEGRANZA
yesterday
1
@MauroALLEGRANZA I get that Tao is concerned with analysis and not set theory proper, but it seems disjointed and inconsistent with some of his explicitly stated goals early on in the text, namely "We will try to introduce these concepts one at a time and identify explicitly what our assumptions are as we go along--and not allow ourselves to use more "advanced" tricks such as the rules of algebra until we have actually proven them" [p. 14]. It seems disjointed is all. Also, my question is now not identical to the linked questions, given my latest edit of actually trying to furnish a proof.
– Jessica
yesterday
Base case : Ok.
– Mauro ALLEGRANZA
yesterday
Inductive step: the i nitial discussion about multi-valued is superfluous: $f_n$ is a function and this it cannot have more than one-value for input $a_n$. This is slightly different with respect to : assuming that $a_n$ has been defined (and thus it is a single specific value) it is not possible that subsequently we can re-define it. This is waht you have discussed in thenext paragraphs, where we want to enusre that there is no $m$ for which $n++=m++$ but $f_n(a_n)≠f_m(a_m)$.
– Mauro ALLEGRANZA
yesterday
@MauroALLEGRANZA Thanks for the clarification! It's starting to make more sense now. Final question: where in your proof sketch do you explicitly use the inductive hypothesis $P(n)$ in proving that's $P(n++)$ follows? I'm so used to explicitly referencing how $P(n++)$ follows from $P(n)$ Andrew $P(0)$ that Iran throwing me off a bit. Is it simply the ability to even define $a_n++$, since it depends on $a_n$, that the inductive hypothesis is being explicitly used?
– Jessica
yesterday