Skip to main content
added 220 characters in body
Source Link
Clive Newstead
  • 65.3k
  • 6
  • 104
  • 172

I get that you can say, "look, $1x = x$, $2x = x+x$, $3x = (x+x)+x$, and so on." But hold it, I say: "and so on" sounds like induction. And the $n$ we referred to isn't really an integer (much less a positive integer in $\mathbb{N}$), but rather a member of $\mathbb{R}$. So, how can we induct on its value?

You might or might not want to consider $\mathbb{N}$ as a subset of $\mathbb{R}$. If you don't want to do this, then in any case there is a natural inclusion $i : \mathbb{N} \hookrightarrow \mathbb{R}$, and then you can replace each '$n$' in your inductive proof by '$i(n)$', so that what you have is really induction on $\mathbb{N}$.

But actually, this isn't necessary. You can perform induction on any well-founded relation. A relation $R \subset X \times X$ is well-founded if for each non-empty subset $Y \subset X$ there is an element $y \in Y$ with no $R$-predecessor in $Y$; that is, there is no $z \in Y$ with $(z,y) \in R$. For a well-founded relation $R$ on a set $X$, we have the principle of $R$-induction. This states that for a property $\phi$ of elements of $X$, if for each $x$, whenever $\phi$ holds for all $R$-predecessors of $x$, it also holds for $x$ then $\phi$ holds for all $x \in X$.

Mathematical induction on $\mathbb{N}$ is an example of this. For strong induction, the relation $R$ is given by $(x,y) \in R$ if and only if $x<y$. For weak induction, the relation is given by $(x,y) \in R$ if and only if $x+1=y$. But we can transfer this relation from $\mathbb{N}$ to $i(\mathbb{N}) \subseteq \mathbb{R}$ easily, so there's no problem performing induction on 'the natural numbers in $\mathbb{R}$' rather than 'the natural numbers themselves'.

How do I navigate his multiple meanings for rationals?

The idea is again the same. You have the integers $\mathbb{Z}$ and the 'integers' $\mathbb{Z}_{\mathbb{R}}$, and an inclusion $i_{\mathbb{Z}} : \mathbb{Z} \hookrightarrow \mathbb{R}$ taking each integer $n$ to the corresponding Dedekind cut in $\mathbb{Z}_{\mathbb{R}}$. You also have the rationals $\mathbb{Q}$ and the 'rationals' $\text{quot}_{\mathbb{R}}$, and an includion $i_{\mathbb{Q}} : \mathbb{Q} \hookrightarrow \text{quot}_{\mathbb{R}}$ taking each rational number $q$ to the corresponding quotient of Dedekind cuts. All the properties of the integers/rationals transfer across under these identifications, and so you can argue about the subsets of $\mathbb{R}$ by using arguments based on the actual sets of integers and rationals without any problem.


Moral of the story: Stop worrying about whether a rational'integer' or 'rational' in $\mathbb{R}$ really is a integer or rational number or not. Whether or not you view the integers and rationals as subsets of $\mathbb{R}$ doesn't matter because when we embed them isomorphically into $\mathbb{R}$, all their properties transfer across. I mean, a real number isn't really a subset of $\mathbb{Q}$ anyway, is it?

I get that you can say, "look, $1x = x$, $2x = x+x$, $3x = (x+x)+x$, and so on." But hold it, I say: "and so on" sounds like induction. And the $n$ we referred to isn't really an integer (much less a positive integer in $\mathbb{N}$), but rather a member of $\mathbb{R}$. So, how can we induct on its value?

You might or might not want to consider $\mathbb{N}$ as a subset of $\mathbb{R}$. If you don't want to do this, then in any case there is a natural inclusion $i : \mathbb{N} \hookrightarrow \mathbb{R}$, and then you can replace each '$n$' in your inductive proof by '$i(n)$', so that what you have is really induction on $\mathbb{N}$.

But actually, this isn't necessary. You can perform induction on any well-founded relation. A relation $R \subset X \times X$ is well-founded if for each non-empty subset $Y \subset X$ there is an element $y \in Y$ with no $R$-predecessor in $Y$; that is, there is no $z \in Y$ with $(z,y) \in R$. For a well-founded relation $R$ on a set $X$, we have the principle of $R$-induction. This states that for a property $\phi$ of elements of $X$, if for each $x$, whenever $\phi$ holds for all $R$-predecessors of $x$, it also holds for $x$ then $\phi$ holds for all $x \in X$.

Mathematical induction on $\mathbb{N}$ is an example of this. For strong induction, the relation $R$ is given by $(x,y) \in R$ if and only if $x<y$. For weak induction, the relation is given by $(x,y) \in R$ if and only if $x+1=y$. But we can transfer this relation from $\mathbb{N}$ to $i(\mathbb{N}) \subseteq \mathbb{R}$ easily, so there's no problem performing induction on 'the natural numbers in $\mathbb{R}$' rather than 'the natural numbers themselves'.

How do I navigate his multiple meanings for rationals?

The idea is again the same. You have the integers $\mathbb{Z}$ and the 'integers' $\mathbb{Z}_{\mathbb{R}}$, and an inclusion $i_{\mathbb{Z}} : \mathbb{Z} \hookrightarrow \mathbb{R}$ taking each integer $n$ to the corresponding Dedekind cut in $\mathbb{Z}_{\mathbb{R}}$. You also have the rationals $\mathbb{Q}$ and the 'rationals' $\text{quot}_{\mathbb{R}}$, and an includion $i_{\mathbb{Q}} : \mathbb{Q} \hookrightarrow \text{quot}_{\mathbb{R}}$ taking each rational number $q$ to the corresponding quotient of Dedekind cuts. All the properties of the integers/rationals transfer across under these identifications, and so you can argue about the subsets of $\mathbb{R}$ by using arguments based on the actual sets of integers and rationals without any problem.


Moral of the story: Stop worrying about whether a rational in $\mathbb{R}$ really is a rational number or not. I mean, a real number isn't really a subset of $\mathbb{Q}$ anyway, is it?

I get that you can say, "look, $1x = x$, $2x = x+x$, $3x = (x+x)+x$, and so on." But hold it, I say: "and so on" sounds like induction. And the $n$ we referred to isn't really an integer (much less a positive integer in $\mathbb{N}$), but rather a member of $\mathbb{R}$. So, how can we induct on its value?

You might or might not want to consider $\mathbb{N}$ as a subset of $\mathbb{R}$. If you don't want to do this, then in any case there is a natural inclusion $i : \mathbb{N} \hookrightarrow \mathbb{R}$, and then you can replace each '$n$' in your inductive proof by '$i(n)$', so that what you have is really induction on $\mathbb{N}$.

But actually, this isn't necessary. You can perform induction on any well-founded relation. A relation $R \subset X \times X$ is well-founded if for each non-empty subset $Y \subset X$ there is an element $y \in Y$ with no $R$-predecessor in $Y$; that is, there is no $z \in Y$ with $(z,y) \in R$. For a well-founded relation $R$ on a set $X$, we have the principle of $R$-induction. This states that for a property $\phi$ of elements of $X$, if for each $x$, whenever $\phi$ holds for all $R$-predecessors of $x$, it also holds for $x$ then $\phi$ holds for all $x \in X$.

Mathematical induction on $\mathbb{N}$ is an example of this. For strong induction, the relation $R$ is given by $(x,y) \in R$ if and only if $x<y$. For weak induction, the relation is given by $(x,y) \in R$ if and only if $x+1=y$. But we can transfer this relation from $\mathbb{N}$ to $i(\mathbb{N}) \subseteq \mathbb{R}$ easily, so there's no problem performing induction on 'the natural numbers in $\mathbb{R}$' rather than 'the natural numbers themselves'.

How do I navigate his multiple meanings for rationals?

