# Sets / Bijection / Countablity

Is the set finite, countably infinite, or uncountable?

a. The set of all real-valued random variables on a finite sample space.

b. The set of all integer-valued random variables defined on the sample space $W$ of positive integers, with $\operatorname{Pr}[w] = 1/(2^w)$

c. The set of all integer-valued random variables on a finite sample space.

d. The set of all possible functions from $\mathbb{Z}_{97}$ to $\mathbb{Z}_{97}$ (modulo 97).

e. $\mathbb{Z}^3 = \{(a,b,c): a,b,c \in \mathbb{Z}\}$ (the set of triples of integers)

-
What do you know? What did you try? Why did this fail? –  Did Dec 2 '11 at 7:14
A random variable is just a function. Already if the sample space has $1$ point, there are as many random variables on the sample space as there are real numbers, since the point can be mapped to any real. –  André Nicolas Dec 2 '11 at 7:34
@LiveYourLife: You might want to tag this as homework. :P –  Mehrdad Dec 9 '11 at 0:08

An $S$-valued random variable on a sample space $X$ is simply a function from $X$ to $S$. Thus, a real-valued random variable on a set $X$ is simply a function from $X$ to $\mathbb{R}$, and an integer-valued random variable on $X$ is a function from $X$ to $\mathbb{Z}$. Your questions (a) and (c) are therefore the same as the questions that I answered here. That answer should also help you with (d) and (e), but (d) shouldn’t cause any trouble anyway: $\mathbb{Z}_{97}$ has $97$ elements, and in $\mathbb{Z}_{97}\times\mathbb{Z}_{97}$ each of them appears in an ordered pair with each of them, so you have a total of $97^2$ elements, a finite number.

That leaves only (b). The information that $\text{Pr}[w]=1/2^w$ is superfluous: you’re just looking at functions from $W$ to $\mathbb{Z}$. There are at least as many of those as there are functions from $W$ to $\{0,1\}$, so ... ?

This should at least get you started.

-
Thanks a lot! I understand the questions much better. I have one question though on e... I am still a little unsure how to prove it. Can i just say that we can create a mapping for each triplet in the sense that (0,0,0) -> 0, (1,0,0) -> 1, (1,0,1) -> 2 etc... every triplet will be accounted for and only once (bijection). Therefore, it is countable? –  LiveYourLife Dec 2 '11 at 8:23
In addition, building off on this...can you explain to me how to do this one: T = {p(x) : p(x) = a_n*x^n + ... + a_1*x + a_0; where n \in N and a0, a1, ..., an \in Z} (the set of all polynomials with integer coecients, of any degree) I believe you use induction on just a polynomial of degree 2 (which is identical to the comment above)...but am not exactly getting it. –  LiveYourLife Dec 2 '11 at 8:25