Model-theoretic Characterizations of Large Cardinals
Will Boney

The Status and Initial Results of the Majorana Demonstrator Experiment
    [
    December 30, 2023
======================================================================






We consider compactness characterizations of large cardinals.  Based on results of Benda <cit.>, we study compactness for omitting types in various logics.  In _κ, κ, this allows us to characterize any large cardinal defined in terms of normal ultrafilters, and we also analyze second-order and sort logic.  In particular, we give a compactness for omitting types characterization of huge cardinals, which have consistency strength beyond Vopěnka's Principle.




§ INTRODUCTION


Large cardinals typically have many equivalent formulations: elementary embeddings, ultrafilters or systems of ultrafilters, combinatorial properties, etc.  We investigate various characterizations in terms of logical compactness.  These formulations have a long history.  Weakly and strongly compact cardinals were first isolated with generalizations of the compactness theorem to infinitary languages.
[<cit.>]
	
  * κ > ω is weakly compact iff every <κ-satisfiable theory of size κ in _κ, κ is satisfiable.
	
  * κ > ω is strongly compact iff every <κ-satisfiable theory in _κ, κ is satisfiable.


Measurable cardinals also have such a characterization, this time in terms of chain compactness of _κ, κ.  This result is interesting because it seems to have been well-known in the past (evidenced by the fact that it appears as an exercise in Chang and Keisler's Model Theory <cit.>), but seems to have fallen out of common knowledge even among researchers working in the intersection of set theory and model theory (at least among the younger generation)[This is based on the author's personal impressions.  Although the statement seems forgotten, the proof is standard: if T = ∪_α < κ T_α and M_α T_α, then set M_κ : = ∏ M_α /U for any κ-complete, nonprincipal ultrafilter U on κ.  Łoś' Theorem for _κ, κ implies M_κ T.].

 
κ is measurable iff every theory T ⊂_κ, κ that can be written as a union of an increasing κ-sequence of satisfiable theories is itself satisfiable.


Magidor <cit.> showed that extendible cardinals are the compactness cardinals of second-order logic, and Makowsky <cit.> gives  an over-arching result that Vopěnka's Principle is equivalent to the existence of a compactness cardinal for every logic (see Fact <ref> below).  This seems to situate Vopěnka's Principle as an upper bound to the strength of cardinals that can be reached by compactness characterizations.

However, this is not the case.  Instead, a new style of compactness is needed, which we call compactness for omitting types (Definition <ref>).  Recall that a type p(x) in a logic  is a collection of -formulas in free variable x.  A model M realizes p if there is a ∈ M realizing every formula in p, and omits p if it does not realize it.  Explicitly, this means that for every a ∈ M, there is ϕ(x) ∈ p such that M ϕ(a).  Although realizing a type in  can be coded in the same logic by adding a new constant, omitting a type is much more difficult.  Thus, while in first-order logic types can be realized using a simple compactness argument, finding models omitting a type is much more difficult.  This is the inspiration for Gerald Sacks' remark[Several colleagues have suggested that Sacks is quoting himself here, as he considers himself a well-known recursion theorist and not a well-known model theorist.] <cit.> “A not well-known model theorist once remarked: `Any fool can realize a type, but it takes a model theorist to omit one.' ”

Compactness for omitting types was first (and seemingly uniquely) used by Benda to characterize supercompact cardinals in _κ, κ.   Tragically, Benda's fantastic result is even less well-known than the characterization of measurable cardinals.  In the almost 40 years since its publication, the publisher reports zero citations of Benda's paper.

 
Let κ≤λ.  κ is λ-supercompact iff for every _κ, κ-theory T and type p(x, y) = {ϕ_i(x, y) | i < λ}, if there are club-many s ∈_κλ such that there is a model of 

    T ∪{∃ x ( ⋀_i ∈ s∃ y ϕ_i(x,y) ∧∃ y ⋀_i ∈ sϕ_i(x, y)) }

then there is a model of 

    T ∪{∃ x ( ⋀_i < λ∃ y ϕ_i(x,y) ∧∃ y ⋀_i < λϕ_i(x, y)) }



The final model omits the type q(y) = {ϕ_i(a, y) | i < λ}, where a is the witness to the existential.  Phrased in these terms, this property says that if every small part of a type can be omitted, then the whole type can be omitted.  One complicating factor is that monotonicity for type omission works in the reverse direction as for theory satisfaction: larger types are easier to omit since they contain more formulas.  This makes Benda's result somewhat awkward to phrase as he fixes the theory.

Our phrasing of compactness for omitting types varies from Benda's formulation in two key ways.  First, we also allow the theory to be broken into smaller pieces, which makes the phrasing more natural (at least from the author's perspective).  Second, and more crucially, we look at other index sets (or templates) than _κλ.  This allows us to capture many more large cardinals than just supercompacts.

Other model-theoretic properties have also been used to characterize large cardinals, mainly in the area of reflection properties and the existence of Löwenheim-Skolem-Tarski numbers.  Magidor <cit.> characterizes supercompacts as the Löwenheim-Skolem-Tarski numbers for second-order, and Magidor and Väänänen <cit.> explore the possibilities surrounding the Löwenheim-Skolem-Tarski numbers of various fragments of second-order logic.  Bagaria and Väänänen <cit.> connect structural reflection properties and Löwenheim-Skolem-Tarski numbers through Väänänen's notion of symbiosis.  Of course, Chang's Conjecture has long been known to have large cardinal strength (see <cit.>).

Section <ref> fixes our notation and gives some basic results.  Section <ref> establishes the main definitions of compactness for type omission and applies it to the logics _κ, κ.  The main result in this section is Theorem <ref>.  Section <ref> examines type-omitting compactness for higher-order (Theorem <ref>) and sort (Theorem <ref>) logics.  This section also deals with compactness characterizations of some other cardinals (e.g., strong) and discusses the notion of elementary substructure in second-order logic.  Section <ref> discusses extenders and type omission around the following question: we give characterizations of large cardinals with various logics, from _κ,κ to the all-powerful ^s, Σ_n.  However, _κ, κ is already able to work its way up the large cardinal hierarchy, including n-hugeness (Corollary <ref>) and rank-into-rank (Section <ref>).  Are these more powerful logics necessary?  In other words, can we characterize all model-theoreticaly characaterizable large cardinals (extendible, etc.) by some property of _κ, κ, or is the use of stronger logics necessary to pin down certain cardinals?  We focus on strong cardinals, and give a theory and collection of types such that the ability to find a model of the theory omitting the types is equivalent to κ being λ strong.  As close as this seems to an _κ, κ (or rather _κ, ω(Q^WF)) characterization of strong cardinals, we still lack a general compactness for type omission for this case.

Preliminary results along these lines were first presented at the Workshop on Set-Theoretical Aspects of the Model Theory of Strong Logics hosted by the Centre de Recerca Matemàtica in 2016, and I'd like to thank many of the participants for helpful conversations, especially Jouko Väänänen for discussions about sort logic.  I'd also like to thank Gabriel Goldberg for helpful discussions regarding the strength of huge-for-^2_κ, κ cardinals, and Adrian Mathias and Sebastien Vasey for comments on a preliminary draft.  I would also like to thank the anonymous referee for helping to improve the paper.






§ PRELIMINARIES
 

We begin with an informal introduction to the logics used.  The large cardinals notions are standard; consult Kanamori <cit.> or the locally given citation for detail.  We introduce some new large cardinal notions, typically naming them and defining them in the statement of a result: see Corollary <ref>, Proposition <ref>,  and Theorems <ref> and <ref>.



_ω, ω is the standard, elementary first-order logic.

_λ, κ augments _ω, ω by allowing

	
  * conjunctions of <λ-many formulas that together contain <κ-many free variables;
	
  * <κ-ary functions and relations in the language; and
	
  * universal and existential quantification over <κ-many variables at once.

We typically restrict to λ≥κ, both regular.

^2 = ^2_ω,ω is second-order logic, which extends _ω, ω by allowing quantification over subsets of finite cartesian powers of the universe and has an atomic `membership' relation.  The standard interpretation of the second-order quantifiers is quantification over all subsets of (finite cartesian powers of) the universe, but an important concept is the nonstandard Henkin models (M, P, E), where M is a τ-structure, E ⊂ M× P is an extensional relation, and P represents a collection of subsets that the second-order quantifiers can range over.  The class of Henkin models of a second-order theory reduces to the models of a sorted _ω, ω-theory, but we will still find use for this definition in Definition <ref> and the characterization of strong cardinals.  There is a second-order sentence Ψ that says a Henkin model is standard:

    ∀ X ⊂ M ∃ x ∈ P ∀ y ∈ M ( y ∈ X ↔ y E x)

We can also introduce higher-order variants ^n, but these are all codeable in ^2, e.g., a Henkin model for ^3 is (M, P, Q, E), where P represents the subsets of M and Q represents the subsets of M.  Then second-order can express the standardness of this model for third-order logic by using Ψ and a copy of Ψ for P and Q.  The ^n are coded similarly, although we must use ^2_|α|^+,ω for ^α when α is infinite.  Thus, it suffices to talk about second order logic.

Additionally, when dealing with second-order logic, we allow the language to include functions and relations  whose domain and range include the second-order part of the model.  Given such a second-order language τ, we describe it as consisting of a strictly first-order part (the functions and relations only using first-order inputs) and a second-order part (the functions and relations that use first- and second-order inputs).

We want to distinguish a very helpful second-order sentence Φ that will allow us to make a statement about the type of model we are in.  The construction of this statement is from Magidor <cit.>, appearing in the proofs of his Theorems 2 and 4.  However, it is useful to extract the construction so we can make explicit reference to it.


There is a second-order sentence Φ in the language with a single binary relation E such that (A, E) Φ iff (A, E) ≅ (V_α, ∈) for some limit ordinal α.  Moreover, Φ is a Π^1_1 sentence.


Proof: There is a first-order sentence ϕ(x,y) that is true iff x is an ordinal and y is a copy of V_x (as computed in the model).  Then Φ is the conjunction of the statements (note that we use `E' for the relation in the language and `∈' for the logical notion of membership between a first- and second-order variable)

	
  * E is well-founded: ∀ X ∃ x ∀ y (y Ex ∧ y ∈ x);
	
  * E is extensional: ∀ x,y (x=y  ↔∀ z (z E x ↔ z E y));
	
  * Every ordinal is in a V_α: ∀ x (On(x) →∃ y ϕ(x,y)); and 
	
  * Every subset of an element is represented in the model: ∀ x ∀ X ( ∀ y (y ∈ X → y Ex) →∃ z ∀ y (y ∈ X ↔ y E z)).
	

†


(Q^WF) is _ω, ω augmented by the quantifier Q^WF that takes in two free variables and so Q^WF xyϕ(x, y, ) is true iff there is no infinite sequence {x_n | n < ω} such that ϕ(x_n+1, x_n, ) holds for all n < ω; that is, ϕ(x, y, ) defines a well-founded relation.  Note that, in models of some choice, Q^WF is both _ω_1, ω_1 and ^2 expressible.  However, it will be useful to have it, e.g., in Theorem <ref>.

Finally, sort logic ^s is a logic introduced by Väänänen <cit.>.  This augments second-order logic by adding sort quantifiers ∃^∼, ∀^∼ where ∃^∼ X ϕ(X, ) is true in a structure M iff there is a set X (any set, not just a subset of the universe of M) such that ϕ(X, ) is true.  Sort logic is very powerful because it allows one to access a large range of information regardless of the language of the initial structure.  For instance, one can easily write down a formula Φ whose truth in any structure implies the existence of an inaccessible cardinal.  Väänänen discusses its use as a foundation of mathematics in <cit.>.  Since sort logic involves satisfaction of formulas in V, for definability of truth reasons, we must restrict to the logics ^s, Σ_n, where ^s, Σ_n consists only of the formulas of sort logic that are of Σ_n complexity when looking at the quantifiers over sorts.

Finally, all of these logics can be combined in the expected way, e.g., ^2_κ, κ.  We often take the union of two logics, e.g., ^2 ∪_κ, ω is the logic whose formulas are in ^2 or _κ, ω; however, no second-order quantifier or variable can appear in any formula with an infinite conjunction, which separates it from ^2_κ, ω.  We typically use boldface  when discussing a particular logic and script  when discussing an abstract logic.

For a logic  and a language τ, an (τ)-theory T is a collection of sentences (formulas with no free variables) of (τ).  An (τ)-type p(x) in x is a collection of formulas from (τ) all of whose free variables are at most x.[Types in single variables suffice for the various characterizations in the paper, but they also extend to types of arity <κ.]  A type p(x) is realized in a τ-structure M iff there is an element of the model that satisfies every formula in it and a type is omitted precisely when it is not realized.  Note that the “monotonicity of type omission" works the opposite way as theories: if p(x) ⊂ q(x) are both types, then it is easier to omit q than p.  We will often refer to filtrations of a theory T.  This means there is some ambient partial order (I, ⊂) and a collection of theories {T_s | s ∈ I} such that T = ⋃_s∈ I T_s and s ⊂ t implies T_s ⊂ T_t.


