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

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!

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

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}$$.

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.

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?

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.

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