On strong measure zero sets

December 6, 2013

I meant to write a longer blog entry on strong measure zero sets (on the real line \mathbb R), but it is getting too long, so it may take me more than I expected. For now, let me record here an argument showing the following:

Theorem. If X is a strong measure zero set and F is a closed measure zero set, then X+F has measure zero.

The argument is similar to the one in

Janusz Pawlikowski. A characterization of strong measure zero sets, Israel J. Math., 93 (1), (1996), 171-183. MR1380640 (97f:28003),

where the result is shown for strong measure zero subsets of \{0,1\}^{\mathbb N}. This is actually the easy direction of Pawlikowski’s result, showing that this condition actually characterizes strong measure zero sets, that is, if X+F is measure zero for all closed measure zero sets F, then X is strong measure zero. (Since this was intended for my analysis course, and I do not see how to prove Pawlikowski’s argument without some appeal to results in measure theory, I am only including here the easy direction.) Pawlikowski’s argument actually generalizes an earlier key result of Galvin, Mycielski, and Solovay, who proved that a set X has strong measure zero iff it can be made disjoint from any given meager set by translation, that is, iff for any G meager there is a real r with X+r disjoint from G.

I proceed with the (short) proof after the fold.

Read the rest of this entry »


Interpretations

August 18, 2013

(This started as an answer on Math.Stackexchange. This version has been lightly edited and expanded. Also posted at fff.)

Throughout this post, theory means first-order theory. In fact, we are concerned with theories that are recursively presented, though the abstract framework applies more generally. Thanks to Fredrik Engström Ellborg for suggesting in Google+ the reference Kaye-Wong, and to Ali Enayat for additional references and many useful conversations on this topic.

1.

Informally, to say that a theory T interprets a theory S means that there is a procedure for associating structures \mathcal N in the language of S to structures \mathcal M in the language of T in such a way that if \mathcal M is a model of T, then \mathcal N is a model of S.

Let us be a bit more precise, and do this syntactically to reduce the requirements of the metatheory. The original notion is due to Tarski, see

Alfred Tarski. Undecidable theories. In collaboration with Andrzej Mostowski and Raphael M. Robinson. Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, Amsterdam, 1953. MR0058532 (15,384h).

I follow here the modern reference on interpretations,

Albert Visser, Categories of theories and interpretations, in Logic in Tehran, Lecture Notes in Logic, vol. 26, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 284–341. MR2262326 (2007j:03083).

One can take “the theory T interprets the theory S to mean that there are

  1. A map i that assigns formulas in the language of T to the symbols of the language \mathcal L of S, and
  2. A formula \mathrm{Dom}(x) in the language of T,

with the following properties: We can extend i to all \mathcal L-formulas recursively: i(\phi\land\psi)=i(\phi)\land i(\psi), etc, and i(\forall x\phi)=\forall x(\mathrm{Dom}(x)\to i(\phi)). It then holds that T proves

  1. \exists x\,\mathrm{Dom}(x), and
  2. i(\phi) for each axiom \phi of S (including the axioms of first-order logic).

Here, T,S are taken to be recursive, and so is i.

If the above happens, then we can see i as a strong witness to the fact that the consistency of T implies the consistency of S.

Two theories are mutually interpretable iff each one interprets the other. By the above, this is a strong version of the statement that they are equiconsistent.

Two theories are bi-interpretable iff they are mutually interpretable, and in fact, the interpretations i from T is S and j from S in T can be taken to be “inverses” of each other, in the sense that T proves that \phi and j(i(\phi)) are equivalent for each \phi in the language of T, and similarly for S, \psi and i(j(\psi)). In a sense, two theories that are bi-interpretable are very much “the same”, only differing in their presentation.

Read the rest of this entry »