MOST ALGEBRAS HAVE THE INTERPOLATION PROPERTY

MARTIN GOLDSTERN

Abstract. We show that for “almost all” algebras on a given set A, every function on A can be interpolated by a polynomial on any set of cardinality κ (for reasonable κ).

1. Introduction

Let 𝔄 = (A, f_{1}, …, f_{n}) be a universal algebra. Let F (A) be the set of all functions from some A^{t} to A (t ∈ {0, 1, 2, 3 … }), P (𝔄) the set of polynomial functions.

If A is a finite set, then it is possible to have F (A) = P (𝔄). In fact, “most” algebras will have this property, see [6]. For infinite A this is impossible by cardinality considerations: |F (A)| = 2^{|A|} > |A| = |P (𝔄)|.

We can still ask if we can “interpolate” all functions by polynomial functions on sufficiently large sets: Let L_{k}P (𝔄) be the set of “k-local” polynomial functions, [that is, functions which can be interpolated by a polynomial on any set containing less than 1 + k (i.e., ≤ k) many points], then we have

F (A) = L_{1}P (𝔄) ⊇ L_{2}P (𝔄) ⊇ ⋯ ⊇ L_{ℵ_{0}}P (𝔄)

where L_{ℵ_{0}}P (𝔄) is the set of all “local” polynomial functions, i.e., functions that can be interpolated by a polynomial on any finite set of points.

This sequence can also be continued into the transfinite by considering L_{κ}P (A) for infinite cardinals κ. We define L_{κ}P (𝔄) to be the set of all functions from some A^{t} into A which can be interpolated by a polynomial on any set of < κ many points. (So L_{κ^{+}}P (𝔄) is the set of functions that can be interpolated by a polynomial on any set of ≤ κ many points. See also 6.1.3)

Trivially, κ < κ′ implies L_{κ}P (𝔄) ⊇ L_{κ′}P (𝔄), and we have L_{κ}P (𝔄) = P (𝔄) whenever κ > |A|, but what else can be said about these various degrees of interpolability? For which κ can we have F (A) = L_{κ}P (𝔄)? In particular, are there algebras 𝔄 on which all functions are interpolable on all sets of cardinality smaller than A itself, i.e., F (A) = L_{|A|}P (𝔄)?

János Kollár in [4] has shown that the answer is “yes” iff |A| = |A|^{<|A|}. It is easy to see (e.g., from 6.2.4, 6.2.6 and 6.3.5), that |A| = |A|^{<|A|} holds iff

– either |A| = ℵ_{0},

– or |A| = κ^{+} = 2^{κ} for some infinite cardinal κ,

– or |A| is a strongly inaccessible cardinal.

We give a criterion to decide, for regular κ, when there are algebras 𝔄 satisfying the κ-interpolation property (i.e., F (A) = L_{κ}P (𝔄)), and we show that a kind of “0-1-law” holds: If one algebra on the underlying set A has the κ-interpolation property, then “almost all” algebras have this property.

Date: July 3, 97.

1991 Mathematics Subject Classification. 08A40, 54H99.

Key words and phrases. polynomial function, infinite interpolation, meager set.

For a fixed set A, a trivial counting argument (see 1.6) gives an upper bound κ^{∗}(A) for the set

K(A) := {κ : there is an algebra 𝔄 on the set A with the κ-IP}.

In 2.7 we show that this bound is sharp: For any κ ≤ κ^{∗}(A) there are algebras with the κ-IP. Moreover, for a fixed similarity type τ and a fixed set A we can define a topology on Alg_{τ} (A), the set of algebras of type τ with underlying set A, which naturally induces an ideal on Alg_{τ} (A), and we will show that except for a set in this ideal, all algebras in Alg_{τ} (A) have the κ-IP but not the κ^{+}-IP. In particular, for any κ ≤ κ^{∗}(A) there are many 𝔄 ∈ Alg_{τ} (A) with F (A) = L_{κ}P (𝔄) ≠ L_{κ^{+}}P (𝔄).

A variation of this argument (in 3.3) gives many algebras on A that have a majority function, and have the κ-IP but not the κ^{+}-IP. This stands in contrast to the case of finite k, where in the presence of a majority function the k-IP implies the k + 1-IP (and hence even the ℵ_{0}-IP).

For the special case of a countable set A we show in 4.5 that the set of algebras on A with the IP is residual (=co-meager) in the Tychonoff topology. If A is uncountable then the set of algebras with the IP is dense but not co-meager in the Tychonoff topology.

Finally we investigate the case of unary algebras in section 5.

In an appendix we review basic notions from set theory.

Acknowledgements. Part of this research was carried out while I was supported by a Schrödinger fellowship from the Austrian Science foundation (FWF).

I am grateful to the referee for pointing out many inaccuracies in previous versions of this paper.

Setup 1.1. We fix a finite similarity type τ = (t_{1}, …, t_{n}), where the t_{ℓ} are finitely many natural numbers. ℓ will always range over 1, …, n. We will assume that one of the t_{ℓ}, say t_{1}, is at least 2. (See section 5 for the case of unary algebras.)

To simplify the notation (but really without loss of generality) we assume t_{1} = 2.

Notation 1.2. Let A be a nonempty (usually: infinite) set, t a natural number (usually > 0). A t-ary operation on A is a function from A^{t} into A. We write dom(f) and ran(f) for the domain and range of f.

We let

F^{t}(A, B) = {f : dom(f) = A^{t}, ran(f) ⊆ B}
F (A, B) = ⋃_{t=0}^{∞} F^{t}(A, B)

and we let F^{t}(A) = F^{t}(A, A), F (A) = F (A, A).

We will often have occasion to also consider partial operations, in particular partial operations with small domain:

