Results 1 to 4 of 4

Math Help - Weird cardinality q

  1. #1
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273

    Weird cardinality q

    A "book" is a finite string of characters from some finite "alphabet," such as the 128-character ASCII system. Is the set B of all possible "books" finite, countably infinite, uncountable?

    Would it be finite as the product of two finite sets is finite?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2010
    From
    Lisbon
    Posts
    51
    The set of all books \mathcal B is countable. For simplicity, just to get the idea across, consider the alphabet \{a,b\} with only two elements. You can then construct a bijection between \mathcal B and \mathbb N in the following way:

    a\mapsto 1
    b\mapsto 2
    aa\mapsto 3
    ab\mapsto 4
    ba\mapsto 5
    bb\mapsto 6
    aaa \mapsto 7
    ...

    The key observation is that, since the string is finite, there's only a finite number of books with a given string length.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by sfspitfire23 View Post
    A "book" is a finite string of characters from some finite "alphabet," such as the 128-character ASCII system. Is the set B of all possible "books" finite, countably infinite, uncountable?

    Would it be finite as the product of two finite sets is finite?
    The books can be put in lexigraphic order (or can be generated in this order), and so the set of all books is countably infinite.

    CB
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by sfspitfire23 View Post
    A "book" is a finite string of characters from some finite "alphabet," such as the 128-character ASCII system. Is the set B of all possible "books" finite, countably infinite, uncountable?
    This looks awfully similar to the last question you posted.

    Would it be finite as the product of two finite sets is finite?
    The product of two finite sets is evidently finite, but I don't see how that's relevant.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 7th 2010, 11:01 AM
  2. Cardinality
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: April 5th 2010, 03:16 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: April 28th 2009, 12:30 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 03:23 PM
  5. cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2008, 08:18 PM

Search Tags


/mathhelpforum @mathhelpforum