In general, we are agnostic about how one codes these logics as sets, except to insist that it is done in a reasonable way, e.g., τ is coded as a set of rank |τ|+ω, _κ, κ(τ) ⊂ V_κ +|τ|, etc.  This gives us two nice facts about the interaction between languages τ and elementary embeddings j:V → (or V_α→ V_β, etc.) with j =κ:

	
  * if τ is made up of < κ-ary functions and relations, then j"τ and τ are just renamings of each other; and
	
  * if ϕ∈^s, Σ_n_κ, κ(τ), then j(ϕ) ∈^s, Σ_n_κ, κ(j"τ).

This means that, when searching for a model of T, it will suffice to find a model of j"T, which is a theory in the same logic and an isomorphic language.

Given an inner model[In an unfortunate collision of notation, M is commonly used for both inner models in set theory and for τ-structures in model theory.  Owing to my model-theoretic roots, this paper uses standard M for τ-structures and script  for inner models.]  (or some V_α), we collect some facts about when  is correct about various logics.  That is, the statement “M is a τ-structure" is absolute from  to V and we want to know when the same holds of “ϕ is an (τ)-formula and M_ϕ."

	
  *  is correct about the logic _ON^, ω(Q^WF).
	
  * If ^<κ⊂, then  is correct about the logic _κ, κ.
	
  * If (A) ∈, then  is correct about ^2 for structures with universe A.
	
  * If ≺_Σ_n V, then  is correct about ^s, Σ_n.


As a warm-up, note that any compactness involving an extension of (Q^WF) will entail the existence of large cardinals.  Fixing κ, if 

    T:=ED__ω, ω(V_κ+1, ∈, x)_x ∈ V_κ+1∪{c_α < c < c_κ|α < κ}∪{Q^WF xy (x ∈ y)}
 
is satisfiable, then there is a non-surjective elementary embedding j:V_κ+1→ to a well-founded structure with j ≤κ.  Standard results imply that j must be measurable.  Moreover, T is `locally satisfiable' in the sense that, if T_0 ⊂ T does not contain constants for elements with ranks unbounded in κ, then V_κ+1 can be made a model of T_0 by adding constants.



§ TYPE-OMITTING COMPACTNESS IN _∞, ∞
 

We introduce some basic definitions that will be used in each of our characterizations.  The notion of containing a strong κ-club becomes very important, and we discuss that concept after the definition.

 
Let κ≤λ and I ⊂(λ).

	
  * I is κ-robust iff for every α < λ, [α]_I:={ s ∈ I |α∈ s}≠∅ and I⊂{s : |s ∩κ|<κ}.
	
  * C ⊂ I contains a strong κ-club iff there is a function F:[λ]^2 →_κλ such that
	
    C(F):= {s ∈ I| s  is infinite and, for all x, y, ∈ s, F(x, y) ⊂ s}⊂ C


Let U be an ultrafilter on I.

	
  (3) U is μ-complete iff for all α < μ and {X_β∈ U |β < α}, we have ⋂_β<α X_β∈ U.
	
  (4) U is fine iff for all α∈λ, [α]_I ∈ U.
	
  (5) U is normal iff for all F:I →λ such that {s∈ I| F(s) ∈ s}∈ U, there is α_0<λ such that {s ∈ I | F(s) = α_0}∈ U. 



The conditions of κ-robustness are intended to make sure that I includes enough sets so that the notion of a “κ-complete, normal, fine ultrafilter on I" makes sense and is possible.  In particular, any such ultrafilter U will be characterized by an elementary embedding j_U with j_U = κ; this implies that {s ∈ I : |s ∩κ |<κ}∈ U.

We define the notion of `contains a strong κ-club' without defining the notion of a strong κ-club.  However, the  first two items of Fact <ref> show that this notion correctly generalizes the notion of containing a club from κ and _κλ.  Moreover, the third item shows that a generalization that replaces _κλ with a different set does not work.

 
	
  * If I = _κλ, then containing a strong κ-club is equivalent to containing a club.
	
  * Fix a κ-robust I ⊂(λ).  If U is a κ-complete, fine, normal ultrafilter on I, then it extends the contains a strong κ-club filter, that is, C(F) ∈ U for all F:[λ]^2→_κλ. 
	
  * If I = [λ]^κ and U is a κ-complete, fine, normal ultrafilter on I, then there is no s ∈ [λ]^κ such that
	
    [s]_I:={t ∈ I | s ⊂ t}∈ U




Proof: (1) is a result of Menas, see <cit.>.

For (2), fix F: [λ]^2 →_κλ and suppose that C(F) ∉U.  For each s ∈ I- C(F), there are α_s < β_s ∈ s such that F(α_s, β_s) ⊄s.  By applying normality twice, there is some Z ∈ U and α_* < β_* such that, for all s ∈ Z, α_s = α_* and β_s = β_*.  By the κ-completeness and fineness of U, we have that [f(α_*, β_*)]_I∈ U.  Thus, there is t ∈ Z ∩ [F(α_*, β_*)]_I; however, this is a contradiction.

For (3), given such a U, build the elementary embedding j_U: V →≅∏ V/U.  Let s ∈ [λ]^κ.  Then, for X ⊂ [λ]^κ, we have that X ∈ U iff j_U”λ∈ j_U(X).  However, since |s|=κ =  j_U, there is some α∈ j_U(s) - j_U"λ.  In particular, this means that

    j_U”λ∉{ t ⊂ j(I) | j_U(s) ⊂ t} = j_U([s]_I)

†


We are interested in model-theoretic conditions that guarantee the existence of a fine, normal, κ-complete ultrafilter on some κ-robust I.  Recall that, from Kunen's proof of the inconsistency of Reinhardt cardinals, every countably complete ultrafilter on (λ) must concentrate on _μλ for some μ≤λ.  If μ is strictly larger than the completeness of the ultrafilter, we will need the following technical condition.  In practice, the set X will always be a theory.


Let I ⊂(λ) and X be a set that is filtrated as an increasing union of {X_s | s ∈ I}.  Then we say this filtration respects the index iff there is a collection {X^α|α∈λ} such that, for each s ∈ I, X_s = ⋃_α∈ s X^α.


This condition says that the filtration at s ∈ I is just determined by the elements of s.  Note this condition is trivially satisfied when I ⊂_κλ, but will be important in certain cases, e.g., to characterize huge cardinals (see Corollary <ref>.(<ref>)).  There, it will guarantee that if ϕ∈∪_s ∈ [λ]^κ T_s, then there are a large number of s ∈ I such that ϕ∈ T_s.

The main concept of this section is the following:


Let  be a logic (in the sense of Barwise <cit.> or taken without formal definition), κ≤λ, and I ⊂(λ) be κ-robust.  Then we say that  is I-κ-compact for type omission iff the following holds:

Suppose that we have

	
  * a language τ;
	
  * a (τ)-theory T that can be written as an increasing union of {T_s :s ∈ I} that respects the index; and
	
  * a collection of types {p^a(x) | a ∈ A} of size λ (for an arbitrary set A), where each type comes with an enumeration p^a(x) = {ϕ^a_α(x) : α < λ} and, for s ⊂λ, we set p^a_s(x):={ϕ^a_α(x):α∈ s}.

If

    CTO{ s ∈ I | T_s  has a model omitting each type in {p^a_s(x) | a ∈ A}}

contains a strong κ-club, then there is a model of T omitting each type in { p^a(x) | a ∈ A}.


This definition is technical, so we will try to unpack it.  A compactness for type omissions result should say that if we want to find a model of a theory T omitting a type p, it should suffice to find a model of all of the small fragments of T omitting the small fragments of p.  When there is no p, the monotonicity of satisfying theories makes looser statements of this possible.  However, the monotonicity of satisfying theories and omitting types work in opposite directions (smaller theories are easier to satisfy, while smaller types are harder to omit), so much more care has to be taken.

The s ∈ I index allows us to associate particular fragments of the theory with particular fragments of the type.  In this sense, wether or not  the set (<ref>) contains a strong κ-club depends very strongly on the particular filtration of T and enumerations of the p^a that are chosen.  Additionally, because the monotonicities work in opposite directions, given s ⊂ t ∈ I, wether or not s and t are in (<ref>) is independent.  As explained in Remark <ref>, we want the set (<ref>) to be in whatever fine, normal, κ-complete ultrafilter our assumptions give us, and the results of Fact <ref> suggest that `contains a strong κ-club' is the right stand in for this notion.

The following gives a framework result for linking compactness for type omission for _κ, λ to various large cardinal notions.

 
Let κ≤λ, and I ⊂(λ) be κ-robust.  The following are equivalent:

	
  * _κ, ω is I-κ-compact for type omission.
	
  * _κ, κ is I-κ-compact for type omission.
	
  *  There is a fine, normal, maximally κ-complete ultrafilter on (λ) concentrating on I; `maximally κ-complete' means κ-complete and not κ^+-complete.
	
  *  There is an elementary j:V → with j = κ and j"λ∈∩ j(I).

Moreover, the first μ such that _μ, ω is I-κ-compact for type omission is the first μ with a fine, normal, μ-complete ultrafilter on I.


Proof: The equivalence of (3) and (4) is straightforward from standard methods, and (2) implies (1) is obvious because _κ, ω⊂_κ, κ.


(4) → (2): Suppose we have a set-up for I-κ-compact type omission: a theory T in _κ, κ(τ) filtrated as T_s for s ∈ I and a collection {p^a:a ∈ A} of _κ, κ(τ)-types as in Definition <ref>.  Set T̅ and p̅^̅a̅ to be the functions that take s ∈ I to T_s and p_s^a, respectively.  Similarly, set M̅ to be the partial function that takes s to M_s that models T_s and omits each p^a_s(x) (when defined).

Since the set (<ref>) contains a strong κ-club, there is a function F:[λ]^2 →_κλ that witnesses this.  Then j(M̅) is a function with domain containing j(C(F)).  We know that j comes from an ultrafilter as in (3) and Fact <ref>.(2) implies that C(F) ∈ U.  Thus, j"λ∈ j(C(F)).

Then  thinks that j(M̅)(j"λ) is a j(τ)-structure that models j(T̅)(j"λ) that omits each j(p̅^a)(j"λ).   is correct about this, so j(M̅)(j"λ) models j(T̅)(j"λ) and omits each j(p̅^a)(j"λ) (in V). As discussed in Section <ref>, τ and j"τ are essentially the same, in the sense that there is a canonical bijection between them–taking F ∈τ to j(F)∈τ–that respects arity; such a function is called a renaming.

Claim: j"T ⊂ j(T̅)(j"λ) and j"p^a = j(p̅^a)(j"λ) for each a ∈ A.