F̃^{t}(A, B) = {f : dom(f) ⊆ A^{t}, ran(f) ⊆ B}
F̃_{κ}^{t}(A, B) = {f ∈ F̃^{t}(A, B) : | dom(f)| < κ}
F̃(A, B) = ⋃_{t=1}^{∞} F̃^{t}(A, B)
F̃(A) = F̃(A, A), etc.

A function is a set of ordered pairs. So if f and g are functions, then f ⊆ g means that f is a restriction of g.

If f is a function, A a set, then f↾A is the restriction of f to A ∩ dom(f), i.e.,

f↾A := f ∩ (A × ran(f))

For any set A we let

Alg_{τ} (A) := {(A, f_{1}, …, f_{n}) : ∀ℓ f_{ℓ} ∈ F^{t_{ℓ}}(A)}

Since A is usually held constant, we identify (A, f_{1}, …, f_{n}) with (f_{1}, …, f_{n}).

Definition 1.3. If 𝔄 = (A, f_{1}, …, f_{n}) is in Alg_{τ} (A), then we define the set of polynomial functions, P (𝔄) or P (A, f_{1}, …, f_{n}), as the smallest set of functions that contains all the constant functions and projections, and is closed under the (pointwise) operations f_{ℓ}. So P (𝔄) ⊆ F (A).

P̃(𝔄) ⊆ F̃(A) is the set of all partial functions which are restrictions of polynomial functions, P̃^{t}(𝔄) = P̃(𝔄) ∩ F̃^{t}(A), etc.

Definition 1.4. Let κ be an infinite cardinal. 𝔄 = (A, f_{1}, …, f_{n}) has the κ-IP if: For all t ∈ ω, all f ∈ F^{t}(A), all B ⊆ A^{t}:

If |B| < κ, then there is g ∈ P^{t}(𝔄), g↾B = f↾B.

The next fact is just a reformulation of this definition.

Fact 1.5. 𝔄 = (A, f_{1}, …, f_{n}) has the κ-IP iff F̃_{κ}(A) ⊆ P̃(𝔄).

If the underlying set A has size λ, then there are of course only λ many polynomials on A, whereas |F (A)| = λ^{λ} = 2^{λ} > λ. It is still possible for 𝔄 to have the κ-IP (for sufficiently small κ), since the same polynomial can serve for many partial functions. The following observation, a straightforward generalization of [4, 4.1], gives an upper bound on κ:

Lemma 1.6. Assume that 𝔄 = (A, f_{1}, …, f_{n}) has the κ-IP, |A| ≥ ℵ_{0}. Then |A|^{<κ} = |A|. (See 6.2)

Proof. Clearly 𝔄 does not have the |A|^{+}-IP, so κ ≤ |A|.

Let μ < κ be arbitrary, and fix a set B ⊆ A of size μ. We have |F^{1}(B, A)| = |A|^{μ}. Each f ∈ F^{1}(B, A) is the restriction of some polynomial function f̄ ∈ P^{1}(𝔄), and clearly f ≠ f′ implies f̄ ≠ f̄′, so |A| = |P^{1}(𝔄)| ≥ |A|^{μ}.

Reformulation 1.7. Let κ^{∗}(A) := min{κ : |A|^{κ} > |A|}. Then 𝔄 can have the κ-IP only if κ ≤ κ^{∗}(A).

In section 2 we will show that this estimate is best possible. That is: If κ ≤ κ^{∗}(A), then “most” algebras on A will have the κ-IP. (Our notion of “most” will depend on κ, see 2.4.)

2. κ-topologies

We will consider universal algebras of a fixed type τ = (t_{1}, …, t_{n}), over a fixed (infinite) set A, i.e., structures of the form 𝔄 = (A, f_{1}, …, f_{n}), where f_{ℓ} ∈ F^{t_{ℓ}}(A). We assume t_{1} = 2.

Fact 2.1. If A is an infinite set of cardinality λ, κ a cardinal ≤ λ, then there is a continuous increasing chain (A_{γ} : γ < κ) such that ⋃_{γ<κ} A_{γ} = A and ∀γ < κ : |A_{γ+1} \ A_{γ}| = λ, |A_{γ}| = λ. (See section 6.3)

Proof. Since κ · λ = λ, there is a bijection f : {(α, β) : α < λ, β < κ} → A. Let A_{α} := {f(γ, β) : γ < λ, β < α}.

Definition 2.2. Assume that A, (A_{γ} : γ < κ) satisfy – A = ⋃_{γ<κ} A_{γ}, |A| = λ

– (A_{γ} : γ < κ) is continuous and increasing

– ∀γ < κ : |A_{γ+1} \ A_{γ}| = λ, |A_{γ}| = λ. Then:

1. For any γ < κ we let

Fun(γ) := {(η_{1}, …, η_{n}) : each η_{ℓ} is in F^{t_{ℓ}}(A_{γ}, A)}

2. For η = (η_{1}, …, η_{n}) ∈ Fun(γ) we define

B_{η} := {(f_{1}, …, f_{n}) ∈ Alg_{τ} (A) : for each ℓ, η_{ℓ} ⊆ f_{ℓ}}

Definition and Remark 2.3. The family {B_{η} : η ∈ Fun(γ), γ < κ} is a basis for a Hausdorff topology on Alg_{τ} (A).

For different choices of the family (A_{γ} : γ < κ) we will of course get different topologies. We call each topology that is obtained in this way a κ-topology.

Definition 2.4. Let (X, E) be a topological space. We say that Y ⊆ X is κ-meager if Y can be covered by κ many nowhere dense sets (or equivalently, by κ many closed sets with empty interior). We say that Y ⊆ X is κ-residual (= κ-co-meager) if X \Y is κ-meager.

Clearly the κ-meager sets form an ideal. (In the general case this ideal may be improper, e.g. if κ is too large. See 4.3 for a less trivial example.)

