# Cardinal number exercise

• Mar 29th 2008, 12:53 AM
Jameson
Cardinal number exercise
5.10 Exercise: Give examples of infinitely many infinite sets no two of which have the same cardinal number.
-------------
My text defines "countably infinite" to be a set that is countable but not infinite. Also it defines "countable" as the set is either finite or it has the same cardinal number as N, the natural numbers.

So if two sets do not have the same cardinal number, then they do not have a one-to-one correspondence, thus there exists not way to map f:A->B such that there exists at most one f(a) in B for a in A.

In previous theorems the text claims that fields N, Z, and Q are countably infinite, meaning they are not infinite sets. All of these fields certainly have an infinitely amount of terms. This doesn't make sense to me. Is the only infinite set R? I don't know if these definitions are standard, but I'm really lost obviously.

As for an example of two infinite sets that don't have the same cardinal number I actually can't think of an example because I don't know how to define an infinite set by these restrictions. It seems both sets A and B would have to have elements strictly in R, and I can't think of a way that you can't map two subsets of R and not be one-to-one.
-------------
Basically I'm really lost and a little clarification would be a lifesaver. Thanks guys.
• Mar 29th 2008, 01:55 AM
Opalg
Quote:

Originally Posted by Jameson
5.10 Exercise: Give examples of infinitely many infinite sets no two of which have the same cardinal number.
-------------
My text defines "countably infinite" to be a set that is countable but not infinite.

Are you sure? A countably infinite set is a set that is countable and infinite (as the name suggests).

Quote:

Originally Posted by Jameson
Also it defines "countable" as the set is either finite or it has the same cardinal number as N, the natural numbers.

—which would seem to suggest that N is not finite. In other words, N is infinite (as common sense suggests).

Quote:

Originally Posted by Jameson
In previous theorems the text claims that fields N, Z, and Q are countably infinite, meaning they are not infinite sets. All of these fields certainly have an infinitely amount of terms. This doesn't make sense to me. Is the only infinite set R? I don't know if these definitions are standard, but I'm really lost obviously.

These sets are indeed all infinite: N, Z and Q are countably infinite; R is uncountably infinite. So R has a different cardinality from the other three sets.

Quote:

Originally Posted by Jameson
As for an example of two infinite sets that don't have the same cardinal number I actually can't think of an example because I don't know how to define an infinite set by these restrictions. It seems both sets A and B would have to have elements strictly in R, and I can't think of a way that you can't map two subsets of R and not be one-to-one.

The big theorem that you really need to know in order to tackle this question is this. Given a nonempty set S, let P(S) denote the sets of all subsets of S (sometimes called the power set of S). The theorem says that the cardinal number of P(S) is greater than the caredinal number of S.

If S is finite, with cardinality n, then the cardinality of P(S) is 2^n. If S is infinite, with cardinal number ℵ then P(S) is "even more infinite", and its cardinality is usually written as 2^ℵ.

For the example of infinitely many infinite sets no two of which have the same cardinal number, you can use an inductive construction. Let S_1 = N (or R), and for n≥1 define S_{n+1} = P(S_n).
• Mar 29th 2008, 02:44 AM
Jameson
I'm looking through the bottom of your post right now so I'll post back when I get somewhere. Thank you so much for clarifying that definition! It must be a typo. Everything seemed so counter-intuitive/impossible.
• Mar 29th 2008, 03:02 AM
Jameson
Quote:

Originally Posted by Opalg
The big theorem that you really need to know in order to tackle this question is this. Given a nonempty set S, let P(S) denote the sets of all subsets of S (sometimes called the power set of S). The theorem says that the cardinal number of P(S) is greater than the caredinal number of S.

If S is finite, with cardinality n, then the cardinality of P(S) is 2^n. If S is infinite, with cardinal number ℵ then P(S) is "even more infinite", and its cardinality is usually written as 2^ℵ.

