0

I have an infinite set $A$ of real numbers and I wish to construct a strictly increasing sequence using elements of $A$. This is what came to my mind -

Pick any element from $A$ and name it $a_1$. Pick a different element from $A$. If this is greater than $a_1$, call it $a_2$. If not, rename the first element $a_2$ and the new one $a_1$. Suppose I have chosen $a_1<a_2<…<a_n$. Pick an element $a$ different from all these. If $a>a_n$, name it $a_{n+1}$. If $a<a_1$, rename $a_i$ as $a_{i+1}$ for all $i$, and $a$ as $a_1$. If $a_k<a<a_{k+1}$, rename $a$ to $a_{k+1}$ and $a_i$ to $a_{i+1}$ for $i\geq k+1$. This way I have $a_1<a_2<…<a_n<a_{n+1}$. Then by induction I have my increasing sequence $(a_n)$.

Am I allowed to do this? Did I invoke any axiom while doing this?

Not Euler
  • 3,079

2 Answers2

2

You are not allowed to do this. As a counter-example, suppose your set $A$ consists of the negative integers: $A=\{-1,-2,-3,\ldots\}$. Then there exists no strictly increasing infinite sequence of elements of $A$!

TonyK
  • 64,559
  • Very nice example. Which line in my "proof" was incorrect then? – Not Euler Jun 06 '19 at 04:33
  • 1
    "This way I have a1<a2<…<an<an+1. Then by induction I have my increasing sequence" Your mistake is by induction you can have a sequence of any finite length. That doesn't mean you can have a sequence of infinite length. – fleablood Jun 06 '19 at 05:31
  • @fleablood That is the answer I was hoping to get. Because this is something that has confused me for a long time. In our class we have always constructed sequence "by induction". Like "after choosing $a_n$ do this and get $a_{n+1}$. Thus we have our sequence by induction." But induction only says when a subset of naturals is the whole set. – Not Euler Jun 06 '19 at 06:02
  • Okay, ... in those cases you are adding numbers, one at a time, adding each to the end of a sequence with each number having the property. In this case each step you are make a new sequence (not a new number) by adding a number in different places. So what you get is a sequence of sequences. Each sequence is increasing and finite and there are an infinite number of sequences but there is no final sequence in the end. – fleablood Jun 06 '19 at 14:51
  • Your first sequence is $a_1 = {a_{1,1}}$ a sequence of one term. You second sequence is $a_2 = {a_{2,1},a_{2,2}}$ a sequence of two terms. Your $k$th sequence is $a_k={a_{k,1},a_{k,2},....,a_{k,}}$ a sequence of $k$ terms. Your final result is ${a_1,a_2, a_3....}$ an infinite sequence of sequences where each sequence is a finite increasing sequence. But you haven't found a way to convert this sequence of sequences into a single infinite sequence of numbers. – fleablood Jun 06 '19 at 14:56
2

This proves you can create an increasing sequence of any finite length (because if a sequence of length $n$ can be made, then a sequence of length $n+1$ can be made) but not an increasing sequence of infinite length (because for any $n$ you can "go one more" to length $n+1$ but adding one will never get you to length $\infty$) .

It's a subtle but important point that induction can give you a conclusion for all natural values but not for a countable infinite value.[1]

In this case it will be possible that for an infinite number of attempts we will find a number $<$ than $a_1$ and thus a new $a_1$ will be assigned an infinite number of times and there will be no "final" $a_1$ for the infinite sequence.

As Tony Ks answer shows the set is $\{-1,-2, -3, ....\}$ then the first sequence will be $\{a_1\} = \{-1\}$ and the second sequence will be $\{a_1, a_2\} = -2, -1$, and so on. Then $n$ sequence will be $\{a_1, .... a_n\} = \{-n, -n+1, ...., -1\}$. But each sequence will always have a different $a_1$ and there will be no "agreed upon" $a_1$ for an infinite sequence.

[1] A false proof that all real numbers between $0$ and $1$ is rational: If every decimal with $n$ places is rational then a decimal with $n+1$ spaces $0.a_1a_2....a_na_{n+1} = 0.a_1a_2.....a_n + \frac {a_{n+1}}{10^{n+1}}$ is the sum of two rational numbers and hence rational. So by induction every decimal with any number of places is rational. As every real number between $0$ and $1$ can be written a decimal with some number (possibly infinite) places, every such real number is rational.

The catch is that induction only proves something about decimals with finite number of places. Not infinite number of places. Although we can "add $1$" an infinite number of times to get an infinite number of numbers, those numbers are all finite. We can never "add $1$" and ever get $\infty$.

fleablood
  • 124,253