First, let j(ϕ) ∈ j"T and let {T_0^β:β∈λ} witness that the filtration respects the index; this is the crucial use of this property.  Then we have that ϕ∈ T_0^α for some α∈λ.  Then 

    j(ϕ) ∈ j(T̅_̅0̅)(α) ⊂ j(T̅)(j"λ)

The proof that j"p^a ⊂ j(p̅^a)(j"λ) is similar.  For the other direction, let ψ∈ j(p̅^a)(j"λ).  By elementarity, we have that j(p^a) = {ψ^a_α(x): α < j(λ)} and j(p̅^a)(s) = {ψ^a_α(x):α∈ s}, where ψ^a_j(β) = j(ϕ^a_β).  This means that ψ is of the form j(ϕ) for ϕ∈ p^a, which exactly says ψ∈ j"p^a.  Here, we have exactly used the condition that j"λ is in the model, and simply using a set that contained this would not work.

With the claim proved, we have produced a model j(M̅)(j"λ) of j"T that omits each j"p^a for a ∈ A.  After applying the inverse of the canonical naming above, we have the desired model of T that omits each p^a.


(1) → (3): We want to write down a theory T and collection of types {p_F:F:I →λ} such that a model of T omitting these types will code the desired ultrafilter.  Set τ = {P, Q, E, c_X, d}_X ⊂ I with P and Q unary predicates, E ⊂ P × Q a binary relation, and c_X, d constants.  We look at the standard structure M = I, (I), ∈, X_X ⊂ I that has no interpretation for d.  Classic results tell us that finding an extension N of M that a new element n (which will be the interpretation of d) codes an ultrafilter U on I by

    X ∈ U  N  n E c_X

The completeness of this ultrafilter comes from how strong the elementarity of the extension is, so we need to add conditions that make the fineness and normality hold.

Set T_0 = __κ, ω(M) (although much less is necessary).  Set T^α := T_0 ∪{“d ∈ c_[α]^I"} for α < λ; T_s := ∪_α∈ s T^α for s ∈ I; and T = ∪_s ∈ I T_s.  For each function F:I →λ, define 

    X_F   :=   {s ∈ I| F(s) ∈ s}
    
    X_F, α   :=   {s ∈ I | F(s) = α}
    
    p_F(x)    :=   { x = d ∧ x E c_X_F∧(x E c_X_F, α) |α < λ}
    Γ   :=   { p_F | F:I →λ}

These types are built so that omitting the type p_F means that the ultrafilter coming from d will be normal with respect to the function F: if F is regressive on a large set, then “dEc_X_F” will hold, so omitting p_F requires that there is an α < λ such that “d E c_X_F, α” holds, and α will then give the constant value of F on a large set.

We will use compactness for type omission to find a model of T omitting Γ.

Claim 1: If there is a model of T omitting Γ, then there is a fine, normal, κ-complete ultrafilter on I.

Let N be this model.  Define U on I by 

    X ∈ U  N d E c_X

It is straightforward to check that U is a κ-complete ultrafilter on I.  For instance, given X_α∈ U |α < μ < κ, we know that the following sentence is in T:

    ∀ x ( ⋀_α < μ x E c_X_α→ x E c_∩_α<μ X_α)

Thus, N  d E c_∩_α<μ X_α.

Given α < λ, by κ-robustness, there is some s ∈ I such that α∈ s.  So T entails that d E c_[α]^I. This means that U is fine.

For normality, if F:I →λ is regressive on a U-large set, then N  d E c_X_F.  Since N omits p_F, there is α < λ such that X_F, α∈ U, so U is normal.

Claim 2: For each s ∈ I, there is a model of T_s omitting {p_F, s| F:I →λ}.

Expand M to M_s by interpreting d^M_s = s.  This models T_s since s ∈ [α]^I for each α∈ s by definition.  Moreover, if there is x ∈ M_s such that

    M_s “x = d ∧ x E X_F"

for some F:I →λ, then x = s and F(s) ∈ s, so there is α∈ s such that F(s) = α.  Thus

    M_s  x E X_F, α

So M_s omits each p_F, s.

By the I-κ-compactness for type omission, we are done.


The proof of the “moreover" follows similarly.†



We chose to show (4)→(2) above because it will more easily generalize to large cardinals characterized by the existence of extenders rather than ultrafilters (this is done in Section <ref>).  However, the direct proof of (3)→(2) helps to emphasize the connection between normality of an ultrafilter and type omission, so we outline it here.  Suppose that U is an ultrafilter as in Theorem <ref>.(3) and we have a language τ, theory T, and set of types {p^a(x) | a ∈ A} as in the hypothesis of Definition <ref>, and let X be the set in <ref>.  For s ∈ X, there is a witnessing model M_s and we can form the ultraproduct[Here we use a more liberal formalism for ultraproducts that allow certain structures to be empty by allowing the choice functions f:I →⋃ M_s to be partial with U-large domain.] ∏ M_s/U.  From Łoś' Theorem, the κ-completeness and fineness of U means that ∏ M_s/U models T.

To prove type omission, suppose that [f]_U ∈∏ M_s/U and let a ∈ A.  Since M_s omits p^a_s(x), there is some α_s ∈ s such that

    M_s ϕ^a_α_s(f(s))

The function s ↦α_s is regressive on the U-large set f, so normality implies that there is a single α_* such that 

    M_s ϕ^a_α_*(f(s))

for a U-large set of s.  Then, by Łoś' Theorem, 

    ∏ M_s/U ϕ^a_α_*([f]_U)

so [f]_U doesn't realize p^a.  Since [f]_U and a were arbitrary, the ultraproduct omits the types {p^a(x) | a ∈ A}.



As an example of the moreover, _ω, ω satisfies Benda's supercompactness theorem iff _ωλ carries a fine, normal measure that need not even be countably complete. 
Note that _ω, ω can never be _ωλ-ω-compact for type omission: the max function shows that no fine ultrafilter on _ωλ can be normal.

This general framework directly gives model theoretic characterizations of large cardinals that are characterized by normal ultrafilters.

 
For each numbered item below, all of its subitems are equivalent:


  * 
	
  * κ is measurable.
	
  * _κ,κ is _κκ-κ-compact for type omission.


  *  
	
  * κ is λ-supercompact.
	
  * _κ,κ is _κλ-κ-compact for type omission.


  *  
	
  * κ is huge at λ; that is, κ is huge and there is j:V→ witnessing this with j(κ)=λ.
	
  * _κ,κ is [λ]^κ-κ-compact for type omission.


  * 
	
  * κ is n-huge at λ_1, …, λ_n.
	
  * _κ,κ is { s ⊂λ : ∀ i < n, |s ∩λ_i+1| = λ_i}-κ-compact for type omission.




Proof: The proof follows the standard characterizations of these notions in terms of normal ultrafilters (see <cit.>) and from Theorem <ref>.

For instance, in (<ref>), if κ is huge at λ, then there j:V → with j = κ with ^j(κ)⊂ and λ = j(κ).  In particular, this means that j"λ∈ and belongs to j([λ]^κ) = ([j(λ)]^j(κ))^.  Using Theorem <ref>.(4)→(2), _κ, κ is [λ]^κ-κ-compact for type omission.

In the other direction, assume that _κ,κ is [λ]^κ-κ-compact for type omission.  By Theorem <ref>.(2)→(3), there is a fine, normal κ-complete ultrafilter on I concentrating on [λ]^κ.  By <cit.>, κ is huge at λ.†


Item (<ref>) is Benda's supercompactness theorem (Theorem <ref>). Item (<ref>) can be reformulated along the lines of Fact <ref>:


If T = ∪_α < κ T_α is an _κ, κ(τ)-theory and p(x) = {ϕ_i(x) | i < κ} is a type such that for every α < κ, there is a model of T_α omitting {ϕ_i (x) | i < α}, then there is a model of T omitting p.



This helps highlight the impact that the normality of an ultrafilter has on the resulting ultraproduct: if U is a normal ultrafilter on I ⊂(λ) and {M_s | s ∈ I} are τ-structures, then ∏ M_s/U omits any type p = {ϕ_α(x) |α < λ} such that {s ∈ I | M_s  omits  p_s}∈ U.


As mentioned above, any ultrafilter on (λ) concentrates on some _μλ.  We can characterize when an ultrafilter exists on some _μλ with the following large cardinal notion:


Fix κ≤μ≤λ.  The following are equivalent:

	
  * κ is λ-supercompact with μ clearing: there is j:V → with j"λ∈ and j(μ) > λ.
	
  * _κ,κ is _μλ-κ-compact for type omission.



Proof: This follows from Theorem <ref>: j(μ) > λ ensures that j"λ∈ j(_μλ).†


This equivalence even holds for κ=ω, where both conditions fail for all μ≤λ.

One feature of the compactness schema are that the theories are not required to have a specific size, but rather should be filtrated by a particular index set.  Note this is also true for strongly compact cardinals; that is, rather than characterizing λ-strongly compact cardinals as compactness cardinals for λ-sized theories in _κ, κ, we can give the following.


κ is λ-strongly compact iff any _κ, κ-theory T that can be filtrated as an increasing union of satisfiable theories indexed by _κλ is itself satisfiable.


This can even be extended to theories of proper class size.  Each item of Corollary <ref> remains true if compactness for type omission is generalized to allow for the T and the T_s in Definition <ref> to be definable proper classes and to allow for satisfaction by definable proper class structures.  The proof of Theorem <ref> goes through with this generalization.


ED_(V, ∈, x)_x ∈ V is used below to denote the -elementary diagram of the structure with universe V, a single binary relation ∈, and a constant for each x that is interpreted as x.  Formally, from Tarski's undefinability of truth, this is not a definable class when  extends _ω, ω.  Similarly, the statement that j:V → is elementary is not definable.

However, e.g., <cit.> shows that, for embeddings between inner models, Σ_1-elementarity implies Σ_n-elementarity for every n < ω.  Thus, mentions of elementary embeddings with domain V can be replaced by Σ_1-elementarity.  Similarly, the full elementary diagram of V could be replaced by its Σ_1-counterpart.  However, following set-theoretic convention, we continue to refer to the full elementary diagram.


Armed with a class version of omitting types compactness, we can show equivalences directly between the model-theoretic characterizations and the elementary embedding characterizations without working through an ultrafilter characterization.  At each stage, we find a model  of ED__κ, κ(V, ∈, x)_x ∈ V along with the sentences {c_α < c < c_κ|α < κ}, where c is a new constant, and some other sentences.  Such a model is well-founded because it models the _ω_1, ω_1-sentence that truthfully asserts well-foundedness, so we can take the Mostowski collapse π: ≅ with  transitive.  Then x ↦π(c_x) is an _κ, κ-elementary embedding that necessarily sends α <κ to itself.  Moreover, the interpretation of c  guarantees that the critical point is at most κ and the use of _κ, ω guarantees the critical point is at least κ.  This is enough to show κ is measurable and extra sentences to be satisfied and types to be omitted can be added to characterize the above large cardinal notions.


For each numbered item below, all of its subitems are equivalent:


  * 
	
  * κ is measurable.
	
  * There is a definable class model of
	
    ED__κ, κ(V, ∈, x)_x ∈ V∪{c_α < c < c_κ|α < κ}



  * 
	
  * κ is λ-strongly compact.
	
  * There is a model of
	
    ED__κ, κ(V, ∈, x)_x ∈ V∪{c_α < c < c_κ|α < κ}∪{c_α∈ d ∧ |d| < c_κ|α < λ}



  * 
	
  * κ is λ-supercompact.
	
  * There is a definable class model of
	
    ED__κ, κ(V, ∈, x)_x ∈ V∪{c_α < c < c_κ|α < κ}∪{c_α∈ d ∧ |d| < c_κ|α < λ}

	that omits
	
    p(x) = { x E d ∧ x ≠ c_α|α < λ}



  * 
	
  * κ is n-huge at λ_1, …, λ_n.
	
  * There is a definable class model of
	
    ED__κ, κ(V, ∈, x)_x ∈ V∪{c_α < c < c_κ|α < κ}∪{c_α∈ d_i+1∧ |d_i+1| = c_λ_i|α < λ_i+1, i < n}

	that omits, for i < n,
	
    p_i(x) = { x E d_i+1∧ x ≠ c_α|α < λ_i+1}





Proof: We prove item (3); the rest of the proofs are similar.

First, suppose that κ is λ-supercompact.  Then there is j:V → with j=κ, j(κ)>λ, and j"λ∈κ.  We claim that (the definable)  is our model after expanding the vocabulary:

	
  * c_x^ = j(x) for x ∈ V;
	
  * c^ = κ; and
	
  * d^ = j"λ.

The elementarity of j and the closure under κ-sequences of  imply that 

    (V, ∈, x)_x ∈ V≡__κ, κ(∏ V/U, E, [s ↦ x]_U)_x ∈ V≅(, ∈ j(x))_x ∈ V

The other sentences of the theory are true because j(α) < κ < j(κ) for α < κ precisely means j =κ, and we know that j(α) ∈ j"λ for all α < λ, with |j"λ|=λ <j(κ).

Second, suppose that we have such a definable class model (, E, a_x, a, b)_x ∈ V.  Well-foundedness is _ω_1, ω-expressible[Note that the first-order Axiom of Foundation can hold in ill-founded classes.]:

    ∀x_n:n<ω⋀_n<ω x_n+1 E x_n

Thus,  is well-founded with respect to E.  By taking the Mostowski collapse, we can assume that  is transitive and E is ∈.  Then define j:V → by j(x) = a_x.  

On the ordinals, j is increasing.  Thus, the second group of sentences tells us that κ≤ a < j(κ), so j ≤κ.  On the other hand, for each α < κ, V models the _κ, ω-sentence

    ∀ x (x E c_α→⋁_β<α x = c_β)

We can use this to show that c_α = α for every α < κ using induction.  Thus, j = κ.

Now we claim that b = j"λ.  For each α∈λ, we ensure that j(α) E b, so j"λ⊂ b.  Given x ∈ b, since  omits p, we must have x = j(α) for some α < λ.†


Note that we didn't directly use compactness for type omission in this proof.  However, in each case, the theory has a natural filtration by the appropriate partial order that is easily seen to be locally consistent while omitting the necessary type in ZFC.  For instance, in the case of κ being λ-supercompact, for s ∈_κλ, set α_s := otp(s).

    T_s    :=    ED__κ, κ(V, ∈, x)_x ∈ (V_≥κ∪ V_α_s)∪{ c_i < c < c_κ| i < α}∪{c_i E d ∧ |d| < c_κ| i ∈ s}
    
    p_s(x)    :=   {x E d ∧ x ≠ c_i | i ∈ s}

Then V is a model of this theory by interpreting every constant in the language by its index, c as α_s, and d as s.  This gives a way to go directly between model-theoretic and elementary embedding characterizations.  It also shows that it is enough to omit a single[In the case of n-huge, recall that the omission of finitely many types can be coded by the omission of a single type.] type to obtain the I-κ-type omission for any number of types.

The ability to characterize cardinals at the level of huge and above shows that the addition of type omission to attempts to characterize large cardinals is a real necessity.  Measurable and strongly compact cardinals have known model-theoretic characaterizations without type omission, so one might wonder if type omission is necessary to characterize huge cardinals.  From the following theorem of Makowsky, we can deduce that it is necessary.

[<cit.>]
The following are equivalent:

	
  * Every logic  has a strong compactness cardinal; that is, for every logic , there is a cardinal μ_ such that for any language τ and (τ)-theory T, if every T_0 ∈_μ_ T has a model then so does T.
	
  * Vopěnka's Principle.



Thus, Vopěnka's Principle “rallies at last to force a veritable Götterdammerung" for compactness cardinals for logics[With apologies to Kanamori <cit.>.].  Nonetheless, κ being almost huge implies that V_κ satisfies Vopěnka's Principle.  Thus, if κ is the first huge cardinal, then V_κ is a model of 


Vopěnka's Principle + “Every logic is compact, but there are no μ≤λ such that _μ,μ is [λ]^μ-μ-compact for type omission"


Indeed, other approaches to model-theoretic characterizations of large cardinals focused solely on compactness or reflection principles have yet to characterize huge cardinals.





§ SECOND-ORDER LOGIC AND BEYOND


We now turn to characterizations based on logics beyond (or orthogonal to) _∞, ∞.  In the spirit of Theorem <ref>, we can characterize compactness for omitting types in second-order logic with a similar theorem.

 
Let κ≤λ and I ⊂(λ) be κ-robust.  The following are equivalent:

	
  * ^2∪_κ, ω is I-κ-compact for type omission.
	
  * ^2_κ, κ is I-κ-compact for type omission.
	
  *  For every α > λ, there is some j:V_α→ V_β such that j = κ, j(κ)>λ, and j"λ∈ j(I).
	
  * For every α > λ, there is some j:V → such that j = κ, j"λ∈ j(I), and V_j(α)⊂.

Moreover, the first μ such that ^2 is I-κ-compact for type omission is the first μ that satisfies (<ref>) except with j = μ.



Proof: (4) implies (3) and (2) implies (1) are immediate.  We show that (1) implies (3) implies (4) implies (2).


For (1) implies (3), fix α > λ and consider the ^2 ∪_κ, ω-theory and type

    T    =    ED__κ, ω(V_α, ∈, x)_x∈ V_α∪{c_i < c < c_κ| i < κ}∪{Φ}
    
    p(x)    =   { x E d ∧ x ≠ c_i | i < λ}

where d is a new constant symbol and Φ is Magidor's sentence from Fact <ref>.  Then, we can filtrate this theory as 

    T_s    =    ED__κ, ω(V_α, ∈, x)_x∈ V_sup s ∪ [κ,α)∪{c_i < c < c_κ| i < sup s}∪{Φ}
    
    p_s(x)    =   { x E d ∧ x ≠ c_i | i ∈ s}

For each s ∈ I, we have that the natural expansion (V_α, ∈, x, s)_x ∈ V_sup s ∪ [κ, α) models T_s and omits p_s.  Thus, our compactness principle tells us there is a model of T omitting p, which, after taking the transitive collapse, gives the desired j:V_α→ V_β.


For (3) implies (4), fix α≥λ and let α' be the next strong limit cardinal above α.  Then there is j:V_α'→ V_β with j =κ and j"λ∈ j(I).  Then derive the extender E of length ℶ_j(α) to capture this embedding.  Forming the extender power of V and taking the transitive collapse, we get j_E:V →_E with the desired properties.


For (4) implies (2), let T̅ = {T_s | s ∈ I} be an increasing filtration of the ^2_κ, κ-theory T that respects the index and {p^a(x) | a ∈ A} be a collection of types indexed as p^a(x) = {ϕ^a_i(x) | i < λ} such that there are a club of s ∈ I with a model M_s that models T_s and omits each p^a_s.  Fix strong limit α≥λ to be greater than the rank of these models, their power sets, and the function f that takes each of these s to M_s; form j:V → with j = κ, j"λ∈ j(I) ∩, and V_j(α)⊂.  Since the domain of f contains a club, it includes j"λ.  Set M_*:= j(f)(j"λ).  By the elementarity of j, inside of  we have that M_*  j(T̅)_j"λ and, for each a ∈ A, M_* omits j(p^a)_j"λ = {j(ϕ^a_i) | i < λ} = j"p^a.  Since V_j(α)⊂ and M_* < j(α),  is correct about this satisfaction.  Finally, j"T ⊂ j(T̅)_j"λ because the filtration respects the index.  Thus, after a suitable renaming, we have found a model of T omitting {p^a(x) | a ∈ A}.†


To aid in the discussion of the implication of this theorem, we introduce the following ad hoc naming convention for large cardinal properties.


Suppose a large cardinal property P is characterized by being an I-κ-compactness cardinal for 𝕃_κ,κ.  Given a logic , we say that κ is P-for- iff  is I-κ-compact for type omission.


For instance, Corollary <ref>.(<ref>) characterizes huge as the existence of a λ > κ such that _κ, κ is [λ]^κ-κ-compact for type omission, so saying that κ is huge-for-^2_κ, κ means that there is a λ > κ so ^2_κ, κ is [λ]^κ-κ-compact for type omission.

Comparing Theorems <ref> and <ref>, a large difference is that the first-order characterizations are witnessed by a single embedding, while the second-order characterizations require class many embeddings.  The reason for this is that a single model  can be right about _κ, κ everywhere, but cannot be right about ^2 everywhere; otherwise, it would compute the power set of every set correctly and would be V.  Similarly, the type omitting compactness does not hold for definable class theories for second-order as it does for first.  If it did, one could easily derive an nontrivial embedding j:V → V.  

The first consequence of Theorem <ref> regards the identity crisis.  In the language of Definition <ref>, Magidor has shown that extendible cardinals are exactly those that are strong compact-for-^2_κ,κ <cit.> and additionally shown that the first strongly compact cardinal could be the first measurable or the first supercompact<cit.>.  This second result means that various compactness notions for _κ, κ have an imprecise relation to one another: chain compactnes could coincide with compactness, or there could be many chain compact cardinals below the first compactness cardinal.  Surprisingly, when moving to ^2, these notions coincide and the identity crisis disappears!


The following are equivalent.

	
  * κ is measurable-for-^2 ∪_κ,ω.
	
  * κ is strongly compact-for-^2_κ,κ.
	
  * κ is supercompact-for-^2_κ,κ.

In particular, all three of these statements characterize extendible cardinals.


Here we take `κ is measurable-for-' as in Fact <ref>.  That is, we don't incorporate any type omission; however, the type omission characterization holds as a result of the above.

Proof:  Clearly, (3) implies (2) implies (1) using (for the first implication) the trivially omitted type {x ≠ x | i < λ}.  

The condition Theorem <ref>.(3) is clearly stronger than extendibility, so any compactness for ^2_κ, κ (including chain compactness) gives extendibility.  In particular, j"κ = κ∈ j(_κκ).  So measurable-for-^2 ∪_κ, ω implies extendible.

Similarly, the definition of extendibility includes that j(κ) > α.  In this case, j"λ has size λ≤α, so j"λ∈ j(_κλ).  Thus extendibility implies supercompact-for-^2_κ, κ.†



The key to these equivalences is that the condition about j"λ in Theorem <ref>.(<ref>) often had more to do with the closure of the target model (i.e., is j"λ in ?), rather than the nature of the relationship between j(I) and j"λ.  When we have extendible-like embeddings, j"λ is always in the target model, so many of the type omitting compactness principles (or even just compactness principles) become trivial.

A possible explanation for the collapse of the identity crisis is that type omission in ^n_κ, κ is expressible[This is immediate for ϕ-type omission for fixed ϕ, and any type omission can be coded as ϕ-type omission in an expansion.] in ^n+1_κ, κ, which is again codeable in ^n_κ, κ.  Thus, one might expect no difference between strong compact- and supercompact-for-^2_κ, κ.  However, this does not explain why measurability coincides with these notions,  and the below proposition shows that some notions of type-omitting compactness for ^2 are strictly stronger than extendibility (in consistency strength).

 
	
  * κ is huge at λ-for-^2_κ, κ iff for every α≥λ, there is j:V_α→ V_β such that j = κ and j(κ) = λ.
	
  * If κ is almost 2-huge at λ_1, λ_2, then there is a κ-complete, normal ultrafilter on κ containing
	
    {α < κ| V_λ_2“α is huge-for-^2_κ, κ"}

	
  * If κ is huge-for-^2_κ, κ, then there is a κ-complete, normal ultrafilter on κ containing
	
    {α < κ|α is huge}




Proof: The first item is just a restatement of Theorem <ref> with I = [λ]^κ.  

Suppose κ is 2-huge at λ_1, λ_2 and j:V → witnesses this.  Fixing α∈ [λ_1, λ_2), j V_α is an embedding from V_α to V_β with j(κ) = λ_1 that is in (V_j(λ_2))^.  So

    (V_j(λ_2))^“∃ j_0:V_α→ V_β such that  j_0 = κ and j_0(κ)=λ_1"

Recall that (by arguments of <cit.>), V_λ_2 = (V_λ_2)^≺(V_j(λ_2))^.  Thus,

    V_λ_2“∃ j_0:V_α→ V_β such that  j_0 = κ and j_0(κ)=λ_1"

Since α was arbitrary,

    V_λ_2      “∀α≥λ_1, ∃ j_0:V_α→ V_β such that  j_0 = κ and j_0(κ)=λ_1"
    
    V_λ_2      “κ is huge at λ_1-for-^2_κ, κ"

Thus, {α < κ| V_λ_2“α is huge-for-^2_κ, κ"} is in the normal ultrafilter on κ derived from j.

Suppose κ is huge at λ-for-^2_κ, κ.  Picking α large enough and getting the corresponding j:V_α→ V_β with j(κ) = λ, we can derive a normal, κ-complete, fine ultrafilter U on [λ]^κ.  Then U ∈ V_β, so V_β“κ is huge."  Thus, {α < κ|α is huge} is in the normal, κ-complete ultrafilter on U generated from j.†


Similar results show that n-huge-for-^2_κ, κ lies strictly between n-huge and almost n+1-huge.  The preceding argument is due to Gabriel Goldberg, who also reports that he can show that huge-for-^2_κ, κ can be characterized in terms of hyperhugeness. Make a fact, check Gabe's argument.  Can we adapt it to get “huge at λ-for-^s, Σ_n_κ, κ implies C^(n)+-hyperhuge?" 

Recall that κ is λ-hyperhuge iff there is j:V → with j = κ and ^j(λ)⊂ and κ is hyperhuge iff it is λ-hyperhuge for every λ.  Hyperhuge cardinals have recently been shown to imply the existence of a minimal inner model of V that can reach V by set-forcing extensions by Usuba <cit.>.  Goldberg proves that κ being hyperhuge is equivalent to the existence of a κ_0<κ such that κ_0 is huge at κ-for-^2_κ, κ.  Additionally, κ being λ-hyperhuge is equivalent to the existence of μ > λ and a normal, fine, κ-complete ultrafilter on 

    [μ]^λ_*κ:={ s ⊂μ| |s| = λ, |s ∩κ| ∈κ, (s∩λ) < κ}

, which is equivalent to _κ, κ being [μ]^λ_*κ-κ-compact for type omission by Theorem <ref>.

Examining the proof of Theorem <ref>, we see that a level-by-level characterization of, e.g., α-extendibility is harder due to the tricky nature of the Löwenheim-Skolem number for second-order logics.  In first-order, the Löwenheim-Skolem number of _λ, κ for theories of size μ is ((λ+μ)^<κ)^+, which is also its Löwenheim-Skolem-Tarski number.  For second-order logic, LS(^2) (for sentences) is the supremum of all Π_2-definable ordinals (Väänänen <cit.>) and LST(^2) is the first supercompact, if one exists <cit.> .  However, weak compactness restricts the size of the theory, so admits a more local characterization.  Denote the Löwenheim-Skolem number of sentences of ^2_κ,κ by ℓ^2_κ.


The following are equivalent for κ.

	
  * κ is weakly compact-for-^2 ∪_κ, ω.
	
  * κ is weakly compact-for-^2_κ, κ.
	
  * Given any κ+1 ⊂⊂ V_ℓ^2_κ of size κ, there is a partial elementary embedding j:V_ℓ^2_κ→ V_β for some β with j = and j = κ.



Proof:  Clearly, (2) implies (1).  We show (1) implies (3) implies (2).


Suppose κ is weakly compact-for-^2 ∪_κ, ω and let κ+1 ⊂⊂ V_ℓ^2_κ.  Let T be the ^2 theory consisting of

	
  * the _κ, ω-elementary diagram of  in V_ℓ^2_κ;
	
  * c_i < c < c_κ for i<κ; and 
	
  * Magidor's Φ from Fact <ref>.

Then every <κ-sized subset of T is satisfiable as witnessed by an expansion of V_ℓ^2_κ.  By weak compactness, we get a model of T, which must be some V_β.  This induces a partial function j:V_ℓ^2_κ→ V_β with j =.  Moreover, the elements of T make this a partial elementary embedding with j = κ.


Suppose that κ satisfies the embedding property.  Let T = {ϕ_i | i < κ} be a ^2_κ, κ(τ)-theory that is <κ-satisfiable with |τ|≤κ.  Then, there is a function f with domain κ such that f(α){ϕ_i | i < α} for every α < κ; moreover, by the definition of ℓ^2_κ, we can assume that f(α) ∈ V_ℓ^2_κ.  Let ⊂ V_ℓ^2_κ contain all of this information and be of size κ.  Then, there is partial elementary j:V_ℓ^2_κ→ V_β with j = and j = κ.  In particular, we have that 

	
  * j(κ) > κ;
	
  * V_β“j(f)(κ)  j"T" and V_β is correct about this; and
	
  * j"T and T are just renamings of the same theory.

Thus, the suitably renamed j(f)(κ) witnesses that T is satisfiable.†


A key piece in translating weak compactness for second-order into an embedding characterization is the ability to axiomatize well-foundedness.  If we look at a fragment of ^2_κ, κ that includes an expression of well-foundedness, then weak compactness for this fragment is characterizable in a similar way, replacing ℓ^2_κ with the Löwenheim-Skolem number of that fragment.  However, if the fragment cannot express well-foundedness, then this characterization is harder.

Similar results can be proved by restricting the size of the theories under consideration.  In the general scheme, the theory T is allowed to be as large as one wants, as are the pieces T_s of the filtration.  If one restricts these pieces to be of size ≤μ and wants to characterize ^2_κ, κ being I-κ-compact for type omission, then it suffices to look at an embedding as in Theorem <ref>.(2) for α equal to the Löwenheim-Skolem number of ^2_κ, κ for μ-sized theories.

For the characterizations of strong and its variants, we need the concept of a Henkin second-order structure that is full up to some rank.  Recall the notion of a Henkin model described in Section <ref>.


Let M_* = (M, P, E) be a Henkin structure and A a transitive set.  

	
  * M_* is full to A iff every X ∈(M) ∩ A is represented in P; this means that there is c_X ∈ P such that, for all y ∈ M,
	
    y ∈ X  M_*  y E c_X

	
  * M_* is full up to rank α iff it is full to V_α.



While a Henkin structure has a nonstandard interpretation of second-order quantifiers, other additions to the logic must be interpreted standardly.  In particular, the next theorem discusses Henkin models of ^2(Q^WF)-theories; while any second-order assertions of well-foundedness–i.e., “∀ X ∃ y ∀ z (y ∈ X ∧ z ∈ X → y R z)"–can be satisfied non-standardly, any Q^WF assertions of well-foundedness–i.e., Q^WFxy(xRY)–must be correctly interpreted (and so R is well-founded).


The following are equivalent for κ≤λ.

	
  * κ is λ-strong.
	
  *  If T ⊂^2_κ, ω(Q^WF)(τ) is a theory that can be written as an increasing union T = ∪_α < κ T_α such that every T_α has a (full) model, then T has a Henkin model whose universe is an ordinal and is full up to rank λ.
	
  *  Same as (<ref>), but there is also a type p={ϕ_i(x) | i <κ} such that T_α has a (full) model omitting p_α, and the resulting model omits p.



Note that we add the condition on the universe of the model in (<ref>) to remove the possibility that the “full up to rank λ" condition is vacuous; if the universe of M just consists of elements of rank bigger than λ, then M is trivially full up to rank λ.

Proof: First, suppose that κ is λ-strong and let T be a theory and p a type as in (<ref>).  We produce a model of T in the standard way: let f be a function with domain κ such that f(α) is a model of T_α.  WLOG, f(s) is a full Henkin structure.  Then, in , j(f)(κ) is a model of (a theory containing) j"T and “j(f)(κ) is a full Henkin structure that omits j(p)_κ = j"p".   is incorrect about second-order satisfaction above rank λ; however, since V_λ⊂, it is correct about second-order satisfaction up to rank λ.


Second, suppose we have compactness.  Then we wish to build an embedding witnessing strength.  By the normal arguments, e.g. <cit.> or see Proposition <ref>, it is enough to derive a (κ, ℶ_λ)-extender from an embedding j: V_κ+2→ with j = κ, V_λ⊂, and  well-founded.  We can find such a model by considering the theory

    ED__κ, ω(V_κ+2, ∈, x)_x ∈ V_κ+2∪{c_i < c < c_κ| i < κ}∪{Φ}∪{Q^WFxy (x E y)}

This can be written as an increasing κ-length union of satisfiable theories in the standard way and any model leads to, after taking transitive collapse, the necessary j:V_κ+2→.
†


We could ask for a variation of (<ref>) that allows for arbitrary κ-satisfiable theories or, equivalently, theories indexed by some _κμ.  This would be equivalent to a jointly λ-strong and μ-strongly compact cardinal: there is a j:V → such that j = κ, V_λ⊂, and there is Y ∈ j(_κμ) such that j"μ⊂ Y.

If we drop the Q^WF, then we can characterize a weakening of λ-strong.  In the following theorem and proof, we break the convention that  always denotes some transitive model of a fragment of ZFC.  In particular, we allow it to be ill-founded.  For such models, wfp() denotes the well-founded part of .

 
The following are equivalent for κ≤λ.

	
  * κ is non-standardly λ-strong: there is an elementary embedding j: V→ with  not necessarily transitive such that j = κ and V_λ⊂ wfp().
	
  * If τ is a language and T ⊂^2_κ, ω is a theory that can be written as an increasing, continuous union T = ∪_α < κ T_α such that every T_α has a (full) model, then T has a Henkin model whose universe is an ordinal and is full up to rank λ.



Proof: The proof is the same as Theorem <ref>, with the changes exactly that we no longer insist on being correct regarding statements about well-foundedness.†


An argument of Goldberg shows that the level-by-level notions of non-standardly λ-strong and λ-strong are not equivalent, but full non-standard strong is equivalent to strong.



 §.§ C^(n) and sort logic


Moving to sort logic, we can prove a metatheorem along the lines of Theorems <ref> and <ref> by introducing the notion of a C^(n)-cardinal.  The C^(n) variants of large cardinals were introduced by Bagaria <cit.>.  Briefly, set C^(n) = {α∈| V_α≺_Σ_n V}, where ≺_Σ_n is elementarity for Σ_n formulas in the Lévy hierarcy (in the language of set theory).  For a large cardinal notion P witnessed by a certain type of elementary embedding, κ is C^(n)-P iff there is an elementary embedding j witnessing that κ is P and so j(κ) ∈ C^(n).  Recently, Tsaprounis <cit.> and Gitman and Hamkins <cit.> have independently shown that C^(n)-extendibility is equivalent to the a priori stronger notion of C^(n)+-extendibility: κ is C^(n)+-extendible iff for all α > κ in C^(n), there j:V_α→ V_β with j = κ and j(κ), β∈ C^(n).  It is the notion of C^(n)+-extendibility that we will use.

For some large cardinal notions, there is no increase of strength from moving to the C^(n)-versions (measurable, strong <cit.>, strongly compact <cit.>), but several other notions give an increasing hierarchy of strength.   Recall the notions of sort logic described in Section <ref> 




Let κ≤λ, n < ω, and I ⊂(λ) be κ-robust.  The following are equivalent:

	
  * ^s, Σ_n∪_κ, ω is I-κ-compact for type omission.
	
  * ^s, Σ_n_κ, κ is I-κ-compact for type omission.
	
  * For every α≥λ in C^(n), there is some j:V_α→ V_β such that j = κ, j"λ∈ j(I), and β∈ C^(n).
	
  * For every α≥λ in C^(n), there is some j:V → such that j = κ, j"λ∈ j(I) ∩,V_j(α)⊂, and j(α) ∈ C^(n).



The proof of Theorem <ref> follows the structure of Theorems <ref> and <ref>.  To make the necessary changes, we introduce the following notion and lemma.  Given a Σ_n formula ϕ() (in the Lévy hierarchy), let ϕ^∼() ∈^s, Σ_n be the same formula where unbounded quantifiers are replaced with the corresponding sort quantifiers.  This allows us to characterize C^(n) as follows.


Let α be an ordinal.  α∈ C^(n) iff V_α models

    {∀(ϕ() ↔ϕ^∼()) |ϕ is Σ_n}



Proof: For ∈ V_α, we always have ϕ() holds in V iff V_αϕ^∼().  The above theory makes this equivalent to V_αϕ(). †


Proof of <ref>:  We sketch the proof and highlight the changes from the proof of Theorem <ref>.


Given the compactness, we prove (3) by considering the theory and type

    T    =    ED__κ, ω(V_α, ∈, x)_x∈ V_α∪{c_i < c < c_κ| i < κ}∪{Φ}
          ∪{∀(ϕ() ↔ϕ^∼()) |ϕ is Σ_n}
    
    p(x)    =   { x E d ∧ x ≠ c_i | i < λ}

We filtrate this according to I in the standard way and use expansion of V_α to provide witness models; here it is crucial that we started with α∈ C^(n).  The model of T omitting p gives the desired j.  We can adjust this proof to get a proof of (4) by finding strong limit α' >α, also in C^(n), and relativizing the appropriate parts of the theory to ensure that j(α) ∈ C^(n).  Then, derive the extender E from this model, and j_E: V →_E that retains the desired properties.


Given (3) or (4), we prove the compactness by starting with a filtration T̅ = {T_s | s ∈ I} of an ^s, Σ_n_κ, κ-theory and types {p^a(x) = {ϕ^a_i(x) | i < λ}| a ∈ A}, find strong limit α∈ C^(n) above the rank of these objects and the function f that takes s to the model of T_s omitting each p^a_s.  V_α reflects these properties since α∈ C^(n), so by elementarity the target model thinks that j(f)(j"λ) models j"T and omits {j"p^a(x) | a ∈ A}.  Since V_β or V_j(α) are Σ_n-elementary in V, the target model is correct.†


Similar to second-order logic, the identity crisis disappears in sort logic and C^(n)-extendible cardinals witness a wide range of type omitting compactness.
First, we show that C^(n)+-extendible cardinals are equivalent to an apparent weakening: the requirement that j(κ) ∈ C^(n) is redundant.

The following are equivalent:

	
  * κ is C^(n)+-extendible.
	
  *  For every α > κ in C^(n), there is j:V_α→ V_β such that j = κ and β∈ C^(n).


We use the following lemma which will also be useful when examining Löwenheim-Skolem-Tarski numbers.  This is similar to Magidor's characterization of supercompacts.


Let κ be C^(n)-extendible.  Then for all α >κ in C^(n) and R ⊂ V_α, there are cofinally many γ < κ such that there are α̅ <κ in C^(n) and S ⊂ V_α̅ with elementary j:(V_α̅, ∈, S) → (V_α, ∈, R), j = γ, and j(γ) = κ.


Proof:  Fix α∈ C^(n) above κ, R ⊂ V_α, and β < κ.  Find α' >α in C^(n).  By assumption, there is j:V_α'→ V_β' with j = κ, j(κ)>α', and β' ∈ C^(n).  Given a transitive model  of a fragment of ZFC, write C^(n), for 's version of C^(n).  Since α, α' ∈ C^(n), α∈ C^(n), V_α'.  By elementarity, j(α) ∈ C^(n), V_β'.  Thus, 

    V_β'“∃α̅ < j(κ) and  S ⊂ V_α̅, j_0:(V_α̅, ∈, S) →(V_j(α), ∈, j(R)) such that 
    j_0( j_0) = j(κ),  j_0>j(β),  and α̅∈ C^(n)"

This is witnessed by j  V_α.  By elementarity,

    V_α'“∃α̅ < κ and  S ⊂ V_α̅, j_0:(V_α̅, ∈, S) →(V_α, ∈, R) such that 
    j_0( j_0) = κ,  j_0>β,  and α̅∈ C^(n)"

This is the desired result; note that it implies α̅∈ C^(n) because α' ∈ C^(n).†


Proof of <ref>:  Suppose (2) holds.  By Lemma <ref>, the class of C^(n)-ordinals are cofinal in κ.  Since this class is club, κ∈ C^(n).  Fix α > κ in C^(n) and find j as in (2); it suffices to show j(κ) ∈ C^(n).  Since κ, α∈ C^(n), we have κ∈ C^(n), V_α.  By elementarity, j(κ) ∈ C^(n),V_β.  Since β∈ C^(n), this gives j(κ) ∈ C^(n).†


 
The following are equivalent for every n<ω.

	
  * κ is C^(n)-extendible.
	
  * κ is measurable-for-^s, Σ_n∪_κ, ω.
	
  * κ is strong compact-for-^s, Σ_n_κ, κ.
	
  * κ is supercompact-for-^s, Σ_n_κ, κ.



Proof:  This follows a similar argument as Theorem <ref>, just requiring that the α's be in C^(n).†


However, the notion of a huge-for-^s, Σ_n_κ, κ cardinal would be similarly stronger in consistency strength than the notion in Proposition <ref>.

While the Löwenheim-Skolem-Tarski number for second order was determined by Magidor in <cit.> and Magidor and Väänänen have explored the Löwenheim-Skolem-Tarski numbers of various fragments of ^2 in <cit.>, the Löwenheim-Skolem-Tarski number of sort logic seems unknown.  We give a characterization of these cardinals in terms of a C^(n)+-version of Magidor's characterization of supercompacts.  We work with Löwenheim-Skolem-Tarski numbers for strictly first-order languages to avoid the technicalities around trying to develop a notion of elementary substructure for sort logic.  See Section <ref> for a definition of elementary substructure in second-order logic.


The following are equivalent for κ:

	
  * The conclusion of Lemma <ref>.
	
  * For all α < κ, if N is a structure in a strictly first-order language τ of size <κ, then there is M ≺__α, α N of size <κ such that M and N have the same ^s, Σ_n_α, α-theory.



Proof: (1) implies (2): Let N be a τ-structure with |τ|<κ.  Find γ < κ that is above α and |τ| and find α'>κ such that N ∈ V_α'.  Code the structure N into a relation R ⊂ V_α'  By assumption, there is α̅∈ (γ, κ) in C^(n) and j:(V_α̅, ∈, S) → (V_α, ∈, R) with j > γ.  Then S codes a structure M in V_α̅ that, by elementarity, models Th_^s, Σ_n_α, α(N).  Moreover, j  M is _α, α-elementary, so the range of j  M is the desired model.


(2) implies (1): Fix α > κ in C^(n), R⊂ V_α, and β < κ.  Apply the assumption to the structure (V_α, ∈, R, δ)_δ < β to get M ≺_^β, β N with the same ^s, Σ_n-theory.  This includes Magidor's Φ, so after taking the transitive collapse, we get ≺__β, β-elementary j:(V_α̅, ∈, S, δ)_δ<β→ (V_α, ∈, R, δ)_δ < β.   The constants for the elements of β force the critical point of j above β.†




 §.§ Rank-into-rank
 

We now turn to the strongest large cardinal principles, the rank-into-rank embeddings.  For an excellent survey of these, see Dimonte <cit.> or the expanded Dimonte <cit.>.  Following <cit.>, this section uses Σ^1_n(_κ,ω) to denote the fragment of infinitary second-order logic ^2_κ, ω consisting of the formulas that are Σ_n in their second-order quantifiers.

We can cast I1, I2, and I3 in a uniform way by saying, for n<ω, I2_n(κ, δ) is the assertion


There is j:V_δ→ V_δ, κ =  j, δ is the supremum of the critical sequence, and j is Σ^1_2n(_κ, ω)-elementary.


Laver <cit.> proved[Laver's paper attributes this result to Martin without citation, but other sources attribute it to Laver.] that Σ^1_2n+1-elementarity of such a j implies its Σ^1_2n+2-elementarity, so it suffices to consider the even levels.  Then I3 is I2_0, I2 is I2_1[Which is in turn equivalent to being elementary about statements of well-foundedness <cit.>.], and I1 is I2_<ω.

Note that second-order elementary embeddings should be understood in the context of Section <ref>.  Given j:V_δ→ V_δ, we can naturally extend this to j^+:(V_δ) →(V_δ) by j^+(R) = ⋃_α <δj(R ∩ V_α). Then set A^V_δ = j^+(A).  Note that j^+ is the only possible extension of j to V_δ+1 that could be elementary, and its Σ^1_0-elementarity follows from its first-order elementarity.

These principles have natural characterizations in terms of extendibility criteria.  Recall that κ is weakly compact iff every κ-sized structure has a proper _κ, κ-elementary extension <cit.> and κ is measurable iff every ≥κ-sized structure has a proper _κ, κ-elementary extension.


For each n≤ω and δ = ℶ_δ, the following are equivalent.

	
  * There is κ < δ such that I2_n(κ, δ).
	
  * Every δ-sized structure has a non-identity Σ^1_2n(_ω, ω)-elementary embedding into itself.



Proof: Suppose (1) holds, and let j:V_δ→δ with j =κ witness.  If M is of size δ, then we can code it as a structure with universe δ.  Then jδ is the desired embedding and it inherits the Σ^1_2n(_ω, ω)-elementarity of j.

Suppose (2) holds.  Then apply it to the structure (V_δ, ∈), which has size ℶ_δ=δ; this gives Σ^1_2n(_ω,ω)-elementary j:V_δ→ V_δ.  j must have a critical point below δ, call it κ.  As in Section <ref>, this strengthens the elementarity of j to Σ_2n^1(_κ, ω).  Since j:V_δ→ V_δ, we must have δ≥sup_n j^n(κ).  By Kunen's inconsistency, we must have δ≤sup_n j^n(κ).  Since δ is limit, this tells us that δ = sup_n j^n(κ), and I2_n(κ, δ) holds.†


I3 and I2 also have standard characterizations in terms of coherent ω-sequences of normal ultrafilters.  This allows us to prove the following type omitting compactness from them.  Unfortunately, this does not give an equivalence, but does allow us to sandwich these properties between two compactness for omitting types statements.  Recall that any type can be trivially extended to an equivalent, larger one by adding instances of “x ≠ x."


	
  * If I2_0(κ, δ), then for any theory T= ∪_s ∈_κκT_s ⊂_κ,ω(τ) and set of types {p^β = {ϕ^β_i(x) | i < κ_n_β+1}|β < μ}, if there are club many s ∈_κκ such that T_s has a model M_s with the property


for β < μ, {t ∈ [κ_n_β+1]^κ_n_β| M_t ∩κ omits  p^β_t = {ϕ^β_i(x) | i ∈  t}} contains a club,


then T has a model omitting {p^β|β < μ}.
	
  * I2_1(κ, δ) implies the same for the logic _κ, ω(Q^WF).



We will use the ultrafilter characterizations of these cardinals, in part because I3 doesn't have a characterization in terms of j:V → and we don't want to restrict to models of size ≤δ.

Proof: We prove the second item.  The first follows by the same argument, just removing the mentions of well-foundedness.

I2_1(κ,δ) is equivalent to the existence of κ-complete, normal ultrafilters U_n on [κ_n+1]^κ_n (where {κ_n| n < ω} is the critical sequence of the witnessing embedding) such that

	
  * coherence: For any X ⊂ [κ_n+1]^κ_n and m > n,
	
    X ∈ U_n {s ∈ [κ_m+1]^κ_m| s ∩κ_n+1∈ X}∈ U_m

	
  * well-founded: For any {n_i < ω| i <ω} and {X_i ∈ U_n_i| i < ω}, there is s ⊂δ such that, for all i < ω, s ∩κ_n_i+1∈ X_i.

Let M_s be the desired models.  Since they exists for club many s and U_0 contains this club, we can form the direct limit of the ultrapowers as standard: M^*_n = ∏_s ∈ [κ_n+1]^κ_n M_s ∩κ/U and there is a coherent system of _κ, κ-embeddings f_n, m: M^*_n → M^*_m that takes [f]_U_n to [s ↦ f(s ∩κ_n+1)]_U_n+1.  Then M^* is the direct limit of these models.  Standard arguments (see Proposition <ref> for a more general case) show that Łoś' Theorem holds for formulas of _κ, ω(Q^WF).  This guarantees that M^*  T.  To show the type omission, let β < μ and [n, f]_U̅∈ M^*.  Setting n' = maxn, n_β, this implies

    X:={t ∈ [κ_n'+1]^κ_n'| M_t ∩κ omits  p^β_t∩κ_n_β+1}∈ U_n'

  Define a function h on X by setting, for t ∈ X, h(t) ∈ t such that M_t ∩κϕ^β_h(t)(f(t∩κ_n+1)); this is possible exactly because of the type omission.  Then, h is regressive on a U_n'-large set, so there is α_0 < κ_n'+1 such that

    Y:={t ∈ [κ_n'+1]^κ_n'| M_t ∩κϕ^β_α_0(f(t∩κ_n+1))}∈ U_n'

Then, by Łoś' Theorem, [n,f]_U̅ = [n', f(s ∩κ_n+1)]_U̅ omits p^β in M^* as 

    M^* ϕ^β_α_0([n, f]_U̅)

Since [n, f]_U̅ and β we arbitrary, were are done.†


We can also isolate a type omitting compactness stronger than these rank-into-rank axioms.  Note that, unlike previous theorems, the types in the following don't shrink in the hypothesis.

 Fix a cardinal δ=ℶ_δ.

	
  * Suppose we have the following for some κ:
	

	For any _ω, ω(τ)-theory T with a filtration {T_α|α < κ} and |τ| = δ and any _ω, ω(τ)-type p(x), if every T_α has a model omitting p, then T has a model omitting p.
	

	Then there is κ_0 ≤κ such that I2_0(κ_0, δ).
	
  * The above implies I2_n(κ, δ) after replacing the logic with Σ^1_2n(_ω, ω).


Proof: Fix a bijection f:δ→ V_δ. Consider the theory and types

    T   =    ED__ω, ω(V_δ, ∈, x)_x ∈ V_δ∪{c_i < c < c_κ|  i < κ}
          ∪{d_i E d_j | i, j < δ, f(i) ∈ f(j)}∪{(d_i E d_j) | i, j < δ, f(i) ∉f(j)}
    
    
    p(x)    =   {x ≠ d_i | i < δ}

We claim that a model of T omitting p will give a bijection as required for I2_0(κ_0,δ): the first two parts of T will give an elementary j:V_δ→, where we don't yet know that  is transitive.  The third and fourth parts of T ensures that  has a (different) copy of V_δ in it given by x ∈ V_δ↦ d^_f^-1(x)∈.  Omitting p means everything in  is in this second copy of V_δ, so ≅ V_δ.  Thus, we have elementary j:V_δ→ V_δ that is not the surjective because its range does not contain c^.  If κ_0 :=  j, then this witnesses that I2_0(κ_0, δ) holds; note the second part of T ensures that j ≤κ.


To find such a model, we apply our compactness principle.  If α < κ, let T_α be T cutting out the constants c_x for elements with rank in the interval [α, κ) as in the discussion following Theorem <ref>, that is,

    T_α   =    ED__ω, ω(V_δ, ∈, x)_x ∈ V_α∪ V_≥κ∪{c_i < c < c_κ|  i < α}
          ∪{d_i E d_j | i, j < δ, f(i) ∈ f(j)}∪{(d_i E d_j) | i, j < δ, f(i) ∉f(j)}

We can find a model of T_α omitting p by taking the identity from V_δ to itself and interpreting c as α.†




 §.§ Elementary substructure for ^2
 

In contrast with first-order logics[Here meant as `sublogics of _∞,∞.'], the notion of elementary substructure in second-order logic has not been well-studied.  As evidence to this, in Väänänen's paper on second-order logic and set theory <cit.>, the word `structure' appears 210 times, but `substructure,' `sub-structure,' or even `sub structure' never appear.  Similarly, Shapiro's book <cit.> never discusses the matter[The notion of “elementary substructure" does appear here, but always in reference to its first-order version.].  A guess at the cause for this is that second-order logic is often employed to find categorical theories, whereas first-order logic attempts only to axiomatize classes of structures.  In such contexts, there is no reason to talk about one model's relation with others.

A first-attempt at second-order elementary substructure would be to work in analogy with first-order and say M is a _2-elementary substructure of N iff every formula holds of parameters from M in M iff it holds in N.  However, this notion doesn't allow for any proper elementary extensions as there are definable sets that must grow.  Concretely, the formula ϕ(X) := “∀ x (x ∈ X)" must be satisfied by the entire universe, so no extension of M can think ϕ(M) holds.  A more modest generalization is used by Magidor and Väänänen in <cit.>.  They say that M is an ^2-elementary substructure of N iff the above property holds restricted to formulas with only first-order free variables.  This works (in the sense that proper extensions can exist), and they observe that Magidor's theorem on the Löwenheim-Skolem-Tarski number of second-order extends to this notion of elementarity.  However, it seems lacking as there's no discussion of free variables in second order.

We give a definition of elementary substructure in second-order logic in Definition <ref> below.  An important point is that this definition includes a stronger notion of substructure in the second-order context (see Definition <ref>.(3)).  Before giving the formal definitions, we give a motivation.  Any second-order structure M can be viewed as a Henkin structure M^+ = (M, P[M], E).  Then every second-order statement about M can be transferred to a first-order statement about M^+, and the fact that M^+ is a full structure (isomorphic to (M, (M), ∈ )) can be captured by a single second statement Ψ asserting every subset of M is represented by a member of E.

Now that we have moved to a more familiar first-order setting, we can ask what relation between the original structures M and N characterizes when M^+ is an elementary substructure of N^+.  The key is that, given s ⊂ M and m_s ∈ P[M] representing it, N^+ thinks the same facts about m_s as M does when the parameters come from M, but N also thinks new things about m_s.  Crucially, there might be elements of N-M that N thinks are in m_s.  Then, setting s^N := {n ∈ N | N  n E m_s}, N thinks all the same facts about s^N that M does about s.  This notion of extending subsets is key to defining second-order elementary substructure.  This leads to the following definitions[We focus on ≺_^2 for ease, but these definitions could easily be changed to accommodate ≺_^2_α, α for α < κ.]:


 


	
  * Set ^ω(X) = ∪_n < ω(X^n).
	
  * For X⊂ Y, an extension function is a function f:^ω(X) →^ω(Y) such that, for all s ⊂ X^n, f(s) ∩ X^n = s and f(s) ⊂ Y^n and f fixes every finite set.
	
  * Given τ-structures M and N, we say M is a second-order substructure of N, written M ⊂_2 N iff |M| ⊂ |N| and there is an extension function s ↦ s^N such that for every atomic ϕ(x_1, …, x_n; X_1, …, X_n'), m_i ∈ M, and s_i ⊂ M^n_i, we have

    M ϕ(m_1, …, m_n; s_1, …, s_n')  N ϕ(m_1, …, m_n; s_1^N, …, s_n'^N)




We turn substructure into elementary substructure by letting ϕ range over all formulas.


Given τ-structures M and N, we say M is an 𝕃^2-elementary substructure of N, written M ≺_𝕃^2 N iff M ⊂_2 N and there is an extension function s ↦ s^N witnessing this such that for every ϕ(x_1, …, x_n; X_1, …, X_m) ∈𝕃^2, m_i ∈ M, and s_i ⊂ M^n_i, we have

    M ϕ(m_1, …, m_n; s_1, …, s_n')  N ϕ(m_1, …, m_n; s_1^N, …, s_n'^N)


Thus, M ≺_^2 N comes with a choice of extensions for each s ⊂ M.  This avoids the issue with the “first-attempt" notion of elementary substructure above.  Indeed, for any definable subset A of M, A^N must be the collection of elements satisfying that definition in N if M ≺_^2 N.

Note that if τ is a strictly first-order language (as is often the case), then M ⊂ N is equivalent to M⊂_2 N for any collection of extensions.  This means that comments about substructures in first-order languages in the context of second-order can be given the normal interpretation.  Also, for such a language, ≺_^2 will imply elementarity in the sense of Magidor and Väänänen.

For a general notion of ≤, a ≤-embedding is f:M → N such that f is a τ-isomorphism onto its range and f(M) ≤ N (a set theorist might prefer to call this model f"M).  Specializing to ≺_^2, f is a map on elements of M and, given s ⊂ M, f"s ⊂ f(M).  Then f(M) ≺_^2 N implies there is an extension (f"s)^N ⊂ N that satisfies the definition of ≺_^2.  To avoid this unfortunate notation, we say that f:M → N is ^2-elementary means that f is a map from M ∪^ω(M) to N ∪^ω(N) such that, for all ϕ(, ), ∈ M, and ∈^ω (M),

    Mϕ(, )  N ϕ(f(), f())



One should be skeptical that this is the “right" notion of ≺_^2 as it adds a strange new condition about global choices of extensions of subsets.  In addition to the heuristic with Henkin models above, we offer two “sanity" checks that this is the right notion.  

The first check is that Magidor's Theorem on the LST number of second order logic holds with this notion.  


Let κ be supercompact.  For any τ of size <κ and α < κ and τ-structure N, there is M ≺_^2_α, α N of size <κ.


This follows from the argument given in our heuristic: take a model N, turn it into a full Henkin structure N^+ with Skolem functions, and apply Magidor's version along with the sentence ∀ X ∃ x (X `=' x).  This quotational equality is an abbreviation of the statement that X and x have the same elements.

The second check is that the natural notion of an elementary diagram characterizes ^2-elementary embedability.  Given a τ-structure M, we define it's ^2 elementary diagram by first adding a first-order constant c_a for each a ∈ M and a second-order constant d_s for each s ∈^ω(M) and setting

    ED_^2(M) = {ϕ(c_a_1, …, c_a_n, d_s_1, …, d_s_k) | M ϕ(a_1, …, a_n, s_1, …, s_k) }



Let M, N be τ-structures.  The following are equivalent.

	
  * N has an expansion that models ED_^2(M).
	
  * There is a ^2-elementary f:M → N.



Proof: The proof follows as the first-order one.  Given ^2-elementary f:M→ N, expand N by c^N_a = f(a) and d^N_s = f(s).  Similarly, if N^*  ED_^2(M), define f:M→ N by the same formula.†


Some of the basic results of first-order elementary substructure transfer, while others do not.  For instance, the Tarski-Vaught test goes through with the same proof, although a slightly modified statement.


Given M ⊂_2 N (with a specified extension map s ↦ s^N), we have that M ≺_^2 N iff both of the following hold:

	
  * ∀ m_i ∈ M, s_j ⊂ |M|^n_j and ϕ(x, , ), if N ∃ x ϕ(x, , ^N), then there is m ∈ M such that N ϕ(m, , ^N); and
	
  * ∀ m_i ∈ M, s_j ⊂ |M|^n_j and ψ(X, , ), if N ∃ X ϕ(X, , ^N), then there is s ⊂ M^n such that N ϕ(s^N, , ^N).



Unfortunately, ≺_^2 does not have properties such as coherence and smoothness under unions of chains fail.  These are properties coming from the study of Abstract Elementary Classes, a general framework for nonelementary model theory (see Baldwin <cit.> for a survey):

	
  * Coherence: A binary relation ≺ on τ-structures is coherent iff whenever M_0 ≺ M_2 and M_1≺ M_2 and M_0 ⊂ M_1, then M_0 ≺ M_1.
	
  * Smoothness: A  binary relation ≺ on τ-structures is smoot under unions of chains iff whenever {M_i | i < α} is a ≺-increasing chain with α limit, then ⋃_i<α M_i is the ≺-least upper bound of the chain.



We can show ≺_^2 fails these properties by using Silver's example, the bane of many a nonelementary model theorist's hope.  Recall Silver's example[Although typically given as a PC-class (see <cit.>), we give it here as the class of models of a second-order sentence.]: the language consists of two sorts P and Q and the sentence ϕ_Silver is

    ∃ E ⊂ P × Q ( ∀ x,y ∈ Q (x = y ∀ z ∈ P (z E x  z Ey )))

In other words, a model M of ϕ_Silver consists of two sets P^M and Q^M such that there is an extensional relation on P^M and Q^M.  The existence of such a relation is equivalent to there being an injection from P^M to (Q^M), which is equivalent to |Q^M| ≤ 2^|P^M|.

If  is any fragment of ^2 containing ϕ_Silver, then M ≺_ N requires that any extensional relation on P^M × Q^M can be extended to an extensional relation on P^N × Q^N.  This is easy unless |Q^M| = 2^|P^M| and |Q^N| > 2^|P^N-P^M|, but it fails in this case.  Thus, we can find counter-examples to coherence and smoothness under unions of chains.  Note that, since the language is first-order, M ⊂_2 N is equivalent to normal substructure.

	
  * Coherence:  Set M_0, M_1, M_2 by P^M_0 = P^M_1 = ω; P^M_2 =ω_1; Q^M_0 = (ω); and Q^M_1 = Q^M_2 = (ω+1).  Then M_0 ⊂ M_1 and M_0, M_1 ≺_^2 M_2, but M_0 ⊀_^2 M_1.
	
  * Smoothness: For α < 2^ω, set M_α by P^M_α = ω and Q^M_α = ω+α.  Then this is a ≺_^2-increasing, continuous chain with union M = ( ω, 2^ω).  Set N by P^N = ω and Q^N = 2^ω+ω.  Then M_α≺_^2 N for each α < 2^ω, but M ⊀_^2 N.


We can also define Skolem function for second-order in the same way as first-order.  To do so, we must add strictly second-order functions to the language, so that even if τ started out strictly first-order, its Skolemization τ_sk won't be.

In the context of first-order, the notions of elementary substructure and that of club sets are very closely intertwined.  For instance, given a structure M and cardinal κ < M, 

    {s ∈_κλ : s  is the universe of an elementary substructure of M}

 is club, and, conversely, given a club ⊂_κλ, we can find a structure M with universe λ such that the above set is contained in .  This connection is mediated by the fact that both notions can be characterized by being the closure sets of certain functions (Skolem functions, in the case of elementary substructure).
 
 With a definition for second-order elementary substructure in hand, we can define a notion of club, which we call superclubs.  Recall our focus on ^2.



  * Fix μ < κ and let F_i:[λ]^<ω× [^ω(λ)]^<ω→^ω(λ) for i < μ.  Then

    C(F̅):={ s ∈_κλ|∃ extension f:^ω(s) →^ω(λ)  such that ∀∈ s, ⊂ s^, i < μ,
     we have  F_i(, f()) = f(y)  for some y ∈^ω(s)}


  * We call the collection  of all sets containing some C(F̅) the superclub filter on λ.



We have called  a filter without proving it is one.  This name is justified in Proposition <ref>, although it might be non-proper.

Although we defined it with a combinatorial characterization in the spirit of Definition <ref>, our interest in superclubs comes from the following model theoretic characterization.  Given a structure M and s ⊂ |M|, set M s to be the τ-substructure of M with universe generated by s (so is the closure of s under the functions of M).


The superclub filter is generated by sets of the form

    D(M):={ s ∈_κλ| M s ≺_^2 M}

for M a τ-structure with universe λ and |τ|<κ.


Proof:  First, suppose we are given {F_α|α < μ}.  Set τ ={F_α^n; m_1, …, m_k|α <μ; k, n, m_i < ω} to be a functional language so the domain of F_α^n; m_1, …, m_k is M^n ×(M^m_1) ×…×(M^m_k).  Expand λ to a τ-structure by interpreting F_α^n; m_1, …, m_k as F_α restricted to the appropriate arity.  Then D(M) ⊂ C(F̅).

Second, suppose we are given M with universe λ.  WLOG, we can assume that τ has (second-order) Skolem functions.  Let F̅ = {F^M | F∈τ} be the functions of M (interpreted as projection on other arities).  Then, since we have Skolem functions, C(F̅) ⊂ D(M).†

This model-theoretic characterization tends to be more useful to show the things that we want.


The superclub filter extends the club filter.


Proof:  The club filter can be characterized in the same way using first-order elementary substructure.  †


The next proposition shows that calling this a filter is justified.


The superclub filter is a κ-complete, possibly non-proper filter.


Proof:  The superclub filter is upwards closed by definition, so we only need to show it is closed under the intersection of <κ-many members.  Suppose that X_α∈ for α < μ < κ.  By Lemma <ref>, there are τ_α-structures M_α with universe λ and |τ_α|<κ such that D(M_α) ⊂ X_α.  Set τ_* to be the disjoint union of the τ_α's and M_* to be the τ_*-structure that is simultaneously an expansion of each M_α.  Then D(M_*) ⊂ D(M_α), so this witnesses that ⋂_α<μ X_α∈.


 It is a filter by definition.  Given D(M_α) with M_α a τ_α structure, set M_* to be the ∪τ_α-structure that is simultaneously an expansion of each M_α.†


Proposition <ref> leaves open the possibility that the superclub filter is non-proper, i.e., contains the empty set.  In fact, the properness of the superclub filter characterizes supercompact cardinals.


Let κ≤λ.

	
  * If κ is not λ-supercompact, then there is an empty superclub.  Moreover, there is a uniform definition of the empty superclub.
	
  * If κ is λ-supercompact, then every normal, fine, κ-complete ultrafilter on _κλ extends the superclub filter.



Proof: If κ is not λ-supercompact, then by Corollary <ref>, there is a structure M of size λ in a language τ of size < κ such that M has no ≺_^2-substructures; looking at Magidor's proof, we can take M to be some (V_β, ∈, α)_α∈μ for some β < λ and μ < β.  WLOG |M| is λ by expanding the universe by a trivial sort.  Then D(M) = ∅ is in the superclub filter.

If κ is λ-supercompact, then let U be a normal, κ-complete ultrafilter on _κλ and derive j_U:V →_U.  Let M be a τ-structure with universe λ and, WLOG, it has Skolem functions.  By Magidor's result and its extensions, j_U"M ⊂_^2 j_U(M).  Since M has Skolem functions, j_U"M≺_^2 j_U(M).  Thus, j"λ∈(D(j_U(M)))^_U = j(D(M)).  So D(M) ∈ U.  †



In particular, we get the following:


Given κ≤λ, κ is λ-supercompact iff the superclub filter on _κλ is proper.


While superclubs give a characterization of supercompact cardinals, they lack a nice characterization in the spirit of “closed unbounded sets" that clubs have.  Such a characterization would shed light on properties of the ≺_^2 relations and permit the exploration of superstationary sets.



§ EXTENDERS AND OMITTING TYPES
 


A key distinction between Theorem <ref> and Theorems <ref> and <ref>  is the lack of an analogue of Theorem <ref>.(<ref>) in the results of Section <ref>.  The large cardinals of Section <ref> are typically characterized by the existence of certain kinds of extenders, but the modifier “certain" is typically characterized in a way that nakedly concerns embeddings between models of set theory–e.g., <cit.> characterizes κ being λ-strong by the existence of an extender E such that j_E:V→_E witnesses λ-strength–rather than any combinatorial feature of the extender.

We begin with a combinatorial characterization, although it still references the V_α's and may be of limited interest.  However, we use this as a starting point to investigate a larger question: to what extent is second-order logic necessary to characterize the large cardinals in Section <ref>?

We should say a few words about our definition of extenders.  We say that a (κ, λ)-extender is E = {E_|∈ [λ]^<ω}, where each E_ is a κ-complete ultrafilter on ^κ satisfying coherence, normality, and well-foundedness (see <cit.> for a statement of these conditions in a slightly different formalism).  Note that this is a compromise between the original definition of Martin-Steel <cit.>–which took ∈ [V_λ]^<ω and required E_ to be on ^ V_κ–and more modern presentations like <cit.>–which takes ∈ [λ]^<ω but requires E_ to be on [κ]^||.  Crucially,  we also depart from both of these and don't require that {s ∈^κ|∀ a_1, a_2 ∈(a_1 < a_2 ↔ s(a_1) < s(a_2))}∈ E_.

Now we are ready to give a combinatorial characterization.


We say a bijection h: ℶ_α→ V_α is rank-layering iff for every β < α, h"ℶ_β = V_β.


Note this condition is equivalent to x ∈ y ∈ V_α implies h^-1(x) ∈ h^-1(y).

 
The following are equivalent.

	
  * κ is λ-strong.
	
  * For some rank-layering bijection h:ℶ_λ→ V_λ, there is a (κ, ℶ_λ)-extender E such that for all α, β < λ, we have
	
    h(α) ∈ h(β) { s ∈^{α, β}κ| h(s(α)) ∈ h(s(β))}∈ E_{α, β}

	
  * For every rank-layering bijection h:ℶ_λ→ V_λ, there is a (κ, ℶ_λ)-extender E such that for all α, β < λ, we have
	
    h(α) ∈ h(β) { s ∈^{α, β}κ| h(s(α)) ∈ h(s(β))}∈ E_{α, β}




In each of the cases, we have that x ∈ V_λ is the image of [{h^-1(x)}, s ↦ h (s(h^-1(x)))]_E after the transitive collapse.

Proof of Proposition <ref>: (3) implies (2) is clear.


(2) → (1): Given such an extender, set j_E: V → to come from the extender power of V by E followed by the transitive collapse; then j = κ and j(κ) > λ by standard arguments (see <cit.>).  So we are left with showing that V_λ⊂.  Let π:∏ V/E → be the Mostowski collapse.  Following the above, we will show that, for each x ∈ V_λ, 

    x = π([{h^-1(x)}, s ↦ h (s( h^-1(x)))]_E)

We work by induction on the rank of x.  For each y ∈ x, the condition on our extender precisely gives that 

    { s ∈^{h^-1(y), h^-1(x)}κ   |    h(s(h^-1(y))) ∈ h(s(h^-1(x)))}∈ E_{h^-1(y), h^-1(x)}
    π([{h^-1(y)}, s ↦ h (s( h^-1(y)))]_E)    ∈   π([{h^-1(x)}, s ↦ h (s( h^-1(x)))]_E)

Now suppose that z ∈π([{h^-1(x)}, s ↦ h ∘ s ∘ h^-1(x)]_E).  We wish to show that π^-1(z) is one of our terms for some y ∈ x.  We know that π^-1(z) is [, f]_E for some ∈ [ℶ_λ]^<ω and f with domain ^κ.  WLOG we may assume that h^-1(x) ∈, and coherence implies that [{h^-1(x)}, s ↦ h (s(h^-1(x)))]_E=[, s ↦ h (s(h^-1(x)))]_E.  Thus, we have that 

    {s ∈^κ| f(s) ∈ h(s(h^-1(x)))}∈ E_

If we set α = h^-1(x), then the rank-layering property tells us that 

    {s ∈^κ| h^-1(f(s)) ∈ s(α)}∈ E_

By normality, this means that there is ⊃ and β∈ such that

    {s ∈^κ| h^-1(f(s)) = s(β) }∈ E_

If we set y=h(β) and g(s)=f(s), we can rewrite this as 

    {s ∈^κ| g(s) = h(s(h^-1(y)))}∈ E_

Putting all of this together, we have that

    π^-1(z) = [, f]_E = [, g]_E = [{h^-1(y)}, s ↦ h(s(h^-1(y)))]_E

So z must be an element of this form with y ∈ x, as desired.

(1) → (3): Fix h:ℶ_λ→ V_λ to be a rank-layering bijection and j:V→ to witness that κ is λ-strong, so j = κ, j(κ)>λ, and V_λ⊂.  <cit.> describes the general method of deriving an extender E^* from an elementary embedding by setting

    X ∈ E^*_𝕀_∈ j(X)

The choice of the identity to `seed' the ultrafilters is not necessary; we can (and will) change this function without changing the fact that the derived ultrafilters form an extender.  In particular, define E by specifying, for each ∈ [ℶ_λ]^<ω and X ⊂^κ, 

    X ∈ E_ j(h)^-1∘ h ∘ j^-1 j() ∈ j(X)

Then E is a (κ, ℶ_λ)-extender and we only need to show the additional property.  We verify this with the following chain of equivalences, making crucial use of our choice of seed: for α, β < λ, set = {α, β}

    {s ∈^κ| h(s(α))∈ h(s(β))}   ∈    E_ j(h)^-1∘ h ∘ j^-1 j() ∈ j( {s ∈^κ| h(s(α))∈ h(s(β))})
           j(h)^-1∘ h ∘ j^-1 j() ∈{s ∈^j()j(κ) | j(h)(s(j(α)))∈ j(h)(s(j(β)))}
           j(h)(j(h)^-1(h(j^-1(j(α))))) =  j(h)(j(h)^-1(h(j^-1(j(β)))))
           h(α) ∈ h(β)

as desired. †


Now we turn to the issue of how necessary logics beyond _∞, ∞ are to characterize large cardinals and focus on strong cardinals.  Theorem <ref> characterizes strong cardinals in terms of the logic ^2; is there a characterization of strong cardinals solely in terms of _∞, ∞?

For κ≤λ, consider the following (definable-class) _κ, ω(Q^WF)-theory and types for y ∈ V_λ:

    τ   =   {E, c_a, c, d_a'}_a ∈ V, a' ∈ V_λ
    
    T    =    ED__κ, ω(Q^WF)(V, ∈, x)_x ∈ V∪{d_i = c_i < c < c_κ| i < κ}∪{d_b ∈ d_a | b ∈ a ∈ V_λ}
    
    p_y(x)    =   { x E d_y ∧ (x = d_z) | z ∈ y}

It follows from the methods of the previous sections that T has a model omitting each p_y iff κ is λ-strong.  However, what we lack from Proposition <ref> is an appropriate type omitting-compactness scheme and a decomposition of T along that scheme that is satisfiable.  The difficulty in constructing this becomes more clear if we look at the extender product construction.

Given a (κ,λ)-extender E, for each ∈ [λ]^<ω, we form the ultraproduct ∏ V/E_.  The coherence axiom and Łoś' Theorem insures that the restriction function induces a coherent system of _κ, κ-elementary embeddings  from ∏ V/E_ to ∏ V/E_ when ⊂.  Since [λ]^<ω is directed, we can get a colimit ∏ V/E and _κ, ω-elementary embeddings.  Since E is well-founded, so is ∏ V/E, so we can form its transitive collapse _E.

We can generalize this to a more general model-theoretic context.  Fix some ∈ [λ]^<ω and suppose that we have a collection of τ-structures {M_s | s ∈^κ} and form the ultraproducts ∏_s ∈^κ M_s  /E_ for ⊃.  Again, the coherence gives a coherent system of embeddings, so we can form the extender product ∏ M_s /E as the colimit of this system.  This structure has universe {[, f]_E |⊂∈ [λ]^<ω, f ∈^κ} where [, f]_E = [, g]_E iff {s ∈^κ| f(s ) = g(s ) }∈ E_.  Then we have following result for Łoś' Theorem.



Let E = {E_|∈ [λ]^<ω} be a system of κ-complete ultrafilters satisfying coherence.  The following are equivalent:

	
  * E is well-founded.
	
  * Łoś' Theorem holds for _κ, ω(Q^WF) formulas.  That is, given τ-structures {M_s | s ∈^κ}, ϕ(x_1, …, x_n) ∈_κ, ω(Q^WF)(τ), and [_1, f_1]_E, …, [_n, f_n]_E ∈∏ M_s/E, we have
	


	
    ∏ M_s/E ϕ([_1, f_1]_E, …, [_n, f_n]_E)

iff
	
    { s ∈^∪_iκ| M_s ϕ( f_1(s_1), …, f_n(s _n))}∈ E_∪_i







Proof: For one direction, it is known that E is well-founded iff ∏ V/E is well-founded, which follows from Łoś' Theorem applied to Q^WFxy(x∈ y).

For the other direction, fix ∈ [λ]^<ω and τ-structures {M_s | s ∈^κ}.  We show Łoś' Theorem for _κ, ω(Q^WF) by induction.  Standard arguments take care of everything but the Q^WF quantifier.  So suppose Łoś' Theorem holds for ϕ(x, y, ) and [, f]_E ∈ M_E := ∏ M_s/E.

First, suppose that {s ∈^κ| M_s Q^WF xy ϕ(x, y, f(s))}∉E_.  Set X to be the complement of this set.  For s ∈ X, there is c^s_r ∈ M_s for r < ω such that M_s ϕ(c^s_r+1, c^2_r, f(s).  Then c_r := [, c^s_r]_E ∈ M_E witnesses the illfoundedness of ϕ.

Second, suppose that X_0 = {s ∈^κ| M_s  Q^WFxyϕ(x,y,f(s))}∈ E_ and M_E  Q^WFxyϕ(x, y, [, f]_E).  Then there is [_r, f_r]_E ∈ M_E such that

    M_E ϕ([_r+1, f_r+1]_E, [_r, f_r]_E, [, f]_E)

for all r < ω and, WLOG, ⊂_r ⊂_r+1.  Then

    X_r+1 := {s ∈^_r+1κ| M_s ϕ(f_r+1(s), f_r(s _r), f(s)}∈ E__r+1

The well-foundedness of E gives h:∪→κ such that h_r+1∈ X_r+1 and h ∈ X_0.  Then, for r < ω,

    M_hϕ(f_r+1(h_r+1), f_r(h _r), f(h))

Thus, f_r(h _r) ∈ M_h | r < ω witnesses the illfoundedness of ϕ(x, y, f(h )) in M_h, contradicting h ∈ X_0.†


So, to decompose T above, one could try to construe ∏ V/ E as an extender product ∏ M_s /E in the appropriate language and for the appropriate , and then see what fragment of T M_s satisfies.  However, the problem is that the factors that make up ∏ V/E don't have expansions to τ-structures.  Rather, the analysis of ∏ V/E crucially uses that it can be seen as the extender power ∏_s∈^κ V/E for any choice of .  Thus, there is no way to analyze which parts of the types each factor omits.

However, there is a nice criterion for when an extender product (or just a coherent ultraproduct by a κ-complete, well-founded coherent ultrafilter) omits a _κ, ω(Q^WF)-type based on the behavior of the original models M_s provided that the domain of the type is a subset that appears as an element of _E.


Let E be a (κ, ℶ_λ)-extender witnessing that κ is λ-strong.  Suppose that ∈ [ℶ_λ]^<ω, {M_s | s ∈^κ} is a collection of τ-structures, A_ℓ⊂∏ M_s/E of rank ≤λ for ℓ = 0, 1, and ϕ(x, y) ∈_κ, ω(Q^WF).  Set p(x) = {ϕ(x, a) | a ∈ A_0}∪{ϕ(x, a) | a ∈ A_1} and p_s(x) = {ϕ(x, a) | a ∈ f_0(s)}∪{ϕ(x, a) | a ∈ f_1(s)}, where [, f_ℓ]_E represents A_ℓ in _E.  Then, the following are equivalent:

	
  * ∏ M_s/E omits p.
	
  * {s ∈^κ| M_s  omits  p_s}∈ E_.



Note that we have restricted both to the case of ϕ-types and to the case where E is an extender witnessing strength for simplicity and because those cases suffice for our assumption.  We could remove these assumptions, instead requiring that A_ℓ is an element of the subset sort of .

Proof: The structure ∏ M_s/E is (isomorphic to) j_E(g)(), where g is the function taking s ∈^κ to M_s and = [, s ↦ s()]_E.  Then, since A_ℓ∈ V_λ∈_E, Łoś' Theorem for extenders tells us that 

    _E “j_E(g)()  omits  p" _E “j_E(g)()  omits the ϕ-type generated by  A_0, A_1"
    {s ∈^κ| g(s )  omits the ϕ-type generated by f_0(s), f_1(s)}∈ E_
    {s ∈^κ| M_s  omits  p_s}∈ E_

†


Still, this doesn't give a syntactic characterization of strength because it deals with type omission for types over sets, whereas Theorem <ref> deals just with type omission over the empty set (in the appropriate language).  Thus, we are still left with the following question.


Given κ≤λ, is there a syntactic property of logics such that _κ, ω(Q^WF) (or some other sub-logic of _κ, κ) satisfies this property iff κ is λ-strong?


amsalpha

