1
$\begingroup$

Let $X$ denote the two point set $\{0,1\}$ and let $X_j=\{0,1\}\forall j=1,2\dots$ let $Y=\Pi_{j=1}^{\infty}X_j$, I need to determine whether each of the following are true or false:

  1. $Y$ is countable

  2. $|Y|$=|[0,1]|

  3. $\bigcup_{n=1}^{\infty}\Pi_{j=1}^{n}X_j$ is uncountable

  4. $Y$ is uncountable.

I guess $Y$ is uncountable (4), but I can not prove it.

$\endgroup$
6
  • $\begingroup$ Do you have any ideas about any of the four? $\endgroup$
    – Brian M. Scott
    Jun 13, 2012 at 10:42
  • $\begingroup$ We have to show any finction $g:\mathbb{N}\rightarrow Y$ is not surjective. $\endgroup$
    – Marso
    Jun 13, 2012 at 10:45
  • $\begingroup$ Is #3 is a typo? You probably meant $n$ for the second infinity? $\endgroup$
    – rschwieb
    Jun 13, 2012 at 11:02
  • $\begingroup$ Yes, I guess so. $\endgroup$
    – Marso
    Jun 13, 2012 at 11:04
  • 1
    $\begingroup$ @mex If you start probing why you feel justified in guessing your guess, more of your guesses will turn into solutions! If you include more of your thoughts about your guess, we can help you do this. $\endgroup$
    – rschwieb
    Jun 13, 2012 at 11:53

3 Answers 3

Reset to default
5
$\begingroup$

HINTS

  1. On a meta-level, if the first is true then the other three are trivially false.
  2. Every real in $[0,1]$ has a binary decimal expansion $0.b_1b_2b_3\ldots$
$\endgroup$
1
  • $\begingroup$ Note that the corrected version of (3) is no longer incompatible with (1) and is in fact false. $\endgroup$
    – Brian M. Scott
    Jun 13, 2012 at 23:31
1
$\begingroup$

Every $a \in Y$ is an infinite series of zeros and ones. Think of any $b \in P(\mathbb N)$ and try to find the connection between this two.

$\endgroup$
0
$\begingroup$

Proof that 3 is false.

List the elements of the union of finite cartesian products of {0,1} by increasing $n$ in layers.

Within layer list them by increasing size of the corresponding binary number:

0, 1 $(n=1)$

00, 01, 10, 11 $(n=2)$

000, 001, 010, 011, 100, 101, 110, 111 $(n=3)$

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 $(n=4)$

....

Now label the list using the natural numbers, first by layer, then moving to the next layer.

The elements in the $n$-th layer will be labeled by $2$$n$-$1$ through $2$$n+1$-$2$.

This provides a bijection between N and all elements of the union of finite cartesian products of {0,1}, so the union of finite cartesian products of {0,1} is countable.

And I think it is done without the assistance of my favourite set theoretical bogeyman, Axiom of Choice.

P.S. Regarding point 1 in the original question, is there any relation between the infinite countable product of {0,1} and w1 (the first uncountable ordinal)?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.