Cardinality of Natural even numbers and Natural numbers

[fabbi007]

Is Card (N even)< Card (N)? Where N even is set of all even Natural numbers, N is set of all Natural numbers.

Hint: use the mapping from N eve→Nn
N even to N is given by n-->n
a. Show examples of this mapping from N even
N even to N.

b. Is the mapping above onto? One-to-one?

My try at this question:

Since the mapping is n-->n it is the range of this mapping function is a proper subset of N hence the card (N even) <card (N) because there is one to one mapping and the N even maps into N.

Examples above mapping. 2->2, 4->4, 8->8, 268->268... Hence card(N even)< Card (N)

 

[CRGreathouse]

Since the mapping is n-->n it is the range of this mapping function is a proper subset of N hence the card (N even) <card (N) because there is one to one mapping and the N even maps into N.

I don't understand what you're saying. I understand that you've demonstrated a function mapping the even numbers into the natural numbers, but that doesn't show that the cardinalities are different. (For example, n |--> n maps N into N, but card(N) is not less than card(N).)

 

[jgm340]

You've made a mistake. You are correct that your mapping is one-to-one, but it is certainly not onto! Remember, part of the definition of a function includes its domain. You can see that no even natural number maps to 3.

More importantly, I think the question was written incorrectly.

The map from N even to N was supposed to be: n --> n/2.

This map is well defined, because for any even n, n/2 is in the naturals. Try to answer the question now!

 

[jgm340]

Remember, two sets A and B have the same cardinality if and only if you can find a bijection between them.

In order to show that set A has a lesser cardinality than set B, you must show two things:
(i) There DOES NOT exist a bijection between them. (A bijection is a one-to-one and onto map).
(ii) There DOES exist a bijection between A and some subset C of B.

In your work, you have shown (ii), but not (i). It turns out that there does exist a bijection between the natural numbers and the even natural numbers, so they have the same cardinality, even though one is a subset of the other!

 

[fabbi007]

jgm340: the question is correct n->n not n->n/2 yes the mapping is one to one in this case. But question is card ( N:even naturals) < card (N)?

CRG:is it clear?

 

[fabbi007]

CRG: The definition from Nayler and sell says that card(X)<card (Y) if every one-to-one mapping phi of X into Y is not onto, that is, the range phi(X) is a proper subset of Y. Range of the mapping in the above problem is (2,4,6,8...) is a proper subset of N, right?

 

[CRGreathouse]

CRG: The definition from Nayler and sell says that card(X)<card (Y) if every one-to-one mapping phi of X into Y is not onto, that is, the range phi(X) is a proper subset of Y. Range of the mapping in the above problem is (2,4,6,8...) is a proper subset of N, right?

You would need to show that for all maps, not just one particular map, to show that the even numbers had smaller cardinality than the naturals.

 

[fabbi007]

well for the given mapping n->n the range is subset of N, hence card(N even)< card (N). I am blindly going by the definition. I am missing anything here? Can you please elaborate on what your thoughts are CRG?

 

[jgm340]

CRG: The definition from Nayler and sell says that card(X)<card (Y) if every one-to-one mapping phi of X into Y is not onto, that is, the range phi(X) is a proper subset of Y. Range of the mapping in the above problem is (2,4,6,8...) is a proper subset of N, right?

Yes, now go check all other 9,999,999,999,999,999,999,999,... one-to-one mappings from (2,4,6,8,...) into N.

Try looking more closely at the logic of that definition you have just given. I'll write it out more formally:

[ card(X) < card(Y) ] \Leftarrow [ \forall \phi mapping X one-to-one into Y, \phi is not onto. ]

This is equivalent to the definition I gave. Look at the word I have bolded in your own definition!

 

[fabbi007]

(i). It turns out that there does exist a bijection between the natural numbers and the even natural numbers, so they have the same cardinality, even though one is a subset of the other!

This part I do not get. There is one-to-one and onto between them?

 

[CRGreathouse]

I am missing anything here?

Yes, my entire point. It's not enough to show that you can map from the even numbers into the natural numbers; you must show that all mappings from the even numbers to the naturals miss some elements, that is, there are no mapping from the even numbers onto the natural numbers.