Terminology 2.5. Assume J is a proper ideal on a (nonempty) set X. Sets in J are considered to be “negligible” or “small”, while sets in the dual filter are considered to be “large”.

We express this intuitive notion of small vs large also in the following way: Let p( ·) be any property. We say that “p(x) holds for J -almost all x ∈ X”(or “J - almost every (J -a.e.) x has property p”) iff

{x ∈ X : p(x) does not hold} ∈ J .

This terminology is derived from measure theory: If μ is a measure, then the customary notion of “μ-a.e.” is in our language “N_{μ}-a.e.”, where N_{μ} is the ideal of μ-null sets, i.e., N_{μ} = {Y ⊆ X : μ(Y) = 0}.

If the definition of J is sufficiently “natural”, then we may write “almost every” instead of “J -almost every”.

Of course such a terminology would not be justified if J were improper, i.e., if X ∈ J. The following lemma, a straightforward generalization of Baire’s theorem, shows that all our ideals are proper.

Lemma 2.6. Let E be a κ-topology on Alg_{τ} (A). Then Alg_{τ} (A) is not κ-meager.

Moreover, no nonempty open set in Alg_{τ} (A) is κ-meager, i.e., the complement of any κ-meager set is still dense.

Proof. Let U be an open set, and let (C_{α} : α < κ) be a family of closed nowhere dense sets. Let O_{α} := Alg_{τ} (A) \ C_{α}. We have to show that U ∩ ⋂_{α<κ} O_{α} is not empty.

Let η_{0} = (η_{0,1}, …, η_{0,n}) ∈ Fun(γ_{0}) be such that B_{η_{0}} ⊆ U. We will define sequences (η_{α} : α < κ) and (γ_{α} : α < κ), η_{α} = (η_{α,1}, …, η_{α,n}) ∈ Fun(γ_{α}), with the following properties:

1. ∀α ∀β : α < β ⇒ γ_{α} < γ_{β}.

2. ∀ℓ ∀α ∀β : α < β ⇒ η_{α,ℓ} ⊂ η_{β,ℓ} (hence B_{η_{α}} ⊃ B_{η_{β}}).

3. ∀ℓ ∀α: If α is a limit ordinal, then η_{α,ℓ} = ⋃_{β<α} η_{β,ℓ} and γ_{α} = sup{γ_{β} : β < α}.

4. ∀α: B_{η_{α+1}} ⊆ O_{α}. The construction of this sequence is straightforward. For limit steps, η_{α} is given by 3, and in successor steps we have to find γ_{α+1} and η_{α+1} ∈ Fun(γ_{α+1}) satisfying B_{η_{α+1}} ⊆ O_{α} ∩ B_{η_{α}}. This is possible because O_{α} is dense open and B_{η_{α}} is open.

Finally, let f_{ℓ} := ⋃_{α<κ} η_{α,ℓ}. Note that sup_{α<κ} γ_{α} = γ, so dom(f_{ℓ}) = ⋃_{α<κ} A_{α}^{t_{ℓ}} = A^{t_{ℓ}}, so f_{ℓ} is a total function in F^{t_{ℓ}}(A). Clearly (f_{1}, …, f_{n}) ∈ ⋂_{α<κ} O_{α} ∩ U.

The following theorem shows that the condition |A| = |A|^{<κ} is not only necessary for an algebra on A to have the κ-IP, but will in “most” cases also be sufficient.

Theorem 2.7. Assume that A is infinite, κ an infinite regular cardinal satisfying |A|^{<κ} = |A|. Then the set of algebras on A of type τ which have the κ-interpolation property is κ-residual in any κ-topology.

For example, choosing a set A of size 2^{ℵ_{0}} and κ = ℵ_{1} we conclude that in any ℵ_{1}-topology on A, “almost all” algebras on A have the property that all functions can be interpolated by a polynomial on any countable set.

Informally, the main point of the proof is the following: Fix a basic set B_{ν}, ν ∈ Fun(α), ν = (ν_{1}, …, ν_{n}). We have to find an η = (η_{1}, …, η_{n}) such that the basic set B_{η} is a subset of B_{ν} and all algebras in B_{η} have the interpolation property with respect to sufficiently many partial functions. (For the details about bookkeeping see the formal proof below.) It turns out that choosing η_{1} appropriately will be sufficient — η_{2}, …, η_{n} can be chosen arbitrarily subject to the requirement that they extend ν_{2}, …, ν_{n}, respectively.

Assume first that we are only concerned with a single partial unary function σ. Recall that ν_{1} : A_{α}^{2} → A. We can pick some element c_{σ} ∈ A_{α+1} \ A_{α} and extend ν_{1} to a function η_{1} : A_{α+1}^{2} → A such that the function x ↦ η_{1}(c_{σ}, x) extends σ. Now for any algebra (A, f_{1}, f_{2}, …) with f_{1} extending η_{1} the partial function σ will be the restriction of the polynomial f_{1}(c_{σ}, x).

We can deal in this way with many functions σ simultaneously, since A_{α+1} \A_{α} is quite large.

Now consider the case with a function σ which is binary: the domain of σ is a set of pairs. For each a which appears as a first coordinate in the domain of σ pick a (distinct) constant c_{σ,a} ∈ A_{α+1} \ A_{α}, and stipulate η_{1}(c_{σ,a}, b) = σ(a, b) for all relevant b. Then pick a new constant c_{σ} ∈ A_{α+1} \ A_{α} and stipulate η_{1}(c, a) = c_{σ,a}. Clearly, then

f_{1}(f_{1}(c, a), b) = f_{1}(c_{σ,a}, b) = σ(a, b)

for all (a, b) ∈ dom(σ) whenever f_{1} is any function extending η_{1}.

k-ary partial functions are treated similarly. This ends our informal description of the proof of theorem 2.7.

The proof of theorem 2.7 is based on the following lemma:

Lemma 2.8. Assume |A|^{<κ} = |A|, and let (A_{α} : α < κ) induce a κ-topology on Alg_{τ} (A) as in 2.2.

Let β < κ. Then the set

U_{β} := {(f_{1}, …, f_{n}) ∈ Alg_{τ} (A) : F̃_{κ}(A_{β}, A) ⊆ P̃(f_{1}, …, f_{n})}

contains a dense open set.

(Note: U_{β} is the set of all algebras 𝔄 such that, for any t, every partial t-ary function whose domain is a subset of A_{β} of cardinality < κ is the restriction of a polynomial function over 𝔄.)

Proof. First we need to define some notation: If f is a binary function, then we define f^{[2]} := f and f^{[t+1]}(x_{0}, …, x_{t}) = f^{[t]}(f(x_{0}, x_{1}), x_{2}, …, x_{t}) for t ≥ 2.

If dom(g) ⊆ A^{t}, x ∈ A, then we define the (t − 1)-ary (partial) function g_{[x]} by

g_{[x]}(x_{2}, …, x_{t}) := g(x, x_{2}, …, x_{t}) whenever (x, x_{2}, …, x_{t}) ∈ dom(g).

We will prove lemma 2.8 by finding, for each basic open set B_{ν}, a basic open set B_{η} (i.e., we construct some appropriate η = η_{ν} from ν) such that B_{η} ⊆ B_{ν} ∩ U_{β}. (This is clearly sufficient, as ⋃_{ν} B_{η_{ν}} is open, contained in U_{β}, and meets every open set B_{ν}.)

So fix ν = (ν_{1}, …, ν_{n}) with dom(ν_{ℓ}) = A_{α}^{n_{ℓ}}. Wlog α ≥ β. ν_{1} is a function from A_{α}^{2} into A. We will extend the function ν_{1} to a function η_{1} on A_{α+1}^{2} such that

(∗∗) for every t and for every t-ary partial function σ ∈ F̃_{κ}^{t}(A_{β}, A) there is a c in A_{α+1} \ A_{α} such that: for all (x_{1}, x_{2}, …, x_{t}) ∈ dom(σ): σ(x_{1}, …, x_{t}) = η_{1}^{[t+1]}(c, x_{1}, …, x_{t}).

Before we construct ν_{1}, let us notice that property (∗∗) is sufficient to ensure B_{η} ⊆ U_{β}: Indeed, let (f_{1}, …, f_{n}) ∈ B_{η} . We have to show (f_{1}, …, f_{n}) ∈ U_{β}, i.e., F̃_{κ}(A_{β}, A) ⊆ P̃(f_{1}, …, f_{n}).

So let σ ∈ F̃_{κ}(A_{β}, A). Then (∗∗) guarantees that we can find some c such that σ(x_{1}, …, x_{t}) = η_{1}^{[t+1]}(c, x_{1}, …, x_{t}) for all (x_{1}, x_{2}, …, x_{t}) ∈ dom(σ). Now the function f_{1}^{[t+1]} extends the partial function η_{1}^{[t+1]}, and clearly the function

(x_{1}, …, x_{n}) ↦ f_{1}^{[t+1]}(c, x_{1}, …, x_{n})

is a polynomial function. This shows that (∗∗) will imply B_{η} ⊆ U_{β}.

Now we begin to define η_{1}: We will “code” partial functions in F̃_{κ}(A_{β}, A) by elements of A_{α+1} \ A_{α}. From the assumption |A|^{<κ} = |A| we get

|F̃_{κ}(A_{β}, A)| ≤ |A|^{<κ} = |A| = |A_{α+1} \ A_{α}|

(for the first inequality see 6.2.7, the last equality is true by our choice of the sets A_{α}, see 2.2).

So we can find a 1-1 function

T : F̃_{κ}(A_{β}, A) → A_{α+1} \ A_{α}

There is a a function η_{1} : A_{α+1}^{2} → A satisfying the following properties:

(a) η_{1} extends ν_{1}.

(b) η_{1}(T (σ), a) = σ(a) whenever σ ∈ F̃_{κ}^{1}(A_{α}, A), a ∈ dom(σ).

(c) η_{1}(T (σ), a) = T (σ_{[a]}) if σ ∈ ⋃_{t≥2} F̃_{κ}^{t}(A_{β}, A).

(d) η_{1}(a, b) = arbitrary, otherwise. (There are no contradictions between the requirements (b) and (c), since T is 1-1. There are no contradictions between the requirements (a) and (b) (or (a) and (c)), because dom(ν_{1}) ⊆ A_{α}^{2}, and T (σ) ∉ A_{α}, so (T (σ), a) ∉ dom(ν_{1}).)

Define η_{2}, …, η_{n} arbitrarily extending ν_{2}, …, ν_{n}. To prove property (∗∗), we show that for all t ≥ 1, all σ ∈ F̃_{κ}^{t}(A_{β}, A):

η_{1}^{[t+1]}(T (σ), a_{1}, …, a_{t}) = σ(a_{1}, …, a_{t}) for all (a_{1}, …, a_{t}) ∈ dom(σ).

The proof is by induction on t: For t = 1 we have

η_{1}^{[t+1]}(T (σ), a_{1}) = η_{1}(T (σ), a_{1}) = σ(a_{1}).

For t > 1 we have:

η_{1}^{[t+1]}(T (σ), a_{1}, …, a_{t}) = η_{1}^{[t]}(η_{1}(T (σ), a_{1}), …, a_{t}) =
(by definition of η_{1}) = η_{1}^{[t]}(T (σ_{[a_{1}]}), a_{2}, …, a_{t}) =
(by induction hypothesis) = σ_{[a_{1}]}(a_{2}, …, a_{t}) = σ(a_{1}, a_{2}, …, a_{t}).

The following fact explains the role that the regularity of κ plays:

