4
$\begingroup$

People at my class acted like it was obvious, but I am not that sure:

Why is this set not countable? $$\{-1,1\}^{\mathbb{Z}^2}$$

So, this set contains all the functions from $$\mathbb{Z}^2\to\{-1,1\}$$

where $\mathbb{Z}$ is the set of integers.

Thank you for all the nice answers!

$\endgroup$
  • $\begingroup$ Is $Z$ the set of integers? $\endgroup$ – Arthur Nov 10 '18 at 9:19
  • $\begingroup$ @Arthur yes, it is $\endgroup$ – ryszard eggink Nov 10 '18 at 9:21
  • $\begingroup$ I think $\{0,1\}^{\mathbb N}$ is also not countable. There is something with cantor diagonal. I guess here it's the same proceed. $\endgroup$ – sam Nov 10 '18 at 9:25
6
$\begingroup$

There is a bijection from $\Bbb Z^2$ to $\Bbb N$, inducing a bijection from $\{-1,1\}^{\Bbb Z^2}$ to $\{-1,1\}^{\Bbb N}$. And $\{-1,1\}^{\Bbb N}$ is famously uncountable by Cantor's diagonal argument:

Assume for contradiction that it is countable. Then it's possible to list all functions in $\{-1,1\}^{\Bbb N}$ as $f_1,f_2,f_3,\ldots$. Now consider the function $g\in \{ -1,1 \} ^{\Bbb N}$ given by $$ g(n)=-f_n(n) $$ This function cannot be equal to any of the functions $f_1,f_2,\ldots$, so it's not in the list, contradicting that our list contained all functions of $\{-1,1\}^{\Bbb N}$.

$\endgroup$
5
$\begingroup$

Consider the bijection $\{-1, 1\}^{\mathbb{Z}^2}$ to $P(\mathbb{Z}^2)$ by sending a function $f$ to the set $\{x \in \mathbb{Z}^2 : f(x) = 1\}$. The inverse is $S \rightarrow f$ where $f(x) = \begin{cases} 1 \text{ if x $\in S$} \\ -1 \text{ otherwise} \end{cases}$

The power set of any infinite set is uncountable by Cantor's theorem.

$\endgroup$
4
$\begingroup$

Hint. Assume that $\{f_n\}_{n\in\mathbb{N}}$ is a countable list of ALL such functions from $\mathbb{Z}^2\to \{-1,1\}$. Now define a new function $g:\mathbb{Z}^2\to \{-1,1\}$ such that for any $(n,m)\in \mathbb{Z}^2$, $g(n,m):=-f_{|n|}(n,m)$. Does the function $g$ belong to the list?

$\endgroup$
1
$\begingroup$

Consider the simpler and, naively, smaller set $\{0, 1\} ^ \mathbb{N}$. There is a clear near bijection to the interval $[0, 1]$ by writing the reals in binary. So, this might make it more clear that this set is uncountable and yours also.

I say near bijection because you need to consider that the binary representation is not always unique. E.g. $0.011111... = 0.1000000...$. You can ignore this if you just want an intuition of the size of the set. To fix the problem, look at Schröder–Bernstein theorem.

$\endgroup$
  • $\begingroup$ Heck, I try to write a quick answer and three others appear while I am doing it. $\endgroup$ – badjohn Nov 10 '18 at 9:33

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.