Given any set of jordan curves that can tile the plane, how to prove that the number of possible tilings using tiles from this set is either in bijection with the real numbers or a (possibly infinite) subset of the integers?

Two tilings are equal if they can be made to coincide by translations or rotations.

  • $\begingroup$ I'm not sure what the title supposed to mean, the Continuum Hypothesis says that the continuum has a very specific cardinality, its minimal possible. What does that have to do with the question? $\endgroup$ – Asaf Karagila Oct 9 '11 at 13:52
  • 1
    $\begingroup$ "There is no set whose cardinality is strictly between that of the integers and that of the real numbers." - Georg Cantor. Does it hold for cardinalities of tilings of the plane ? $\endgroup$ – Optimus Prime Oct 9 '11 at 13:54
  • 2
    $\begingroup$ I know there is sets of polyominoes say, for which the number of tilings are of the same cardinality as the integers, and there are sets of polyominoes which admit uncountable number of tilings. Is there a way to prove that there is no set of tiles that tiles the plane such that the number of tilings are not in bijection with the integers or the reals? $\endgroup$ – Optimus Prime Oct 9 '11 at 14:01
  • 5
    $\begingroup$ @Asaf: It is not unusual to call results of the form "every blah is either countable or of size continuum" a continuum hypothesis result. This is why one sometimes says that CH holds for Borel sets. I take the question here is in the same spirit. $\endgroup$ – Andrés E. Caicedo Oct 9 '11 at 14:54
  • 1
    $\begingroup$ Can you be more precise about what a tile is, and what it means to tile the plane (e.g., are rotations allowed)? For example, if you allow tiles which are unit squares with edges perturbed by a sine function of varying magnitude, it's not hard to build a family of $\kappa$ many tiles (for any $\kappa \leq 2^{\aleph_0}$) which can tile the plane in exactly $\kappa$ many ways (up to translation/rotation invariance): each tiling will use a single tile type. $\endgroup$ – user83827 Oct 9 '11 at 16:40

Are your tiles square shaped? One can then prove the result by what is essentially a compactness argument. Here is a brief idea:

Tile in order a square of size $1\times1$, then a larger square containing that one, of size $2\times 2$, then a larger one containing it, of size $3\times 3$, etc.

Suppose that your tiling allows us you to tile the plane in a non-periodic fashion. Then, for some $n$, you will have at least two options on how to tile the $n\times n$ square when you get there. Continue "on separate boards" with each of these two ways. Again, by non-periodicity, you should in each case reach a larger $m$ such that the $m\times m$ square can be tiled in at least two ways when you get there (of course, the $m$ in one case may be different from the $m$ in the other case). Continuing "on separate boards" in this fashion, you are building a complete binary tree, each path through which gives you a "different" tiling of the plane. The quotes are here, as we are not yet distinguishing between translations. But there are only countably many translates of a given tiling (if we insist that, say, the borders of our squares coincide with the lines of the form $x=n$ or $y=m$ for $n,m\in{\mathbb Z}$). But then, even after identifying translates, we are left with continuum many different tilings of the plane.

The other possibility is that your tiles does not allow non-periodic tilings. Then, no matter what path you follow, the process above should stop "splitting". But then you are only producing countably many tilings in this fashion.

| cite | improve this answer | |
  • $\begingroup$ No, the tiles need not be square shaped. $\endgroup$ – GEdgar Oct 9 '11 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.