Register to reply 
Intro Topology  Cardinality of a subset of N 
Share this thread: 
#1
Sep710, 07:35 AM

P: 4

1. The problem statement, all variables and given/known data
Every subset of [tex]\mathbb{N}[/tex] is either finite or has the same cardinality as [tex] \mathbb{N}[/tex] 2. Relevant equations N/A 3. 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 onetoone 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 onetoone 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 onetoone 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. 


#2
Sep710, 11:14 AM

P: 540

Define [tex] g: \mathbb{N} \to A[/tex], given by [tex] x \mapsto x[/tex]. Then show, as you did, that this is a bijection. Say B is set of positive even integers. Define [tex] g: \mathbb{N} \to B[/tex], given by [tex] x \mapsto 2x[/tex] g is onto: for every b in B there is an element in N that maps to it, namely b/2. g is onetoone: 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'. 


#3
Sep710, 11:51 AM

P: 361

@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 [itex]\mathbb{N}[/itex] 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 [itex]a_1[/itex] be the least element of A (wellordering principle). Then let [itex]a_2[/itex] be the least element of A  {[itex]a_1[/itex]}, and so on. Show that the map f defined by f(n) = [itex]a_n[/itex] is a bijection from [itex]\mathbb{N}[/itex] to A. HTH Petek 


#4
Sep810, 08:48 PM

P: 4

Intro Topology  Cardinality of a subset of N
I originally tried that way (using the well ordering principal), where I got stuck was proving the surjection of [tex] f(n)=a_n [/tex]. 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 [tex] a_n \in A [/tex] for an [tex] n \in \mathbb{N} [/tex]. 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. 


#5
Sep810, 08:59 PM

Sci Advisor
HW Helper
Thanks
P: 25,228




#6
Sep810, 09:12 PM

Emeritus
Sci Advisor
PF Gold
P: 4,500

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 


#7
Sep810, 09:23 PM

P: 361

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 


#8
Sep810, 09:29 PM

P: 4




Register to reply 
Related Discussions  
Subset vs proper subset?  Set Theory, Logic, Probability, Statistics  22  
Product topology, closed subset, Hausdorff  Calculus & Beyond Homework  1  
Closed subset (with respect to weak topology)?  Differential Geometry  2  
Subset and proper subset  Set Theory, Logic, Probability, Statistics  6  
Intro Topology: boundry Q  Calculus & Beyond Homework  5 