Admissible Sets

Origin. Saul Kripke ("Transfinite recursions on admissible ordinals, I and II", abstracts, Journal of Symbolic Logic 29, 1964) and Richard Platek ("Foundations of Recursion Theory", dissertation, Stanford 1966) independently isolated the set theory KP whose transitive models are the admissible sets, to generalize computability from ω to the ordinals — see Kripke–Platek Set Theory. Jon Barwise joined admissibility to infinitary logic after reading Platek's thesis and Lopez-Escobar's Berkeley thesis on infinitary logic: his own dissertation "Infinitary Logic and Admissible Sets" (Stanford 1967, under Solomon Feferman), the paper of the same title (Journal of Symbolic Logic 34, 1969, 226–252), and the monograph Admissible Sets and Structures (Perspectives in Mathematical Logic, Springer 1975) that fixed the subject. Keisler and Knight's survey (Bulletin of Symbolic Logic 10, 2004, 4–26) is the retrospective.

Models. An admissible set is a transitive set A such that (A, ∈) satisfies KP, and the subject is the model theory of the fragments L_A it carves out of L_{∞ω}: for countable admissible A, the fragment recovers the compactness that Infinitary Logic records as failing for L_{ω₁ω}, and a completeness theorem whose proofs the fragment itself contains. The elements of A act as the finite objects — A-finite — and the Σ₁-definable subsets as the computably enumerable ones, so each admissible set is a universe of generalized computability and L_A is the logic whose sentences, proofs, and theories that universe can compute with. The least admissible set HF returns first-order logic; the least one containing ω is L(ω₁^CK), whose fragment is the computable infinitary formulas; HC = H(ω₁) returns all of L_{ω₁ω}, which is where the recovery stops.

Formalism.

Admissible set: A transitive, (A, ∈) ⊨ KP. Admissible ordinal: α with L(α) ⊨ KP. o(A): the least ordinal not in A. HF = H(ω): the least admissible set, and the only one with o(A) = ω. L(ω₁^CK): the least admissible set with ω ∈ A; ω and ω₁^CK are the first two admissible ordinals. H(κ) for uncountable κ, in particular HC = H(ω₁): admissible (Kripke, Platek).

A-finite, A-c.e.: A-finite: an element of A. A-c.e.: Σ₁-definable over (A, ∈) with parameters. A-computable: X and its complement both A-c.e. At A = L(ω₁^CK): the A-finite subsets of ω are the Δ¹₁ (hyperarithmetical) sets, the A-c.e. ones the Π¹₁ sets (Kleene).

Admissible fragment: L_A: the formulas of L_{∞ω} that are elements of A. L_{HF} = L_{ωω}. L_{HC} = L_{ω₁ω}. L_A is an A-computable set, closed under subformulas, finite connectives, substitution.

Barwise compactness: A countable admissible, Γ a set of L_A-sentences that is Σ₁ on A. If every Γ′ ⊆ Γ with Γ′ ∈ A has a model, then Γ has a model.

Completeness: A countable admissible. Every valid L_A-sentence has a proof that is an element of A. The set of valid L_A-sentences is Σ₁ on A. Every Σ₁-on-A theory from which no contradiction is provable has a model. Proofs reworked from Lopez-Escobar's sequent calculus so that "p is a proof" is Δ over KP.

Urelements and HYP: KPU: KP over a structure M of urelements. KPU⁺: KPU plus "the urelements form a set". Truncation lemma: the well-founded part of any model of KPU over M is an admissible set over M. HYP(M): the least admissible set above a countable structure M (Barwise 1975). Scott height of an A-finite structure ≤ o(A) (Nadel); Scott height of countable M ≤ o(HYP(M)).

Hanf number: For countable admissible A ≠ HF: the Hanf number of L_A is ℶ_{o(A)} (Barwise, dissertation).

Symbols.

Metatheory. The Barwise compactness theorem (dissertation 1967; JSL 34, 1969): for countable admissible A and Γ a set of L_A-sentences Σ₁ on A, if every subset of Γ that is an element of A has a model, Γ has a model. It follows from completeness: Barwise reworked the proof system so that proofs are objects of A, making every valid L_A-sentence provable inside A and the valid sentences Σ₁ on A, with consistent Σ₁ theories getting models. Kreisel had earlier proved compactness for ω-logic — a Π¹₁ set of finitary sentences has an ω-model if every Δ¹₁ subset has one — though Barwise proved his theorem without knowing of it; the Kreisel–Barwise theorem for the computable infinitary sentences is the special case A = L(ω₁^CK). Countability of A cannot be dropped: compactness fails outright for L_{ω₁ω}, the fragment of the uncountable admissible set H(ω₁) — first-order arithmetic plus ω₁ new constants forced into the natural numbers has no model though every countable subset has one — and Barwise showed, building on work of Kunen, that his compactness theorem holds for an uncountable L_A exactly when A satisfies reflection for strict Π¹₁ formulas. Lopez-Escobar's interpolation theorem extends to every countable admissible fragment (Barwise). The Hanf number of L_A is ℶ_{o(A)} for countable admissible A ≠ HF (Barwise, dissertation). On the structure side, Nadel proved that the Scott height of a structure in a countable admissible set A is at most o(A), hence at most o(HYP(M)) for any countable M, where HYP(M) — the least admissible set above M, built from KPU⁺ by the truncation lemma — makes L_{HYP(M)} the fragment tailored to analyzing M. Barwise's end extension theorem: every countable model of ZF has a proper end extension satisfying ZF + V = L, by Barwise compactness together with Lévy–Shoenfield absoluteness; the appendix of the 1975 monograph, "Nonstandard compactness arguments and the admissible cover", extends the argument to nonstandard models of set theory through the admissible cover.

Applies to. Computable structure theory — the computable version of Barwise compactness yields computable models, the Harrison ordering of type ω₁^CK(1 + η), and the ω₁^CK bound on Scott heights of hyperarithmetical structures. Higher recursion theory and α-recursion. Descriptive set theory, through Π¹₁ and Δ¹₁ as the Σ₁ and finite sets of L(ω₁^CK). Model theory of set theory — end extensions. Hanf number computations. Ordinal analysis, where the admissible ordinals are the scale (see Kripke–Platek Set Theory).

Limitations. Countability of A cannot be dropped: for uncountable A the compactness theorem holds only under strict Π¹₁ reflection, and compactness fails for L_{ω₁ω} itself — so the method never recovers compactness for L_{ω₁ω} as a whole, only for its countable admissible fragments. The hypotheses are Σ₁ throughout: the theory must be Σ₁ on A and the subtheories assumed satisfiable must be elements of A, so a set of sentences that no countable admissible set recognizes as one of its Σ₁ collections is beyond the method's reach. Everything rests on the Σ₁-recursion KP provides: proofs must be Δ over KP, theories Σ₁ on A, fragments A-computable. For L_{ω₁ω₁} and the other languages with infinite quantifier strings there is no comparable theory (see Infinitary Logic). And KP itself is weak — proof-theoretically far below ZF — so an admissible set certifies closure under computation, not mathematical strength (see Kripke–Platek Set Theory).

© 2026 Lingenic LLC