- #1
dyrich
- 4
- 0
Homework Statement
Every subset of [tex]\mathbb{N}[/tex] is either finite
or has the same cardinality as [tex] \mathbb{N}[/tex]
Homework Equations
N/A
The Attempt at a Solution
Let [tex]A \subseteq \mathbb{N}[/tex] and [tex]A[/tex] not be finite. [tex]\mathbb{N}[/tex] is countable, trivially, which means there is a bijective function [tex]f: \mathbb{N} \rightarrow \mathbb{N}[/tex]. There is a mapping, [tex] g: \mathbb{N} \rightarrow A[/tex] that is one-to-one and onto. The set [tex]A[/tex] is a subset of [tex]\mathbb{N}[/tex], so if we define [tex]g[/tex] to have the same mapping between [tex]\mathbb{N}[/tex] and [tex]A[/tex] as [tex]f[/tex] did for [tex]\mathbb{N}[/tex] and [tex]\mathbb{N}[/tex], but only for the terms in [tex]A[/tex], we will have built in the onto and one-to-one mapping into [tex]g[/tex] that we need.
To show the function is onto, let [tex]a \in A \subseteq \mathbb{N} [/tex]. [tex]f[/tex] ensures that there exists an [tex]n\in \mathbb{N}[/tex] such that [tex]f(n)=a[/tex]. Since we defined [tex]g[/tex] to map the same way [tex]f[/tex] did, we know that there also exists the same [tex]n \in \mathbb{N}[/tex] such that [tex]g(n)=a[/tex]. Thus the function [tex]g[/tex] is onto.
To show the one-to-one mapping, let [tex]a, b \in A \subseteq \mathbb{N}[/tex] such that [tex]a \not = b[/tex], this implies [tex]f(a) \not = f(b)[/tex], but since we defined [tex]g[/tex] to map the same as [tex]f[/tex], [tex]g(a) \not = g(b)[/tex].
There is a bijection between [tex]\mathbb{N}[/tex] and [tex]A[/tex] 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.