For the example of infinitely many infinite sets no two of which have the same cardinal number, you can use an inductive construction. Let S_1 = N (or R), and for n≥1 define S_{n+1} = P(S_n).

We just finished talking about power sets last class, although I was very lost. I think I understand what the power set theorem says, although being "even more infinite" is something I don't quite fully understand.

That is a clever method of finding infinitely many infinite sets! I'll definitely use that. Of course the hinge of this method is understanding the proof behind it, so I'll have to look into that.

Here is the hint that my text gave: maybe you could help put it into easier terms for me. This proving that for all non-empty sets A, P(A) > A.
----
Hint: Indirect proof! Suppose to the contrary that f:A->P(A) is a one-to-one correspondence between A and P(A) and consider the set $B = \{ x \in A: x \notin f(x) \}$. Then $B \in P(A)$ so it must correspond to some element $b \in A$. Is $b \in B$?

----------
I was going to try to say as much as I understood, but I actually don't know what the colon means when defining a set. Is set B have x in A and x not in f(x)? That seems impossible.
• Mar 29th 2008, 05:14 AM
Opalg
Quote:

Originally Posted by Jameson
Here is the hint that my text gave: maybe you could help put it into easier terms for me. This proving that for all non-empty sets A, P(A) > A.
----
Hint: Indirect proof! Suppose to the contrary that f:A->P(A) is a one-to-one correspondence between A and P(A) and consider the set $B = \{ x \in A: x \notin f(x) \}$. Then $B \in P(A)$ so it must correspond to some element $b \in A$. Is $b \in B$?

----------
I was going to try to say as much as I understood, but I actually don't know what the colon means when defining a set. Is set B have x in A and x not in f(x)? That seems impossible.

The colon should be read as "such that". In the definition $B = \{ x \in A: x \notin f(x) \}$, the condition for x to belong to B is that x is not in the subset $f(x)\subseteq A$.

To take a concrete example, suppose A = N (the natural numbers). If f is a function from N to P(N) then for every n in N, f(n) has to be a subset of N. For instance, f(1) might be {1,3,5,7,...} and f(2) might be {10,11,12}. Then 1∈f(1) but 2∉f(2).

The idea of the hint for proving the cardinality theorem is essentially the same as the argument of Russell's paradox. If there is a surjective mapping f from A to P(A) then the set B (consisting of all x in A such that x∉f(x)) must be equal to f(b) for some b∈A. But then if you ask whether b∈B, you find that this implies that b∉B, and vice versa. That is a contradiction, and proves that f cannot exist.
• Mar 29th 2008, 07:02 AM
Jameson
Quote:

Originally Posted by Opalg
To take a concrete example, suppose A = N (the natural numbers). If f is a function from N to P(N) then for every n in N, f(n) has to be a subset of N. For instance, f(1) might be {1,3,5,7,...} and f(2) might be {10,11,12}. Then 1∈f(1) but 2∉f(2).

Thank you very much for all of this. I'm trying to make sure I completely understand your example. So f is also mapping N to P(N), where N would a single element input, and the output would be some sort of subset of N, correct? Hence like you said, for every n in N, f(n) has to be a subset of N. And I understand the last part of that paragraph, so good.

The thing I don't get is we are saying that f:A->P(A) for all n in A and they have a one-to-one correspondence, meaning for all P(n), there exists only one n in A which f will output P(n). Now, we're saying suppose there is a set B, $B = \{ x \in A: x \notin f(x) \}$. So all x's in B, must be in A, but not any subsets of A? That seems impossible since f always maps A->P(A).

So you're saying that since B is composed of elements of A, then there must exist some subset mapped by f that is equal to B. I think you wrote this as set B must equal f(b) for some b in A. So now because there is this subset f(b), than there must equal some b in A that satisfies this mapping for f, thus b is in A, but also b is in B? I'm stuck on the very last part. I feel I almost have it.