Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can you prove that the set of integers are infinite?

And can the proof be generalized to prove the set of natural numbers, rational numbers, and complex numbers are infinite?

share|improve this question
    
I'm not sure how you're defining any of these sets of numbers, but the simplest are the natural numbers. And yes - the fact that there are infinitely many natural numbers does generalize to the others you mentioned. –  mixedmath Oct 8 '11 at 22:26
2  
@freedom8707: What definition of the integers are you using? –  Zev Chonoles Oct 8 '11 at 22:28
    
It is the big Z. –  geraldgreen Oct 8 '11 at 22:33
4  
@freedom, that's the symbol for the integers. Zev was asking for your definition of what that symbol means. (I think he imagined that the question is homework such that you need to work with a particular set of definitions). In any case, one can't prove things at this fundamental level without being very explicit about which axioms one starts from. –  Henning Makholm Oct 8 '11 at 22:40

4 Answers 4

up vote 3 down vote accepted

As noted in the comments, this depends a lot of exactly which definitions and axioms one is using,

The most mainstream set-theoretic approach, I think, is (slightly popularized) to define "infinite" as "not of the same size as $\{x\in\mathbb N_0\mid x<n\}$ for any $n\in\mathbb N_0$". Where "same size" is again defined by the existence of a bijective function between two set.

So $\mathbb Z$ is infinite iff for every natural number $n$ it holds that there is no bijection from $\mathbb Z$ to the set of natural numbers less than $n$. This is so intuitively obvious that it almost hurts to have to think there is anything to prove, but if we want to be formal about it we're not supposed to just shout "obvious!" and leave it at that. So we forge onwards.

The way to prove something about every natural number is to use mathematical induction (which itself is often an axiom, but in some systems can be proved from yet more primitive axioms. That shall not concern us here). Thus:

The base case. We must prove that there is no bijection $f$ from $\mathbb Z$ to the set of natural numbers less than 0. That is, in fact, obvious by contradiction: If such an $f$ existed, $f(42)$ would be a natural number less than 0, but such a number doesn't exist, so $f$ itself cannot exist.

The induction step. We must prove that there is no bijection $f$ from $\mathbb Z$ to the set of natural numbers less than $n+1$, given that we know that there can be no bijection from $\mathbb Z$ to the naturl numbers less than $n$. Again we proceed by contradiction, so assume that $f$ is a bijection $\mathbb Z\to\{0,1,...,n\}$. Because $f$ is a bijection, there must be a $k\in z$ such that $f(k)=n$ and $f(j)\ne n$ for every $j\ne k$. Now define $$g(i) = \cases{f(i)&\text{if }i<k\\f(i+1)&\text{if }i\ge k}$$ A bit of thought convinces us that $g$ must be a bijection from $\mathbb Z$ to $\{0,1,...,n-1\}$. But the induction hypothesis was that no such $g$ can exist, so we have reached a contradiction.

Thus, $\mathbb Z$ is infinite.

share|improve this answer

If you are defining the naturals from the Peano axioms, the first two suffice. Given $\forall x S(x)\neq 0$ and $\forall x,y S(x)=S(y)\implies x=y$ the universe must be infinite. For if it were finite, you would have $S^m(0)=S^n(0)$ (where the superscript represents iteration) for $n \neq m$. Then $|n-m|$ operations of the second axiom contradicts the first.

share|improve this answer

Suppose there were only finitely many integers. Take the largest such integer, and add one to it.

To be more precise, this follows from the Peano Axioms regarding the successor function. Namely that it is injective, that it is a natural number, that no natural number has $0$ as a successor, and lastly that $0$ is a natural number.

share|improve this answer

Because you tagged this with number theory, I'll give a number theoretic view. One can see that there are infinitely many natural numbers by seeing that there are infinitely many primes, for example. Once we have that, all we need to realize is that every prime is a natural number. So there are infinitely many natural numbers.

But every natural number is an integer, so there are infinitely may integers. Again, every integer is a rational, so there are infinitely many rationals. This is an old trick, but every rational is a complex number, and so there are infinitely many complex numbers.

So I just gave a big inclusion/injection chain. It's more interesting to show that each set has the 'same' cardinality, except for the complex numbers (which has more). One could do this with an injective chain in the other direction - it's a good exercise.

share|improve this answer
3  
The Euler product expansion for the $\zeta$ function and the fact that the latter has a pole at $1$ as a way to show the infinity of the integers! –  Mariano Suárez-Alvarez Oct 8 '11 at 23:14
    
@Mariano I like that one too! –  mixedmath Oct 9 '11 at 2:02
2  
@Mariano, mixedmath: I am going to be a bit critical, but I am not too fond of either of these reasons since they implicit use the fact that there are infinitely many integers. In particular, if you prove that their are infinitely many primes, you are using that there are infinitely many integers. (i.e., that $p_1\cdots p_n +1$ is again an integer) –  Eric Naslund Oct 9 '11 at 12:45
    
@Eric, my comment was more of a joke, really. But I don't think mixedmath's argument uses the fact that there are infinitely many integers, but constructs infinitely many integers thereby proving that. –  Mariano Suárez-Alvarez Oct 9 '11 at 15:17
    
(Of course, if you know the fundamental theorem of arithmetic and the existence of one prime, you can simply consider its powers!) –  Mariano Suárez-Alvarez Oct 9 '11 at 15:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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