Of course if you find a mapping from the even numbers onto[/i[ the natural numbers, you would have shown that the two had the same cardinality.

 

[jgm340]

This part I do not get. There is one-to-one and onto between them?

Yes. Let f(n) = n/2.

For any even natural number, f(n) is a natural number.

2 -> 1
4 -> 2
6 -> 3
8 -> 4
etc...

Notice that it is defined for each and every even natural number. f is clearly one-to-one. Moreover, for each number in N, we can find an even natural number m such that f(m) = n. Simply let m = 2n. So, f is onto as well.

This is why cardinality can be unintuitive at times when dealing with non-finite sets. The cardinality of a proper subset can be equal to the cardinality of the whole set.

 

[fabbi007]

I am lost here and confused by the ideas. What are the other mappings like n-->n/2? n-->2power n? I am tending to believe the cardinality is equal but hard to come to a conclusion . Please help.

 

[CRGreathouse]

I am tending to believe the cardinality is equal but hard to come to a conclusion .

Really? You can't come up with a 1-1 correspondence between natural numbers and even natural numbers?

Hint: natural numbers are {n: n in N} and even numbers are {2n: n in N}.

 

[fabbi007]

Yes. Let f(n) = n/2.

For any even natural number, f(n) is a natural number.

2 -> 1
4 -> 2
6 -> 3
8 -> 4
etc...

Notice that it is defined for each and every even natural number. f is clearly one-to-one. Moreover, for each number in N, we can find an even natural number m such that f(m) = n. Simply let m = 2n. So, f is onto as well.

This is why cardinality can be unintuitive at times when dealing with non-finite sets. The cardinality of a proper subset can be equal to the cardinality of the whole set.

So in this mapping the range of f(m) = N hence the mapping is onto and hence Card(N even)= Card (N). I think I got it now! Thanks for the huge explanation both of you.

 

[fabbi007]

Really? You can't come up with a 1-1 correspondence between natural numbers and even natural numbers?

Hint: natural numbers are {n: n in N} and even numbers are {2n: n in N}.

you are saying there is no one-to-one. The other person here is saying there is equality. Conflicting!??

 

[CRGreathouse]

you are saying there is no one-to-one. The other person here is saying there is equality. Conflicting!??

I haven't said -- but I don't know why you'd believe either of us. Just try to find one, and if you can't try to prove that instead, You'll go through the same thought process either way.

 

[jgm340]

Well, n --> n/2 is also a bijection between the two sets, just in the other direction.

In fact we can make this a theorem:

THEOREM: If f is a bijection between A and B, then f^-1 exists and is a bijection between B and A.

(Remember, bijection <==> one-to-one and onto).

Now, a mapping like f(n) = n^2 would not be a bijection between the set of natural numbers and the set of even natural numbers. Not every even natural number has a square root, so it's not onto. Moreover, not every natural number has an even square, so it isn't even well defined. It is, however, a bijection between the non-negative reals and the non-negative reals.

But that's irrelevant. For A and B to have the same cardinality, there just has to be AT LEAST one bijection between them. If there are also some other functions between them that aren't bijections, that doesn't change a thing.

 

[fabbi007]

Well, n --> n/2 is also a bijection between the two sets, just in the other direction.

In fact we can make this a theorem:

THEOREM: If f is a bijection between A and B, then f^-1 exists and is a bijection between B and A.

(Remember, bijection <==> one-to-one and onto).

Now, a mapping like f(n) = n^2 would not be a bijection between the set of natural numbers and the set of even natural numbers. Not every even natural number has a square root, so it's not onto. Moreover, not every natural number has an even square, so it isn't even well defined.

It is, however, a bijection between the non-negative reals and the non-negative reals.

So no every function is subset of the Set N.

 

[jgm340]

So no every function is subset of the Set N.

Well, normally you define a function to have three parts:

1) The domain.
2) The codomain.
3) A rule assigning to each element of the domain an element of the codomain.

This is why you often write, f: A --> B when f maps the set A into the set B.

f(n) = n^2 between the naturals and the even naturals is not a well-defined function; or rather, it isn't really a function at all. What the hell is f(3) supposed to be? 9? What is this strange non-even number 9?

So in order to see if a function is a bijection, you have to consider all three parts of it. This is vital to begin to understand cardinality.