If a subset of the square grid can be tiled by $1\times n$ rectangles for every $n$, can it be tiled by infinite rays?

Apologies in advance for shooting sparrows with cannons, but I can't give away such a funny opportunity to see "pure" math being applied to "simple" geometry problems.

I'll be using Gödel's compactness theorem, which is well-explained here, so check it out. In essence, the theorem is as follows: In first-order logic, if a property is witnessed by arbitrarily large finite numbers, then there is a way to witness it by infinities. It certainly feels relevant in the post's context.

Consider the theory of the abelian group $\mathbb{Z}^2$ with generators $a,b$. Thus the following sentences hold:

• $ab=ba$
• $\forall y,\,ey=ye=y$
• $a\ne b\ne e$
• $a^{-1}\ne a^{1729}$
• etc.

We collect all valid sentences into the set $\operatorname{Th}(\mathbb{Z}^2,a,b)$.

We introduce the relation $R(x,y)$, which says that "the group elements $x,y$ of $\mathbb{Z}^2$ belong to the same tile". Then the following things can be expressed as formulas/sentences:

• $R$ is an equivalence relation (left as exercise)
• Every tile is a single strip of rectangle, or equivalently, any two elements not on a same row/column cannot be in the same tile. We express this with infinitely many sentences. For example, $\forall x,\lnot R(x,a^{-3} b^4 x)$ would be one of them. We also need the rectangles to be connected, and they can also be expressed by infinitely many sentences, for example, $\forall x,R(x,a^6 x)\rightarrow \bigwedge_{i=1}^5 R(x,a^i x)$.
• For a particular group element $x$, we can ask for it not to be tiled. We use the sentence $\phi(x)$, which says that $\forall y\ne x,\lnot R(x,y)$.
• For a particular group element $x$, we can also ask for it to be tiled, and we get to choose how big the tile is! For an integer $n>0$, we use the sentence $\psi_n(x)$ to mean that $x$ is in a tile of size $\ge n$, which is expressed as: $$\left(\bigvee_{i=1-n}^0\bigwedge_{j=i}^{i+n-1} R(x,a^j x)\right)\lor\left(\bigvee_{i=1-n}^0\bigwedge_{j=i}^{i+n-1} R(x,b^j x)\right)$$

Now consider making a theory $T$ in the language of groups with the marked elements $a,b$ and the relation $R$. The consistency of this theory will claim that $S\subseteq \mathbb{Z}^2$ can be tiled by infinite-sized tiles. It will contain all appropirate axioms listed above, but we take special care when putting in any $\phi(x)$ or $\psi_n(x)$ into $T$. In particular, if $x\in S$ is an element of $\mathbb{Z}^2$ expressed as a word in $a,b$, then we put $\psi_n(x)\in T$ for all $n$ (but of course $\phi(x)\notin T$). Otherwise if $x\notin S$, then we only put $\phi(x)\in T$.

By the compactness theorem, the consistency of $T$ will follow from the consistency of every finite segment $T_0\subseteq T$. However as $T_0$ is finite, there is some bound $N\in\mathbb{N}$ such that every $\psi_n(x)\in T_0$ will be of the form $n\le N$. In particular, $T_0$ is now a segment of a theory whose consistency claims that $S$ can be tiled by rectangular tiles, and every tile has size at least $N$. By our assumption, we can simply tile $S$ by rectangular tiles of size $N$, and see that $T_0$ is indeed consistent. By the compactness theorem, $T$ is consistent.

Thus we know that $S$ can indeed be tiled by rectangles of infinite size. Any such rectangle is either a ray or can be tiled by two rays. Hence $S$ can also be tiled by rays.

Shortly after reading Edward H's answer, I realized that there is a self-contained compactness argument, which I missed the first time around; I thought I would present it here.

Let $T$ be an infinite set of polyominoes. Say that an infinite "polyomino" $P$ is an extension of $T$ if, for every finite region in the plane, its possible intersections with that region could also be an intersection of $t$, for infinitely many $t\in T$. (Intuitively, we're saying that local patches of $P$ look like part of a generic large element of $T$ - if you have a finite field of view, you can't distinguish it from infinitely many possibilities in $T$.)

Then, we claim that for every region $R$ which can be tiled by every element of $T$, $R$ has a tiling using extensions of $T$. (As a trivial consequence, at least one such extension must exist.)

In the original example, $T$ is the set of all $1\times n$ rectangles, and the extensions are $\{\text{infinite ray},\text{infinite line}\}$ - but since infinite lines can be tiled by infinite rays, we can just use the rays for everything.

Proof: For every positive integer $N$, let $S_N$ denote the square $[-N,N]\times[-N,N]$. Consider the restrictions of the tilings of $R$ to $R\cap S_n$ for each tile $t\in T$. Since there are finitely many ways to partition $R\cap S_n$ into tiles, but infinitely many tilings of $R$ by some $t\in T$, at least one of these partitions of $R\cap S_n$ must extend to a $t$-tiling of $R$ for infinitely many $t\in T$.

Now, fix our partition of $S_N\cap R$, and consider ways of extending it to a partition of $S_{N+1}\cap R$. Again, there are finitely many ways to do this, so again, of the infinitely many ways to extend to a $t$-tiling of $R$, infinitely many $t$ must cluster around one such partition. (The wording of this suggests a canonical choice of tiling for each $t\in T$, but we don't need to make this selection.)

Extending this construction inductively, we end up with a tiling of $R$ with tiles that have the property that every restriction of them to a finite square resembles (a part of) infinitely many tiles in $T$. Hence, all our tiles are extensions of $T$.

---

To show that this generality is actually good for something, here are some other special cases of the above theorem:

• A region tileable by arbitrarily large squares can be tiled by infinite quadrants. (The possible extensions are quadrants, half-planes, and the whole plane, but all of these can be tiled by quadrants.)

• A region tileable by arbitrarily long "zigzag" shapes can be tiled by an infinite staircase ray, i.e. the points $\{(x,y)\ |\ x,y\ge 0, x-y\in \{0,1\}\}$.

• A region tileable by all "hooks" ($1\times n$ rectangles with an extra cell on the side of one end, e.g. :.......) can be tiled using an infinite ray and an infinite ray with a cell on the side of one end.

The same proof extends to most reasonable sort of grids - $\mathbb{Z}^n$, polyiamonds on the triangular grid, etc.