Universal Functions

Paul B. Larson^{1} Arnold W. Miller Juris Steprāns William A.R. Weiss

Contents

1. Introduction 2 1.1. Cardinal characteristics 4 2. Borel universal functions 5 3. Universal functions and Martin’s Axiom 9 4. Universal functions of special kinds 12 5. Abstract universal functions 18 5.1. Property R 28 6. Higher dimensional universal functions 30 7. Model-theoretic universality 43 8. Appendix 50 References 52

Abstract^{2}

A function of two variables F (x, y) is universal if for every function G(x, y) there exists functions h(x) and k(y) such that

G(x, y) = F (h(x), k(y))

2 Universal Functions

for all x, y. Sierpiński showed that assuming the Continuum Hypothesis there exists a Borel function F (x, y) which is universal. Assuming Martin’s Axiom there is a universal function of Baire class 2. A universal function cannot be of Baire class 1. Here we show that it is consistent that for each α with 2 ≤ α < ω_{1} there is a universal function of class α but none of class β < α. We show that it is consistent with ZFC that there is no universal function (Borel or not) on the reals, and we show that it is consistent that there is a universal function but no Borel universal function. We also prove some results concerning higher-arity universal functions. For example, the existence of an F such that for every G there are h_{1}, h_{2}, h_{3} such that for all x, y, z

1Research supported in part by NSF Grants DMS-0801009 and DMS-1201494.

Much of the writing of the paper was done while all four authors attended the thematic program on Forcing and its Applications at the Fields Institute in Fall 2012.

2Mathematics Subject Classification 2000: 03E15 03E35 03E50

Keywords: Borel function, Universal, Martin’s Axiom, Baire class, cardinality of the continuum, Cohen real model.

Results obtained March-June 2009, November 2010. Last revised May 2014.

G(x, y, z) = F (h_{1}(x), h_{2}(y), h_{3}(z))

is equivalent to the existence of a binary universal F, however the existence of an F such that for every G there are h_{1}, h_{2}, h_{3} such that for all x, y, z

G(x, y, z) = F (h_{1}(x, y), h_{2}(x, z), h_{3}(y, z))

follows from a binary universal F but is strictly weaker.

1. Introduction

A function F : X × X → X is said to be universal if for any

G : X × X → X

there is g : X → X such that for all x, y ∈ X

G(x, y) = F (g(x), g(y)).

In the Scottish book (problem 132, see Mauldin [15]) Sierpiński asked if there always is a Borel function which is universal, when X is the real line. He had shown that there is a Borel universal function assuming the Continuum Hypothesis (Sierpiński [29]). This notion of universal function is also studied in Rado [21] (see Theorem 6 there).

Remark 1.1. Without loss of generality we may use different functions on the x and y coordinates, i.e., G(x, y) = F (g_{0}(x), g_{1}(y)) in the definition of universal function F. To see this suppose we are given F^{∗} such that for every G we may find g_{0}, g_{1} with G(x, y) = F^{∗}(g_{0}(x), g_{1}(y)) for all x, y. Then we can construct a universal F which uses only a single g. Take a bijection, i.e., a pairing function, between X × X and X, which write as: (x_{0}, x_{1}) ↦ ⟨x_{0}, x_{1}⟩. Define

F (⟨x_{0}, x_{1}⟩, ⟨y_{0}, y_{1}⟩) = F^{∗}(x_{0}, y_{1}).

Given any g_{0}, g_{1} define g(u) = ⟨g_{0}(u), g_{1}(u)⟩ and note that

F (g(x), g(y)) = F^{∗}(g_{0}(x), g_{1}(y))

for every x, y.

In the case X = 2^{ω} there is a pairing function which is a homeomorphism and hence the Borel complexity of F and F^{∗} are the same. For abstract universal F a pairing function exists for any infinite X. For finite sets X, universal functions exist if and only if |X| ≤ 1.

Remark 1.2. The definition of universal function is not changed by requiring the function g to be injective, as, given a function π: X → X for which |π^{−1}(x)| = |X| for all x ∈ X, we can replace a given F (x, y) in the original sense with F (π(x), π(y)).

The notion of universal function naturally generalizes to functions of the form f: X × Y → Z, as follows.

Definition 1.3. Given sets X, Y and Z, a function F : X × Y → Z is universal if for each function

G : X × Y → Z

there exist functions h : X → X and k: Y → Y such that for all (x, y) ∈ X × Y,

G(x, y) = F (h(x), k(y)).

We record a few simple observations about functions of this type.

Remark 1.4. If f: X × Y → Z is universal, Z′ ⊆ Z and z_{0} ∈ Z′, then the function f′: X × Y → Z′ defined by setting

