• Nov 16th 2010, 07:20 PM
girgishf
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.

(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.
• Nov 16th 2010, 07:59 PM
topspin1617
(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.
• Nov 16th 2010, 08:04 PM
girgishf
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.
• Nov 16th 2010, 08:31 PM
topspin1617
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}$).
• Nov 17th 2010, 07:18 AM
girgishf
Thanks :))