How can I expand mathematical induction to rational numbers?

Question

I know mathematical induction can be used to prove that a statements is true for all natural numbers (or those belonging to a certain subset of N). However, it is pretty obvious, unless I'm terribly mistaken, that this method can be expanded for any integer, as any integer can be expressed as a natural number or its opposite. However, since rational numbers are defined as a fraction of two integers, induction should also be expandable into rational numbers as well. If x is a rational number, it can be expressed as a/b where a,b are integers and b does not equal 0. So, if I want to prove a statement P(x)=P(a/b) is true for every x, is it sufficient to prove it for (a+1)/b and a/(b+1)? If not, would it be sufficient to also prove it for (a+1)/(b+1), or should a different method altogether be used?

Answer 1

You need to do a little more work, because as you noted in the case for integers you must take into account negatives. Thus it suffices to show the following:

1. $P(0)$
2. $P(x)\implies P(-x)$
3. $P(a/b)\implies P((a+1)/b)$
4. $P(a/b)\implies P(a/(b+1))$

Answer 2

I think your statement is a bit imprecise. Let's say your hypothesis is $p:\mathbb{Q}\rightarrow\left\{0,1\right\}$ ($0$ denotes falsehood, $1$ denotes truth). If you can find a bijection $f\colon \mathbb{N} \rightarrow \mathbb{Q}$ between $\mathbb{N}$ and $\mathbb{Q}$ with:

1. $p\left(f\left(0\right)\right)=1$
2. $p\left(f\left(n\right)\right)=1 \implies p\left(f\left(n + 1\right)\right)=1$

Then you are done.

Answer 3

There are many ways.

1. Perhaps the problem allows for an enumeration $a_n$ of the rationals. Then you use induction on $n$.
2. Another way could be as a double induction in increasing numerators and denominators. You would prove the initial case for $0/1$ and then assuming the statement for $a/b$ prove it for $(a+1)/b$ and $a/(b+1)$. Or increasing factors of numerator and denominator.

It depends on the problem. But in a way what you are using is induction on the naturals.

Answer 4

You can use induction on every infinite set, a way to do it is to endow the set with what is called a "well order". A well order is an order which has the property that every non-empty subset has a minimal element, and assuming the axiom of choice every set has a well-order.

So let us assume that $(X, <)$ is a well ordered set. Every element $x$ of $X$ has a successor $x^+$, by the properties of $<$ (indeed, the set $\{y \in X : x < y\}$ is non empty, hence it has a minimal element). Now if you can show that a property $P$ holds for an initial segment of $<$ (i.e a part $Y\subseteq X$ such that if $x\in Y$ and $y < x$ then $y\in Y$) and moreover that $P(x) \Rightarrow P(x^+)$ then you have $\forall x\in X, P(x)$.

For $\mathbb Z$ for example, a well-order could be $0 < 1 < -1 < -2 < 2 < 3 <-3 < \ldots$. And for the rationals, just take the well-order image of $\mathbb N$ by your favorite bijection between $\mathbb N$ and $\mathbb Q$ and it will work just as well.