Thread: Show that the sets are countable:

(a) {1,3,5,7..}

(b) {0,1,4,9..}

I know that by definition a set S is countable if there exists an injective function f: S to N..

I also know that if f is also surjective (so bijective) then the set is coutably infinite.


But I don't know how to PROVE IT!

Have I proved it if I say

f: Natural numbers to S f(n) = 2n-1

?

f: Natural numbers to S f(n) = 2n-1

According to your definition, you need a function from $\displaystyle S$ to $\displaystyle \mathbb{N}$... But yes, $\displaystyle f:\mathbb{N}\to S$ defined by $\displaystyle f(n)=2n+1$ is a bijection for (a). Note that if 0 in considered a natural number (it varies by country ), then you need 2n+1, not 2n-1. You need to show that f is a bijection by proving that it is an injection and a surjection. Then, from a general theorem, you know that the inverse function exists and it is also a bijection. It is also easy to write this inverse function explicitly.

The set in (b) seems to be the set of squares of all natural numbers, so this tells you what the bijection is.

Looking at question b), I would guess that the author is using the convention that $\displaystyle \mathbb{N}=\{0,1,2,\cdots\}$.
That is, zero is the first natural number.
$\displaystyle f(n)=n^2$ is a bijection in that case.

Originally Posted by emakarov

According to your definition, you need a function from $\displaystyle S$ to $\displaystyle \mathbb{N}$... But yes, $\displaystyle f:\mathbb{N}\to S$ defined by $\displaystyle f(n)=2n+1$ is a bijection for (a). Note that if 0 in considered a natural number (it varies by country ), then you need 2n+1, not 2n-1. You need to show that f is a bijection by proving that it is an injection and a surjection. Then, from a general theorem, you know that the inverse function exists and it is also a bijection. It is also easy to write this inverse function explicitly.

The set in (b) seems to be the set of squares of all natural numbers, so this tells you what the bijection is.

Sorry I don't quite understand. Are you saying that I haven't proved it yet? I need to show that it is a bijection right?

Also we have learnt N to be 1,2,3, etc not including 0.

To prove 2n+1 is injective:

f(n1) = f(n2) so 2(n1) + 1 = 2(n2) + 2
2(n1) = 2(n2) so n1 = n2

This proves it's an injection?

If your text book uses $\displaystyle \mathBB{N}=\{1,2,3,\cdots\}$
then $\displaystyle f(n)=2n-1$ works for part a) and $\displaystyle g(n)=(n-1)^2$ works for part b).

Have I proved it if I say

f: Natural numbers to S f(n) = 2n-1

Defining a function f does not prove anything. It's the properties of f with respect to S and N that mean something, so they have to be proved.

I need to show that it is a bijection right?

Yes. Also note, as I said, that proving that f : N -> S is a bijection is not a proof "by definition" that S is countable. Since your definition talks about a function S -> N, you need to make an extra step by saying that a bijection N -> S implies the existence of a bijection S -> N. It may be easier to define a bijection S -> N to begin with.

To prove 2n+1 is injective:

f(n1) = f(n2) so 2(n1) + 1 = 2(n2) + 1
2(n1) = 2(n2) so n1 = n2

This proves it's an injection?

Yes, though, as Plato pointed out, you were right in defining f(n) = 2n - 1.

Originally Posted by Plato

If your text book uses $\displaystyle \mathBB{N}=\{1,2,3,\cdots\}$
then $\displaystyle f(n)=2n-1$ works for part a) and $\displaystyle g(n)=(n-1)^2$ works for part b).

I meant 2n-1. Is my proof of injection correct? Or is there more to it?

Thankyou. So now showing that it is surjective.

Let y = (y+1)/2

f(2n-1) = 2 [(y+1)/2] -1

Sof(2n-1) = y

Is this correct?

So now showing that it is surjective.

Let n = (y+1)/2

f(2n-1) = 2 [(y+1)/2] -1

Sof(2n-1) = y

Is this correct?

Yes. It is easier, though, to define g: S -> N by g(y) = (y + 1) / 2 and to prove that it is an injection: this is all you need to prove that S is countable according to your definition. For every y in S, g(y) is indeed a natural number because y is odd, and so y + 1 is even. Also, for every y1, y2 in S, (y1 + 1) / 2 = (y2 + 1) / 2 implies y1 + 1 = y2 + 1 and so y1 = y2, so g is injective.

Originally Posted by Plato

If your text book uses $\displaystyle \mathBB{N}=\{1,2,3,\cdots\}$
then $\displaystyle f(n)=2n-1$ works for part a) and $\displaystyle g(n)=(n-1)^2$ works for part b).

Wait a minute. For (b) (n-1)^2 is not injective because for say n = 4 an n = -2 both give the function equalling 9...

So how is this one done? I can't prove it's injective...

Originally Posted by chr91

Wait a minute. For (b) (n-1)^2 is not injective because for say n = 4 an n = -2

Come on. Of course it is injective.

$\displaystyle -2\notin \mathbb{N}$. There are no negative numbers in $\displaystyle \mathbb{N}$.

Originally Posted by Plato

Come on. Of course it is injective.

$\displaystyle -2\notin \mathbb{N}$. There are no negative numbers in $\displaystyle \mathbb{N}$.

Oh yeh. I suppose I got confused as we learnt that x^2 is not injective but that was for all real numbers..