Results 1 to 5 of 5

Math Help - countable languages..please help!

  1. #1
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20

    countable languages..please help!

    Let S = {0, 1}.

    (a) Let F1 be the set of all functions f : S ! IN.
    For example, the function f that has f(0) = 92873 and f(1) = 908 is one element of
    F1.
    Is F1 countable? Prove your answer is correct.

    (b) Let F2 be the set of all functions f : IN ! S.
    For example, the function f defined by f(n) = n mod 2 for all n 2 IN is one element
    of F2.
    Is F2 countable? Prove your answer is correct.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2010
    Posts
    193
    (a) So, F_1 is the set of all functions from S={0,1} into the integers \mathbb{Z}; I'm going to write F_1=\mathbb{Z}^S.

    These things can be pictured in different ways; sometimes looking at the same thing from different points of view can be helpful.

    For instance, my first instinct would be to consider functions as collections of ordered pairs (basically their definition); so the example you gave would be f=\{ (0,92873),(1,908)\}.

    But I think another way may be more enlightening: a function f:S\longrightarrow \mathbb{Z} can be viewed as a sequence of two integers. For the example, we write f=\left< 92873,908\right>. Using this way of thinking, we see that the number of such functions is exactly equal to the number of such two-term integer sequences.

    Notice, however, that a "two-term sequence" is pretty much exactly the same as an ordered pair. Thus we see that \left| F_1\right| =\left| \mathbb{Z}\times \mathbb{Z}\right|. Have you discussed any results in your class about the countability of a finite Cartesian product of countable sets?

    (b) So F_2=S^\mathbb{Z}. First, let me visualize \mathbb{Z} as being written \mathbb{Z}=\{0,1,-1,2,-2,\ldots \} (standard way to show the countability of \mathbb{Z}). I think of a function f:\mathbb{Z}\longrightarrow S as a countable sequence

    f=\left< a_0,a_1,a_{-1},a_2,\ldots \right>, where a_n=f(n). Then |F_2| is equal to the cardinality of the set of all such countable sequences of 0's and 1's (usually written \{ 0,1\}^\omega). We show \{ 0,1\}^\omega is uncountable.

    Suppose, for sake of contradiction, that \{ 0,1\}^\omega is countable. Then we may list its elements as \{ 0,1\}^\omega=\{ x_0,x_1,x_2,\ldots \}. Consider now the sequence t=\left< t_0,t_1,\ldots \right>, where

    t_k=(k-th entry of x_k) +1\,\,(\mathrm{mod} 2). In words, the k-th entry of t is the opposite of the k-th entry of x_k.
    Certainly, then, t\in \{ 0,1\}^\omega. But notice that, for any k\in [0,\infty)\cap \mathbb{Z}, t\neq x_k because they differ (at least) in position k.
    But the x_k are supposed to make up all of \{ 0,1\}^\omega; this is clearly a contradiction. We conclude that \{ 0,1\}^\omega must be uncountable.
    Last edited by topspin1617; November 16th 2010 at 07:25 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    umm..no, we didn't discuss anything about the countability of a finite Cartesian product of countable sets. We did discuss the principle of the countability of the languages.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2010
    Posts
    193
    Is this like... a Logic Theory course or something?

    I'm not too sure about the "languages"; I do remember that part of a language of a logical system consists of functions, but I don't recall much more.

    But this question doesn't REALLY have anything to do with languages, as stated. It is just asking about the cardinality of a given set of functions.

    As far as the countability of \mathbb{Z}\times \mathbb{Z}: this set is countable. Look up the Cantor pairing function for an explanation, and a diagram of why this is true (it's actually simpler to understand just from the picture). You'll probably find it applied for \mathbb{N}, but it works for any countable set (e.g., for \mathbb{Z}).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    Thanks )
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. Replies: 2
    Last Post: November 11th 2010, 04:56 AM
  3. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  4. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum