Cardinality of Natural even numbers and Natural numbers

In summary: All one-to-one and onto maps between the even and natural numbers must miss something, otherwise they would be onto! This is why the even numbers have a smaller cardinality than the naturals.
  • #1
fabbi007
20
0
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)
 
Physics news on Phys.org
  • #2
fabbi007 said:
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).)
 
  • #3
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!
 
  • #4
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!
 
  • #5
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?
 
  • #6
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?
 
  • #7
fabbi007 said:
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.
 
  • #8
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?
 
  • #9
fabbi007 said:
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) ] [tex]\Leftarrow[/tex] [ [tex]\forall[/tex] [tex]\phi [/tex] mapping X one-to-one into Y, [tex] \phi [/tex] is not onto. ]

This is equivalent to the definition I gave. Look at the word I have bolded in your own definition!
 
  • #10
jgm340 said:
(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?
 
  • #11
fabbi007 said:
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.
 
  • #12
fabbi007 said:
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.
 
  • #13
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.
 
  • #14
fabbi007 said:
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}.
 
  • #15
jgm340 said:
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.
 
  • #16
CRGreathouse said:
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!??
 
  • #17
fabbi007 said:
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.
 
  • #18
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.
 
Last edited:
  • #19
jgm340 said:
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.
 
  • #20
fabbi007 said:
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.
 

Related to Cardinality of Natural even numbers and Natural numbers

1. What is the difference between the cardinality of natural even numbers and natural numbers?

The cardinality of a set is the measure of its size or the number of elements it contains. The cardinality of natural even numbers is equal to the cardinality of natural numbers divided by 2. This is because natural even numbers are a subset of natural numbers, and for every even number, there is a corresponding natural number.

2. Is the cardinality of natural even numbers larger than or equal to the cardinality of natural numbers?

The cardinality of natural even numbers is equal to the cardinality of natural numbers divided by 2. Therefore, the cardinality of natural even numbers is always smaller than the cardinality of natural numbers. This can be shown using mathematical proofs and techniques such as set theory.

3. How can the cardinality of natural even numbers and natural numbers be compared?

The cardinality of natural even numbers and natural numbers can be compared using the concept of one-to-one correspondence. This means that for every element in one set, there is a corresponding element in the other set. In this case, every natural even number has a corresponding natural number, but not every natural number has a corresponding natural even number. Therefore, the cardinality of natural even numbers is smaller than the cardinality of natural numbers.

4. Can the cardinality of natural even numbers and natural numbers be infinite?

Yes, both the cardinality of natural even numbers and natural numbers can be infinite. This is because both sets are countably infinite, meaning that they contain an infinite number of elements that can be counted or put into one-to-one correspondence with the natural numbers (1,2,3,4...).

5. How does the cardinality of natural even numbers and natural numbers relate to the concept of infinity?

The concept of infinity is often associated with the cardinality of natural even numbers and natural numbers because both sets are countably infinite. This means that even though the sets have an infinite number of elements, they can still be put into one-to-one correspondence with the natural numbers, showing that there are different sizes of infinity, and some infinities are larger than others.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
22
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Back
Top