Fact 2.9. If (A_{α} : α < κ) is increasing, A = ⋃_{α<κ} A_{α}, and B ⊆ A^{t} has cardinality < cf(κ), then there is an α < κ such that B ⊆ A_{α}^{t}.

In particular, if κ is regular then every set set B ⊆ A^{t} of size < κ is “bounded”, i.e. B ⊆ A_{α}^{t} for some α < κ.

Proof. Define a function f : B → 𝔒_{<κ} by

f(b_{1}, …, b_{t}) = min{β : {b_{1}, …, b_{t}} ⊆ A_{β}}

Then ran(f) cannot be cofinal in 𝔒_{<κ}, so there is β < κ such that ∀b ∈ B : f(b) < β. Thus, ∃β < κ ∀(b_{1}, …, b_{t}) ∈ B b_{1}, …, b_{t} ∈ A_{f(b)} ⊆ A_{β}, i.e., B ⊆ A_{β}.

Proof of theorem 2.7. Let (U_{β} : β < κ) be the sets defined in 2.8. The set ⋂_{β<κ} U_{β} is κ-residual, so it is enough to show that every algebra in ⋂_{β<κ} U_{β} has the κ-IP.

Let (A, f_{1}, …, f_{n}) ∈ ⋂_{β<κ} U_{β} , and let σ ∈ F̃_{κ}^{t}(A). Since | dom(σ)| < κ, we can use the regularity of κ to conclude that there is an α such that dom(σ) ⊆ A_{α}^{t}.

Hence σ ∈ F̃_{κ}^{t}(A_{α}, A) ⊆ P̃(f_{1}, …, f_{n}).

3. The Baker-Pixley Theorem

It is known that the k-IP and the k′-IP can coincide for natural numbers k ≠ k′. For example (see [1])

Theorem 3.1. Let m : A^{3} → A be a majority function, i.e.:

∀x, y ∈ A : m(x, x, y) = m(x, y, x) = m(y, x, x) = x

Then:

If 𝔄 := (A, f_{1}, …, f_{n}, m) has the 3-IP, then 𝔄 has the ℵ_{0}-IP.

We now show that such an implication κ-IP ⇒ κ′-IP does not hold for infinite cardinals. (Except for the trivial cases: κ ≥ κ′, or κ > κ^{∗}(A).)

We will need the following concept:

Definition 3.2. Let (A_{γ} : γ < κ) be as in 2.2, f : A^{t} → A. We say that α < κ is a ceiling for f if for all b ∈ A_{α+1} \ A_{α} and for all a_{2}, …, a_{t} ∈ A_{α+1} we have:

{f(b, a_{2}, …, a_{t}), f(a_{2}, b, …, a_{t}), …, f(a_{2}, a_{3}, …, b)} ⊆ A_{α+1}.

We say that α is a ceiling for 𝔄 = (A, f_{1}, …, f_{n}) if α is a ceiling for each f_{ℓ}. We let cl(𝔄) be the set of all ceilings for 𝔄.

Theorem 3.3. Let τ = (t_{1}, …, t_{n}) be a similarity type, t_{1} = 2.

(1) In any κ-topology on Alg_{τ} (A) the set of algebras which have the κ-IP but not the κ^{+}-IP is κ-residual.

(2) Moreover: Let (A_{γ} : γ < κ) be as in 2.2, t_{0} ∈ ω. Let m : A^{t_{0}} → A be any function satisfying m[A_{α}^{t_{0}}] ⊆ A_{α} for all α (i.e., m(a_{1}, …, a_{t}) ∈ A_{α} whenever a_{1}, …, a_{t} ∈ A_{α}). (It is easy to find a majority function m : A^{3} → A with this property.) Let κ ≤ κ^{∗}(A) (see 1.7). Then the set

{(f_{1}, …, f_{n}) ∈ Alg_{τ} (A) : (A, m, f_{1}, …, f_{n}) has the κ^{+}-IP}

is κ-meager.

Proof. By 2.7, (2) implies (1).

First note that cl(A, m, f_{1}, …, f_{n}) = cl(A, f_{1}, …, f_{n}) by our assumption on m. We have:

1. For every α < κ, the set {𝔄 : α ∈ cl(𝔄)} is clopen.

[Why? If 𝔄 = (f_{1}, …, f_{n}) and 𝔄′ = (f′_{1}, …, f′_{n}) agree up to α, i.e., f_{ℓ}↾A_{α}^{t_{ℓ}} = f′_{ℓ}↾A_{α}^{t_{ℓ}} for all ℓ, then α ∈ cl(𝔄) iff α ∈ cl(𝔄′).]

2. The sets D_{α} := {𝔄 : ∃β > α β ∈ cl(𝔄)} are open and dense.

[Given η ∈ Fun(γ), it is easy to find an extension η′ such that B_{η′} ⊆ D_{α}]

3. The set {𝔄 : cl(𝔄) is bounded in κ} is κ-meager in Alg_{τ} (A).

[Its complement is equal to ⋂_{α<κ} D_{α}.] Now let cl(𝔄) be unbounded. We will show that 𝔄 cannot have the κ^{+}-interpo-

lation property:

For each α < κ pick a_{α} ∈ A_{α+1} \ A_{α}.

Let f be the partial function that maps each a_{α} to a_{α+1}.

If p is a nonconstant polynomial with coefficients in A_{β}, then we can find α > β in cl(𝔄). Clearly we must then have p(a_{α}) ∈ A_{α+1}, but a_{α+1} ∈ A_{α+2} \ A_{α+1}, so p(a_{α}) ≠ a_{α+1}.

4. The Tychonoff Topology

Although the topologies presented in the previous section are very convenient to work with, they are rather unnatural since they depend on a specific arbitrary representation A = ⋃_{α} A_{α}. In this section we will investigate Alg_{τ} (A) with the natural topology:

Definition 4.1. Consider A as a discrete topological space. The product (or “Tychonoff”) topology on Alg_{τ} (A) is generated by sets of the form

B_{η} := {(f_{1}, …, f_{n}) : ∀ℓ f_{ℓ} ⊇ η_{ℓ}}

where η ranges over the set

Fun := {η : η = (η_{1}, …, η_{n}), ∀ℓ η_{ℓ} ∈ F_{ℵ_{0}}^{t_{ℓ}}(A)},

i.e., over all sequences of the form η = (η_{1}, …, η_{n}), where each η_{ℓ} is a partial finite t_{ℓ}-ary function.

A set is meager (also called: of the first category) if it can be covered by countably many [closed] nowhere dense sets, and a set is residual (or co-meager) if it contains a countable intersection of dense open sets.

The following well-known fact can be proved similarly to 2.6.

Fact 4.2. If A is any (infinite) set, then no nonempty open set in Alg_{τ} (A) is meager in the Tychonoff topology.

However, κ-meager sets are often trivial:

Remark 4.3. If the continuum hypothesis holds, then for any countable set A we have | Alg_{τ} (A)| = ℵ_{1}, so Alg_{τ} (A) is trivially ℵ_{1}-meager.

If A has cardinality ℵ_{1}, then irrespective of the underlying cardinal arithmetic, Alg_{τ} (A) is ℵ_{1}-meager in the Tychonoff topology.

Proof. The first remark is clear.

To prove the second remark, let A be of size ℵ_{1}. So we can write A as an increasing continuous union A = ⋃_{α<ω_{1}} A_{α}, where each A_{α} is countable.

For α < ω_{1} let

C_{α} := {(f_{1}, …, f_{n}) ∈ Alg_{τ} (A) : A_{α} is a subalgebra of (A, f_{1}, …, f_{n})}

We have to check that 1. C_{α} is closed.

2. C_{α} does not contain any nonempty open set, hence is nowhere dense.

3. ⋃_{α<ω_{1}} C_{α} = Alg_{τ} (A).

Proof of 1: Let (f_{1}, …, f_{n}) ∉ C_{α}. So there are ℓ and a_{1}, …, a_{t_{ℓ}} ∈ A_{α} with f_{ℓ}(a_{1}, …, a_{t_{ℓ}}) ∉ A_{α}. Define η ∈ Fun by letting η_{ℓ} have domain {(a_{1}, …, a_{t_{ℓ}})} and range {f_{ℓ}(a_{1}, …, a_{t_{ℓ}})}, and let η_{i} = ∅ for i ≠ ℓ. Then B_{η} ∩ C_{α} = ∅ and (f_{1}, …, f_{n}) ∈ B_{η}, so we have found a basic neighborhood of (f_{1}, …, f_{n}) disjoint from C_{α}. This shows that the complement of C_{α} is open.

Proof of 2: We have to show that there is no η such that B_{η} ⊆ C_{α}. Easy.

Proof of 3: Let 𝔄 = (A, f_{1}, …, f_{n}) ∈ Alg_{τ} (A). We have to find α such that 𝔄 ∈ C_{α}. For each α < ω_{1} and each ℓ ∈ {1, …, n} we can find an ordinal β = β(α, ℓ) < ω_{1} such that ran(f↾A_{α}^{t_{ℓ}}) ⊆ A_{β} (since ran(f↾A_{α}^{t_{ℓ}}) is countable). Let β(α) := max(α + 1, β(α, 1), …, β(α, n)). Define a countable sequence γ_{0} < γ_{1} < ⋯ < ω_{1} by requiring γ_{n+1} = β(γ_{n}). Let γ = sup{γ_{0}, γ_{1}, … }, then γ < ω_{1} since ω_{1} is regular. Now for each n we have ran(f_{ℓ}↾A_{γ_{n}}^{t_{ℓ}}) ⊆ A_{γ_{n+1}} ⊆ A_{γ}, so ran(f_{ℓ}↾A_{γ}^{t_{ℓ}}) ⊆ A_{γ}, which means 𝔄 ∈ C_{γ}.

So how many algebras will have the κ-interpolation property? From our result in the previous section we can deduce the following corollary:

Observation 4.4. Using the Tychonoff topology on Alg_{τ} (A), we have:

1. Let |A|^{<κ} = |A|. Then the set of algebras in Alg_{τ} (A) that have the κ-IP is dense.

2. However, if A is uncountable, then the set of algebras with the 2-IP is not residual.

Proof. (1) The set of algebras with the κ-IP is dense in any κ-topology, so also dense in the (coarser) Tychonoff topology.

(2) Let M be a meager set in Alg_{τ} (A), then we can find a family (M_{i} : i ∈ ω) of closed sets such that M ⊆ ⋃_{i} M_{i}. Define a sequence (η_{i} : i ∈ ω), η_{i} ∈ Fun, η_{i} = (η_{i,1}, …, η_{i,n}), such that for all i:

• B_{η_{i}} ∩ M_{i} = ∅

• η_{i,ℓ} ⊆ η_{i+1,ℓ}, for ℓ = 1, …, n (i.e., B_{η_{i}} ⊇ B_{η_{i+1}}). [Given η_{i}, it is possible to find the required η_{i+1} because M_{i+1} is nowhere dense.]

Now let B ⊆ A be a countable set such that for all i ∈ ω, all ℓ ∈ {1, …, n} the range of η_{i,ℓ} is contained in B. We can find an algebra 𝔄 = (f_{1}, …, f_{n}) such that for all ℓ = 1, …, n:

– For all i ∈ ω: η_{i,ℓ} ⊆ f_{ℓ}, i.e., 𝔄 ∈ ⋂_{i∈ω} B_{η_{i}}.

