The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

Proving a set is infinite

I'm trying to work my way through a book and the following definition comes up:
'A set is infinite if it can be placed in bijection with a subset of itself.'
Now this seems like a fairly understandable definition but I'm having trouble applying the idea to a specific set. For example, how would I prove with this definition that Q\mathbb{Q} is an infinite set. I can't see how I could order the elements of Q\mathbb{Q} to be in bijection with a subset of itself. Could anyone help me shed some light on this?
(edited 10 years ago)
Reply 1
Avatar for Small123
Small123
OP
15
I've sorted this out now. By arranging fractions in an infinite table of numerators and denominators and cancelling those not in lowest terms I can see how an order can be achieved diagonally through the table.
Original post by Small123
I've sorted this out now. By arranging fractions in an infinite table of numerators and denominators and cancelling those not in lowest terms I can see how an order can be achieved diagonally through the table.


Simpler; this is equivalent to there being a map from that set to itself that's injective but not surjective. So we can just use the map from the rationals to the rationals defined by f(m/n)=2m3nf(m/n)=2^m 3^n , f(−m/n)=5m7nf(-m/n)=5^m 7^n for m,nm,n natural.
(edited 10 years ago)
Reply 3
Avatar for BlueSam3
BlueSam3
17
The other way to do it would be to prove that the integers are infinite (very easy: the bijection f:x→2x,Z→2Z⊂Zf: x \rightarrow 2x, \mathbb{Z} \rightarrow 2 \mathbb{Z} \subset \mathbb{Z}, for example), then use the map:

Unparseable latex formula:

\begin{displaymath} g: \mathbb{Q} \rightarrow \mathbb{Q}\backslash(2\mathbb{N}+1) \subset \mathbb{Q}, x \rightarrow \left\{ \begin{array}{cc}2x & x \in \mathbb{N} \\ x & x \notin \mathbb{N}



(Forgive my awful LaTeX)

If you want to be really fancy, you could just do the proof for N\mathbb{N}, then prove that if B⊂A B \subset A, and B is infinite, then A is also infinite (try generalising the method I've used above), then just state that as N⊂Q \mathbb{N} \subset \mathbb{Q}, and hence is infinite.
(edited 10 years ago)

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you