f′(x, y) = \{ \begin{matrix}f(x, y) & if f(x, y) ∈ Z′ \\ z_{0} & otherwise \end{matrix}

is also universal.

The following observation shows that the existence of a universal function from 2^{ω} × 2^{ω} to 2^{ω} is equivalent to the existence of a universal function from 2^{ω} ×2^{ω} → 2, even when one asks for a universal function in a particular complexity class. Similarly, for all infinite sets X and Y, and any n ∈ ω, the existence of a universal function from X × Y to Z implies the existence of a universal function from X × Y to Z^{n}.

Proposition 1.5. If κ is a cardinal, f: X × Y → Z is a universal function, |X^{κ}| = |X| and |Y^{κ}| = |Y |, then there is a universal function F: X × Y → Z^{κ}.

Proof Fix bijections π: X^{κ} → X and ν: Y^{κ} → Y. For each (x, y) ∈ X × Y, let F (x, y) be

⟨f(π^{−1}(x)(α), ν^{−1}(y)(α)) : α < κ⟩.

To see that F is universal, fix G: X × Y → Z^{κ}. For each α < κ, define g_{α}: X × Y → Z by setting g_{α}(x, y) = G(x, y)(α). By the universality of f, there exist functions h_{α}: X → X and k_{α}: Y → Y (α < κ) such that for all α < κ and all (x, y) ∈ X × Y, g_{α}(x, y) = f(h_{α}(x), k_{α}(y)). Define H: X → X and K: Y → Y by setting

H(x) = π(⟨h_{α}(x) : α < κ⟩)

and K(y) = ν(⟨k_{α}(y) : α < κ⟩). Then for all (x, y) ∈ X × Y, F (H(x), K(y)) = ⟨f(h_{α}(x), k_{α}(y)) : α < κ⟩ = ⟨g_{α}(x, y) : α < κ⟩ = G(x, y). QED

In Section 2 we show that the existence of a Borel universal function is equivalent under a weak cardinality assumption to the statement that every subset of the plane is in the σ-algebra generated by the abstract rectangles. We also show that a universal function cannot be of Baire class 1.

In Section 3 we prove some results concerning Martin’s axiom and universal functions. We show that although MA implies that there is a universal function of Baire class 2 it is consistent to have MA_{ℵ_{1}} hold but no analytic universal functions.

In Section 4 we consider universal functions of special kinds, for example, F (x, y) = k(x + y). We also discuss special versions due to Todorcevic and Davies.

In Section 5 we consider abstract universal functions, i.e., those defined on a cardinal κ with no notion of definability, Borel or otherwise. We show that if 2^{<κ} = κ, then they exist. We also show that it is consistent that none exist for κ = 2^{ℵ_{0}}, and we construct some weak abstract versions of universal functions from the assumption MA_{ℵ_{1}}.

In Section 6 we take up the problem of universal functions of higher arity. We show that there is a natural hierarchy of such notions and we show that this hierarchy is strictly descending.

In Section 7 we compare the notion of universal function with the notional of universality from model theory.

1.1. Cardinal characteristics. The following definitions show up at various points in this paper. We let 𝔠 denote the cardinality of the continuum, i.e., 2^{ℵ_{0}}. The cardinal 𝔭 is the psuedo-intersection number, the smallest cardinality of a collection of infinite subsets of ω having the finite intersection property (i.e., all finite subcollections have nonempty intersection) but no pseudo-intersection (i.e., no infinite subset of ω is contained mod-finite in each member of the collection). Equivalently, it is the smallest cardinal for which Martin’s Axiom for σ-centered posets fails. This equivalence is due to Bell [1]; for the proof see also Weiss [33]. The tower number 𝔱 is smallest cardinality of a collection of infinite subsets of ω linearly-ordered by mod-finite containment but having no pseudo-intersection. Evidently, 𝔭 ≤ 𝔱, but a recent result of Malliaris and Shelah [14] shows that 𝔭 = 𝔱 (in light of this fact, the hypotheses of Propositions 6.16 and 7.14 are each equivalent to 𝔭 = 𝔠). The cardinal 𝔟 is the smallest cardinality of a set X ⊆ ω^{ω} such that for every f: ω → ω there exist a g ∈ X with {n ∈ ω | g(n) ≥ f(n)} infinite. See pages 426-427 of [2] for a proof that 𝔱 ≤ 𝔟.

The cardinal 𝔮 is the smallest cardinality of a set X ⊆ 2^{ω} which is not a Q-set, i.e., for which there exists a set Y ⊆ X such that Z ∩ X ≠ Y, for every G_{δ} set Z ⊆ 2^{ω}. The inequality 𝔭 ≤ 𝔮 can be proved in ZFC. This is due to Silver; see Section 5 of [20]. The cardinal characteristic 𝔞𝔭 is defined to be the least cardinal κ such that there exist an almost disjoint family {x_{α} : α < κ} (i.e., each x_{α} is an infinite subset of ω, and for each distinct pair α, β < κ, x_{α} ∩ x_{β} is finite) and a set A ⊆ κ such that for no y ⊆ ω does it hold for all α < κ that α ∈ A if and only if y ∩ x_{α} is infinite. Standard arguments show that 𝔭 ≤ 𝔞𝔭 ≤ 𝔮.

For any cardinal κ, MA_{κ} implies that 𝔭 ≥ κ, which means that Martin’s Axiom implies that 𝔭 = 𝔟 = 𝔞𝔭 = 𝔮 = 𝔠. See [2] for more on cardinal characteristics of the continuum.

2. Borel universal functions

Definition 2.1. We let R denote the family of abstract rectangles,

R = {A × B : A, B ⊆ 2^{ω}}.

Definition 2.2. For α < ω_{1}, Σ_{α}^{0}(R) and Π_{α}^{0}(R) are inductively defined by:

• Σ_{0}^{0}(R) = Π_{0}^{0}(R) = the set of finite boolean combinations of sets from R,

• Σ_{α}^{0}(R) is the set of countable unions of sets from

Π_{<α}^{0}(R) = ⋃_{β<α} Π_{β}^{0}(R),

and

• Π_{α}^{0}(R) is the set of countable intersections of sets from Σ_{<α}^{0}(R).

Definition 2.3. A Borel function F : 2^{ω} × 2^{ω} → 2^{ω} is at the α-level if for any n ∈ ω the set {(u, v) : F (u, v)(n) = 1} is Σ_{α}^{0}.

We write “a function of level α” for “a function which is at the α-th level”. A Borel function at level α is in Baire class α, but the converse does not hold. In the context of 2^{ω}, a function is of Baire class α if the preimage of every clopen set is Δ_{α+1}. For more on the classical theory of Baire class α, see Kechris [8], p. 190.

Proposition 2.4. A universal function cannot be of Baire class 1.

Proof Suppose toward a contradiction that F: 2^{ω} × 2^{ω} → 2^{ω} is a universal function of Baire class 1. Let {h_{ξ}}_{ξ∈𝔠} enumerate all functions with domain a countable subset of 2^{ω} and range dense in itself. Let {r_{ξ}}_{ξ∈𝔠} enumerate all of 2^{ω}. For each ξ ∈ 𝔠, partition the domain of h_{ξ} into A_{ξ} and B_{ξ} such that \overline{h_{ξ}[A_{ξ}]} = \overline{h_{ξ}[B_{ξ}]}. Let G : (2^{ω})^{2} → 2^{ω} be any function such that for each ξ ∈ 𝔠 and r ∈ 2^{ω}, G(r_{ξ}, r) = 1 if r ∈ A_{ξ} and G(r_{ξ}, r) = 0 if r ∈ B_{ξ}.

Now suppose that h : 2^{ω} → 2^{ω} witnesses the universality of F with respect to the function G. The range of h must be uncountable; otherwise there would be a countable collection {{C_{i}, D_{i}} : i < ω} of partitions of 2^{ω} such that for each ξ ∈ 𝔠 there exists an i ∈ ω such that \overline{h_{ξ}[C_{i} ∩ dom(h_{ξ})]} = \overline{h_{ξ}[D_{i} ∩ dom(h_{ξ})]}, and it not hard to build a counterexample to this. Hence, there is ξ such that h_{ξ} ⊆ h, and for all r ∈ A_{ξ} ∪ B_{ξ}, G(r_{ξ}, r) = F (h(r_{ξ}), h_{ξ}(r)).

If f is the function defined by setting f(y) = F (h(r_{ξ}), y), then f must be Baire class 1 and, in particular, letting C = \overline{h_{ξ}[A_{ξ}]} (which is equal to \overline{h_{ξ}[B_{ξ}]}), it follows that f ↾ C is Baire class 1. However,

f(h_{ξ}(r)) = F (h(r_{ξ}), h_{ξ}(r)) = G(r_{ξ}, r) = 1 for r ∈ A_{ξ}.

Similarly f(h_{ξ}(r)) = 0 for r ∈ B_{ξ}. This is impossible for any Baire class 1 function on the perfect set C. QED

Theorem 2.5. If 2^{<𝔠} = 𝔠, then the following are equivalent. (1) There is a Borel function F : 2^{ω} × 2^{ω} → 2^{ω} which is universal.

(2) Every subset of the plane 2^{ω} × 2^{ω} is in the σ-algebra generated

by the abstract rectangles, R. Furthermore, for any ordinal α, P(2^{ω} × 2^{ω}) = Σ_{α}^{0}(R) if and only if there is a universal function from 2^{ω} × 2^{ω} to 2^{ω} at the α-level.

Proof

(1) → (2). Suppose that there is a Borel universal F : 2^{ω}×2^{ω} → 2. Let A ⊆ 2^{ω}×2^{ω} be arbitrary and suppose that g : 2^{ω} → 2^{ω} has the property that

∀x, y (x, y) ∈ A ⇔ F (g(x), g(y)) = 1.

Let B be the Borel set F^{−1}[{1}]. Then for all (x, y) ∈ 2^{ω}×2^{ω}, (x, y) ∈ A if and only if (g(x), g(y)) ∈ B.

The set B is generated by countable unions and intersections from sets of the form C ×D, for C, D clopen subsets 2^{ω}. Define h on 2^{ω} ×2^{ω} by setting h(x, y) = (g(x), g(y)), and note that

h^{−1}[C × D] = g^{−1}[C] × g^{−1}[D]

for all sets C, D ⊆ 2^{ω}. Since preimages pass over countable unions and intersections, for each α < ω_{1}, the h-preimage of each Σ_{α}^{0} set is in Σ_{α}^{0}(R). In particular, if α < ω_{1} is such that B is Σ_{α}^{0}, then A = h^{−1}[B] is Σ_{α}^{0}(R).

(2) → (1). We show first that there exists an X ⊆ 2^{ω} of cardinality 𝔠 which has the property that every Y ⊆ X of cardinality strictly smaller than 𝔠 is Borel relative to X, i.e., is the intersection of a Borel set with X. The following argument is modeled after the one in Bing, Bledsoe, and Mauldin [3]. Let A ⊆ 𝔠 × 𝔠 be such that for every B ∈ [𝔠]^{<𝔠} there exists a δ < 𝔠 such that

B = A_{δ} =^{def} {γ < 𝔠 : (δ, γ) ∈ A}.

This is possible, as 2^{<𝔠} = 𝔠. Fix α < ω_{1} such that A is in Σ_{α}^{0}(R), and fix a sequence ⟨B_{n} : n ∈ ω⟩ of subsets of 𝔠 such that A is generated in α many steps from the sets

{B_{n} × B_{m} : n, m < ω}.

Let f : 𝔠 → 2^{ω} be the Marczewski characteristic function for the sequence ⟨B_{n} : n < ω⟩, i.e.,

f(δ)(n) = \{ \begin{matrix}0 & if δ ∉ B_{n} \\ 1 & if δ ∈ B_{n} \end{matrix}

Define the function f^{2} : 𝔠×𝔠 → 2^{ω}×2^{ω} by setting f^{2}(α, β) = (f(α), f(β)). Each set of the form B_{n} × B_{m} is the f^{2}-preimage of the clopen set

{x ∈ 2^{ω} | n ∈ x} × {x ∈ 2^{ω} | m ∈ x}.

Again using the fact that preimages pass over countable unions and intersections, we can find a Σ_{α}^{0} set Z ⊆ 2^{ω} × 2^{ω} whose f^{2}-preimage is A.

Let X = f[𝔠]. Let us check that X has the required property. Let Y be a subset of X of cardinality less than 𝔠, and let B be a subset of 𝔠 of cardinality less than 𝔠 such that Y = f[B]. Then Y will be a section of Z, intersected with X, i.e.,

Y = f[A_{δ}] = {(x, y) ∈ Z | x = f(δ), y ∈ X},

where δ < 𝔠 is such that B = A_{δ}. It follows then that Y is Σ_{α}^{0} relative to X.

Now let U ⊆ 2^{ω}×2^{ω} be a universal Σ_{α}^{0} set. Define G : 2^{ω}×2^{ω} → 2^{ω} by

setting G(x, y)(n) = 1 ⇔ (x_{n}, y) ∈ U, where x ↦^{Φ} ⟨x_{n} : n < ω⟩ ∈ (2^{ω})^{ω}

is a homeomorphism. Let k: 𝔠 → X be a bijection.

Let f_{1} : 𝔠 × 𝔠 → 2^{ω} be an arbitrary function with the property that if γ < δ < 𝔠, then f_{1}(δ, γ) = 0 (the identically zero map). We claim that there exists a function h_{1} : 𝔠 → 2^{ω} such that

f_{1}(δ, γ) = G(h_{1}(γ), k(δ)) for all (δ, γ) ∈ 𝔠 × 𝔠.

To see this, note that for each n < ω and each γ < 𝔠 the set

Y_{n} =^{def} {k(δ) : f_{1}(δ, γ)(n) = 1}

is a subset of X of cardinality less that 𝔠, so there exists a y_{n} ∈ 2^{ω} such that Y_{n} = X ∩ U_{y_{n}}. Let h_{1}(γ) = y be chosen such that the homeomorphism Φ sends y to the sequence ⟨y_{n} : n < ω⟩.

By an analogous argument, if f_{2} : 𝔠 × 𝔠 → 2^{ω} is an arbitrary map with the property that 𝔠 > γ > δ implies f_{2}(δ, γ) = 0, then there exists a functions h_{2} : 𝔠 → 2^{ω} such that

f_{2}(δ, γ) = G(h_{2}(δ), k(γ)) for all (δ, γ) ∈ 𝔠 × 𝔠.

Now define F : 2^{ω} × 2^{ω} → 2^{ω} by letting ⟨x, y⟩ be a pairing function (a homeomorphism) from 2^{ω} × 2^{ω} to 2^{ω} and setting

F (⟨x_{1}, y_{1}⟩, ⟨x_{2}, y_{2}⟩) = max(G(x_{2}, x_{1}), G(y_{1}, y_{2})),

where max : 2^{ω} × 2^{ω} → 2^{ω} is the pointwise maximum, i.e., max(u, v) = w, where w(n) is the maximum of u(n) and v(n) for each n < ω. Then F (⟨x_{1}, y_{1}⟩, ⟨x_{2}, y_{2}⟩)(n) = 1 if and only if 1 ∈ {G(x_{2}, x_{1})(n), G(y_{1}, y_{2})(n)}.

We show that F is universal. Given an arbitrary f : 𝔠 × 𝔠 → 2^{ω} we can find f_{1} and f_{2} as above so that

f(δ, γ) = max(f_{1}(δ, γ), f_{2}(δ, γ))

for all (δ, γ) ∈ 𝔠 × 𝔠. For each δ, γ < 𝔠, set l_{1}(δ) = ⟨k(δ), h_{2}(δ)⟩ and l_{2}(γ) = ⟨h_{1}(γ), k(γ)⟩. Then, for all δ, γ < 𝔠, f(δ, γ) = F (l_{1}(δ), l_{2}(γ)).

Also, F is at the α-level, i.e., for any n the set

{(u, v) : F (u, v)(n) = 1}

is in Σ_{α}^{0}. QED Remark 2.6. By Proposition 1.5, part (1) of Theorem 2.5 is equivalent to the alternate version where the range of F is 2 instead of 2^{ω}. This variation allows for an alternate, possibly simpler, proof of the reverse direction of Theorem 2.5.

Corollary 2.7. For each α with 2 ≤ α < ω_{1} there is a c.c.c. forcing extension in which there is a universal function of level α but none of level β < α. There is a c.c.c. forcing extension in which there is a universal function but no Borel universal function.

Proof The first part follows from the corresponding results about the σalgebra of abstract rectangles, see Miller [17], Theorems 37 and 52 (𝔠^{<𝔠} = 𝔠 in the models from these theorems). For the second, the existence of an abstract universal function follows from 𝔠^{<𝔠} = 𝔠 by Theorem 5.1, and this holds in many models in which not every subset of the plane is in the σ-algebra generated by the abstract rectangles. For example, Kunen in his Ph.D. thesis [9] showed this is true after a finite support iteration of Cohen forcing of length ω_{2} over a model of GCH. QED

Remark 2.8. Theorem 4.8 and Proposition 6.16 each show that if 𝔭 = 𝔠, then there is a universal function at level 2.

Question 2.9. Suppose that there is a universal function of Baire class α. Then is there a universal function of level α?

The techniques of Miller [18] can be used to produce models with an analytic universal function (that is, a universal function which is analytic), but no Borel universal function.

3. Universal functions and Martin’s Axiom

Proposition 6.16 below shows that if Martin’s Axiom holds then there are universal functions on the reals of Baire class 2. Here we show that the axiom MA_{ℵ_{1}} (the restriction of MA to collections of ℵ_{1} many dense sets) is not strong enough for this result.

The following lemma will be our tool for showing that a given function is not universal.

Lemma 3.1. Let F: 2^{ω} × 2^{ω} → 2^{ω} be a function, and suppose that there exist S_{y,z} ⊆ 2^{ω} (y, z ∈ 2^{ω}) such that

(1) each S_{y,z} is a subset of 2^{ω} containing {y, z} and closed under F;

(2) no S_{y,z} contains 2^{ω}; (3) for each function h: 2^{ω} → 2^{ω} there exist y, z ∈ 2^{ω} such that

{h(y), h(z)} ⊆ S_{y,z}. Then F is not universal.

Proof Let G: 2^{ω} × 2^{ω} → 2^{ω} be such that each value G(y, z) is an element of 2^{ω} \ S_{y,z}. Then for each h: 2^{ω} → 2^{ω} it is possible to find reals y and z such that {h(y), h(z)} ⊆ S_{y,z}. Since S_{y,z} is closed under F, F (h(y), h(z)) ∈ S_{y,z}. Since G(y, z) ∉ S_{y,z}, it follows that F (h(y), h(z)) ≠ G(y, z), so F is not universal. QED

Combined with Lemma 3.1, Theorem 3.3 below shows that if there is a model of set theory then there is a model of set theory in which there is no analytic universal function on the reals. First we note a general combinatorial fact, which is a generalization of one of Sierpiński’s characterizations of the failure of the Continuum Hypothesis (see [30]). In our first application of the lemma, δ will be ω; in the second it will be an arbitrary uncountable cardinal. We let P_{κ}(λ) denote the collection of subsets of λ of cardinality less than κ.

Lemma 3.2. Suppose that δ and κ are cardinals with κ > δ^{+}, and let f: κ × κ → κ be injective. Then for each function H: κ → P_{δ^{+}}(κ) there exist α < δ^{+} and β ∈ κ such that f(α, β) ∉ H(α) ∪ H(β).

Proof Choose β ∈ κ such that, for all α < δ^{+}, f(α, β) ∉ H(α). Now choose α < δ^{+} such that f(α, β) ∉ H(β). QED

The proofs of following theorems apply to any class of functions with the property that for each F in the class there exists a set of ordinals x of cardinality less than κ with the property that every inner model with x as a member is closed under F.

Theorem 3.3. Suppose that κ > ω_{1} is a cardinal of uncountable cofinality. Then there is no analytic universal function on 2^{ω} in any model obtained by forcing with a finite support product of κ many nontrivial c.c.c. partial orders.

Proof Let ℙ_{α} be a c.c.c. partial order for each α ∈ κ and suppose that

G ⊆ ∏_{α∈κ} ℙ_{α}

is generic over V. Since infinite finite-support products of nontrivial partial orders add reals, by grouping together products of countably many ℙ_{α}’s we may assume that each ℙ_{α} adds a real. We work in V [G]. Let F: 2^{ω} × 2^{ω} → 2^{ω} be analytic, and let x ∈ 2^{ω} be a code for F.

For each β ∈ κ, let G_{β}^{∗} denote the restriction of G to ∏_{α∈κ\{β}} ℙ_{α}. Since ∏_{α∈κ} ℙ_{α} is c.c.c., each real is in V [G_{β}^{∗}] for all but countably many β ∈ κ. Fix X ⊆ 2^{ω} with |X| = κ, and let f: X × X → κ be injective with the property that {x, y, z} ⊆ V [G_{f(y,z)}^{∗}] for each pair (y, z) ∈ X × X. Define S_{y,z} ⊆ 2^{ω} for each y, z ∈ 2^{ω} by setting

S_{y,z} = 2^{ω} ∩ V [G_{f(x,y)}^{∗}]

whenever (y, z) ∈ X × X, and letting S_{y,z} = {y, z} otherwise. Then item (1) of Lemma 3.1 clearly holds, and item (2) follows from the fact that each ℙ_{α} adds a real.

To see that (3) holds, fix a function h: 2^{ω} → 2^{ω}. Applying the c.c.c. of ∏_{α∈κ} ℙ_{α} we can find a function H: X → P_{ℵ_{1}}(κ) such that, for each y ∈ X, h(y) ∈ V [G ↾ ∏_{α∈H(y)} ℙ_{α}]. Applying Lemma 3.2, we can find y, z ∈ X such that f(y, z) ∉ H(y) ∪ H(z), which means that {h(y), h(z)} ⊆ S_{y,z}. QED

Theorem 3.4. Suppose that λ and κ are uncountable cardinals such that λ^{+} < κ, κ^{λ} = κ and κ has uncountable cofinality. Then there is a c.c.c. forcing extension in which 𝔠 = κ, MA_{λ} holds and there is no analytic universal function.

Proof Let ℙ be a finite support product of c.c.c. partial orders ℙ_{α} (α < κ), such that each ℙ_{α} has cardinality at most λ and adds a real. Let G ⊆ ℙ be a V -generic filter, and, for each X ⊆ κ, let G_{X} be the restriction of G to ∏_{α∈X} ℙ_{α}. For each α < κ, let G_{α}^{∗} denote G_{κ\{α}}, and let a_{α} be an element of (2^{ω} ∩ V [G]) \ V [G_{α}^{∗}].

Working in V [G], let ℚ be the direct limit of a finite support iteration ⟨ℚ_{α}, Ṙ_{α} : α < κ⟩ of c.c.c. partial orders on λ, such that ℚ forces MA_{λ}. For each X ⊆ κ, let ℚ_{X} be the subiteration of ℚ consisting of those Ṙ_{α}’s which depend only on ∏_{α∈X} ℙ_{α} (as opposed to all of ℙ) and the initial segment of ℚ_{X} before stage α. Since ℙ ∗ ℚ is in V, each ℚ_{X} is in V [G_{X}] and regularly embeds into ℚ. Furthermore, each Ṙ_{α} (and each countable set of Ṙ_{α}’s) is part of ℚ_{X} for some X ⊆ κ of cardinality λ.

Let K be V [G]-generic filter for ℚ, and for each X ⊆ κ, let K_{X} be the restriction of K to ℚ_{X}. For each α ∈ κ, let K_{α}^{∗} denote K_{κ\{α}}.

Then every element of 2^{ω} in V [G][K] is in V [G_{X}][K_{X}] for some X ⊆ κ of cardinality λ. By mutual genericity, no a_{α} is in V [G_{α}^{∗}][K_{α}^{∗}].

Now suppose that F is an analytic function in V [G][K], coded by some x ∈ 2^{ω}. Fix X ⊆ κ of cardinality λ such that x is in V [G_{X}][K_{X}]. Let

i: {a_{α} : α ∈ κ}^{2} → {a_{α} : κ \ X}

be an injection such that {a_{α}, a_{β}} ⊆ V [G_{i(a_{α},a_{β})}^{∗}][K_{i(a_{α},a_{β})}^{∗}] for all α, β ∈ κ. Let S_{y,z} = 2^{ω} ∩V [G_{i(y,z)}^{∗}][K_{i(y,z)}^{∗}], for each pair (y, z) ∈ {a_{α} : α ∈ κ}^{2}, and let S_{y,z} = {y, z} for all other pairs (y, z) from 2^{ω} × 2^{ω}. Then items (1) and (2) of Lemma 3.1 are clearly satisfied.

Fix a function h: 2^{ω} → 2^{ω}. For each α ∈ κ, we have a set H(α) ⊆ κ of size λ, containing X, such that h(α) is in V [G_{H(α)}][K_{H(α)}]. By Lemma 3.2, there are α and β in κ such that i(a_{α}, a_{β}) is not equal to a_{γ} for any γ ∈ H(α) ∪ H(β). It follows that {h(a_{α}), h(a_{β})} ⊆ S_{a_{α},a_{β}}. Then item (3) of Lemma 3.1 is satisfied, showing that F is not universal in V [G][K]. QED

4. Universal functions of special kinds

Elementary functions in the calculus of two variables can be obtained from addition, the elementary functions of one variable and closing under composition. For example, xy = \frac{1}{2}((x+y)^{2} −x^{2} −y^{2}). We might ask if there could be a universal function which uses addition.

Proposition 4.1. Suppose that U : 2^{ω} × 2^{ω} → 2^{ω} is a universal function. Then there is a universal function F (x, y) = k(x + y), where k : 2^{ω} → 2^{ω} has the same Borel complexity as U and x + y refers to pointwise addition in 2^{ω}.

Proof Given any u ∈ 2^{ω} let u_{0} be u shifted onto the even coordinates, i.e, u_{0}(2n) = u(n) and u_{0}(2n + 1) = 0. Similarly for v ∈ 2^{ω} let v_{1} be v shifted onto the odd coordinates. Note that (u, v) is easily recovered from u_{0} + v_{1}. Hence we can define k by k(w) = U(u, v) where w = u_{0} + v_{1}. Then, given H : 2^{ω} × 2^{ω} → 2^{ω} there is g : 2^{ω} → 2^{ω} such that H(u, v) = U(g(u), g(v)). Let g_{0}(x) = (g(x))_{0} and g_{1}(x) = (g(x))_{1}. Then H(u, v) = U(g(u), g(v)) = k((g(u))_{0} + (g(v))_{1}) = F (g_{0}(u), g_{1}(v)). Now apply Remark 1.1. QED

Proposition 4.3 gives a generalization of the result above which applies, for example, to any Borel subgroup of a Polish group or even a Borel subsemigroup of a Polish cancellation^{3} semigroup. First we prove a general result about Borel binary operations. We say that a binary operation * on a set B is separately one-to-one if for every x, y, z ∈ B, if x ∗ y = x ∗ z or y ∗ x = z ∗ x then y = z.

Lemma 4.2. Suppose that ∗ is a Borel binary operation on an uncountable Borel B ⊆ 2^{ω}, and that ∗ is separately one-to-one. Then there exist perfect subsets P_{1}, P_{2} of B such that ∗ is one-to-one and continuous on P_{1} × P_{2}.

Proof Let Q ⊆ B be a perfect set. Let M be the transitive collapse of a countable elementary substructure X of H(𝔠^{+}) which contains reals coding Q and (B, ∗). Let T ⊆ 2^{<ω} be the tree whose infinite branches are the elements of Q. Forcing with T is equivalent to forcing with the poset 2^{<ω}. It is well-known (see [4], where it is credited to Folklore) that there is a countable partial order forcing a perfect set P ⊆ Q with the property that every finite sequence of distinct elements (x_{1}, …, x_{n}) of P is T^{n}-generic. Let P be such a generic set over M, and let P_{1} and P_{2} be any pair of disjoint perfect subsets of P.

To see that ∗ is continuous on P_{1} × P_{2} suppose that (x_{1} ∗ x_{2})↾n = s. Then there must be m such that (x_{1}↾m, x_{2}↾m) forces in T^{2} that (g_{1} ∗ g_{2})↾n = s where g_{1} and g_{2} are the generic reals added by T^{2}. It follows that (x′_{1} ∗ x′_{2})↾n = s for all (x′_{1}, x′_{2}) in P_{1} × P_{2} which agree with (x_{1}, x_{2}) up to m.

To see that ∗ is one-to-one on P_{1} × P_{2}, suppose that

z = x_{1} ∗ x_{2} = x′_{1} ∗ x′_{2}.

Since P_{1} and P_{2} are disjoint and ∗ is separately one-to-one, either (x_{1}, x_{2}) and (x′_{1}, x′_{2}) are the same pair or all four reals are distinct. If all four are distinct, then ((x_{1}, x_{2}), (x′_{1}, x′_{2})) is T^{2} × T^{2}-generic over M. A well-known lemma on product forcing (see page 13 of Solovay [31]) gives that in this case,

M[x_{1}, x_{2}] ∩ M[x′_{1}, x′_{2}] = M,

so z ∈ M. Then there exists an n ∈ ω such that (x_{1}↾n, x_{2}↾n) forces in T^{2} that g_{1} ∗ g_{2} = z. Since P_{2} is perfect, there exists a y ∈ P_{2} \ {x_{2}} for which y↾n = x_{2}↾n. This contradicts our assumption that ∗ is separately one-to-one. QED Proposition 4.3. Suppose that U : 2^{ω} × 2^{ω} → 2^{ω} is a universal function, and (B, ∗) consists of an uncountable Borel set with a Borel binary operation * on B which is separately one-to-one. Then there exists a function F : B → 2^{ω} such that for each g : 𝔠 × 𝔠 → 2^{ω} there exist h, k mapping 𝔠 to B with

3A semigroup is a cancelation semigroup if it satisfies that for all a, b and c, if ac = bc then a = b.

g(α, β) = F (h(α) ∗ k(β)) for all α, β ∈ 𝔠

Furthermore, if U is Borel then F can be taken to have the same Borel rank as U.

Proof Fix P_{1} and P_{2} as in the conclusion of Lemma 4.2. Let R be the range of the binary operation ∗, so that ∗ : P_{1} × P_{2} → R is a homeomorphism. Let f_{1}, f_{2} be the continuous functions with domain R such that f_{1}(x ∗ y) = x and f_{2}(x∗y) = y. Since P_{1} and P_{2} are each homeomorphic to 2^{ω} we may assume without loss of generality that U : P_{1}×P_{2} → 2^{ω}. Define F: B → 2^{ω} by setting F (z) = U(f_{1}(z), f_{2}(z)) if z ∈ R and F (z) = 0 otherwise. Then F (x ∗ y) = U(x, y) for each (x, y) ∈ P_{1} × P_{2}. To verify that F is universal, fix an arbitrary function g : 𝔠 × 𝔠 → 2^{ω}. Since U is universal there are h : 𝔠 → P_{1} and k : 𝔠 → P_{2} such that g(α, β) = U(h(α), k(β)) for all α, β ∈ 𝔠. Then F (h(α) ∗ k(β)) = U(h(α), k(β)) = g(α, β) for all such α, β. QED

The following proposition shows that functions which are universal with respect to symmetric functions can have a simpler form.

Proposition 4.4. Suppose that F : 2^{ω} × 2^{ω} → 2^{ω} is a universal function. Then there exists a function f : 2^{ω} → 2^{ω} such that for each symmetric function H : 2^{ω} × 2^{ω} → 2^{ω} there exists a function g : 2^{ω} → 2^{ω} such that H(x, y) = f(g(x) + g(y)) for every two distinct x, y ∈ 2^{ω}. Furthermore if F is Borel, then f can be taken to be Borel.

Proof Let P_{s} ⊆ ω for s ∈ 2^{<ω} partition ω into infinite sets. Given s ∈ 2^{<ω}, we say that y : P_{s} → 2 codes x : ω → 2 if y(a_{n}) = x(n) where a_{0} < a_{1} < a_{2} < … is the increasing listing of P_{s}.

Define q: 2^{ω} → 2^{ω} by letting q(x) be such that q(x)↾P_{x↾n} codes x for every n < ω and q(x)↾P_{s} is identically 0 for any s which is not an initial segment of x.

Notice that it is possible to recover u and v from q(u) + q(v) as long as neither u nor v is the constant 0 function. To see this let

Σ = {s ∈ 2^{<ω} : ∃n ∈ P_{s} (q(u) + q(v))(n) ≠ 0}.

Suppose that u(m) ≠ v(m) and recall that neither u nor v is identically zero. Then for every s ∈ Σ of length greater than m, exactly one of the following must hold:

• q(v)↾P_{s} is identically zero and (q(u) + q(v))↾P_{s} codes u;

• q(u)↾P_{s} is identically zero and (q(u) + q(v))↾P_{s} codes v.

In other words, for sufficiently large values of s the uncoding of

(q(u) + q(v))↾P_{s}

will take on only one of two possible values and these two values will be u and v.

Using this, f(w) is defined as follows. If there are distinct, non-zero, u and v such that w = q(u) + q(v) then these are unique. In this case define f(w) = F (u, v) where u < v (for the sake of avoiding arbitrary choices in the definition). Otherwise, define f(w) to be the constant 0 function. If F is Borel, then f can be defined in a Borel way, although its rank might increase.

To see that this definition works, let a symmetric function

H : 2^{ω} × 2^{ω} → 2^{ω}

be given. By assumption there exists h such that

H(x, y) = F (h(x), h(y))

for all x, y ∈ 2^{ω}. Without loss of generality we may assume that h is one-to-one and h(x) is not equal to the constant 0 function for any x. To see this, note that we may replace any h with ĥ(x) = ⟨1^{⌢}x, h(x)⟩ and then alter F so that it ignores the first coordinate of ĥ(x); that is, define

F_{0}(⟨u_{0}, u_{1}⟩, ⟨v_{0}, v_{1}⟩) = F (u_{1}, v_{1}).

Now let g = q ∘ h. Then f(g(x) + g(y)) = f(q(h(x)) + q(h(y))) and keep in mind that h(x) and h(y) are non-zero and distinct. Hence f(q(h(x)) + q(h(y))) = F (h(x), h(y)) = H(x, y) as required. Note that the symmetry of H allowed the arbitrary choice of ordering of u and v in the definition of f. QED

The proof of the following result is similar to Mansfield and Rao’s proof [12, 13, 23] that the universal analytic set in the plane is not in the σ-algebra generated by rectangles with measurable sides. See also Miller [19].

Proposition 4.5. There does not exist a Borel function

F : 2^{ω} × 2^{ω} → 2^{ω}

such that for every Borel G : 2^{ω} × 2^{ω} → 2^{ω} there exist functions h and k from 2^{ω} to 2^{ω} such that k is Borel and

G(x, y) = F (h(x), k(y))

for all x, y ∈ 2^{ω}.

Proof Let F: 2^{ω} × 2^{ω} → 2^{ω} be a Baire class α function, let U ⊆ 2^{ω} × 2^{ω} be a universal Σ_{α+1}^{0} set and let G be the characteristic function of U. Suppose that h and k are functions from 2^{ω} to 2^{ω} such that k is Borel and

G(x, y) = F (h(x), k(y))

for all x, y ∈ 2^{ω}. Let P ⊆ 2^{ω} be a perfect set on which k is continuous, and fix x_{0} so that U_{x_{0}} ⊆ P and U_{x_{0}} is not Δ_{α+1}^{0}. If we define q : P → 2^{ω} by setting q(y) = F (h(x_{0}), k(y)), then then q is Baire class α and U_{x_{0}} = q^{−1}(1), giving a contradiction. QED

Remark 4.6. The second author has recently shown that consistently the Borel subsets of the plane are not in contained any bounded level of the σ-algebra generated by the abstract rectangles. The proof of Theorem 2.5 shows that in this situation, there does not exist a Borel function

F : 2^{ω} × 2^{ω} → 2^{ω}

such that for every Borel H : 2^{ω} × 2^{ω} → 2^{ω} there exist functions g and h from 2^{ω} to 2^{ω} such that

H(x, y) = F (g(x), h(y))

for all x, y ∈ 2^{ω}. The proof is a modification of arguments in [17].

The following type of universal function was introduced by Stevo Todorcevic.

Definition 4.7. Given a cardinal κ and k ∈ ω, a sequence of continuous functions

F_{n}: (2^{ω})^{k} → 2^{ω} (n < ω)

is κ limit-universal if for each X ⊆ 2^{ω} of cardinality at most κ and each function G: X^{k} → 2^{ω} there exists an injective function h: X → 2^{ω} such that for all x_{1}, …, x_{k} ∈ X,

G(x_{1}, …, x_{k}) = lim_{n→∞} F_{n}(h(x_{1}), …, h(x_{k})).

Theorem 4.8 (Todorcevic [32]). For each k ∈ ω, there exists a 𝔭 limit-universal sequence of functions F_{n}: (2^{ω})^{k} → 2^{ω}, for n < ω.

Remark 4.9. In the model from Theorem 3.3, 𝔭 = ℵ_{2} and 𝔠 = ℵ_{3}.

Recall that a function F: 2^{ω} × 2^{ω} → 2^{ω} being of level 2 means that for every n ∈ ω the set {(x, y) : F (x, y)(n) = 1} is F_{σ}. The following proposition shows that the existence of a 𝔠 limit-universal sequence of functions is equivalent to the existence of a level 2 universal function.

Proposition 4.10. For any cardinal κ the following are equivalent:

(1) There exists continuous functions F_{n} : 2^{ω} × 2^{ω} → 2^{ω} (n < ω) with the property that for each function G : κ × κ → 2^{ω} there exists a function h : κ → 2^{ω} such that

G(α, β) = lim_{n→∞} F_{n}(h(α), h(β))

for all α, β ∈ κ.

(2) There exists a level 2 function F : 2^{ω} ×2^{ω} → 2^{ω} with the property that for each function G : κ×κ → 2^{ω} there exists a function h : κ → 2^{ω} such that

G(α, β) = F (h(α), h(β))

for all α, β ∈ κ.

Proof

(1) → (2). Given the sequence of continuous functions F_{n} : 2^{ω} × 2^{ω} → 2^{ω} (n < ω) define F : 2^{ω} × 2^{ω} → 2^{ω} by setting F (x, y)(k) = 1 if and only if F_{n}(x, y)(k) = 1 for all but finitely many n < ω.

(2) → (1). Using a continuous pairing function ⟨·, ·⟩ on 2^{ω} ×2^{ω}, define for each k ∈ ω the pair of (nondisjoint) F_{σ} subsets of 2^{ω}, P_{k}^{0} and P_{k}^{1}, by setting

(⟨u_{0}, u_{1}⟩, ⟨v_{0}, v_{1}⟩) ∈ P_{k}^{i}

if and only if F (u_{i}, v_{i})(k) = 1. By the reduction property for F_{σ} sets, for each k ∈ ω there exist disjoint F_{σ} sets Q_{k}^{0}, Q_{k}^{1} with Q_{k}^{i} ⊆ P_{k}^{i} and Q_{k}^{0} ∪ Q_{k}^{1} = P_{k}^{0} ∪ P_{k}^{1}. Write each Q_{k}^{i} as an increasing sequence of closed sets Q_{k}^{i} = ⋃_{n∈ω} C_{k,n}^{i}. For each n, k ∈ ω, C_{k,n}^{0} and C_{k,n}^{1} are disjoint closed sets, so there exists a clopen set D_{k,n} with C_{k,n}^{0} ⊆ D_{k,n} and C_{k,n}^{1} disjoint from D_{k,n}.

Define the continuous map F_{n}: 2^{ω} × 2^{ω} → 2^{ω} by setting

F_{n}(u, v)(k) = 1

if and only if (u, v) ∈ D_{k,n}. Now we verify that this works. Given G: κ × κ → 2^{ω}, let G_{0} be G and define G_{1} : κ × κ → 2^{ω} by setting G_{1}(α, β)(n) = 1 − G_{0}(α, β)(n) (that is, we switch 0 and 1 on every coordinate of the output). Let h_{0} and h_{1} be the results of applying (2) to G_{0} and G_{1}, respectively. We have then that for every k ∈ ω and all α, β < κ, • G(α, β)(k) = 1 implies

F (h_{0}(α), h_{0}(β))(k) = 1 and F (h_{1}(α), h_{1}(β))(k) = 0

• G(α, β)(k) = 0 implies

F (h_{0}(α), h_{0}(β))(k) = 0 and F (h_{1}(α), h_{1}(β))(k) = 1

Define h: 2^{ω} → 2^{ω} by setting h(γ) = ⟨h_{0}(γ), h_{1}(γ)⟩. Then for all α, β < κ and all k ∈ ω the following hold.

• If G(α, β)(k) = 1, then (h(α), h(β)) ∈ P_{k}^{0} \P_{k}^{1} so (h(α), h(β)) ∈ Q_{k}^{0} and F_{n}((h(α), h(β)))(k) = 1 for all but finitely many n.

• If G(α, β)(k) = 0, then (h(α), h(β)) ∈ P_{k}^{1} \P_{k}^{0} so (h(α), h(β)) ∈ Q_{k}^{1} and F_{n}((h(α), h(β)))(k) = 0 for all but finitely many n.

QED

Davies [6] showed that the Continuum Hypothesis is equivalent to the assertion that the function

F (x⃗, y⃗) = ∑_{n<ω} x_{n}y_{n}

has the following universal property: for every H : ℝ × ℝ → ℝ there are functions f_{n}, g_{n} for n < ω such that

H(x, y) = ∑_{n<ω} f_{n}(x)g_{n}(y)

for all x, y ∈ ℝ. Moreover, the functions f_{n} and g_{n} (n < ω) can be taken so that the sum ∑_{n<ω} f_{n}(x)g_{n}(y) has only finitely many nonzero terms. If this requirement is relaxed to ordinary convergence of the infinite sum, then the function F (x⃗, y⃗) = ∑_{n<ω} x_{n}y_{n} is still universal under the assumption 𝔭 = 𝔠 (Shelah [27]). However, it is not universal after adding ℵ_{2} many Cohen reals with finite support ([27]). These considerations suggest the following context for studying universal functions. Let (𝔹, ·) be a Banach algebra and ψ ∈ 𝔹^{∗}. The linear functional ψ can be said to be κ-universal if for every f : κ × κ → ℝ there are h : κ → 𝔹 and g : κ → 𝔹 such that f(α, β) = ψ(h(α) · g(β)). This will be examined elsewhere.

5. Abstract universal functions

This section considers the question of universal functions without regard to any definability properties. The notion of universal function naturally generalizes to functions of the form F : α × β → γ.

Theorem 5.1. If α and κ are cardinals such that α^{<κ} = κ, then there is a universal function from κ × κ to α.

Proof

Let F be the set of functions f: κ → α for which {γ < κ | f(γ) ≠ 0} is a bounded subset of κ. Then |F| = α^{<κ} = κ. Define U: (κ×F)^{2} → α by setting

U((γ, f_{1}), (β, f_{2})) = \{ \begin{matrix}f_{1}(β) & if β < γ \\ f_{2}(γ) & if γ ≤ β \end{matrix}

By Remark 1.1, it is enough to show that for each g: κ × κ → α there exist h: κ → (κ × F) and k: κ → (κ × F) such that

U(h(γ), k(β)) = g(γ, β)

for all γ, β in κ. Fix g: κ × κ → α. Define h: κ → (κ × F) by setting h(γ) = (γ, f_{1,γ}), where f_{1,γ}: κ → α is such that f_{1,γ}(β) is g(γ, β) for all β < γ and 0 for all β ≥ γ. Define k: κ → (κ × F) by setting k(β) = (β, f_{2,β}), where f_{2,β}: κ → α is such that f_{2,β}(γ) is g(γ, β) for all γ ≤ β and 0 for all γ > β.

Now fix γ, β in κ. If γ > β, then U(h(γ), k(β)) = f_{1,γ}(β) = g(γ, β). If γ ≤ β, then U(h(γ), k(β)) = f_{2,β}(γ) = g(γ, β). QED

It follows from Theorem 5.1 that if κ^{<κ} = κ, then there is a universal function U : κ × κ → κ. So, for example, there is a universal function from ω × ω to ω. If κ^{<κ} = κ, then κ must be a regular cardinal. Theorem 5.1 implies that if κ is strong limit cardinal, then for every α < κ there is a universal function from κ × κ to α. However we don’t know the answer to the following question:

Question 5.2. If κ is a singular strong limit cardinal, does there exist a universal function from κ × κ to κ?

Proposition 5.3. Suppose that κ is a singular strong limit cardinal and that α < κ. Then there is a universal function U : κ × α → κ if and only if α is less than the cofinality of κ.

Proof Let τ be the cofinality of κ. If α < τ, then there are only κ many maps from α into κ, so U just needs to list all of them as a cross section U_{β}(·) = U(β, ·) for β < κ.

If α ≥ τ, we can diagonalize against any U by eventually avoiding the range of any cross section. To see this suppose U : κ × α → κ is any map. Let κ_{δ} for δ < τ be increasing and cofinal in κ. Construct a map d : τ → κ so that

d(δ) ∈ κ \ { U(β, γ) : β < κ_{δ}, γ < α}.

The map f : κ × τ → κ defined by f(β, δ) = d(δ) witnesses that U is not universal. QED

The following proposition, which also applies to singular cardinals, shows that a negative answer to Question 5.2 for κ = ℵ_{ω} must use maps with domain at least ω_{1} × ω. Its proof is similar to the proof of Theorem 5.1.

Proposition 5.4. For each infinite cardinal κ there exists a function U : κ × κ → κ such that for each G : ω × ω → κ there exists a function h : ω → κ such that G(n, m) = U(h(n), h(m)) for all n, m ∈ ω.

Proof Let

F = {F : ω → κ : ∀^{∞}n F (n) = 0}

Define U : (ω × F)^{2} → κ by

U((n, F_{1}), (m, F_{2})) = \{ \begin{matrix}F_{1}(m) & if n > m \\ F_{2}(n) & if n ≤ m \end{matrix}

Given any G define h(n) = (n, F_{n}) where F_{n} ∈ F has the property that F_{n}(m) = G(n, m) whenever m ≤ n. Define k(m) = (m, F′_{m}) where F′_{m} ∈ F has the property that F_{m}(n) = G(n, m) whenever n ≤ m. Then

• for any n ≤ m U(h(n), k(m)) = F′_{m}(n) = G(n, m) and
• for any n > m U(h(n), k(m)) = F_{n}(m) = G(n, m).

As usual we may encode distinct h, k into a single map. QED

The following theorem shows that it is relatively consistent with ZFC that there is no universal function F: 𝔠 × 𝔠 → 2. Given sets X, Y and a cardinal κ, the partial order Fn(X, Y, κ) consists of partial functions from X to Y of cardinality less than κ, ordered by inclusion.

Theorem 5.5. If 𝔠 = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2}, then the partial order

Fn(ω_{3}, 2, ω_{1}) × Fn(ω_{2}, 2, ω)

forces that 𝔠 = ℵ_{2} and that there is no F: ω_{2}×ω_{2} → 2 with the property that for every f : ω_{2}×ω_{1} → 2 there exists g_{1} : ω_{2} → ω_{2} and g_{2} : ω_{1} → ω_{2} such that f(α, β) = F (g_{1}(α), g_{2}(β)) for every α < ω_{2} and β < ω_{1}.

Proof

Suppose that 𝔠 = ℵ_{1} and 2^{ℵ_{1}} = ℵ_{2}. Force with Fn(ω_{3}, 2, ω_{1}) followed by Fn(ω_{2}, 2, ω). Let G be Fn(ω_{3}, 2, ω_{1})-generic over V and H be Fn(ω_{2}, 2, ω)-generic over V [G]. We will show there is no such F as above in the model V [G][H].

By standard arguments^{4} involving iteration and product forcing we may regard V [G][H] as being obtained by forcing with Fn(ω_{3}, 2, ω_{1})^{V} over the ground model V [H]. Of course, in V [H] the poset Fn(ω_{3}, 2, ω_{1})^{V} is not countably closed but it still must have the ω_{2}-cc. Hence for any F : ω_{2} × ω_{2} → 2 in V [G][H] we may find γ < ω_{3} such that F ∈ V [H][G↾γ].

Use G above γ to define f : ω_{2} × ω_{1} → 2, i.e.,

f(α, β) = G(γ + ω_{1} · α + β).

Suppose towards a contradiction that in V [G][H] there were functions g_{1} : ω_{2} → ω_{2} and g_{2} : ω_{1} → ω_{2} such that f(α, β) = F (g_{1}(α), g_{2}(β)) for every α < ω_{2} and β < ω_{1}. Using the ω_{2}-chain condition of Fn(ω_{3}, 2, ω_{1}) × Fn(ω_{2}, 2, ω), there would be an I ⊆ ω_{3} in V of size ω_{1} such that g_{2} ∈ V [H][G↾(γ ∪ I)]. Choose α_{0} < ω_{2} so that γ ∪ I is disjoint from

D = {γ + ω_{1} · α_{0} + β : β < ω_{1}}.

It easy to see by a density argument that the function G↾D is not in V [H][G↾(γ ∪ I)]. But this is a contradiction, since G↾D is easily defined from the function f(α_{0}, ·), f(α_{0}, β) = F (g_{1}(α_{0}), g_{2}(β)) for all β, and F, g_{2} are in V [H][G↾(γ ∪ I)]. QED

Question 5.6. Is it consistent with 2^{<𝔠} > 𝔠 to have a universal function F : 2^{ω} × 2^{ω} → 2^{ω}? What about a Borel F?

The two following propositions illustrate two cases where a universal function with range κ can be lifted to one with range κ^{+}.

Proposition 5.7. For any infinite cardinal κ, there is a universal

F : κ^{+} × κ^{+} → κ^{+}

if and only if there is a universal function G : κ^{+} × κ^{+} → κ.

Proof The forward direction follows from Remark 1.4. For the reverse direction, suppose that we are given a universal G : κ^{+} × κ^{+} → κ. For each α < κ^{+} let b_{α}: κ → α be a bijection. Define F : κ^{+} × κ^{+} → κ^{+} by setting

F (⟨α_{1}, α_{2}, α_{3}⟩, ⟨β_{1}, β_{2}, β_{3}⟩) = \{ \begin{matrix}b_{β_{3}}(G(α_{2}, β_{2})) & if α_{1} ≤ β_{1} \\ b_{α_{3}}(G(α_{2}, β_{2})) & if α_{1} > β_{1} \end{matrix}

4Kunen[10] p.253, Solovay [31] p.10

where ⟨a, b, c⟩ represents a bijection between an infinite set and its triples, or, equivalently, ⟨a, b, c⟩ is defined to be ⟨⟨a, b⟩, c⟩. To see that F is universal, fix a function f : κ^{+} × κ^{+} → κ^{+}. Let j : κ^{+} → κ^{+} be such that f(α, β) < j(max(α, β)) for all α, β < κ^{+}. Define f^{∗} : κ^{+} × κ^{+} → κ by setting f^{∗}(α, β) = ξ, where ξ < κ is such that f(α, β) = b_{j(max(α,β))}(ξ). As G is universal, there exists a function h: κ^{+} → κ^{+} such that

f^{∗}(α, β) = G(h(α), h(β))

for all α, β < κ^{+}. This means that for all α, β < κ^{+},

f(α, β) = b_{j(max(α,β))}(G(h(α), h(β))).

It follows that for all α, β < κ^{+},

f(α, β) = F (⟨α, h(α), j(α)⟩, ⟨β, h(β), j(β)⟩).

QED

Proposition 5.8. For any pair of infinite cardinals κ > λ, there is a universal function from κ×λ to λ if and only if there is one from κ×λ to λ^{+}.

Proof Again, the reverse direction follows from Remark 1.4. For the forward direction, let F : κ × λ → λ be a universal function and fix bijections j_{α} : λ → α, for each α in the interval [λ, λ^{+}). Construct F′ with the property that for each pair α ∈ κ, β ∈ λ^{+} there exists a γ < κ such that F′_{γ} = j_{β} ∘ F_{α}, i.e.,

F′(γ, δ) = j_{β}(F (α, δ)) for all δ < λ.

Now we verify that F′ is universal. Let f′ : κ × λ → λ^{+} be arbitrary. For each α < κ, let

ι_{α} = λ + sup{f′(α, δ) + 1 : δ < λ}.

Define f into λ by f(α, δ) = j_{ι_{α}}^{−1}(f′(α, δ)). Since F is universal there exist g, h with

F (g(α), h(δ)) = f(α, δ) = j_{ι_{α}}^{−1}(f′(α, δ))

for all (α, δ) ∈ κ × λ. By our definition of F′ we may construct g′ so that

F′(g′(α), h(δ)) = j_{ι_{α}}(F (g(α), h(δ)))

for all (α, δ) ∈ κ × λ. Then we are done, since

j_{ι_{α}}(F (g(α), h(δ))) = f′(α, δ)

for all (α, δ) ∈ κ × λ.

QED

The following theorem connects the existence of universal functions on κ × κ with finite range to the existence of universal graphs.

Theorem 5.9. For any infinite cardinal κ the following are equivalent:

(1) For each n ∈ ℕ there is a universal function from κ × κ to n.

(2) For some n ∈ ℕ with n ≥ 2 there is a universal function from κ × κ to n.

(3) There is a symmetric, irreflexive function from κ × κ to 2 universal for all symmetric, irreflexive functions from κ × κ to 2; in other words, there is a symmetric, irreflexive function U : κ × κ → 2 such that for any symmetric, irreflexive function f : κ × κ → 2 there is h : κ → κ such that f(ξ, η) = U(h(ξ), h(η)) for all ξ and η.

(4) There is a universal graph on κ; in other words, there is a graph G whose vertex set is κ such that for any other graph G^{∗} with vertex set κ there is a graph embedding of G^{∗} into G.

Proof Statement (1) clearly implies statement (2); (2) implies (1) by Remark 1.4 and Proposition 1.5 (with finite exponent). To get from (2) to (3), given a universal function U : κ × κ → n, define

V (α, β) = \{ \begin{matrix}1 & if α ≠ β and either U(α, β) = 1 or U(β, α) = 1 \\ 0 & otherwise \end{matrix}

Then V is universal in the sense of (3). Statements (3) and (4) are equivalent since the characteristic function of a graph is symmetric and irreflexive and Remark 1.2 is still in effect.

It remains only to show that one of (3) and (4) implies one of (1) and (2). We give a proof of (1) from (3). Fix n ∈ ω with n ≥ 2, and let Ψ : κ → [κ]^{n} be a bijection. If U : κ × κ → 2 is a function universal for symmetric functions, define U^{∗} : κ × κ → n by letting U^{∗}(α, β) be

( max_{ξ∈Ψ(α)} ∑_{η∈Ψ(β)} U(ξ, η)) − 1

if this quantity is nonnegative, and 0 otherwise. To see that U^{∗} is universal for functions from κ × κ to n, fix F: κ × κ → n. Let {E_{ξ}}_{ξ∈κ} be a partition of κ into sets of size n. We construct a symmetric function F^{∗} from κ × κ to 2 so that for each α, β ∈ κ

F (α, β) = (max_{ξ∈E_{α}} ∑_{η∈E_{β}} F^{∗}(ξ, η)) − 1.

We can realize F^{∗} as the characteristic function of a graph. For each α ∈ κ, let α^{∗} denote min(E_{α}). Construct the graph on each of the pairwise disjoint pieces E_{α}×E_{β} by connecting α^{∗} to F (α, β)+1 elements of E_{β} including β^{∗} and connecting β^{∗} to exactly F (β, α) + 1 elements of E_{α}. The “plus one” is so that the two minimum elements can always be connected.

Let g : κ → κ be one-to-one (see Remark 1.2) such that

U(g(α), g(β)) = F^{∗}(α, β)

for all α, β in κ. Define H : κ → κ by setting each H(ξ) = Ψ^{−1}g[E_{ξ}]. Then for each α, β in κ,

F (α, β) = (max_{ξ∈E_{α}} ∑_{η∈E_{β}} F^{∗}(ξ, η)) − 1 = (max_{ξ∈E_{α}} ∑_{η∈E_{β}} U(g(ξ), g(η))) − 1,

which, as g is one-to-one, is equal to (max_{ξ∈g[E_{α}]} ∑_{η∈g[E_{β}]} U(ξ, η)) − 1. Since this last term is nonnegative, it is equal to U^{∗}(H(α), H(β)). QED

Question 5.10. Does the existence of a universal F : ω_{1} × ω_{1} → 2 imply that there is a universal function G : ω_{1} × ω_{1} → ω?

The rest of this section concerns universal functions on ω_{1} × ω_{1}.

Remark 5.11. Shelah [24, 25, 26] proved that it is consistent with 𝔠 > ℵ_{1} that there is a universal graph on ω_{1}. By Theorem 5.9, in his model there are universal functions from ω_{1} × ω_{1} to n for each n < ω.

Shelah’s result was generalized in Mekler ([16], Theorem 2). In Mekler’s terminology, a 3-amalgamation class K is a class of models of a universal theory in a relational language which satisfies the following amalgamation property: if {M_{a} : a ∈ P^{−}(3)} are structures in K for which M_{a} ∩ M_{b} = M_{a∩b} for all a, b ∈ P^{−}(3), then there is an M ∈ K such that M_{a} ⊆ M for each a ∈ P^{−}(3), where P^{−}(3) denotes the set P(3) \ {3}.

Theorem 5.12 (Mekler [16]). If 2^{ℵ_{1}} = ℵ_{2}, then there is a c.c.c. partial order forcing that that 𝔠 = ℵ_{2} and that for every 3-amalgamation class K having only countably many finite models up to isomorphism, there is a model M in K of cardinality ℵ_{1} such that every model in K of cardinality ℵ_{1} is isomorphic to a substructure of M.

The following theorem is a corollary of Mekler’s result.

Theorem 5.13. It is consistent that 2^{ℵ_{0}} > ℵ_{1} and there is a universal function from ω_{1} × ω_{1} to ω_{1}.

Proof By Proposition 5.7 it is enough to find a universal function from ω_{1}×ω_{1} to ω. Let L be the language with countably many binary predicate symbols R_{n}(x, y). Let T be the theory with countably many axioms:

∀x, y (R_{n}(x, y) → ¬R_{m}(x, y))

for each n ≠ m. Note that T has only countably many finite models up to isomorphism and is axiomatized by universal sentences.

To verify that the class of models of T satisfies the amalgamation property of 3-amalgamation classes, note that if M_{a} (a ∈ P^{−}(3)) are models of T such that M_{a} ∩ M_{b} = M_{a∩b} for all a, b ∈ P^{−}(3), then ⋃{M_{a} : a ∈ P^{−}(3)} ⊧ T.

Suppose now that (ω_{1}, {R_{n}}_{n<ω}) is a universal model of T. Define a function U : ω_{1}^{2} → ω by

U(α, β) = \{ \begin{matrix}n & if R_{n}(α, β) \\ 0 & if ∀n ¬R_{n}(α, β) \end{matrix}

Now given any g : ω_{1}^{2} → ω define R_{n}^{g}(α, β) if and only if g(α, β) = n. The structure (ω_{1}, {R_{n}^{g}}_{n<ω}) is a model of T. An embedding of this structure into our universal model gives a map h : ω_{1} → ω_{1} such that g(α, β) = U(h(α), h(β)) for all α, β < ω_{1}. QED

We take up the question of model-theoretic universality in section 7. Next we consider the problem of universal functions on ω_{1} assuming Martin’s Axiom.

Theorem 5.14. Assume MA_{ω_{1}}. Then there exists F : ω_{1} × ω → ω_{1} which is universal.

Proof By Proposition 5.8 we need only produce a universal F : ω_{1}×ω → ω. Standard arguments show that there exists a family h_{α} : ω → ω for

α < ω_{1} of independent functions, i.e., for any n, α_{1} < α_{2} < ⋯ < α_{n} < ω_{1} and s : {1, …, n} → ω there are infinitely many k < ω such that

h_{α_{1}}(k) = s(1)
h_{α_{2}}(k) = s(2)
⋮

h_{α_{n}}(k) = s(n).

Define H : ω_{1} × ω → ω by H(α, n) = h_{α}(n). We show that H is universal mod finite, in sense which will be made clear. Given any f : ω_{1} × ω → ω define the following poset ℙ. A condition p = (s, F) is a pair such that s ∈ ω^{<ω} is one-to-one and F ∈ [ω_{1}]^{<ω}. We define p ≤ q if and only if

(1) s_{q} ⊆ s_{p},

(2) F_{q} ⊆ F_{p}, and

(3) f(α, n) = h_{α}(s_{p}(n)) for every α ∈ F_{q} and n ∈ dom(s_{p})\dom(s_{q}). The poset ℙ is c.c.c., and in fact σ-centered, since any two conditions with the same s are compatible. Since the family {h_{α} : α < ω_{1}} is independent, for any p ∈ ℙ there are extensions of p with arbitrarily long s part. It follows from MA_{ω_{1}} that there exists h : ω → ω with the property that for every α < ω_{1} for all but finitely many n that f(α, n) = h_{α}(h(n)).

To get a universal map F : ω_{1} × ω → ω, simply take any F with the property that for every α < ω_{1} and any h′ =^{∗} h_{α} (equal mod finite) there is β such that F (β, n) = h′(n) for every n. Since the function h is one-to-one, it easy to find k : ω_{1} → ω_{1} such that F (k(α), h(n)) = f(α, n) for all α and n. QED

Theorem 5.17 below shows that the existence of a universal function for ω_{1} does not follow from Martin’s Axiom. First we have the following lemmas, the first of which follows from a simple modification of the Sierpiński partition sending pairs of reals to some rational between.

Lemma 5.15. There exists S : [ω_{1}]^{2} → ω such that

• for all uncountable X ⊆ ω_{1} and j ∈ ω there is an uncountable Z ⊆ X such that S(p) > j for all p ∈ [Z]^{2}

• for all ξ the restriction of the mapping η ↦ S({ξ, η}) to ξ is one-to-one.

Proof Let {r_{ξ}}_{ξ∈ω_{1}} enumerate any uncountable set of reals and let ℚ = {q_{n}}_{n∈ω}. Any function S : [ω_{1}]^{2} → ω satisfying q_{S(ξ,η)} falls between r_{ξ} and r_{η} will satisfy the first requirement because, given j and X there is a ⊆-minimal interval J with endpoints in {q_{i}, q_{2}, … q_{j}} such that Z = J ∩ X is uncountable. It is immediate that S(p) > j for all p ∈ [Z]^{2}. Any easy inductive argument then yields an S satisfying both requirements. QED Lemma 5.16. For each r ∈ 2^{ω}, let G_{r}: ω_{1} × ω_{1} → ω be defined by setting G_{r}(η, ξ) = r(S({η, ξ})). Fix U : ω_{1} × ω_{1} → ω, and let H ∈ 2^{ω} be Hechler generic over a model V containing U. Then, in V [H], any partial order ℙ such that

1 ⊩_{ℙ} “(∃h : ω_{1} → ω_{1})(∀η)(∀ξ ≠ η) U(h(η), h(ξ)) = G_{H}(η, ξ)”

contains an uncountable antichain.

Proof Let h be a name such that

1 ⊩_{ℙ} “(∀η)(∀ξ ≠ η) U(h(η), h(ξ)) = G_{H}(η, ξ)”.

For each ξ ∈ ω_{1}, choose a condition (t_{ξ}, F_{ξ}) in Hechler forcing ℍ, a name p_{ξ} for an element of ℙ and an ordinal α_{ξ} such that

((t_{ξ}, F_{ξ}), p_{ξ}) ⊩_{ℍ⋆ℙ} “h(ξ̌) = α̌_{ξ}”.

Let t : n → ω be such that there is an uncountable set X ⊆ ω_{1} such that t_{ξ} = t for all ξ ∈ X. Let Z ⊆ X be uncountable such that S(w) > n for all w ∈ [Z]^{2}.

For each ξ ∈ ω_{1} let D_{ξ} be the partial function from ω to ω with domain {S({ξ, η}) : η < ξ} defined by setting

D_{ξ}(S({ξ, η})) = U(α_{ξ}, α_{η}) + 1.

This is well defined by the one-to-one property of S. By extending the second coordinate of (t_{ξ}, F_{ξ}) = (t, F_{ξ}) it may be assumed that F_{ξ}(j) ≥ D_{ξ}(j) for all j ∈ dom(D_{ξ}) ∩ dom(F_{ξ}). Now if ξ and η belong to Z and η < ξ then ((t, F_{ξ}), p_{ξ}) and ((t, F_{η}), p_{η}) are incompatible.

To see this suppose that a condition ((s, F), p) were stronger than both ((t, F_{ξ}), p_{ξ}) and ((t, F_{η}), p_{η}). By extending (s, F), it may be assumed that S({ξ, η}) ∈ dom(s). Since {ξ, η} ⊆ Z, each value S({ξ, η}) > n, so S({ξ, η}) ∈ dom(s) \ dom(t). Hence, ((s, F), p) as an element of ℍ ⋆ ℙ forces the following

s(S({ξ, η})) ≥ F_{ξ}(S({ξ, η})) ≥ D_{ξ}(S({ξ, η})) > U(α_{ξ}, α_{η})
= U(h(ξ), h(η)) = G_{H}(ξ, η) = H(S({ξ, η})) = s(S({ξ, η}))

yielding a contradiction. Since ℍ has the c.c.c. it follows that ℙ does not. QED

Lemma 5.16 implies the following.

Theorem 5.17. In the standard model of MA obtained by forcing over a model of GCH with a finite support iteration of length ω_{2} of c.c.c. posets, there is no universal function from ω_{1} × ω_{1} to ω.

5.1. Property R. We conclude this section by connecting the existence of universal functions from ω_{1} × ω_{1} to ω with the existence of certain functions on pairs from ω_{1}.

Definition 5.18. A function Φ: [ω_{1}]^{2} → ω has Property R if

• whenever k ∈ ω and {{a_{ξ}, b_{ξ}} : ξ ∈ ω_{1}} is a family of disjoint pairs from ω_{1} with each a_{ξ} ≤ b_{ξ}, there are distinct ξ and η such that Φ({a_{ξ}, a_{η}}) ≥ Φ({b_{ξ}, b_{η}}) ≥ k;

• for each ξ ∈ ω_{1} and k ∈ ω there are only finitely many η ∈ ξ such that Φ({ξ, η}) = k.

Functions with similar properties appear in Theorem 6 of [28].

Given a sequence ⟨σ_{α} : α < ω_{1}\ω⟩ such that each σ_{α} is an infinite set of pairwise disjoint pairs from α, one can recursively define a function Φ: [ω_{1}]^{2} → ω with the property that for each η < ω_{1},

• for all distinct ζ, ρ < η, Φ({ζ, η}) ≠ Φ({ρ, η});

• for all ζ ∈ [ω, η), all α ∈ [ω, ζ] and all k ∈ ω, there exist δ < γ

such that {δ, γ} ∈ σ_{α} and Φ({δ, ζ}) = Φ({γ, η}) ≥ k.

It follows that if ◇ holds, and is exemplified by ⟨σ_{α} : α < ω_{1} \ ω⟩, then functions with Property R exist. It can be verified in a straightforward manner that functions with Property R are preserved by forcing by partial orders satisfying Knaster’s condition (i.e., for which every uncountable set of conditions has an uncountable pairwise compatible subset). The existence of a function with Property R is then consistent with the statement 𝔟 > ℵ_{1}.

Proposition 5.19. If 𝔟 > ℵ_{1} and there exists a function Φ: [ω_{1}]^{2} → ω with Property R then there is no universal function from ω_{1} × ω_{1} to ω.

Proof Let U : ω_{1} × ω_{1} → ω be given. Define F_{ξ} : ω → ω for each ξ < ω_{1} by setting F_{ξ}(m) to be the largest member of the finite set

{U(ξ, η) + 1 | η < ξ ∧ Φ({ξ, η}) = m} ∪ {0}.

Let F : ω → ω be a non-decreasing function such that F ≥^{∗} F_{ξ} for all ξ. Define G : ω_{1} × ω_{1} → ω by setting G(ξ, η) = F (Φ({ξ, η})). Fixing an injection h: ω_{1} → ω_{1}, we will find ξ and η in ω_{1} such that G(ξ, η) ≠ U(h(ξ), h(η)).

Let Z ∈ [ω_{1}]^{ℵ_{1}} be such that h(ξ) ≥ ξ for all ξ ∈ Z. Choose k and X ∈ [Z]^{ℵ_{1}} such that F (j) ≥ F_{h(ξ)}(j) for all ξ ∈ X and j ≥ k. Since h(ξ) ≥ ξ for all ξ ∈ X, it is possible to choose ξ > η in X such that h(ξ) > h(η) and k ≤ Φ({h(ξ), h(η)}) ≤ Φ({ξ, η}). It follows that

G(ξ, η) = F (Φ({ξ, η})) ≥ F (Φ({h(ξ), h(η)})),

and that

F (Φ({h(ξ), h(η)})) ≥ F_{h(ξ)}(Φ({h(ξ), h(η)}) > U(h(ξ), h(η)),

contradicting that h is an embedding. QED

The argument of Proposition 5.19 shows that if 𝔟 > ℵ_{1} and Property R holds then there are no universal functions from ω_{1} × ω_{1} → ω, but it does not rule out the existence of a universal functions from ω_{1} × ω_{1} → 2. The following result of Saharon Shelah addresses this question.

Definition 5.20. A graph (V, E) is said to be universal (for ℵ_{1}) if given any graph (U, F) such that |U| = ℵ_{1} there is a function Φ : U → V such that {x, y} ∈ F if and only if {Φ(x), Φ(y)} ∈ E. The function Φ will be called an embedding in this case.

Theorem 5.21 (Shelah). Assuming the following two hypotheses:

(1) For every F ⊆ [ω_{1}^{ω_{1}}]^{2^{ℵ_{0}}} there exist two functions f and g in F such that {ξ ∈ ω_{1} | f(ξ) = g(ξ)} is stationary.

(2) There exist f_{ξ} for every limit ordinal ξ ∈ ω_{1} such that • f_{ξ} : ω → ξ is increasing and cofinal in ξ

• for every club C ⊆ ω_{1} there is a club X such that for each ξ ∈ X there is some n such that f_{ξ}(k) ∈ C for all k ≥ n.

there is no universal graph on ω_{1}.

Proof Suppose that U is a universal graph on ω_{1}. For any r : ω → 2 define the graph G_{r} to consist of all edges {ξ, η} such that there exists n ∈ ω such that r(n) = 1 and f_{η}(n) ≤ ξ < f_{η}(n + 1). Since U is universal there exist embeddings h_{r} : ω_{1} → ω_{1} of G_{r} into U.

Now let A ⊆ 2^{ω} be any set of size 2^{ℵ_{0}} consisting of reals any two of which differ on an infinite set. The first hypothesis yields r and s in A such that that E = {ξ ∈ ω_{1} | h_{r}(ξ) = h_{s}(ξ)} is stationary. Then let C be any club such that if α and β are in C and α ∈ β then E∩[α, β) ≠ ∅.

The second hypothesis then yields ξ ∈ E and n ∈ ω such hat f_{ξ}(k) ∈ C for all k ≥ n. Choose k ≥ n such that r(k) = 1 ≠ s(k) and let η ∈ E be such that f_{ξ}(k) ≤ η < f_{ξ}(k + 1). Then {η, ξ} is an edge of G_{r} but not of G_{s} contradicting that h_{s}(η) = h_{r}(η) and h_{s}(ξ) = h_{r}(ξ).

Corollary 5.22. It is consistent with MA that there is no universal graph on ω_{1}.

Proof Begin with model of ♢ and GCH and force with ccc partial order ℙ of cardinality ℵ_{4} to obtain a model of MA and 2^{ℵ_{0}} = ℵ_{4}. The second hypothesis of Theorem 5.21 is true because it holds in the ground model satisfying ♢ and clubs in the forcing extension contain clubs in the ground model.

To see that the first hypothesis is true, let {ḟ_{μ}}_{μ∈ω_{4}} be ℙ-names for functions from ω_{1} to ω_{1}. For each μ ∈ ω_{4} choose a function w_{μ} : ω_{1} → ω_{1} and conditions p_{μ,ξ} ∈ ℙ such that

p_{μ,ξ} ⊩_{ℙ} “ḟ_{μ}(ξ) = w_{μ}(ξ)”

for all ξ ∈ ω_{1}. For each pair μ ≠ θ let Ċ_{μ,θ} be a ℙ-name for a club such that 1 ⊩_{ℙ} “(∀ξ ∈ Ċ_{μ,θ})ḟ_{μ}(ξ) ≠ ḟ_{θ}(ξ)”. Because ℙ is ccc there is a club D_{μ,θ} in the ground model such that 1 ⊩_{ℙ} “D_{μ,θ} ⊆ Ċ_{μ,θ}”.

First let E ⊆ ω_{4} be of cardinality ℵ_{4} such that there is a function w such that w_{μ} = w for all μ ∈ E. Since the ground model satisfies ℵ_{4} → [ℵ_{1}]_{ℵ_{2}}^{2} it follows that there is an uncountable set B ⊆ E and a club D such that D_{μ,θ} = D for {μ, θ} ∈ [B]^{2}. Let δ ∈ D. Then since ℙ is ccc there are distinct μ and θ in B such that there is p ∈ ℙ such that p ≤ p_{μ,δ} and p ≤ p_{θ,δ}. This contradicts that δ ∈ D and p ⊩_{ℙ} “w(ξ) = w_{μ}(ξ) = ḟ_{μ}(ξ) ≠ ḟ_{θ}(ξ) = w_{θ}(ξ) = w(ξ)”.

Remark 5.23. Justin Moore has shown that under the Proper Forcing Axiom there are no functions with property R — his argument is included in the appendix to this article. Justin Moore and Stevo Todorcevic have independently indicated to the authors that the existence of a function with Property R follows from the assumption that 𝔟 = ℵ_{1}.

6. Higher dimensional universal functions

Definition 6.1. Given k ∈ ω and sets X_{i} (i < k) and Z, a function F: ∏_{i<k} X_{i} → Z is universal if for each function G: ∏_{i<k} X_{i} → Z there exist functions h_{i}: X_{i} → X_{i} (i < k) such that

G(x_{0}, …, x_{k−1}) = F (h_{0}(x_{0}), …, h_{k−1}(x_{k−1}))

for all (x_{0}, …, x_{k−1}) ∈ ∏_{i<k} X_{i}.

As in Remark 1.1, in the case where the X_{i}’s are all the same set X, the existence of a universal function is not changed by requiring that the functions h_{i} are all the same.

Given a set X and a k ∈ ω, we call a universal function F: X^{k} → X a k-dimensional universal function on X. The following proposition shows that the existence of a 2-dimensional universal function on an infinite set X is equivalent to the existence of a k-dimensional universal function, for any k > 1. Note however that the Baire complexity of F (F (x, y), z) can be higher than that of F.

Proposition 6.2. Let X, Y be sets such that |X × Y | = |X|. If

F: X × Y → X

is a universal function, then the function F′: X × Y × Y → X defined by setting F′(x, y, z) = F (F (x, y), z) is a universal function.

Proof Fix functions π_{0} : X → X and π_{1} : X → Y such that the function π: X → X × Y defined by setting π(x) = (π_{0}(x), π_{1}(x)) is a bijection. Given G: X × Y × Y → X, define G_{0} : X × Y → X by setting G_{0}(x, z) = G(π_{0}(x), π_{1}(x), z). By the universality of F there exist functions g: X → X and h: Y → Y such that G_{0}(u, z) = F (g(u), h(z)) for all (u, z) ∈ X × Y. Again by the universality of F there are functions g_{0} : X → X and g_{1} : Y → Y such that

g(π^{−1}(x, y)) = F (g_{0}(x), g_{1}(y))

for all (x, y) ∈ X × Y. Then for all (x, y, z) ∈ X × Y × Y,

G(x, y, z) = G_{0}(π^{−1}(x, y), z) = F (g(π^{−1}(x, y)), h(z)),

which is equal to F (F (g_{0}(x), g_{1}(y)), h(z)). QED

One may also consider universal functions F where the parameterizing functions take in more than one variable, for example, a function F: X^{3} → Y such that for all G: X^{3} → Y there exist functions g, h and k from X^{2} to X such that G(x, y, z) = F (g(x, y), h(y, z), k(x, z)) for all x, y, z in X. A 3-dimensional universal function is universal in this sense, since g, h and k can be chosen to each depend on only one variable. However, we do not know if a universal function in this sense implies the existence of a 3-dimensional universal function.

The reader will easily be able to imagine many variants. For example, • G(x, y, z) = F (g(x, y), h(y, z));

• G(x_{1}, x_{2}, x_{3}, x_{4}) = F (g_{1}(x_{1}, x_{2}), g_{2}(x_{2}, x_{3}), g_{3}(x_{3}, x_{4}), g_{4}(x_{4}, x_{1})); where we have omitted quantifiers for clarity. These two variants are each equivalent to the existence of 2-dimensional universal function. To see this in the first example put y = 0 and get

G(x, z) = F (g(x, 0), h(0, z)).

In the second example put x_{2} = x_{4} = 0 and get

G(x_{1}, x_{3}) = F (g_{1}(x_{1}, 0), g_{2}(0, x_{3}), g_{3}(x_{3}, 0), g_{4}(0, x_{1})).

More generally, suppose that F and the x⃗_{k}’s have the property that for every G there are g_{k}’s such that for all x⃗

G(x⃗) = F (g_{1}(x⃗_{1}), …, g_{n}(x⃗_{n})).

Suppose that there are two variables x and y from x⃗ which do not simultaneously belong to any x⃗_{k}. Then we get a universal 2-dimensional function simply by setting all of the other variables equal to zero.

For the rest of this section we will often leave implicit the domains of our universal functions, for notional ease. When we talk of the complexity of universal functions, however, the underlying domain space is taken to be 2^{ω}.

Definition 6.3. Given n ∈ ω \ {0, 1}, an (n, 2)-dimensional universal

function is an ( \begin{matrix}n \\ 2 \end{matrix} )-ary function F such that for every n-ary function

G there is a binary function h with

G(x_{1}, x_{2}, …, x_{n}) = F (⟨h(x_{i}, x_{j}) : 1 ≤ i < j ≤ n⟩)

for all x_{1}, x_{2}, …, x_{n}.

Proposition 6.4. If there is a (3, 2)-dimensional universal function, then for every n > 3 there is a (n, 2)-dimensional universal function F. Conversely, if there is a (n + 1, 2)-dimensional universal function for some n ≥ 3, then there is an (n, 2)-dimensional universal function.

Proof Suppose that F is a (3, 2)-dimensional universal function and F′ is an (n, 2)-dimensional universal function, for some n ≥ 3. Given an (n+1)-ary function G(x_{1}, …, x_{n+1}), for each fixed w we get a function h_{w}(x_{1}, …, x_{n}) with

G(x_{1}, …, x_{n}, w) = F′(⟨h_{w}(x_{i}, x_{j}) : 1 ≤ i < j ≤ n⟩)

for all x_{1}, …, x_{n}. Now, considering h(y_{1}, y_{2}, y_{3}) = h_{y_{3}}(y_{1}, y_{2}) we get a function k(s, t) with h(y_{1}, y_{2}, y_{3}) = F (⟨k(y_{i}, y_{j}) : 1 ≤ i < j ≤ 3⟩) for all y_{1}, y_{2}, y_{3}. Then, for all x_{1}, …, x_{n+1}, G(x_{1}, …, x_{n+1}) =

F′(⟨F (k(x_{i}, x_{j}), k(x_{i}, x_{n+1}), k(x_{j}, x_{n+1})) : 1 ≤ i < j ≤ n⟩).

From this one gets an (n + 1, s)-dimensional universal function, with k playing the role of h in the definition.

For the converse, suppose that F is an (n+1, 2)-dimensional universal function. Consider F as a function of variables p_{i,j} (1 ≤ i < j ≤ n+1), and, fixing a tripling function ⟨·, ·, ·⟩, let u_{1}, u_{2} and u_{3} be functions so that u_{i}(⟨x_{1}, x_{2}, x_{3}⟩) = x_{i} for all x_{1}, x_{2}, x_{3} and i ∈ {1, 2, 3}. Let K be the function which takes in a sequence

⟨q_{i,j} : 1 ≤ i < j ≤ n⟩

and returns the sequence

⟨p_{i,j} : 1 ≤ i < j ≤ n + 1⟩

for which p_{i,j} is • u_{1}(q_{i,j}) if j ≤ n;

• u_{2}(q_{i,i+1}) if i < n and j = n + 1;
• u_{3}(q_{n−1,n}) if i = n and j = n + 1.

Define F′ by setting

F′(⟨q_{i,j} : 1 ≤ i < j ≤ n⟩) = F (K(⟨q_{i,j} : 1 ≤ i < j ≤ n⟩)).

Given an n-ary function G, there exists a binary function h with

G(x_{1}, …, x_{n}) = F (⟨h(x_{i}, x_{j}) : 1 ≤ i < j ≤ n + 1⟩)

for all x_{1}, …, x_{n+1}. Fix a domain element w, and define a function h′ by setting h′(x, y) = ⟨h(x, y), h(x, w), h(y, w)⟩. Then

G(x_{1}, …, x_{n}) = F′(⟨h′(x_{i}, x_{j}) : 1 ≤ i < j ≤ n⟩)

for all x_{1}, …, x_{n}. QED

Next we state a generalization of these ideas.

Definition 6.5. Let X be a set, and n an element of ω. Suppose that Σ ⊆ P({0, 1, 2, …, n − 1}) = P(n) (the power set of n). We let U(X, n, Σ) be the assertion that there exists a function F : X^{Σ} → X such that for every G : X^{n} → X there are h_{Q} : X^{Q} → X for Q ∈ Σ such that

G(x_{0}, x_{1}, …, x_{n−1}) = F (⟨h_{Q}(⟨x_{j} : j ∈ Q⟩) : Q ∈ Σ⟩)

for all x_{0}, …, x_{n−1} ∈ X.

Propositions 6.2 and 6.4 can be generalized as follows. The proofs of the first two parts of Proposition 6.6 are similar to the corresponding proofs from Proposition 6.4.

Proposition 6.6. For any infinite set X and any positive integer n, (1) U(X, n + 1, [n + 1]^{n}) implies ∀m > n U(X, m, [m]^{n});

(2) ∃m > n U(X, m, [m]^{n}) implies U(X, n + 1, [n + 1]^{n});

(3) U(X, n + 1, [n + 1]^{n}) implies U(X, n + 2, [n + 2]^{n+1}).

Proof For the first part, we follow the proof of the first part of Proposition 6.4, inducting on m. Fix m > n, and suppose that F_{0} witnesses the statement U(X, n + 1, [n + 1]^{n}) and F_{1} witnesses U(X, m, [m]^{n}). Given G: X^{m+1} → X, we can find for each w ∈ X functions h_{Q}^{w} (Q ∈ [m]^{n}) such that, for all x_{0}, …, x_{m−1} ∈ X,

G(x_{0}, …, x_{m−1}, w) = F_{1} (⟨h_{Q}^{w}(⟨x_{j} : j ∈ Q⟩) : Q ∈ [m]^{n}⟩) .

Furthermore, there are functions k_{R} (R ∈ [n + 1]^{n}) such that (abusing notation slightly on the left side of the equality)

h_{Q}^{x_{n}}(⟨x_{i} : i < n⟩) = F_{0}(⟨k_{R}(⟨x_{i} : i ∈ R⟩) : R ∈ [n + 1]^{n}⟩)

for all x_{0}, …, x_{n} ∈ X. The functions k_{R} witness in this instance then that the function F_{1}(⟨F_{0}(⟨y_{R} : R ∈ [Q ∪ {m}]^{n}⟩) : Q ∈ [m]^{n}⟩) witnesses U(X, m + 1, [m + 1]^{n}).

For the second part, we follow the proof of the second part of Proposition 6.4. Suppose that F witnesses U(X, m, [m]^{n}). Fix a bijection π: X^{([m]^{n})} → X, and let p_{R} (R ∈ [m]^{n}) be the functions from X to X such that π^{−1}(x) = ⟨p_{R}(x) : R ∈ [m]^{n}⟩. Let H: [m]^{n} → [n + 1]^{n} be such that R ∩ (n + 1) ⊆ H(R) for all R ∈ [m]^{n}. Let K be the function which takes in a sequence

⟨y_{Q} : Q ∈ [n + 1]^{n}⟩

from X and returns the sequence

⟨p_{R}(y_{H(R)}) : R ∈ [m]^{n}⟩.

Define F′: X^{([n+1]^{n})} → X by setting

F′(⟨y_{Q} : Q ∈ [n + 1]^{n}⟩) = F (K(⟨y_{Q} : Q ∈ [n + 1]^{n}⟩)).

To see that this works, fix G: X^{n+1} → X. Since F witnesses U(X, m, [m]^{n}), there exist functions h_{R}: X^{R} → X (R ∈ [m]^{n}) such that

G(x_{0}, …, x_{n}) = F (⟨h_{R}(⟨x_{i} : i ∈ R⟩) : R ∈ [m]^{n}⟩)

for all x_{0}, …, x_{m−1} ∈ X. Fix w ∈ X. For each Q ∈ [n + 1]^{n}, let k_{Q}: X^{Q} → X be defined by setting k_{Q}(⟨x_{i} : i ∈ Q⟩) to be

π(⟨h_{R}(⟨t_{i} : i ∈ R⟩) : R ∈ [m]^{n}⟩),

where each t_{i} is x_{i} if i ∈ Q, and w otherwise. To check that the functions k_{Q} witness that F′ is as desired, it suffices to see that for all x_{0}, …, x_{m−1} in X for which x_{i} = w for all i ∈ {n + 1, …, m − 1}, and all R ∈ [m]^{n}, h_{R}(⟨x_{i} : i ∈ R⟩) is equal to p_{R}(k_{H(R)}(⟨x_{i} : i ∈ H(R)⟩)). Now, p_{R}(k_{H(R)}(⟨x_{i} : i ∈ H(R)⟩)) is h_{R}(⟨t_{i} : i ∈ R⟩), where each t_{i} is x_{i} if i ∈ H(R) and w otherwise. Since R ∩ (n + 1) ⊆ H(R), ⟨t_{i} : i ∈ R⟩ = ⟨x_{i} : i ∈ R⟩, as desired.

For the third part, we follow (loosely) the proof of Proposition 6.2. Suppose that F witnesses U(X, n+1, [n+1]^{n}). Let F′: X^{([n+2]^{n+1})} → X be such that

F′(⟨z_{Q} : Q ∈ [n + 2]^{n+1}⟩) = F (⟨y_{R} : R ∈ [n + 1]^{n}⟩),

where each y_{R} = z_{R∪{n+1}}. Fix functions π_{0} : X → X and π_{1} : X → X such that the function π: X → X × X defined by setting

π(x) = (π_{0}(x), π_{1}(x))

is a bijection. Given G: X^{n+2} → X, define G_{0} : X^{n+1} → X by setting

G_{0}(x_{0}, …, x_{n}) = G(x_{0}, …, x_{n−1}, π_{0}(x_{n}), π_{1}(x_{n})).

By the universality of F there exist functions h_{R} (R ∈ [n + 1]^{n}) such that

G_{0}(x_{0}, …, x_{n}) = F (⟨h_{R}(⟨x_{i} : i ∈ R⟩) : R ∈ [n + 1]^{n}⟩)

for all x_{0}, …, x_{n} from X. Let k_{n+1} be any function from X^{n+1} to X, and let k_{n∪{n+1}}: X^{n+1} → X be such that

k_{n∪{n+1}}(x_{0}, …, x_{n}) = h_{n}(x_{0}, …, x_{n−1})

for all x_{0}, …, x_{n} from X. For each Q ∈ [n+2]^{n+1} containing {n, n+1}, let k_{Q}: X^{n+1} → X be the function defined by setting

k_{Q}(x_{0}, …, x_{n}) = h_{Q∩(n+1)}(x_{0}, …, x_{n−2}, π^{−1}(x_{n−1}, x_{n})).

Then for all x_{0}, …, x_{n+1},

G(x_{0}, …, x_{n+1}) = G_{0}(x_{0}, …, x_{n−1}, π^{−1}(x_{n}, x_{n+1})),

which is equal to F (⟨h_{R}(⟨y_{i} : y ∈ R⟩) : R ∈ [n + 1]^{n}⟩), where y_{i} = x_{i} for all i < n, and y_{n} = π^{−1}(x_{n}, x_{n+1}). Furthermore,

F (⟨h_{R}(⟨y_{i} : i ∈ R⟩) : R ∈ [n + 1]^{n}⟩)

is equal to

F′(⟨k_{Q}(⟨x_{i} : i ∈ Q⟩) : Q ∈ [n + 2]^{n+1}⟩),

as h_{R}(⟨y_{i} : i ∈ R⟩) = k_{R∪{n+1}}(⟨x_{i} : i ∈ R ∪ {n + 1}⟩) for each R ∈ [n + 1]^{n}. QED

In the following definition, n is the arity of the inside parameter functions. The arity of the universal function is less important.

Definition 6.7. For any infinite set X, and any n ∈ ω, we define U(X, n) to be any of the equivalent propositions U(X, m, [m]^{n}) for m in ω \ (n + 1).

Proposition 6.8 and Theorem 6.9 show that the U(κ, n)’s are the only generalized multi-dimensional universal functions properties. Clause (3) of Proposition 6.6 says that U(κ, n) implies U(κ, n + 1) and we will show in Corollary 6.13 that none of these implications can be reversed.

Proposition 6.8. Let X be an infinite X, n ∈ ω \ 2, and Σ, Σ_{0}, Σ_{1} subsets of P(n).

(1) If Σ_{0} ⊆ Σ_{1}, then U(X, n, Σ_{0}) implies U(X, n, Σ_{1}).

(2) If Q_{0} ⊆ Q_{1} ∈ Σ, then U(X, n, Σ) is equivalent to

U(X, n, Σ ∪ {Q_{0}}).

(3) Suppose that Σ is closed under taking subsets, every element of n is in some element of Σ, and n = {0, 1, 2, …, n − 1} ∉ Σ. Let m + 1 be the size of the smallest subset of n not in Σ. Then U(X, n, Σ) is equivalent to U(X, m).

Proof

(1) This follows from the fact that the F which works for Σ_{0} also works for Σ_{1} by ignoring the values of h_{Q} for Q ∈ Σ_{1} \ Σ_{0}.

(2) One direction follows from part (1). For the other suppose that F: X^{Σ∪{Q_{0}}} → X witnesses U(X, n, Σ ∪ {Q_{0}}). Let π: X → X × X be a bijection, and let π_{0} : X → X and π_{1} : X → X be such that π(x) = (π_{0}(x), π_{1}(x)) for all x ∈ X. Define F′: X^{Σ} → X by setting F′(⟨x_{Q} : Q ∈ Σ⟩) to be F (⟨y_{R} : R ∈ Σ ∪ {Q_{0}}⟩), where y_{Q_{0}} = π_{0}(x_{Q_{1}}), y_{Q_{1}} = π_{1}(x_{Q_{1}}) and y_{R} = x_{R} if R ∉ {Q_{0}, Q_{1}}. Fix G: X^{n} → X, and let h_{R} (R ∈ Σ ∪ {Q_{0}}) be as in the definition of U(X, n, Σ ∪ {Q_{0}}). For each Q ∈ Σ \ {Q_{1}}, let h′_{Q} = h_{Q}. Let h′_{Q_{1}} be such that

h′_{Q_{1}}(⟨x_{j} : j ∈ Q_{1}⟩) = π(h_{Q_{0}}(⟨x_{j} : j ∈ Q_{0}⟩), h_{Q_{1}}(⟨x_{j} : j ∈ Q_{1}⟩))

for all x_{0}, …, x_{n−1} from X. Then h′_{Q} (Q ∈ Σ) are as desired.

(3) First suppose that U(X, n, Σ) holds. Choose R ⊆ {0, 1, … n−1} not in Σ with |R| = m + 1. By the choice of m all subsets of R of size m are in Σ. By restricting to the case where x_{i} = 0 for i ∉ R, we see that U(X, m, [m]^{m+1}) holds.

Now assume that U(κ, m) holds. Then U(κ, n, [n]^{m}) holds. Since [n]^{m} ⊆ Σ, part (1) implies that U(κ, n, Σ) holds. QED

Proposition 6.8 gives the following. The first two statements in the theorem are trivial.

Theorem 6.9. For any n ∈ ω, any infinite cardinal κ and any Σ ⊆ P(n), if

⋃ Σ ≠ n = {0, 1, 2, …, n − 1}

then U(κ, n, Σ) fails. If n ∈ Σ, then U(κ, n, Σ) holds. If neither of these is true, then by the Proposition 6.8 there exists m with U(κ, n, Σ) equivalent to U(κ, m).

The following fact will be used in the proof of Proposition 6.11. Recall that a linear preorder on a set X is a binary relation ⪯ on X which is reflexive, transitive and total (i.e., for all x, y ∈ X, at least one of x ⪯ y and y ⪯ x holds). Every linear preorder is a superset of a linear order.

Proposition 6.10. Let κ be an infinite cardinal and let m < n be integers, with m ≥ 2. Suppose that F_{0} : κ^{([n]^{m})} → κ has the property that for each G: κ^{n} → κ there exist h_{Q}: κ^{Q} → κ (Q ∈ [n]^{m}) such that

G(y_{0}, …, y_{n−1}) = F (⟨h_{Q}(⟨x_{i} : i ∈ Q⟩) : Q ∈ [n]^{m}⟩)

for all nondecreasing ⟨y_{0}, …, y_{n−1}⟩ ∈ κ^{n}. Then U(κ, n, [n]^{m}) holds.

Proof Let κ, m and n be as given. As in Remark 1.1, we may assume that F_{0} has the property that for each G: κ^{n} → κ there exists a single function h: κ^{Q} → κ such that

G(y_{0}, …, y_{n−1}) = F (⟨h(⟨x_{i} : i ∈ Q⟩) : Q ∈ [n]^{m}⟩)

for all nondecreasing ⟨y_{0}, …, y_{n−1}⟩ ∈ κ^{n}.

Let P be the set of all permutations of n. Let π: κ → κ^{P} be a bijection, and let F = π ∘ F_{0}. Then for each G: κ^{n} → κ^{P} there exist an h: κ^{Q} → κ such that

G(y_{0}, …, y_{n−1}) = F (⟨h(⟨x_{i} : i ∈ Q⟩) : Q ∈ [n]^{m}⟩)

for all nondecreasing ⟨y_{0}, …, y_{n−1}⟩ ∈ κ^{n}.

Let L be the set of all linear preorders on members of [n]^{m}. Let r: L×κ → κ be a bijection. Let e be a function taking linear preorders on n to linear orders contained in them.

Let F^{∗}: κ^{([n]^{m})} → κ be the function which takes in a sequence

⟨r(l_{Q}, α_{Q}) : Q ∈ [n]^{m}⟩,

where each l_{Q} is a linear preorder on Q and each α_{Q} is in κ, and returns a value in κ defined as follows. If ⋃{l_{Q} : Q ∈ [n]^{m}} is not a linear preorder, then let F^{∗} take any value in κ. Otherwise, let

l = e(⋃{l_{Q} : Q ∈ [n]^{m}}),

and let s: n → n be the function that takes each i ∈ n to its l-rank. For each Q ∈ [n]^{m}, let β_{Q} be α_{s^{−1}[Q]}. Finally, let

F^{∗}(⟨r(l_{Q}, α_{Q}) : Q ∈ [n]^{m}⟩) = F (⟨β_{Q} : Q ∈ [n]^{m}⟩)(s^{−1}).

Let us see that this F^{∗} works. Fix a function G^{∗}: κ^{n} → κ. Let G: κ^{n} → κ^{P} be the function defined by letting

G(y_{0}, …, y_{n−1}) = ⟨G^{∗}(y_{p(0)}, …, y_{p(n−1)}) : p ∈ P ⟩.

Let h: κ^{Q} → κ be such that

G(y_{0}, …, y_{n−1}) = F (⟨h(⟨y_{i} : i ∈ Q⟩) : Q ∈ [n]^{m}⟩)

for all nondecreasing ⟨y_{0}, …, y_{n−1}⟩ ∈ κ^{n}. For each Q ∈ [n]^{m}, define h_{Q}^{∗}: κ^{Q} → κ by setting h_{Q}^{∗}(⟨x_{i} : i ∈ Q⟩) to be

r(l_{Q}(⟨x_{i} : i ∈ Q⟩), h(⟨z_{i} : i ∈ Q⟩)),

where l_{Q} is the linear order on Q induced by ⟨x_{i} : i ∈ Q⟩ and ⟨z_{i} : i ∈ Q⟩ lists {x_{i} : i ∈ Q} in nondecreasing order.

Now each ⟨x_{0}, …, x_{n−1}⟩ ∈ κ^{n} is ⟨y_{p(0)}, …, y_{p(n−1)}⟩ for some p ∈ P and a unique nondecreasing ⟨y_{0}, …, y_{n−1}⟩ in κ^{n}. Furthermore, p can be taken to be s^{−1}, where l = e(⋃{l_{Q} : Q ∈ [n]^{m}}), each l_{Q} is the linear order on Q given by {x_{i} : i ∈ Q} and s is the function taking each element of n to its l-rank. Then G^{∗}(x_{0}, …, x_{n−1}) = G(y_{0}, …, y_{n−1})(p), which is

F (⟨h(⟨y_{i} : i ∈ Q⟩) : Q ∈ [n]^{m}⟩)(p).

Finally, each ⟨y_{i} : i ∈ Q⟩ = ⟨x_{i} : i ∈ s^{−1}[Q]⟩, so that

F (⟨h(⟨y_{i} : i ∈ Q⟩) : Q ∈ [n]^{m}⟩)(p)

equals

F^{∗}(⟨(r(l_{Q}(⟨x_{i} : i ∈ Q⟩), h(z_{i} : i ∈ Q)) : Q ∈ [n]^{m}⟩)

(where ⟨z_{i} : i ∈ Q⟩ is ⟨x_{i} : i ∈ Q⟩ listed in increasing order), which is equal to

F^{∗}(⟨h_{Q}^{∗}(⟨x_{i} : i ∈ Q⟩) : Q ∈ [n]^{m}⟩).

QED

Since |ω^{<ω}| = ω, U(ω, 1) follows from Theorem 5.1. The following proposition allows us to propagate this fact, showing for instance that U(ω_{n}, n + 1) holds for every n ∈ ω.

Proposition 6.11. For any infinite cardinal κ, and any n ∈ ω, U(κ, n) implies U(κ^{+}, n + 1)

Proof

Let Σ = {a ∪ {n + 1} : a ∈ [n + 1]^{n}}. Applying Proposition 6.10, and the idea behind the first part of Proposition 6.8, it suffices to produce a function

F: (κ^{+})^{Σ} → κ^{+}

such that for every G: (κ^{+})^{n+2} → κ^{+} there exist

H_{Q}: (κ^{+})^{n+1} → κ^{+}(Q ∈ Σ)

for which G(ξ_{0}, …, ξ_{n+1}) = F (⟨H_{Q}(⟨ξ_{i} : i ∈ Q⟩) : Q ∈ Σ⟩) for all nondecreasing sequences ⟨ξ_{0}, …, ξ_{n+1}⟩ from κ^{+}.

Suppose that f : κ^{([n+1]^{n})} → κ witnesses U(κ, n + 1, [n + 1]^{n}). For each α ∈ [κ, κ^{+}), let B_{α}: α → κ be a bijection. Let r: κ × κ^{+} → κ^{+} be a bijection.

Let F be a function which takes in a sequence ⟨r(α_{Q}, β_{Q}) : Q ∈ Σ⟩ and returns a value in κ^{+} as follows. If β_{Q} is not the same value for all Q, then F returns any value. Otherwise, letting β be this constant value, and letting γ_{R} be α_{R∪{n+1}} for each R ∈ [n + 1]^{n}, F returns the value

B_{β}^{−1}(f(⟨γ_{R} : R ∈ [n + 1]^{n}⟩)).

Let us check that this definition works. Suppose we are given

G: (κ^{+})^{n+2} → κ^{+}.

For each δ < κ^{+}, let k(δ) be sup(G[(δ + 1)^{n+2}]) + 1. For each δ < κ^{+} there exist h_{R}^{δ}: κ^{n} → κ (R ∈ [n + 1]^{n}) such that

f(⟨h_{R}^{δ}(⟨B_{δ+1}(α_{i}) : i ∈ R⟩) : R ∈ [n + 1]^{n}⟩) = B_{k(δ)}(G(α_{0}, …, α_{n}, δ))

for all α_{0}, …, α_{n} ≤ δ.

For each Q ∈ Σ, let H_{Q}: (κ^{+})^{n+1} → κ^{+} be defined as follows. Given ⟨ζ_{i} : i ∈ Q⟩ from κ^{+}, if ζ_{n+1} < ζ_{i} for some i ∈ Q, then let H_{Q}(⟨ζ_{i} : i ∈ Q⟩) take any value in κ^{+}. Otherwise, let H_{Q}(⟨ζ_{i} : i ∈ Q⟩) take the value r(α_{Q}, k(ζ_{n+1})), where

α_{Q} = h_{Q∩(n+1)}^{ζ_{n+1}}(⟨B_{ζ_{n+1}+1}(ζ_{i}) : i ∈ Q ∩ (n + 1)⟩).

Now let ξ_{0}, …, ξ_{n+1} be a nondecreasing sequence from κ^{+}. Then G(ξ_{0}, …, ξ_{n+1}) is equal to

B_{k(ξ_{n+1})}^{−1}(f(⟨h_{R}^{ξ_{n+1}}(⟨B_{ξ_{n+1}+1}(ξ_{i}) : i ∈ R⟩) : R ∈ [n + 1]^{n}⟩)).

Then we are done, since, as written above, each γ_{R} is α_{R∪{n+1}}, which is h_{R}^{ξ_{n+1}}(⟨B_{ξ_{n+1}+1}(ξ_{i}) : i ∈ R⟩). QED

The partial order Fn(X, Y, κ) was defined before Theorem 5.5. For any n ∈ ω and any infinite cardinal κ, the partial order Fn(κ^{n}, 2, ℵ_{0}) is forcing-equivalent to the partial order which adds a subset of κ by finite conditions.

Proposition 6.12. Suppose that n ∈ ω \ {0} and that γ < κ are cardinals with ℵ_{n} ≤ γ. Then U(γ, n) fails after forcing with Fn(κ^{n+1}, 2, ℵ_{0}).

Proof Let G ⊆ Fn(κ^{n+1}, 2, ℵ_{0}) be a V -generic filter, and fix a function

F: γ^{n+1} → γ

in V [G]. Since Fn(κ^{n+1}, 2, ℵ_{0}) is c.c.c., we may fix an η < κ such that F is in V [G ↾ η^{n+1}]. Supposing toward a contradiction that F witnesses U(γ, n + 1, [n + 1]^{n}) in V [G], there exist functions

h_{i}: ( ∏_{j∈(n+1)\{i}} ω_{j}) → γ (i < n + 1)

such that for all (α_{0}, …, α_{n}) ∈ ∏_{i<n+1} ω_{i}, G(α_{0}, …, η + α_{n}) is equal to

F (h_{0}(α_{1}, …, α_{n}), h_{1}(α_{0}, α_{2}, …, α_{n}), …, h_{n}(α_{0}, …, α_{n−1})).

Again applying the fact that Fn(κ^{n+1}, 2, ℵ_{0}) is c.c.c., there exists a δ_{n} < ω_{n} such that h_{n} ∈ V [G^{{n}}], where G^{{n}} is the restriction of G to those members of κ^{n+1} whose last element is not η + δ_{n}. For each i < n, let h_{i}^{{n}} be the function on ∏_{j∈n\{i}} ω_{j} defined by setting

h_{i}^{{n}}(α_{0}, …, α_{i−1}, α_{i+1}, …, α_{n−1})

to be

h_{i}(α_{0}, …, α_{i−1}, α_{i+1}, …, α_{n−1}, η + δ_{n}).

Applying the c.c.c. of Fn(κ^{n+1}, 2, ℵ_{0}) again, we can find a δ_{n−1} < ω_{n−1} such that, letting G^{{n−1,n}} be the restriction of G to those members of κ^{n+1} whose last two elements are not δ_{n−1} and η + δ_{n}, h_{n−1}^{{n}} ∈ V [G^{{n−1,n}}]. For each i < n, let h_{i}^{{n−1,n}} be the function on

∏_{j∈(n−1)\{i}} ω_{j}

defined by setting

h_{i}^{{n−1,n}}(α_{0}, …, α_{i−1}, α_{i+1}, …, α_{n−2})

to be

h_{i}(α_{0}, …, α_{i−1}, α_{i+1}, …, α_{n−2}, δ_{n−1}, η + δ_{n}).

Continuing in this fashion, we can find (δ_{1}, …, δ_{n−1}) ∈ ω_{1} × … × ω_{n−1} such that,

• letting G^{{1,...,n}} be the restriction of G to those elements of κ^{n+1}

whose last n elements are not δ_{1}, …, δ_{n−1}, η + δ_{n}, and

• letting, for each positive i < n, h_{i}^{{1,...,n}} be the function on ω

whose value at n is h_{i}(n, δ_{1}, …, δ_{i−1}, δ_{i+1}, …, δ_{n−1}, η + δ_{n}),

each h_{i}^{{1,...,n−1}} is in V [G^{{1,...,n}}].

Finally, we see that the function g: ω → 2 defined by setting g(n) = G(n, δ_{1}, …, δ_{n−1}, η + δ_{n}) is Cohen-generic over V [G^{{1,...,n}}]. However, as h_{0}(δ_{1}, …, δ_{n−1}, η + δ_{n}) is a fixed member of ω_{2}, our assumptions on F and h_{0}, …, h_{n} give that g is an element of V [G^{{1,...,n}}]. QED

Putting together Propositions 6.11 and 6.12, we have the following.

Corollary 6.13. Let γ < κ be cardinals, with ℵ_{ω} ≤ γ. After forcing to add a subset of κ by finite conditions, we have that

U(ω_{n}, n + 1) + ¬U(ω_{n}, n) + ¬U(γ, n),

for all positive n ∈ ω.

If we start with a model M_{1} of GCH and force with the set of countable partial functions from κ = ℵ_{ω+1} into 2, then in the resulting model M_{2} we have CH so U(ω_{1}, 1) holds by Theorem 5.1. Proposition 6.11 then gives U(ω_{n}, n) for all positive n ∈ ω. By an argument similar to Proposition 6.12 but raised up one cardinal, we have ¬U(ω_{n}, n − 1) for n ≥ 2. If we then add κ = ω_{3} Cohen reals to M_{2} to get M_{3}, then we will have in M_{3} that |2^{ω}| = ω_{3} and ¬U(ω_{3}, 2) by the argument of Proposition 6.12 lifted by one cardinal. By Proposition 6.11, U(ω_{3}, 4) is true in ZFC. This leaves open the question of whether U(ω_{3}, 3) holds in M_{3}.

Definition 6.14. For Borel universal functions of higher dimensions, we let U(Borel, Σ, n) and U(Borel, n) denote the versions of Definition 6.5 and 6.7 where X is 2^{ω} and F is required to be Borel.

The following proposition follows from the proofs of part (3) of Propositions 6.6 and 6.8, using the fact that the composition of Borel functions is Borel, and the fact that there exist continuous pairing and unpairing functions. The reader interested in constructing a complete proof will also have to verify that the universal functions constructed in Propositions 6.2 and 6.4 are Borel assuming the functions in the hypothesis are, thus yielding the same conclusion for Proposition 6.6 and 6.8.

Proposition 6.15. The following hold for any n ∈ ω.

(1) U(Borel, n) implies U(Borel, n + 1)

(2) U(Borel, Σ, n) is equivalent to U(Borel, m) for m + 1 the size of the smallest subset of n not in the downward closure of Σ.

We can further refine U(Borel, n) in the special case that our universal function F is a level α Borel function. The composition of level α-functions is not necessarily level α, i.e., F (F (x, y), z) need be at the level α just because F is. Hence it is not immediately obvious that the binary case of the next proposition implies the n-ary case. The proof here is similar to that of Rao [22]. Recall from Subsection 1.1 that the hypothesis of the proposition is implied by Martin’s Axiom. The hypotheses on cardinal characteristics in Proposition 6.16 (and Proposition 7.14) are used only to get a set of reals of cardinality 𝔠 which is wellordered by a Borel relation.

Proposition 6.16. Suppose that 𝔱 = 𝔮 = 𝔠. Then for every n > 1 there is a level 2 Borel function F : (2^{ω})^{n} → 2^{ω} which is universal, i.e., such that for every G : (2^{ω})^{n} → 2^{ω} there exist h_{i} : 2^{ω} → 2^{ω} (1 ≤ i ≤ n) such that for every x in (2^{ω})^{n}

G(x_{1}, …, x_{n}) = F (h_{1}(x_{1}), …, h_{n}(x_{n}))

Proof By Proposition 1.5 and the remarks before, it suffices to find an F_{σ} set H ⊆ (2^{ω})^{n} such that for each A ⊆ 𝔠^{n} there exists an h: 𝔠 → 2^{ω} such that for all (α_{0}, …, α_{n−1}) ∈ 𝔠^{n}, (α_{0}, …, α_{n−1}) ∈ A if and only if (h(α_{0}), …, h(α_{n−1})) ∈ H.

Let F ⊆ (2^{ω})^{n+1} be an F_{σ} set with the property that for every F_{σ} set K ⊆ (2^{ω})^{n} there exists x ∈ 2^{ω} with K = F_{x}, i.e., the set of (y_{1}, …, y_{n}) in (2^{ω})^{n} with (x, y_{1}, …, y_{n−1}) ∈ F.

Define the binary relation ≤^{∗} on 2^{ω} by setting x ≤^{∗} y if

x^{−1}[{1}] \ y^{−1}[{1}]

is finite. Let g : 𝔠 → 2^{ω} be an injection such that for each pair α, β from 𝔠, α ≤ β if and only if g(α) ≤^{∗} g(β). The existence of such a function follows from the statement 𝔱 = 𝔠.

For each β < 𝔠, let D_{β} be the set of (α_{0}, …, α_{n−1}) ∈ 𝔠^{n} such that max{α_{0}, …, α_{n−1}} ≤ β. Since 𝔮 = 𝔠, every set X ⊆ 2^{ω} with |X| < 𝔠 is a Q-set (see Subsection 1.1). Thus given A ⊆ 𝔠^{n}, there exists a function k : 𝔠 → 2^{ω} with the property that for each β < 𝔠 and every (α_{0}, …, α_{n−1}) in D_{β}, (α_{0}, …, α_{n−1}) ∈ A if and only if

(k(β), g(α_{0}), …, g(α_{n−1})) ∈ F.

Let ⟨·, ·⟩ be the pairing function on 2^{ω} such that ⟨x, y⟩(2n) = x(n) and ⟨x, y⟩(2n + 1) = y(n), for each n ∈ ω. Now let H be the set of (⟨x_{0}, y_{0}⟩, …, ⟨x_{n−1}, y_{n−1}⟩) ∈ (2^{ω})^{n} such that, for some i < n, x_{j} ≤^{∗} x_{i} for all j < n, and (y_{i}, x_{0}, …, x_{n−1}) ∈ F. Then H is F_{σ}.

Given A ⊆ 𝔠^{n}, for each α < 𝔠, let h(α) be ⟨g(α), k(α)⟩, where k is as above with respect to A. QED

7. Model-theoretic universality

In this section we consider the relationship between the existence of abstract universal functions and the existence of universal models. The key difference is that if one were to consider a universal function as the model of some theory, then embedding would require embedding the range as well as the domain of the function. This is different than the notion of universality being considered here since the values in the range remain fixed. Nevertheless, there is insight to be gained from the model theoretic perspective. It is well known that saturated models are universal in the sense of elementary substructures and that saturated models of cardinality κ exist if κ^{<κ} = κ, see Chapter 5 of Chang and Keisler [5], for instance.

Definition 7.1. For any cardinal κ let L_{κ} be the first order language consisting of a single binary function symbol Φ and constant symbols {c_{γ}}_{γ∈κ} for distinct constants. Let T_{κ} be the L_{κ}-theory consisting of the sentences c_{γ} ≠ c_{β} for γ ≠ β and the sentences Φ(c_{γ}, c_{β}) = c_{0} for all γ, β.

There is some overlap between the following proposition and Theorem 5.1.

Proposition 7.2. If T_{κ} has a model of cardinality κ which is universal in the model theoretic sense, then there is a universal function F : κ × κ → κ.

Proof Let (X, Φ, c_{α})_{α<κ} be a universal T_{κ} model of cardinality κ, and let C = {c_{α} : α < κ}. Universality implies that Y = X \ C has cardinality κ. Let ⟨d_{α} : α < κ⟩ enumerate Y. Define F : κ^{2} → κ by setting F (α, β) to be the unique γ such that Φ(d_{α}, d_{β}) = c_{γ}, if one exists, and 0 otherwise. Given an arbitrary f : κ × κ → κ, construct a T_{κ} model ({b_{α} : α < κ} ∪ C, Φ_{f}, c_{α})_{α<κ} where {b_{α} : α < κ} is disjoint from C and Φ_{f}(b_{α}, b_{β}) = c_{γ} if and only if f(α, β) = γ. Since a model theoretic embedding fixes the constant symbols, we get an h showing that f(α, β) = F (h(α), h(β)) for all α, β ∈ κ. QED

In this section we will use the term Sierpiński universal for the notion of universal function which is the subject of this paper, to distinguish it from model theoretic universality.

Definition 7.3. A function U : κ×κ → κ is Sierpiński universal if for every f : κ × κ → κ there exists h : κ → κ such that for all α, β ∈ κ,

f(α, β) = U(h(α), h(β)).

Definition 7.4. A function U : κ × κ → κ is model theoretically universal if for every f : κ × κ → κ there exists h : κ → κ one-to-one such that for all α, β ∈ κ,

h(f(α, β)) = U(h(α), h(β)).

In other words, a function U: κ × κ → κ is model theoretically universal if and only if every structure (X, f) where f : X^{2} → X and |X| = κ is isomorphic to a substructure of (κ, U).

We define a common weakening of these notions, as follows.

Definition 7.5. A function U : κ × κ → κ is weakly universal if for every f : κ × κ → κ there exist h : κ → κ and k : κ → κ one-to-one such that for all α, β ∈ κ,

k(f(α, β)) = U(h(α), h(β)).

Remark 7.6. The existence of a weakly universal function on κ × κ is not changed if we allow the codomains of U and k to be any set of cardinality κ.

Remark 7.7. Model theoretically universal functions are weakly universal with h = k, and Sierpiński universal functions are weakly universal with k the identity function. implies weakly universal. For maps into 2 (or binary relations) all three notions are equivalent.

Question 7.8. Is the existence of a model theoretically universal function from κ×κ to κ equivalent to the existence of a Sierpiński universal one? Does the existence of either one imply the existence of the other?

Proposition 7.9. If κ is a singular strong limit cardinal then there is a model theoretically universal function from κ × κ to κ.

Proof Let γ be the cofinality of κ, and let ⟨κ_{α} : α < γ⟩ be an increasing sequence of cardinals cofinal in κ. Let G be the set of functions g from κ × κ to κ such that g[κ_{α} × κ_{α}] ⊆ κ_{α} for each α < γ. For any function f: κ × κ → κ, there exist a bijection h: κ → κ and a function g ∈ G such that for all β, δ < κ, h(f(β, δ)) = g(h(β), h(δ)) (that is, (κ, f) is isomorphic to (κ, g) via h). This follows from the fact that we can write κ as a continuous increasing union of a sequence of sets X_{α}, each closed under f and having size κ_{α}.

It suffices then to find a U: κ × κ → κ which is model theoretically universal with respect to functions in G. Since κ is a strong limit cardinal, we can recursively build U so that for each α < γ and each function f: κ_{α} × κ_{α} → κ_{α} there exist X_{f} ⊆ κ and a bijection h_{f}: κ_{α} → X_{f} such that h(f(β, δ)) = U(h(β), h(δ) for all β, δ in κ_{α}. Furthermore, we can build U so that for all α < α′ < γ and all f: κ_{α′} × κ_{α′} → κ_{α′} such that f[κ_{α} × κ_{α}] ⊆ κ_{α}, h_{f↾κ_{α}×κ_{α}} = h_{f} ↾ κ_{α}.

Then for each g ∈ G, ⋃{h_{g↾κ_{α}×κ_{α}} : α, γ} is the desired function h witnessing that U is model theoretically universal with respect to g. QED

Question 7.10. Suppose that κ = ℵ_{ω} is a strong limit cardinal. For each α < κ we have a Sierpiński universal U : κ^{2} → α universal for all maps of the same type, by Theorem 5.1. By Proposition 5.4 we have a map U : κ^{2} → κ which is Sierpiński universal for all maps of the form G : ω^{2} → κ. By Proposition 7.9 we have U : κ^{2} → κ which is model-theoretically universal for all maps of the same type. Is there a Sierpiński universal U : κ × κ → κ for maps of type G : ω × ω_{1} → κ?

Let E_{4} be the theory in the language of a single 4-ary relation A that is an equivalence relation between the first two and last two coordinates. In other words, it has the following axioms:

• A(a, b, c, d) → A(c, d, a, b)

• A(a, b, a, b)
• A(a, b, c, d) & A(c, d, e, f) → A(a, b, e, f)

The transitivity condition on A implies that E_{4} does not have the 3amalgamation property, so Mekler’s argument of [16] (see Theorem 5.12) can not be applied to produce a universal model for this theory of cardinality ℵ_{1} along with 2^{ℵ_{0}} > ℵ_{1}. Nevertheless, the following observation highlights the connection between Sierpiński universality and model theoretic universality.

Proposition 7.11. There is a universal model for E_{4} of cardinality κ if and only if there is a function U : κ × κ → κ which is weakly universal.

Proof

Let (κ, A) be a universal model of E_{4}. Let E be the equivalence relation on κ × κ induced by A and let {E_{ξ}}_{ξ∈κ} enumerate the equivalence classes of E. Define U : κ × κ → κ × 2 by setting U(α, β) = (ξ, 0) if and only if (α, β) ∈ E_{ξ}. We will show that U is weakly universal (using Remark 7.6).

Given g: κ × κ → κ let G be the 4-ary relation defined by letting G(α, β, δ, γ) hold if and only if g(α, β) = g(δ, γ). It is clear that G satisfies the axioms of E_{4} hence there exists an injective h : κ → κ such that G(α, β, δ, γ) holds if and only if A(h(α), h(β), h(δ), h(γ)) does. It follows that g(α, β) = g(δ, γ) if and only if U(h(α), h(β)) = U(h(δ), h(γ)). Then any injection k: κ → κ × 2 such that k(g(α, β)) = U(h(α), h(β)) for all α, β < κ is as desired.

The converse is proved by running the preceding argument backwards — given a Sierpiński universal function U : κ × κ → κ satisfying the hypothesis, define A(α, β, γ, δ) to hold precisely when U(α, β) = U(γ, δ). QED

The next three propositions concern Borel universal functions.

Proposition 7.12. There exists a Borel U : 2^{ω} × 2^{ω} → 2^{ω} which is model theoretically universal with respect to all F : ω_{1} × ω_{1} → ω_{1}.

Proof We first describe U. We use some Borel encoding of the structures below for which the exact details are not important.

Suppose that we are given a, b ∈ 2^{ω}. There are four cases:

Case 1. a codes a pair (n, x), and b codes a pair (m, x), where n, m ∈ ω and x ∈ 2^{ω} codes a tuple (f, B, <, ⟨c_{k} : k ∈ B⟩), where f is a function from ω × ω to ω, B is subset of ω, < is a linear order on ω and each c_{k} is in 2^{ω}; Case 2. Case 1 fails and a codes a pair (n, x), where n ∈ ω, x ∈ 2^{ω} and x codes a tuple (f, B, <, ⟨c_{k} : k ∈ B⟩) as in Case 1, with b = c_{m} for some m ∈ B; Case 3. Cases 1 and 2 fail, and b codes a pair (m, x), where m ∈ ω, x ∈ 2^{ω} and x codes a tuple (f, B, <, ⟨c_{k} : k ∈ B⟩) as in Case 1, with a = c_{n} for some n ∈ B; Case 4. none of the previous cases hold.

In the first three cases, if f(n, m) = k and k ∈ B, then we let U(a, b) = c_{k}, otherwise we let it be (a code for) (k, x). In the fourth case we let U(a, b) = 0.

Now we verify that this works. Given F : ω_{1} × ω_{1} → ω_{1}, let C be a closed unbounded subset of the countable limit ordinals, such that F [α × α] ⊆ α, for each α ∈ C. We recursively define h: ω_{1} → ω_{1} by assuming that we have h ↾ α as desired, for some α ∈ C ∪ {0}, and defining h ↾ min(C \ (α + 1)). Fix such an α, and let α^{+} denote the least member of C above α. Let j : ω → α^{+} be a bijection. Define f : ω × ω → ω by setting f(n, m) = j^{−1}(F (j(n), j(m)), and the binary relation < on ω by setting n < m if and only if j(n) < j(m). Let B = j^{−1}[α], and, for each k ∈ B, let c_{k} = a_{j(k)}. Let x ∈ 2^{ω} be a code for the tuple (f, B, <, ⟨c_{k} : k ∈ B⟩). For each β ∈ [α, α^{+}), let h(β) be (a code for) the pair (j^{−1}(β), x).

Now suppose that we are given β, γ < ω_{1}. Fix α ∈ C ∪{0} such that max(β, γ) is in [α, min(C \ (α + 1))), and let α^{+} = min(C \ (α + 1)) as above. If {β, γ} ⊆ [α, α^{+}), then the pair (h(β), h(γ)) is in Case 1 above. If β = max(β, γ) and γ < α, then (h(β), h(γ)) is in Case 2, and if γ = max(β, γ) and β < α, then (h(β), h(γ)) is in Case 3. In any case, U(h(β), h(γ)) will be h(F (β, γ)). QED

Remark 7.13. The second author has recently shown that the version of Proposition 7.12 with ω_{2} in place of ω_{1} can consistently hold. Moreover, he has shown the following: if there is a Borel Sierpinski universal function and 2^{<𝔠} = 𝔠, then there is a Borel map H : 2^{ω} × 2^{ω} → 2^{ω} such that for every cardinal κ < 𝔠, and for every function G: κ × κ → κ, there exist x_{α} (α < κ) in the Cantor space such that for all α, β, γ < ω_{2} G(α, β) = γ if and only if H(x_{α}, x_{β}) = x_{γ}. Whether this can hold for κ = 𝔠 is still open, as far as we know.

Given an ordinal γ, say that a function f: γ × γ weakly pushes down if f(α, β) < max(α, β) for all α, β < γ.

Proposition 7.14. If 𝔱 = 𝔞𝔭 = 𝔠, then there is a Borel function U : 2^{ω} × 2^{ω} → 2^{ω} such that for every f : 𝔠 × 𝔠 → 𝔠 which weakly pushes down, there exists a one-to-one h : 𝔠 → 2^{ω} such that h(f(α, β)) = U(h(α), h(β)) for all α, β < 𝔠.

Proof Assuming 𝔞𝔭 = 𝔠, by the standard almost-disjoint forcing technique there exists a Borel function F : 2^{ω} × 2^{ω} → 2^{ω} such that for every function g : X → 2^{ω} with X ⊆ 2^{ω} and |X| < 𝔠, there exists y ∈ 2^{ω} with g(x) = F (x, y) for all x ∈ X (see Lemma 3.7, of [7], for instance).

As in the proof of Proposition 6.16, since 𝔱 = 𝔠 we may fix an injection h : 𝔠 → 2^{ω} such that for each pair α, β from 𝔠, α ≤ β if and only if h(α) ≤^{∗} h(β).

Now given any f : 𝔠 × 𝔠 → 𝔠 which pushes down, recursively choose x_{α} ∈ 2^{ω} so that x_{α} = ⟨y_{α}, z_{α}, h(α⟩, t_{α}) where (1) t_{α} is ⟨0, x_{f(α,α)}⟩ if f(α, α) < α and ⟨1, 1⟩ otherwise;

(2) for all β < α, • if f(α, β) < α, then F (x_{β}, z_{α}) = ⟨0, x_{f(α,β)}⟩;

• if f(β, α) < α, then F (x_{β}, y_{α}) = ⟨0, x_{f(β,α)}⟩;

• if f(α, β) = α, then F (x_{β}, z_{α}) = ⟨1, 1⟩;

• if f(β, α) = α, then F (x_{β}, y_{α}) = ⟨1, 1⟩.

Let π_{0} and π_{1} be such that x = ⟨π_{0}(x), π_{1}(x)⟩ for all x ∈ 2^{ω}. Using this we may define the Borel function U by setting U(x, x′), where x = ⟨y, z, s, t⟩ and y = (y′, z′, s′, t′) to be

• π_{1}(F (x, y′)) if s <^{∗} s′ and π_{0}(F (x, y′)) = 0;

• π_{1}(F (x′, z)) if s′ <^{∗} s and π_{0}(F (x′, z)) = 0;

• x′ if s <^{∗} s′ and π_{0}(F (x, y′)) = 1;

• x if s <^{∗} s′ and π_{0}(F (x′, z)) = 1;

• x if x = x′ and π_{0}(F (x, x)) = 1;

• t otherwise.

One can now verify that f(α, β) = γ if and only if U(x_{α}, x_{β}) = x_{γ} for all α, β, γ < 𝔠 by considering the cases α < β, β < α, and α = β. QED

The identity function satisfies the analogous notion of Sierpiński universality for unary maps. The corresponding result for model theoretic universality appear to be more difficult.

Proposition 7.15. Define π : 2^{ω} → 2^{ω} by setting π(x) = y if and only if ∀n y(n) = x(2n). Then π is a model theoretically universal for all maps f : 𝔠 → 𝔠.

Proof Any function g: X → X from a set X to itself induces a partition {Q(x) : x ∈ X} of X, where each Q(x) is the smallest subset of X closed under g-images and g-preimages with x as a member. We will refer to the sets Q(x) as g-components. For each x ∈ X, the pre-image tree of x (according to g) is the tree of height at most ω whose root is x, and for which the immediate successors of each node y are the members of g^{−1}[{y}]. Let T_{g}(x) denote the set of nodes of this tree. A g-component Q either contains a unique cycle of length n, for some positive n ∈ ω, or it contains none. In the former case, Q consists of the union of the sets T_{g}(x), for each member x of the cycle, and we say that the component has type n. In the latter case, for each x in Q, Q = ⋃{T_{g}(g^{i}(x)) : x ∈ ω}, and we say that the component has type ω.

Fix a function f: 𝔠 → 𝔠. We seek a function h: 𝔠 → 2^{ω} such that h(f(α)) = π(h(α) for all α ∈ 𝔠. Since the π-preimage of each singleton from 2^{ω} has size continuum, the analysis of the previous paragraph shows that it suffices to prove that there are continuum many π-components of type n, for each positive n ∈ ω, and continuum many π-components of type ω, as then the components of f can be embedded into distinct π-components.

For each x ∈ 2^{ω}, and all i, n ∈ ω, π^{n}(x)(i) = x(2^{n}(i)). Given a positive n ∈ ω, x is then part of a cycle of length n if x(2^{n}i) = x(i) for all i ∈ ω. There are continuum many such x, as the values x(i) can be chosen freely for each odd i ∈ ω. Since each component of type n contains exactly n such x’s, there are continuum many π-components of type n.

On the other hand, one can build by recursion an increasing sequence of natural numbers ⟨p_{i} : i < ω⟩ and a collection of sequences t_{σ} ∈ 2^{p_{|σ|}} for each σ ∈ 2^{<ω} such that for each pair n, m ∈ ω there exists an i ∈ ω such that for each pair σ, σ′ ∈ 2^{i}, if either n ≠ m or σ ≠ σ′ then there exists j ∈ ω such that 2^{n}j, 2^{m}j < p_{i} and t_{σ}(2^{m}j) ≠ t_{σ′}(2^{n}j). Then the sets ⋃{t_{y↾p_{i}} : i < ω} (y ∈ 2^{ω}) are members of distinct π-components of type ω. QED

Finally, we indicate another possible distinction between Sierpiński universal functions and model theoretically universal ones. Let us say that a function f : κ × κ → κ is Sierpiński universal for regressive functions if for every function g : κ × κ → κ such that g(α, β) < max(α, β) for all α, β (other than α = β = 0) there exists h : κ → κ such that f(h(α), h(β)) = g(α, β) for all α, β in κ.

Proposition 7.16. If κ is regular, then every f: κ × κ → κ which is Sierpiński universal for regressive functions is Sierpiński universal.

Proof Let f : κ × κ → κ be Sierpiński universal for regressive functions and fix g : κ × κ → κ. Let j : κ → κ be an increasing function such that g(ξ, η) < j(α) for all (ξ, η) ∈ (α + 1)^{2}, and let

g^{∗}(ξ, η) = \begin{cases}g(j^{−1}(ξ), j^{−1}(η)) & if ξ and η are in the range of j \\ 0 & otherwise. \end{cases}

Since g^{∗}(α, β) is either 0 or equal to g(j^{−1}(α), j^{−1}(β)) < max(α, β) and f is weakly Sierpiński universal there exists an h : κ → κ such that f(h(α), h(β)) = g^{∗}(α, β) for all α, β in κ. Then f(h(j(α)), h(j(β))) = g^{∗}(j(α), j(β)) = g(α, β) for all α, β in κ, so h ∘ j is the required embedding. QED

Question 7.17. Is Proposition 7.16 is true for the analogous notion of model theoretically universal for regressive functions?

In the proof of Proposition 7.16, the given function g was embedded into the regressive function g^{∗}. Note however that if g : κ × κ → κ is such that g(α, β) < max(α, β) for all α, β (aside from α = β = 0), then no substructure of (κ, g) is isomorphic to the positive integers under addition. To see this, suppose toward a contradiction that π : ω → κ is one-to-one and ∀n, m, k > 0

n + m = k iff g(π(n), π(m)) = π(k)

then

π(2n) = π(n + n) = g(π(n), π(n)) < π(n)

and therefore (π(2^{n}) : n < ω) is an infinite descending sequence of ordinals.

8. Appendix

We conclude this section with an argument, due to Justin Moore, which shows that under the Proper Forcing Axiom there are no functions with property R.^{5} We begin by introducing some notation.

Given a function Φ: [ω_{1}]^{2} → ω, a finite set F ⊆ ω_{1} and k ∈ ω, we let B_{k}(Φ, F) denote the set

{β ∈ ω_{1} | (∀α ∈ F) Φ({α, β}) > k } .

Lemma 8.1. Suppose that Φ: [ω_{1}]^{2} → ω is a function with Property R. Then for each k ∈ ω there exists an α < ω_{1} such that for each finite F ⊆ ω_{1} either F ∩ α ≠ ∅ or B_{k}(Φ, F) is uncountable.

Proof Otherwise, there exist infinitely many pairwise disjoint F for which B_{k}(Φ, F) is countable. Then there exist β ∈ ω_{1} and an infinite pairwise disjoint family of finite sets F for which F ⊆ β and β ∉ B_{k}(Φ, F). This yields infinitely many ξ ∈ β such that Φ({β, ξ}) ≤ k contradicting that Φ satisfies Property R.

5We thank Alan Dow for discussions clarifying this argument.

QED

Applying Lemma 8.1, we can find for any function Φ with Property R a minimal ordinal α(Φ) with the property that for any k ∈ ω and any finite F ⊆ ω_{1} either F ∩ α(Φ) ≠ ∅ or B_{k}(Φ, F) is uncountable.

Given a function Φ: [ω_{1}]^{2} → ω with Property R let ℙ(Φ) be the partial order consisting of pairs (A, M) such that:

• A is a finite set of pairs from ω_{1} \ α(Φ), and for all distinct a, b ∈ A, a ⊆ min(b) or b ⊆ min(a);

• M is a finite ∈-chain of elementary submodels of H(ℵ_{2}), each having Φ as a member.

• For all a ∈ A, there is 𝔐 ∈ M such that |𝔐 ∩ a| = 1.

• For all a ∈ A and b ∈ A such that a ⊆ min(b), there is 𝔐 ∈ M such that a ⊆ 𝔐 and b ∩ 𝔐 = ∅.

• For all distinct a, b from A,

Φ({min(a), min(b)}) < Φ({max(a), max(b)}).

The ordering on ℙ(Φ) is : (A, M) ≤ (B, N) if B ⊆ A, N ⊆ M and, for all 𝔐 ∈ N and all a ∈ A, if |𝔐 ∩ a| = 1, then a ∈ B.

The partial order ℙ(Φ) adds an uncountable set of pairs from ω_{1} witnessing the failure of Property R for Φ.

Claim 8.2. Given any (A, M) ∈ ℙ(Φ) and ξ ∈ ω_{1} there exists a condition (A′, M′) ≤ (A, M) such that (⋃ A′) \ ξ ≠ ∅.

Proof By adding a model to the top of M if necessary, we may assume that there is 𝔐 ∈ M such that A ∈ 𝔐 and ξ < ω_{1} ∩ 𝔐. Let γ be any element of ω_{1} greater than ω_{1} ∩ 𝔐, and extend M to M′ by adding an elementary submodel 𝔐′ on top with γ < ω_{1} ∩ 𝔐′. Let k > Φ({α, β}) for all distinct α, β from (⋃ A) ∪ {γ}. Then B_{k}(Φ, (⋃ A) ∪ {γ}) is uncountable since ((⋃ A) ∪ {γ}) ∩ α(Φ) = ∅. Let δ ∈ B_{k}(Φ, ⋃ A) \ 𝔐′. Then (A ∪ {{γ, δ}}, M′) ∈ ℙ(Φ).

Claim 8.3. ℙ(Φ) is proper.

Proof Let (A, M) ∈ ℙ(Φ) and (A, M) ∈ 𝔐 ≺ H(κ) for some uncountable κ. Since 𝔐∩H(ℵ_{2}) ≺ H(ℵ_{2}) it suffices to show that (A, M ∪{𝔐∩H(ℵ_{2})}) is ℙ(Φ)-generic for 𝔐. To see this, let D ∈ 𝔐 be a dense subset of ℙ(Φ) and suppose that (B, N) ∈ D is such that (B, N) ≤ (A, M ∪ {𝔐}). Since there is no a ∈ A with |a ∩ 𝔐| = 1, by the definition of the order on ℙ(Φ) , there is also no b ∈ B with |b ∩ 𝔐| = 1. Let {b_{1}, …, b_{j}} enumerate (⋃ B) \ 𝔐 in such a way that min(b_{i}) increases with i, and for each i ∈ {1, …, j}, let β_{2i+1} = min(b_{i}) and β_{2i+2} = max(b_{i}).

Let S be the set of increasing sequences of ordinals ⟨γ_{1}, …, γ_{2j}⟩ such that

(1) γ_{1} is greater than every member of ⋃(B ∩ 𝔐);

(2) letting π: ⋃ B → (⋃(B ∩ 𝔐)) ∪ {γ_{1}, …, γ_{2j}} be an orderpreserving bijection, Φ({α_{1}, α_{2}}) = Φ({π(α_{1}), π(α_{2})}) for all α_{1} < α_{2} from ⋃ B;

(3) for some N′ containing 𝔐 ∩ N,

((B ∩ 𝔐) ∪ {{γ_{2i+1}, γ_{2i+2}} : i ∈ j}, N′)

is an element of D. Notice that while the Condition 2 mentions an object outside 𝔐, this object is finite and so the condition can be described by a first order formula in 𝔐 ∩ H(ℵ_{2}). Since the theory H(ℵ_{2}) can be coded by a real in transitive models, the existence of N′ posited in Condition 3 can also be described in 𝔐 ∩ H(ℵ_{2}).

As a consequence, if T_{0} is defined to be the tree consisting of all initial segments of members of S, then, since T_{0} ∈ H(ℵ_{2}), T_{0} ∈ 𝔐 and T_{0} is an element of every model of N containing 𝔐∩H(ℵ_{2}). Since ⟨β_{1}, …, β_{j}⟩ ∈ S, and since each β_{2i+1} is separated by elementary submodels in N from β_{2i+2}, T_{0} can be thinned (in 𝔐) to a tree T_{1}, still containing ⟨β_{1}, …, β_{j}⟩, such that every node of T_{1} on an odd level (where the least level is the 1st level) has uncountably many immediate successors. Finally, still in 𝔐, thin T_{1} to a tree T, still of height j, such that each node of T on an even level has infinitely many immediate successors.

We wish to pick a sequence ⟨γ_{1}, …, γ_{2j}⟩ from T such that, for some N′ containing N, (B ∪ {{γ_{2i+1}, γ_{2i+2}} : i ∈ j}, N′) is a condition. We pick the γ_{i}’s recursively, picking any available ordinal when i is odd. When i is even, we need to pick γ_{i} so that, for each b ∈ B \ 𝔐 Φ({γ_{i−1}, min(b)}) < Φ({γ_{i}, max(b)}). Since B is finite, and we have infinitely many possibilities for γ_{i}, we can meet this condition, using the finite-to-one property of Φ.

References

[1] Bell, Murray G.; On the combinatorial principle P (𝔠). Fund. Math. 114 (1981), no. 2, 149-157.

[2] Blass, Andreas; Combinatorial cardinal characteristics of the continuum. Handbook of Set Theory, Foreman, Kanamori, eds., Springer, 2010

[3] Bing, R. H.; Bledsoe, W. W.; Mauldin, R. D.; Sets generated by rectangles. Pacific J. Math. 51 (1974), 27-36.

[4] Brendle, J.; Mutual generics and perfect free subsets. Acta Math. Hungar. 82 (1999), no. 1-2, 143-161.

[5] Chang, C. C.; Keisler, H. J.; Model theory. Third edition. Studies in Logic and the Foundations of Mathematics, 73. North-Holland Publishing Co., Amsterdam, 1990. xvi+650 pp. ISBN: 0-444-88054-2

[6] Davies, Roy O.; Representation of functions of two variables as sums of rectangular functions. I. Fund. Math. 85 (1974), no. 2, 177–183.

[7] Hjorth, Greg; Humphries, Leigh; Miller, Arnold; Universal sets for pointsets properly on the nth level of the projective hierarchy, Journal of Symbolic Logic 78 (1), 2013, 237–244

[8] Kechris, Alexander S.; Classical descriptive set theory. Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995. xviii+402 pp. ISBN: 0-387-94374-9

[9] Kunen, Kenneth; Inaccessibility properties of cardinals. Ph.D. Thesis, Stanford University. 1968

[10] Kunen, Kenneth; Set Theory. An introduction to independence proofs. Reprint of the 1980 original. Studies in Logic and the Foundations of Mathematics, 102. North-Holland Publishing Co., Amsterdam, 1983. xvi+313 pp. ISBN: 0-444-86839-9

[11] Louveau, Alain; A separation theorem for Σ_{1}^{1} sets. Trans. Amer. Math. Soc. 260 (1980), no. 2, 363–378.

[12] Mansfield, Richard; The solution of one of Ulam’s problems concerning analytic rectangles. 1971 Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) pp. 241–245 Amer. Math. Soc., Providence, R.I.

[13] Mansfield, Richard; The solution to one of Ulam’s problems concerning analytic sets. II. Proc. Amer. Math. Soc. 26 1970 539–540.

[14] Malliaris, Maryanthe; Shelah, Saharon; Cofinality spectrum theorems in model theory, set theory, and general topology. preprint, 2012.

[15] Mauldin, R. Daniel (Editor), Mathematics from the Scottish Cafe. Including selected papers presented at the Scottish Book Conference held at North Texas State University, Denton, Tex., May 1979. Edited by Birkhauser, Boston, Mass., 1981. xiii+268 pp. (2 plates). ISBN: 3-7643-3045-7

[16] Mekler; Alan H.; Universal structures in power ℵ_{1}. J. Symbolic Logic, 55(2):466–477, 1990.

[17] Miller, Arnold W.; On the length of Borel hierarchies. Ann. Math. Logic 16 (1979), no. 3, 233–267.

[18] Miller, Arnold W.; Generic Souslin sets. Pacific J. Math. 97 (1981), no. 1, 171–181.

[19] Miller, Arnold W.; Measurable rectangle. Real Anal. Exchange 19 (1993/94), no. 1, 194–202.

[20] Miller, Arnold W.; Descriptive set theory and forcing. Lecture Notes in Logic, 4. Springer-Verlag, Berlin, 1995

[21] Rado, R.; Universal graphs and universal functions. Acta Arith. 9 1964 331– 340.

[22] Rao, B. V.; On discrete Borel spaces and projective sets. Bull. Amer. Math. Soc. 75 1969 614–617.

[23] Rao, B. V.; Remarks on analytic sets. Fund. Math. 66 1969/1970 237–239.

[24] Shelah, Saharon; On universal graphs without instances of CH. Ann. Pure Appl. Logic 26 (1984), no. 1, 75–87.

[25] Shelah, S.; A graph which embeds all small graphs on any large set of vertices. Ann. Pure Appl. Logic 38 (1988), no. 2, 171–183.

[26] Shelah, Saharon; Universal graphs without instances of CH: revisited. Israel J. Math. 70 (1990), no. 1, 69–81.

[27] Shelah, Saharon; On Ciesielski’s Problems. J Applied Analysis 3 (1997) 191– 209

[28] Shelah, Saharon; Steprāns, Juris, Extraspecial p-groups. Ann. Pure Appl. Logic 34 (1987), no. 1, 87–97

[29] Sierpiński, Waclaw; Sur une function universelle de deux variables reelles, Bull Acad Sci Cracovie A(1936), 8–12.

[30] Sierpiński, Waclaw; Hypothèse du continu. Monogr. mat. 4. Warszawa-Lwow: Subwencji Funduszu Kultur. Narodowej. V, 192 S. , 1934.

[31] Solovay, Robert M.; A model of set-theory in which every set of reals is Lebesgue measurable. Ann. of Math. (2) 92 1970, 1–56

[32] Todorcevic, Stevo; A universal sequence of continuous functions. The Teaching of Mathematics 14 (2011) 2, 71-76

[33] Weiss, William; Versions of Martin’s axiom. Handbook of Set-Theoretic Topology, 827, North-Holland, Amsterdam, 1984.

Paul B. Larson larsonpb@miamioh.edu http://www.users.miamioh.edu/larsonpb Department of Mathematics Miami University Oxford, Ohio 45056

Arnold W. Miller miller@math.wisc.edu http://www.math.wisc.edu/∼miller University of Wisconsin-Madison Department of Mathematics, Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388

Juris Steprāns steprans@yorku.ca York University Department of Mathematics 4700 Keele Street Toronto, Ontario Canada M3J 1P3 William A.R. Weiss weiss@math.toronto.edu Department of Mathematics University of Toronto, Ontario Canada M5S 3G3