Intro Topology - Cardinality of a subset of N

[dyrich]

Homework Statement

Every subset of $$\mathbb{N}$$ is either finite
or has the same cardinality as $$\mathbb{N}$$

Homework Equations

N/A

The Attempt at a Solution

Let $$A \subseteq \mathbb{N}$$ and $$A$$ not be finite. $$\mathbb{N}$$ is countable, trivially, which means there is a bijective function $$f: \mathbb{N} \rightarrow \mathbb{N}$$. There is a mapping, $$g: \mathbb{N} \rightarrow A$$ that is one-to-one and onto. The set $$A$$ is a subset of $$\mathbb{N}$$, so if we define $$g$$ to have the same mapping between $$\mathbb{N}$$ and $$A$$ as $$f$$ did for $$\mathbb{N}$$ and $$\mathbb{N}$$, but only for the terms in $$A$$, we will have built in the onto and one-to-one mapping into $$g$$ that we need.

To show the function is onto, let $$a \in A \subseteq \mathbb{N}$$. $$f$$ ensures that there exists an $$n\in \mathbb{N}$$ such that $$f(n)=a$$. Since we defined $$g$$ to map the same way $$f$$ did, we know that there also exists the same $$n \in \mathbb{N}$$ such that $$g(n)=a$$. Thus the function $$g$$ is onto.

To show the one-to-one mapping, let $$a, b \in A \subseteq \mathbb{N}$$ such that $$a \not = b$$, this implies $$f(a) \not = f(b)$$, but since we defined $$g$$ to map the same as $$f$$, $$g(a) \not = g(b)$$.

There is a bijection between $$\mathbb{N}$$ and $$A$$ and thus they have the same cardinality.



Now I feel as though, I've proved it successfully, but at the same time, I'm having problems with it. Let me explain. I'm imagining the mapping from the natural numbers to the natural numbers as a diagram with the arrows of f going between the two sets. Now removing the some of the elements in the range (say the odd ones) and the corresponding arrows. This is an example of a possible mapping between the natural numbers and A. There are now elements in the domain that don't have arrows (such as, all the odds in this example). There are arrows going to everything in the range still. This is the diagram of what I've done above in the proof. I think in order to show the same cardinality, each element in the natural numbers should go to A. What I've done is different. However, I've shown a clear bijection between the two sets, so the proof is right. Can anyone help clarify my confusion? I wish I could draw a picture to help explain this.

 

[gerben]

[STRIKE]You do not need your function f, you could simply say:

Define $$g: \mathbb{N} \to A$$, given by $$x \mapsto x$$.
Then show, as you did, that this is a bijection.[/STRIKE] see Petek's response below

Now I feel as though, I've proved it successfully, but at the same time, I'm having problems with it. Let me explain. I'm imagining the mapping from the natural numbers to the natural numbers as a diagram with the arrows of f going between the two sets. Now removing the some of the elements in the range (say the odd ones) and the corresponding arrows. This is an example of a possible mapping between the natural numbers and A. There are now elements in the domain that don't have arrows (such as, all the odds in this example). There are arrows going to everything in the range still. This is the diagram of what I've done above in the proof. I think in order to show the same cardinality, each element in the natural numbers should go to A. What I've done is different. However, I've shown a clear bijection between the two sets, so the proof is right. Can anyone help clarify my confusion? I wish I could draw a picture to help explain this.

This is just a, perhaps unexpected, thing that can be the case in infinite sets. There can be subsets that are not equal to the set but that do have the same cardinality as the set. The even positive integers do have the same cardinality as N:

Say B is set of positive even integers.
Define $$g: \mathbb{N} \to B$$, given by $$x \mapsto 2x$$

g is onto: for every b in B there is an element in N that maps to it, namely b/2.
g is one-to-one: say a and a' in N both map to the same element b in B, then a=b/2 and a'=b/2 so a=a'.

 

[Petek]

@gerben: Regarding your definition of the function g, what if we select an x that isn't an element of A? Then g(x) = x isn't in A so g doesn't map $\mathbb{N}$ to A.

@dyrich: Your solution doesn't seem to use the assumption that A is infinite. Also, your definition of the function g isn't clear to me. Given any natural number n, what is g(n)?

Here's a quick sketch of a proof. Let $a_1$ be the least element of A (well-ordering principle). Then let $a_2$ be the least element of A - {$a_1$}, and so on. Show that the map f defined by f(n) = $a_n$ is a bijection from $\mathbb{N}$ to A.

HTH

Petek

 

[dyrich]

I originally tried that way (using the well ordering principal), where I got stuck was proving the surjection of $$f(n)=a_n$$. That's why I switched to the method that I posted. Any suggestions would be helpful. I know that it would start by saying let $$a_n \in A$$ for an $$n \in \mathbb{N}$$. But showing that an n exists in the natural numbers that maps to it escapes me.

I mean, can I say that the n described in this post, is the one that maps to it? That seems to unclear, I feel I would need more.

 

[Dick]

I originally tried that way (using the well ordering principal), where I got stuck was proving the surjection of $$f(n)=a_n$$. That's why I switched to the method that I posted. Any suggestions would be helpful. I know that it would start by saying let $$a_n \in A$$ for an $$n \in \mathbb{N}$$. But showing that an n exists in the natural numbers that maps to it escapes me.

I mean, can I say that the n described in this post, is the one that maps to it? That seems to unclear, I feel I would need more.

That's a reasonable good point. Isn't there a simpler way? Uh, I don't know what theorems you are using, but f:A->N defined by f(x)=x is an injection from A to N, isn't it? Doesn't that make card(A)<=card(N)?

 

[Office_Shredder]

You certainly don't need to construct an explicit bijection, but if you want to

a_n is the nth largest element of A. We know this exists by well ordering. Now if the map is not surjective, it means there is a smallest element of A that we missed (the set of all elements not in the image has a smallest element by well ordering). On the other hand, we couldn't have missed it since it's only larger than finitely many elements of the sequence, which means that it was the next one after them

 

[Petek]

I was about to post a comment similar to Office_Shredder's, but he expressed the idea much better. One minor point for dyrich to consider: Where does the assumption that A isn't finite come into play?

Petek

 

[dyrich]

I was about to post a comment similar to Office_Shredder's, but he expressed the idea much better. One minor point for dyrich to consider: Where does the assumption that A isn't finite come into play?

Petek

In order to use the well ordering principal the set must be non-empty. Since the set isn't finite, it can't possibly be empty and thus we can use the well ordering principal. Was this the point?

 

[Petek]

In order to use the well ordering principal the set must be non-empty. Since the set isn't finite, it can't possibly be empty and thus we can use the well ordering principal. Was this the point?

Kind of. We also need that the sets A - {$a_1$}, A - {$a_1, a_2$} and so on are non-empty. Can you prove that if A is infinite, then so is A - {$a_1$}? It seems obvious, but a proof should be provided for the sake of rigor.

Petek