Michael Wolman's Home Page

I am a fifth year graduate student at Caltech studying mathematical logic and descriptive set theory. My supervisor is Alexander Kechris.

Contact me: mwolman ~at~ caltech ~dot~ edu

Papers

• Definable expansions on countable groups and countable Borel equivalence relations. Preprint 2025. [pdf, arxiv]
  Abstract

  We define and study expansion problems on countable structures in the setting of descriptive combinatorics. We consider both expansions on countable Borel equivalence relations and on countable groups, in the Borel, measure and category settings, and establish some basic correspondences between the two notions. We also prove some general structure theorems for measure and category. We then explore in detail many examples, including finding spanning trees in graphs, finding monochromatic sets in Ramsey's Theorem, and linearizing partial orders.

• Invariant uniformization, joint with Alexander Kechris. Preprint 2024. [pdf, arxiv]
  Abstract

  Standard results in descriptive set theory provide sufficient conditions for a set P ⊆ ℕ^ℕ × ℕ^ℕ to admit a Borel uniformization, namely, when P has "small" sections or "large" sections. We consider an invariant analogue of these results: Given a Borel equivalence relation E and an E-invariant set P with "small" or "large" sections, does P admit an E-invariant Borel uniformization?
  Given E, we show that every such P admits an E-invariant Borel uniformization if and only if E is smooth. We also compute the definable complexity of counterexamples in the case where E is not smooth, using category, measure, and Ramsey-theoretic methods.
  We provide two new proofs of a dichotomy of Miller classifying the pairs (E, P) such that P admits an E-invariant uniformization, for P with countable sections. In the process, we prove an ℵ₀-dimensional (G₀, H₀) dichotomy, generalizing dichotomies of Miller and Lecomte. We also show that the set of pairs (E, P) such that P has "large" sections and admits an E-invariant Borel uniformization is Σ¹₂-complete; in particular, there is no analog of Miller's dichotomy for P with "large" sections.
  Finally, we consider a less strict notion of invariant uniformization, where we select a countable nonempty subset of each section instead of a single point.

• Ditzen's effective version of Nadkarni's Theorem, joint with Alexander Kechris. Preprint 2024. [pdf]
  Abstract

  Nadkarni’s Theorem asserts that for a countable Borel equivalence relation (CBER) exactly one of the following holds: (1) It has an invariant Borel probability measure or (2) it admits a Borel compression, i.e., a Borel injection that maps each equivalence class to a proper subset of it. An effective version of Nadkarni’s Theorem was included in Ditzen’s unpublished PhD thesis, where it is shown that if a CBER is effectively Borel, then either alternative (1) above holds or else it admits an effectively Borel compression. In his thesis, Ditzen also proves an effective version of the Ergodic Decomposition Theorem. These notes contain an exposition of these results. We include Ditzen’s proof of the Effective Nadkarni’s Theorem, and use this construction to provide a different proof of the Effective Ergodic Decomposition Theorem. In addition, we construct a counterexample to show that alternative (1) above does not admit an effective version.

• Probabilistic programming semantics for name generation, joint with Marcin Sabok, Sam Staton and Dario Stein, Proc. ACM Program. Lang. 5, POPL, Article 11 (January 2021). [pdf, arxiv, doi]
  Abstract

  We make a formal analogy between random sampling and fresh name generation. We show that quasi-Borel spaces, a model for probabilistic programming, can soundly interpret the 𝜈-calculus, a calculus for name generation. Moreover, we prove that this semantics is fully abstract up to first-order types. This is surprising for an ‘off-the-shelf’ model, and requires a novel analysis of probability distributions on function spaces. Our tools are diverse and include descriptive set theory and normal forms for the 𝜈-calculus.

• Abstractness of the nu-calculus in quasi-Borel spaces at first-order types, Master's thesis, 2020. Supervised by Marcin Sabok and Prakash Panangaden. [pdf, McGill library]
  Abstract

  The nu-calculus is a simply typed, higher-order, call-by-value language that models fresh name generation [PS93]. In this language, names can be checked for equality and newly generated names are guaranteed to be distinct from all others.
  In this thesis, we show that we can interpret names to be elements of a probability space, modelling fresh name generation as sampling names from a continuous measure. Specifically, we show that the nu-calculus can be soundly interpreted in the category of quasi-Borel spaces, a recent construction providing a model of higher-order probabilistic programming [Heu+17].
  We then provide a novel analysis of higher-order functions in both the nu-calculus and the category of quasi-Borel spaces. In the nu-calculus, we construct a normal form for terms at first-order types eliminating the use of private names. We then analyze the structure of higher-order quasi-Borel spaces to prove that our semantics are abstract at first-order types.

  ---

  Le nu-calcul est un langage simplement typé, d’ordre supérieur, appel par valeur qui modélise la génération de noms frais [PS93]. Dans ce langage, l’égalité des noms peut être vérifié et les noms nouvellement générés sont garantis d’être distincts de tous les autres.
  Dans cette thèse, nous montrons que nous pouvons interpréter les noms comme des éléments d’un espace de probabilité, modélisant la génération de noms frais comme échantillonnage de noms à partir d’une mesure continue. Plus précisément, nous montrons que le nu-calcul peut être correctement interprété dans la catégorie d’espaces quasi-boréliennes, une construction récente fournissant un modèle de programmation probabiliste d’ordre supérieure [Heu+17].
  Nous fournissons ensuite une nouvelle analyse de fonctions d’ordre supérieur, à la fois dans le nu-calcul et dans la catégorie des espaces quasi-boréliennes. Dans le nu-calcul, nous construisons une forme normale pour les termes de types de premier ordre, éliminant l’utilisation de noms privés. Nous analysons ensuite la structure des espaces quasi-boréliennes d’ordre supérieur pour prouver que notre sémantique est abstraite aux types du premier ordre.

Notes

• A proof of the E₀ dichotomy from the G₀ dichotomy. DRAFT 2024-05-04. [pdf]
  Abstract

  We give a short proof of the E₀ dichotomy from the (directed) G₀ dichotomy.