Results 1 to 6 of 6

Math Help - Cardinal number exercise

  1. #1
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Jameson View Post
    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 View Post
    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 View Post
    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 View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by Opalg View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Jameson View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by Opalg View Post
    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.
    Last edited by Jameson; March 29th 2008 at 07:30 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. cardinal number
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 13th 2012, 05:15 AM
  2. [SOLVED] the cardinal number of a finite local ring
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 30th 2010, 05:55 AM
  3. regular cardinal. ZFC
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 24th 2010, 05:47 PM
  4. exercise in Number Theory
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 22nd 2008, 01:44 AM
  5. Cardinal number
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 16th 2008, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum