Intro Topology - Cardinality of a subset of N


by dyrich
Tags: cardinality, intro, subset, topology
dyrich
dyrich is offline
#1
Sep7-10, 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 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.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
gerben
gerben is offline
#2
Sep7-10, 11:14 AM
P: 540
You do not need your function f, you could simply say:

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.
see Petek's response below

Quote Quote by dyrich View Post
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 [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 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
Petek is offline
#3
Sep7-10, 11:51 AM
Petek's Avatar
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 (well-ordering 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

dyrich
dyrich is offline
#4
Sep8-10, 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.
Dick
Dick is offline
#5
Sep8-10, 08:59 PM
Sci Advisor
HW Helper
Thanks
P: 25,174
Quote Quote by dyrich View Post
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.
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
Office_Shredder is offline
#6
Sep8-10, 09:12 PM
Mentor
P: 4,499
You certainly don't need to construct an explicit bijection, but if you want to

an 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
Petek is offline
#7
Sep8-10, 09:23 PM
Petek's Avatar
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
dyrich
dyrich is offline
#8
Sep8-10, 09:29 PM
P: 4
Quote Quote by Petek View Post
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
Petek is offline
#9
Sep8-10, 09:51 PM
Petek's Avatar
P: 361
Quote Quote by dyrich View Post
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 - {[itex]a_1[/itex]}, A - {[itex]a_1, a_2[/itex]} and so on are non-empty. Can you prove that if A is infinite, then so is A - {[itex]a_1[/itex]}? It seems obvious, but a proof should be provided for the sake of rigor.

Petek


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