– ran(f_{ℓ}) ⊆ B. Now since B is countable and A is uncountable, B ≠ A. But any nonconstant polynomial in P (𝔄) takes only values in B, so clearly 𝔄 does not have the IP; in fact, there are functions that cannot be interpolated on 2 points. By construction, 𝔄 ∉ M.

For countable sets A the situation is different:

Theorem 4.5. Let A be a countable set. Then the set of algebras on A which have the interpolation property is residual in the Tychonoff topology on Alg_{τ} (A).

Proof. Let A = ⋃_{j} A_{j}, where the A_{j} form an increasing sequence of finite sets satisfying

|A_{j+1} \ A_{j}| > |F^{≤j}(A_{j})|

(where F^{≤j}(A_{j}) = ⋃_{m≤j} F^{m}(A_{j})). Similarly to 2.8 we can now show that each set

U_{j} := {(f_{1}, …, f_{n}) ∈ Alg_{τ} (A) : F̃^{≤j}(A_{j}) ⊆ P̃(f_{1}, …, f_{n})}

contains a dense open set, so the complement of ⋂_{j} U_{j} is meager. Now let 𝔄 ∈ ⋂_{j} U_{j}, σ ∈ F_{i}^{t}(A), i < ω. Then there is some n such that σ ∈ F̃^{≤j}(A_{j}), so σ ∈ P̃(𝔄).

Remark 4.6. One can argue that this topology does not capture the “right” notion of smallness. After all, many interesting sets, for example Alg_{τ} (A) ∩ 𝕍, for any nontrivial variety 𝕍, will be (closed and) nowhere dense.

5. Unary algebras

If t_{1} = ⋯ = t_{n} = 1, then for any algebra of type τ = (t_{1}, …, t_{n}), all polynomials will depend at most on one variable, so the best one can hope for is F^{1}(A) ⊆ P (𝔄).

Since there are, irrespective of the size of A, at most countably many (unary) polynomial functions that are not constant, we will consider only countably infinite algebras.

Definition 5.1. We say that a ∈ A is a fixpoint of 𝔄 = (A, f_{1}, …, f_{n}) iff f_{ℓ}(a) = a for ℓ = 1, …, n.

Observation 5.2. Let A be countable, τ = (1, …, 1). Then the set of algebras with a fixpoint is open dense in the Tychonoff topology. Hence the set of algebras with the interpolation property is nowhere dense.

However, if we consider algebras with at least one injective function without cycles, then the picture changes: Let τ = (1, …, 1), with n ≥ 2 many 1’s.

Definition 5.3. Let f_{∗} : A → A. We define

Alg_{τ} (A, f_{∗}) := {(A, f_{∗}, f_{2}, …, f_{n}) : f_{2}, … f_{n} ∈ F^{1}(A)}.

As a subset of Alg_{τ} (A), Alg_{τ} (A, f_{∗}) carries the induced topology. Since we keep A and f_{∗} fixed, we identify (A, f_{∗}, f_{2}, …, f_{n}) with (f_{2}, …, f_{n}).

Theorem 5.4. Let f_{∗} : A → A be 1-1 and without cycles. Then the set of algebras in Alg_{τ} (A, f_{∗}) for which the inclusion F̃_{ℵ_{0}}^{1}(A) ⊆ P^{1}(𝔄) holds is residual in Alg_{τ} (A, f^{∗}). In other words: Almost all algebras have the ℵ_{0}-IP with respect to unary functions.

Proof. For any σ ∈ F̃_{ℵ_{0}}^{1}(A) let

U(σ) := {(f_{2}, …, f_{n}) : σ ∉ P̃(A, f_{∗}, f_{2}, …, f_{n})}.

Note that U(σ) is closed and that there are only countably many possible values for σ. Hence it is enough to show that U(σ) does not contain an open set.

So fix ν_{2}, …, ν_{n}. We will find (f_{2}, …, f_{n}) ∈ B_{ν_{2},... ,ν_{n}} \ U(σ).

We will write f^{(j)} for the j-th iteration of f: f^{(1)} = f, f^{(j+1)} = f ∘ f^{(j)}. First find j such that ∀a ∈ dom(σ) : f_{∗}^{(j)}(a) ∉ dom(ν_{2}). Let η_{2} := ν_{2} ∪ {(f_{∗}^{(j)}(a), σ(a)) : a ∈ dom(σ)}. η_{2} is still a function, since f_{∗}^{(j)} is 1-1. Clearly, for any f_{2} ⊇ η_{2} we have f_{2} ∘ f_{∗}^{(j)} ⊇ σ, and f_{2} ∘ f_{∗}^{(j)} is a polynomial function.

6. Appendix: Set-theoretical Background

We collect here a few notations, definitions and results from basic set theory that can be helpful to understand the paper. The reader is referred to the first chapters of [3] and [5] for more information. We assume that the reader is familiar with the concepts of cardinals and ordinals, as discussed in basic algebra books (e.g. [2, 0.4]).

6.1. Ordinals, cardinals and cofinality.

1. We let 𝔒 be the class of all ordinals, 𝔒_{<α} = {β ∈ 𝔒 : β < α}. We reserve the variables α, β, γ, δ, ε to range over the class of ordinals (e.g., “∀α ∃β : … ” is an abbreviation for ∀α ∈ 𝔒 ∃β ∈ 𝔒 : … ”)

2. For every set A there is an ordinal α and a bijection from A onto 𝔒_{<α}. We let |A|, the cardinality of A, be the least α with this property. An ordinal κ is called a cardinal if κ = |A| for some A. All infinite cardinals are limit ordinals. We will reserve the variables κ, λ, μ for infinite cardinals.

3. If κ is a cardinal, then we let κ^{+} be the smallest cardinal > κ (the “cardinal successor”) of κ:

κ^{+} = min{λ : λ is a cardinal, λ > κ }

