Follow

ok here's a more concrete + human understandable proof of uncountability
---
RT @pawnofcthulhu
cute
one quote "the tile admits uncountably many tilings": is it even possible to have a set of tiles that aperiodically tile the plane without having uncountably many tilings? twitter.com/cs_kaplan/status/1
twitter.com/pawnofcthulhu/stat

for any tilings of the plane T,S we write T->S if every finite patch of tiles in S occurs infinitely often in T.

(1) we first show that if T->T either T is periodic or there are uncountably many tilings

lets imagine building up a tiling S step by step (for concreteness in say, a square grid we can enumerate the squares in a spiral around the origin and say at each stage we're adding a tile to cover the uncovered square with the smallest number, so we reach everywhere eventually)

we also want T->S
we say a "decision" happens when there is more than one way to extend our tiling so that it appears in T (and thus appears in T infinitely many times)

if we can build our tiling so we're only making finitely many decisions, after we've made all those decisions we're left with some patch P.
for every occurrence of P in T it extends to S, and as it occurs infinitely many times T is periodic

if on the other hand we're always making infinitely many decisions, we have continuum many tilings
(we can imagine making each decision based on the next unused bit of an infinite bitstring, say)
so lemma (1) done.

(2)for any T we can construct an S so that T->S

this time whenever we make a decision we have finitely many options

so we can always choose one so that our current patch (and any subpatches, and with these we'll eventually have all finite patches in S) occurs infinitely often in T, by the infinite pigeonhole principle
so lemma (2) done.

now assume there is no T->T and there are countably many tilings
let's organise them into a list
T1, T2, ...

(more thread)

---
RT @pawnofcthulhu
alternative proof of the last bit: for any tiling T let P_k(T) be the set of ways T covers a kxk square
twitter.com/pawnofcthulhu/stat

(note that we're talking about extending the tiling to *cover a particular square*, so all the ways of extending are mutually exclusive + exhaustive)

Sign in to participate in the conversation
Mastodon

a Schelling point for those who seek one