The idea is again the same. You have the integers $\mathbb{Z}$ and the 'integers' $\mathbb{Z}_{\mathbb{R}}$, and an inclusion $i_{\mathbb{Z}} : \mathbb{Z} \hookrightarrow \mathbb{R}$ taking each integer $n$ to the corresponding Dedekind cut in $\mathbb{Z}_{\mathbb{R}}$. You also have the rationals $\mathbb{Q}$ and the 'rationals' $\text{quot}_{\mathbb{R}}$, and an includion $i_{\mathbb{Q}} : \mathbb{Q} \hookrightarrow \text{quot}_{\mathbb{R}}$ taking each rational number $q$ to the corresponding quotient of Dedekind cuts. All the properties of the integers/rationals transfer across under these identifications, and so you can argue about the subsets of $\mathbb{R}$ by using arguments based on the actual sets of integers and rationals without any problem.


Moral of the story: Stop worrying about whether a 'integer' or 'rational' in $\mathbb{R}$ really is a integer or rational number or not. Whether or not you view the integers and rationals as subsets of $\mathbb{R}$ doesn't matter because when we embed them isomorphically into $\mathbb{R}$, all their properties transfer across. I mean, a real number isn't really a subset of $\mathbb{Q}$ anyway, is it?

Source Link
Clive Newstead
  • 65.3k
  • 6
  • 104
  • 172

I get that you can say, "look, $1x = x$, $2x = x+x$, $3x = (x+x)+x$, and so on." But hold it, I say: "and so on" sounds like induction. And the $n$ we referred to isn't really an integer (much less a positive integer in $\mathbb{N}$), but rather a member of $\mathbb{R}$. So, how can we induct on its value?

You might or might not want to consider $\mathbb{N}$ as a subset of $\mathbb{R}$. If you don't want to do this, then in any case there is a natural inclusion $i : \mathbb{N} \hookrightarrow \mathbb{R}$, and then you can replace each '$n$' in your inductive proof by '$i(n)$', so that what you have is really induction on $\mathbb{N}$.

But actually, this isn't necessary. You can perform induction on any well-founded relation. A relation $R \subset X \times X$ is well-founded if for each non-empty subset $Y \subset X$ there is an element $y \in Y$ with no $R$-predecessor in $Y$; that is, there is no $z \in Y$ with $(z,y) \in R$. For a well-founded relation $R$ on a set $X$, we have the principle of $R$-induction. This states that for a property $\phi$ of elements of $X$, if for each $x$, whenever $\phi$ holds for all $R$-predecessors of $x$, it also holds for $x$ then $\phi$ holds for all $x \in X$.

Mathematical induction on $\mathbb{N}$ is an example of this. For strong induction, the relation $R$ is given by $(x,y) \in R$ if and only if $x<y$. For weak induction, the relation is given by $(x,y) \in R$ if and only if $x+1=y$. But we can transfer this relation from $\mathbb{N}$ to $i(\mathbb{N}) \subseteq \mathbb{R}$ easily, so there's no problem performing induction on 'the natural numbers in $\mathbb{R}$' rather than 'the natural numbers themselves'.

How do I navigate his multiple meanings for rationals?

The idea is again the same. You have the integers $\mathbb{Z}$ and the 'integers' $\mathbb{Z}_{\mathbb{R}}$, and an inclusion $i_{\mathbb{Z}} : \mathbb{Z} \hookrightarrow \mathbb{R}$ taking each integer $n$ to the corresponding Dedekind cut in $\mathbb{Z}_{\mathbb{R}}$. You also have the rationals $\mathbb{Q}$ and the 'rationals' $\text{quot}_{\mathbb{R}}$, and an includion $i_{\mathbb{Q}} : \mathbb{Q} \hookrightarrow \text{quot}_{\mathbb{R}}$ taking each rational number $q$ to the corresponding quotient of Dedekind cuts. All the properties of the integers/rationals transfer across under these identifications, and so you can argue about the subsets of $\mathbb{R}$ by using arguments based on the actual sets of integers and rationals without any problem.


Moral of the story: Stop worrying about whether a rational in $\mathbb{R}$ really is a rational number or not. I mean, a real number isn't really a subset of $\mathbb{Q}$ anyway, is it?