Skip to main content
2 of 3
deleted 2 characters in body
Magma
  • 1k
  • 8
  • 11

Here's a reformulation of my other answer in terms of compactness and general topological abstract nonsense, for those who are interested in the general template for this style of argument:

For a given finite polyomino which can cover squares of arbitrary size, consider the set $S$ of all possible ways to place this polyomino onto an infinite grid. A subset $Q$ of $S$ can be considered a placement of copies of the polyomino onto the plane, where gaps or overlap may occur. A placement $Q$ may be represented by its characteristic function $\chi_Q: S \to \{0,1\}$.

The space $P := \mathcal P(S)$ of all possible placements has a canonical bijection to the space $\{0,1\}^S$ of all characteristic functions. The latter set is a cartesian product of two-element sets indexed by $S$, so we can equip it with the topology of a direct product of discrete two-point spaces indexed by $S$. Two-point spaces are compact, so the resulting topology on $\mathcal P(S)$ is also compact.

The topology of this direct product is generated by the clopen sets $A_s := \{s\}$ for $s \in S$ and their complements $A_s^c$.

For any cell $x$ of the grid, we can define the subset $P_x$ of placements which are valid on $x$, meaning that exactly one polyomino of the placement covers the cell $x$. Observe that since the set $S_x := \{s \in S: x \in s\}$ is finite, we can describe

$$P_x = \bigcup_{s \in S_x}\left(A_s \cap \bigcap_{t \in S_x\setminus\{s\}}A_t^c\right)$$

as a finite union of intersections of closed sets, so $P_x$ is a closed subset of $P$.

Now let $B_1 \subset B_2 \subset \ldots$ be a sequence of larger and larger squares of grid cells whose union is the entire plane. For each $B_i$ we can define the set $Q_i := \bigcap_{x \in B_i} P_x$ of placements valid within the square $B_i$. As an intersection of closed subsets of $P$, the $Q_i$ are themselves closed subsets of $P$, and since $P$ is compact so are the $Q_i$. Observe that $B_i \subset B_j$ implies $Q_i \supset Q_j$, and note that each $Q_i$ nonempty because of our initial assumption that the polyomino we chose can cover every square $B_i$ somehow.

Now the $Q_i$ are an infinite descending nested sequence of nonempty compact sets. This lets us apply Cantor's intersection theorem, the core of most compactness arguments out there, which simply tells us that the intersection of all $Q_i$ is nonempty.

However, the intersection of all $Q_i$ is also the intersection of all $P_x$, and if we recall how we defined those $P_x$, namely that $P_x$ only contains placements valid on the cell $x$, we notice that we just proved the existence of a placement that is valid on every single cell of the plane, also known as a tiling of the plane by copies of the polyomino. $~~\square$


Of note here is that it is essential for this proof that the polyomino in question is finite, otherwise the $P_x$ are not necessarily closed. In fact, there are many classes of infinite polyominos which can tile arbitrary squares but not the entire plane. The simplest of these infinite polyominos is probably just a whole plane with a single cell missing, but there are many pretty counterexamples. Finding some is left as an exercise to the reader.

Magma
  • 1k
  • 8
  • 11