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!
On
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.
On
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?
On
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.
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}$.