4. λ is called a “successor cardinal” if λ = κ^{+}, for some (uniquely determined) cardinal κ, and “limit cardinal” otherwise.

5. All the finite natural numbers are cardinals. ℵ_{0} is the smallest infinite cardinal. We let ℵ_{1} = (ℵ_{0})^{+}, ℵ_{2} = (ℵ_{1})^{+}, etc. We may write ω_{1} for ℵ_{1}. We write ω for the set of natural numbers.

6. For any partial order 𝔄 = (A, ≤) we call a set B ⊆ A “cofinal” if ∀a ∈ A ∃b ∈ B : a ≤ b.

7. For any (wlog limit) ordinal α we let cf(α) be the cofinality of 𝔒_{<α}:

cf(α) = min{|B| : B ⊆ 𝔒_{<α} is cofinal}

Equivalently, cf(α) is the smallest cardinal κ such that there is a ((strictly) monotone) function f : (𝔒_{<κ}, ≤) → (𝔒_{<α}, ≤) whose range is cofinal in 𝔒_{<α}.

8. We call an infinite cardinal κ “regular” if cf(κ) = κ, and “singular” otherwise. Equivalently, κ is singular iff there is λ < κ and a family (A_{α} : α < λ) such that |A_{α}| < κ for all α, and | ⋃_{α} A_{α}| = κ.

9. ℵ_{0} and all successor cardinals (such as ℵ_{1}) are regular.

6.2. Cardinal Arithmetic.

1. Recall that for any sets A, B we defined F^{1}(A, B) to be the set of all functions from A into B.

2. For (finite or infinite) cardinals κ, λ, we let κ^{λ} be the cardinality of the set F^{1}(𝔒_{<λ}, 𝔒_{<κ}). Equivalently, choose any sets K, L of cardinalities κ and λ, respectively, and let κ^{λ} = |F^{1}(L, K)|.

3. We let κ^{<λ} = sup{κ^{μ} : μ < λ} (In particular, κ^{<λ^{+}} = κ^{λ}.)

4. Cantor’s theorem tells us 2^{λ} > λ, and König’s theorem says that even λ^{cf(λ)} > λ (for infinite λ). In particular, λ^{<λ} > λ if λ is singular.

5. If n is a finite cardinal, κ an infinite cardinal, then κ^{n} = κ, so κ^{<ω} = κ.

6. Let 𝔓(X) be the power set of X. It is easy to see that |𝔓(X)| = 2^{|X|}. If κ is infinite, we have moreover 2^{κ} = κ^{κ} and even 2^{κ} = (κ^{+})^{κ} (see also 6.3.4).

7. If |L| = λ and |M| = μ are infinite, t a natural number > 0, then

|F (L, M)| = |F^{t}(L, M)| = |F^{1}(L, M)| = μ^{λ}

In particular, |F (L)| = λ^{λ} = 2^{λ}. For κ ≤ λ^{+} we have |F̃_{κ}(L, M)| = λ^{<κ} ·μ^{<κ}, in particular |F̃_{κ}(L)| = λ^{<κ}.

8. κ is a limit cardinal iff λ^{+} < κ is true for any λ < κ. We call a cardinal κ a “strong limit cardinal” iff 2^{λ} < κ is true for any λ < κ, or equivalently, iff 2^{<κ} = κ.

9. We call κ “strongly inaccessible” iff κ is an uncountable regular strong limit cardinal.

6.3. Increasing unions.

1. We say that a sequence (A_{α} : α < δ) of sets is increasing iff α < β < δ implies A_{α} ⊆ A_{β}. We call this sequence “continuous” iff A_{α} = ⋃_{β<α} A_{β} whenever β is a limit ordinal < δ.

2. If (A_{α} : α < κ) is increasing, A = ⋃_{α<κ} A_{α}, and B ⊆ A has cardinality < cf(κ), then there is an α < κ such that B ⊆ A_{α}. (Since this fact is essential for our main theorem, we give the [easy] proof in the main part of the paper. See 2.9.)

3. If cf(κ) > λ, then κ^{λ} = sup{μ^{λ} : μ < κ}.

Proof: Let |K| = κ, then we can write K as an increasing union of κ many “small” sets: K = ⋃_{i<κ} K_{i}, |K_{i}| < κ. Let |L| = λ. By 6.3.2, the range of every function f : L → K is contained in some K_{i}, so F^{1}(L, K) = ⋃_{i<κ} F (L, K_{i}). Hence κ^{λ} = |F^{1}(L, K)| = sup{κ_{i}^{λ} : i < κ} = sup{μ^{λ} : μ < κ}.

4. Consequently, (κ^{+})^{κ} = κ^{κ} for all κ, as κ^{+} is always regular.

5. If κ is a regular strong limit cardinal, then κ^{<κ} = κ.

Proof: For all μ < κ and all λ < κ we have μ^{λ} < κ, as κ is a strong limit. Hence for every λ < κ we have κ^{λ} = sup{μ^{λ} : μ < κ} ≤ κ, so κ^{<κ} ≤ κ.

References

[1] K.A. Baker and A.F. Pixley. Polynomial interpolation and the chinese remainder theorem for algebraic systems. Math. Z., 143:165–174, 1975.

[2] George Grätzer. Universal algebra. Springer-Verlag, 1979.

[3] T. Jech. Set theory. Academic Press, New York, 1978.

[4] János Kollár. Interpolation property in semigroups. Semigroup Forum, 17:337–350, 1979.

[5] K. Kunen. Set Theory: An Introduction to Independence Proofs, volume 102 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1983.

[6] V. L. Murskii. The existence of a finite basis of identities, and other properties of “almost all” finite algebras. Problemy Kibernet., 30:43–56, 1975.

Technische Universität, Wiedner Hauptstraße 8-10/118, A-1040 Wien, Austria

E-mail address: Martin.Goldstern@tuwien.ac.at