In class I mentioned without proof that there is a finite set of squares with which we can tile the plane, but not periodically. Hao Wang was the first to study the question of whether there are such tilings. He conjectured that the answer was not. In 1966, his student Robert Berger disproved the conjecture. He explained how tiles could be used to code the workings of a formalized computer (a Turing machine), in a way that one could solve recursively the Halting Problem if it were the case that any set that tiles can do so periodically. Since it is a well-known result from computability theory that the halting problem cannot be solved recursively, it follows that Wang’s conjecture is false.

Examining the tiling given by Berger, one finds that he requires 20426 tiles to do his coding. The number has been substantially reduced since. I believe the currently known smallest set of tiles that can only cover the plane aperiodically has size 13. It was exhibited by Karel Culik II in his paper An aperiodic set of 13 Wang tiles, Discrete Mathematics 160 (1996), 245-251. The Wikipedia entry on Wang tiles displays his example. Once again, the proof of aperiodicity uses the halting problem.

(I would be curious to know of improved bounds.)

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Friday, October 16th, 2009 at 1:02 pm and is filed under 502: Logic and set theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

The first example that came to mind was MR0270881 (42 #5764) van der Waerden, B. L. How the proof of Baudet's conjecture was found. 1971 Studies in Pure Mathematics (Presented to Richard Rado) pp. 251–260 Academic Press, London. There, van der Waerden describes some of the history as well as his proof of his well-known theorem. Another example: MR224589 […]

The key reference for this is MR0799042 (87d:03141). Henle, J. M.; Mathias, A. R. D.; Woodin, W. Hugh. A barren extension. In Methods in mathematical logic (Caracas, 1983), C. A. Di Prisco, editor, 195–207, Lecture Notes in Math., 1130, Springer, Berlin, 1985. There, Henle, Mathias, and Woodin start with $L(\mathbb R)$ under the assumption of determinacy (an […]

This is consistent, at least under a rather tame large cardinal assumption. (One can also produce examples by manipulating Dedekind finite sets, but Asaf's answer addresses this. The answer here works even in the context of $\mathsf{DC}$.) For instance, see MR3612001. Conley, Clinton T.; Miller, Benjamin D. Measure reducibility of countable Borel equiva […]

The only reference I know for precisely these matters is the handbook chapter MR2768702. Koellner, Peter; Woodin, W. Hugh. Large cardinals from determinacy. In Handbook of set theory. Vols. 1, 2, 3, 1951–2119, Springer, Dordrecht, 2010. (Particularly, section 7.) For closely related topics, see also the work of Yong Cheng (and of Cheng and Schindler) on Harr […]

Check first that $\liminf |a_n|=0$ if and only if some subsequence of the $a_n$ converges to $0$. Assuming that $\liminf|a_n|=0$, use the equivalence above to show that, indeed, there is a subsequence $(a_{n_k})_{k\ge0}$ that, not only converges to 0, but does it very quickly, say $|a_{n_k}|

Forcing with sufficiently homogeneous forcing that adds reals is enough to obtain the negation of $(*)$. The point is that if a formula $\phi$ defines a parameter-free well-ordering of $\mathbb R$, then for any ordinal $\alpha$, the statement "$x$ is the $\alpha$-th real in the well-ordering defined by $\phi$" uniquely characterizes $x$ in terms of […]

This is an excellent question! Note first that, just from cardinal arithmetic considerations, whether we obtain all sets is independent (and therefore so is whether we obtain all Lebesgue measurable sets). The right context to study this question is descriptive set theory, and indeed the problem was considered early on. For example, Sierpiński proved in Sur […]

Surprisingly, the answer is no due to serious set-theoretic restrictions. If $X$ is an infinite set such that there is a ($\sigma$-additive) measure on $\mathcal P(X)$ that only takes the values 0 and 1, assigns 1 to $X$ and 0 to singletons, then the cardinality $\kappa=|X|$ of $X$ is much much larger than $\mathfrak c=|\mathbb R|$, the cardinality of the se […]

No, you cannot show this. For instance, it is consistent to have infinite Dedekind-finite sets whose power set is still Dedekind-finite. Now, if there is a surjection from $A$ to $\omega$, then there is an injection from $\omega$ (indeed, from $\mathcal P(\omega)$) to $\mathcal P(A)$, so $\mathcal P(A)$ is Dedekind-infinite. Thus, if $\mathcal P(X)$ is infin […]