# 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

http://inst.cs.berkeley.edu/~cs70/fa11/web/hws/hw13.pdf

This is from problem 3. How do you expect to survive the upper div classes if you can't get through the lower divs without cheating? Please go ask Rao or one of the GSIs, or add a homework tag, so we dont think that you're just trying to get us to do your work.

How to ask a homework question?

-
Sorry, I didn't know about the homework tag. I will make sure to use it next time. I just wanted help with how to approach the problem and solidify my understanding. I will definetely make it clear next time –  LiveYourLife Dec 2 '11 at 10:28
ok; i lit into you because one of your previous questions was tagged with homework, so i thought you would know about it –  josh Dec 2 '11 at 10:38
I didn't know that it was a mandatory tag (but rather just a helpful tag if needed). I will use it from next time if any question is related to homework. Just for clarification - should the tag be used even if its for concepts from homework or just if its problems? –  LiveYourLife Dec 2 '11 at 10:46