2. Preliminaries

Gödel logics are logics intermediate between intuitionistic logic and classical logic derived from intuitionistic logic by assuming that the set of truth values is a suborder of $\mathbb {R}$ . They typically do not validate the principle of excluded middle. We consider here first-order Gödel logics $G_v$ , which are defined with the same syntax of classical or intuitionistic first-order logic. They were introduced by Gödel [Reference Gödel11] as part of his proof that intuitionistic logic is not finite-valued, and were axiomatized by Dummett [Reference Dummett9]. For more background, we refer the reader to Baaz, Preining, and Zach [Reference Baaz, Preining and Zach3], Baaz and Preining [Reference Baaz and Preining2], or Hájek [Reference Hájek12]. A characterization of the recursively axiomatizable Gödel logics can be found in [Reference Baaz, Preining and Zach3].

2.2. Syntax

First-order logic contains the binary connectives $\wedge , \vee , \to $ and the propositional constant $\bot $ (false), as well as quantifiers $\forall ,\exists $ . For arbitrary formulae $\phi $ , the truth value is defined by induction according to Figure 1. The set v is assumed to be closed as suprema and infima figure in the definition, and $0$ and $1$ are respectively interpreted as “false” and “true.”

Figure 1

Definition of truth values for nonatomic formulas in Gödel logic.

We introduce the following defined connectives, which will be used below in the proof:

$$ \begin{align*} \top &:= \bot\to\bot\\ \lnot \varphi &:= \varphi \to \bot\\ \varphi\leftrightarrow\psi &:= \varphi\to \psi\wedge \psi\to\varphi\\ \varphi \prec\psi &:= (\psi\to\varphi)\to\psi. \end{align*} $$

Note that it need not be the case that for any $a\in M$ . We write $M \models \varphi $ if , in which case we say that M is a model of $\varphi $ . Given a set of formulae $\Gamma $ , we write $M\models \Gamma $ if $M\models \varphi $ for each $\varphi \in \Gamma $ .

3. Proof of the theorem

Let us first focus on the logic $G_{[0,1]}$ for definiteness and, in particular, on showing that if $\kappa $ is a compactness cardinal for $G_{[0,1]}$ then $\kappa $ is $\omega _1$ -strongly compact; the other direction has an easier proof and will be treated toward the end. We do remark that the only fact about $[0,1]$ we will use in the construction is the fact that it contains an infinite subset order-isomorphic to $\mathbb {N}$ .

We shall consider a specific theory T in first-order logic consisting of sentences (3.1)–(3.14) below and use a $G_{[0,1]}$ -model M of it to extend a given $\kappa $ -complete filter to a countably complete ultrafilter. We describe the theory in what follows. Its vocabulary will be the set of symbols occurring in (3.1)–(3.14) and will also be described in what follows.

The vocabulary of the theory T contains a binary relation symbol $\in $ . We add excluded middle for membership:

(3.1) $$ \begin{align} \forall x\, &\forall y\, \big( x \in y \vee \lnot (x \in y) \big). \end{align} $$

Thus, $\in $ is crisp and behaves classically. We will use $x\not \in y$ as shorthand for $\lnot (x\in y)$ . T also contains axioms for

(3.2) $$ \begin{align} {\mathsf{ZFC}}^* \end{align} $$

for the relation symbol $\in $ . Here, ${\mathsf {ZFC}}^*$ is some large enough finite fragment of ${\mathsf {ZFC}}$ , such as ${\mathsf {ZFC}}$ with Replacement restricted to $\Sigma _{2025}$ formulas. Since ${\mathsf {ZFC}}$ proves the consistency of all its finite subtheories and we are working in ${\mathsf {ZFC}}$ , ${\mathsf {ZFC}}^*$ has many (classical) models, and in fact some of the form $V_\eta $ , for $\eta $ a cardinal. If necessary to avoid confusion, we will use $\in ^M$ to refer to the interpretation of $\in $ in the (eventual) model $M\models T$ . In continuing the description of T, we shall speak of objects such as $\mathbb {N}^M$ or the interval $[0,1]^M$ as shorthand for the unique element satisfying the usual definition of $\mathbb {N}$ or $[0,1]$ , using the prediate $\in ^M$ . We may also simply write $\mathbb {N}$ or $[0,1]$ , but will use superscripts if necessary to avoid confusion with $\mathbb {N}^V$ and $[0,1]^V$ . Later, we will also identify natural numbers $n\in \mathbb {N}^V$ with numerals that denote them. Note that, according to T, $\mathbb {N}$ and $[0,1]$ must exist, by ${\mathsf {ZFC}}^*$ , and $\mathbb {N}^M$ is a model of $\mathsf {PA}$ .

The theory T also makes use of a unary relation symbol R. It also contains the following axiom:

(3.3) $$ \begin{align} \forall x\,\forall y\, \bigg[\Big(\lnot\lnot R(x) \wedge \lnot\lnot R(y)\Big) \to \Big( \big(R(x)\leftrightarrow R(y)\big) \to x = y\Big)\bigg]. \end{align} $$

The predicate R will be the only relation symbol for which excluded middle does not hold in T, other than identity. The axiom asserts that if R attains the same non-zero value at two arguments $x,y$ , then they must be equal. We also have

(3.4) $$ \begin{align} \forall x\, \Big(x \in \mathbb{N} \leftrightarrow \lnot\lnot R(x)\Big), \end{align} $$

which asserts that the elements of $\mathbb {N}^M$ are precisely the objects at which the predicate R attains non-zero values. We also add:

(3.5) $$ \begin{align} \forall x\,\forall y\, \bigg[\Big(\lnot\lnot R(x) \wedge \lnot\lnot R(y)\Big) \to \Big( x <_{\mathbb{N}} y \to R(x) \prec R(y)\Big)\bigg]. \end{align} $$

Observe that $R(x) \prec R(y)$ attains value $1$ if and only if $R(x)$ has strictly smaller truth value than $R(y)$ or else if both $R(x)$ and $R(y)$ have truth value $1$ (see Figure 2). We have:

Claim 2. Suppose that

$$\begin{align*}M = \big(M, \in^M, \mathbb{N}^M\big)\end{align*}$$

is a model of (3.1)–(3.5). Then, $\mathbb {N}^M$ embeds into the unit interval $(0,1)$ .

Proof. The embedding is given by mapping . The domain of this mapping is $\mathbb {N}^M$ by (3.4). The mapping is injective by (3.3).

Note that for no $y \in \mathbb {N}^M$ do we have , for otherwise we would have

but by (3.3) we cannot have and hence we would have

which would force (3.5) to have truth value $<1$ . Thus, the range of the mapping is contained in $(0,1)$ .

According to (3.5), for all $x,y \in \mathbb {N}^M$ , $x <_{\mathbb {N}}^M y$ implies that , since is impossible. Hence, the mapping is strictly order-preserving, and thus an embedding, as desired.

We add to the vocabulary continuum-many unary function symbols $\{f_x\}_{x \in (2^{\mathbb {N}})^V}$ . We add an axiom

(3.6) $$ \begin{align} f_x: \mathbb{N}^M \to \mathbb{N}^M \end{align} $$

for each $x\in (2^{\mathbb {N}})^V$ . (This axiom is expressed using membership $\in $ .)

Figure 2

Evaluation of defined connectives in Gödel logic.

Moreover, whenever $x,y \in 2^{\mathbb {N}}$ and $n\in \mathbb {N}$ are such that $x\upharpoonright n \neq y\upharpoonright n$ , we add the axiom:

(3.7) $$ \begin{align} \forall k\in\mathbb{N}^M\, \big(n <_{\mathbb{N}} k \to f_x(k) \neq f_y(k) \big). \end{align} $$

Here, (3.7) is expressed using the numeral n, which in turn is expressed using membership $\in $ . Similarly, the inequality $n <_{\mathbb {N}} k$ is expressed using membership.

Claim 3. Suppose that

$$\begin{align*}M = \big(M, \in^M, \mathbb{N}^M, \{f_x^M: x\in 2^{\mathbb{N}}\}\big)\end{align*}$$

is a model of (3.1)–(3.7). Then, M is an $\omega $ -model.

Proof. Suppose otherwise and let $k \in \mathbb {N}^M$ be non-standard. Let $x,y \in (2^{\mathbb {N}})^V$ be different. Then, there is some standard $n\in \mathbb {N}$ such that $x\upharpoonright n \neq y\upharpoonright n$ and so by (3.7), we have $f_x(k) \neq f_y(k)$ . By (3.6), it follows that

$$\begin{align*}|\mathbb{N}^M| \geq 2^{\aleph_0}.\end{align*}$$

In particular, $\mathbb {N}^M$ is uncountable. By Claim 2, $\mathbb {N}^M$ embeds into $(0,1)$ . However, it is a theorem of Smoryński [Reference Smoryński, Lollu, Longo and Marcja18] that no uncountable model of $\mathsf {PA}$ embeds into $\mathbb {R}$ . (To see this, suppose otherwise and let $e:\mathbb {N}^M \to \mathbb {R}^V$ be an order-preserving embedding. For each $m\in \mathbb {N}^M$ , let

$$\begin{align*}I_m = \big(e(m), e(m+1)\big).\end{align*}$$

Then, $\{I_m: m\in \mathbb {N}^M\}$ is an uncountable family of pairwise disjoint nontrivial intervals of real numbers, which is absurd). Since clearly $\mathbb {N}^M \models \mathsf {PA}$ , this is a contradiction, so the claim is proved.

Now, let F be a $\kappa $ -complete filter on some set. Without loss of generality, let us assume that F is a filter on some cardinal $\lambda $ with $\kappa \leq \lambda $ . We add to T a family of $2^\lambda $ -many unary predicates $\dot A$ , one for each $A\subset \lambda $ . We also add a constant c. We add axioms:

(3.8) $$ \begin{align} \dot A(c)\vee\lnot\dot A(c),& \text{ whenever}\ A \subset \lambda \end{align} $$

(3.9) $$ \begin{align} \dot A(c),& \text{ whenever}\ A\in F \end{align} $$

(3.10) $$ \begin{align} \dot A(c)\leftrightarrow \lnot \dot B(c),& \text{ whenever}\ A = \lambda\setminus B \end{align} $$

(3.11) $$ \begin{align} \dot A(c) \wedge \dot B(c)\leftrightarrow \dot C(c),& \text{ whenever}\ C = A \cap B \subset \lambda \end{align} $$

(3.12) $$ \begin{align} \dot A(c) \to \dot B(c),& \text{ whenever}\ A\subset B \subset \lambda. \end{align} $$

In addition, for each $\omega $ -sequence $s:\mathbb {N}\to \mathcal {P}(\lambda )$ of subsets of $\lambda $ , we add a binary relation symbol $\dot A^s$ and axioms:

(3.13) $$ \begin{align} \dot A^s(i,c)\leftrightarrow \dot A(c),& \text{ whenever}\ A = s(i) \end{align} $$

(3.14) $$ \begin{align} \forall x\, \Big(x \in\mathbb{N}^M \to \dot A^s(x,c)\Big) \leftrightarrow \dot A(c),& \text{ whenever}\ A = \bigcap_{i\in\mathbb{N}} s(i). \end{align} $$

As before, (3.13) is expressed using the numeral i.

Claim 4. Suppose that

$$\begin{align*}M = \Big(M, \in^M, \mathbb{N}^M, \big\{f^M_x: x\in 2^{\mathbb{N}}\big\}, \big\{\dot A^M: A \subset\lambda\big\}, \big\{(\dot A^s)^M: s \in \mathcal{P}(\lambda)^{\mathbb{N}} \big\}, c^M\Big)\end{align*}$$

is a model of (3.1)–(3.14). Let

$$\begin{align*}U = \Big\{A\subset\lambda : M\models \dot A(c)\Big\}.\end{align*}$$

Then, U is an $\omega _1$ -complete ultrafilter extending F.

Proof. U extends F by (3.9). It is a filter by (3.11) and (3.12). Moreover, it is an ultrafilter by (3.8) and (3.10). It remains to verify that it is $\omega _1$ -complete. Let $s = \{A_i:i\in \mathbb {N}\}$ be an $\omega $ -sequence of subsets of $\lambda $ in U. By (3.13), we have

$$\begin{align*}M\models \dot A^s(i,c)\end{align*}$$

for all $i\in \mathbb {N}$ . By Claim 3, M is an $\omega $ -model, so we have

$$\begin{align*}M\models \forall x\, \Big(x \in\mathbb{N} \to \dot A^s(x,c)\Big).\end{align*}$$

By (3.14), we then have

$$\begin{align*}M\models \dot A(c),\end{align*}$$

where $A = \bigcap _{i\in \mathbb {N}}A_i$ , so $A \in U$ . This proves the claim.

In order to complete the proof of the theorem, it remains to show.

Proof. We will in fact find a model M of all sentences (3.1)–(3.8) and (3.10)–(3.14), together with any collection of size $\gamma < \kappa $ of sentences of the form (3.9). We begin the description of the model by setting $(M, \in ^M) = (V_\eta , \in )$ , where $\eta $ is large enough so that $\lambda < \eta $ and $V_\eta \models {\mathsf {ZFC}}^*$ . For each $n \in \mathbb {N}$ , we let

(3.15)

For elements $x \in V_\eta \setminus \mathbb {N}$ , we put . Identity is defined as usual for all x which are not natural numbers. For $n,m \in \mathbb {N}$ , we put if $n=m$ and otherwise we put

Axioms (3.1)–(3.5) are thus satisfied. In particular, note that $(M, \in )$ satisfies extensionality: if two sets $x,y\in M$ have the same elements (this is an antecedent with value in $\{0,1\}$ ), then we really have $x = y$ and thus . Perhaps the only axiom that needs further arguing is (3.3) for elements $n,m\in \mathbb {N}$ , in which case the antecedent of the implication attains truth value $1$ . If $n =m$ , then the conclusion trivially attains truth value $1$ , so the implication is true. Otherwise, by (3.15) we have

so according to Figure 2, we have

so the implication is true.

For the functions $f_x$ , notice that for each $k \in \mathbb {N}$ there are only $2^k$ different sequences of the form $x\upharpoonright k$ , for $x\in 2^{\mathbb {N}}$ . Thus, we define all $f_x$ by induction on k so that $f_x(k)$ depends only on $x\upharpoonright k$ and for each distinct sequence $x\upharpoonright k$ , $f_x(k)$ takes a different value in

Thus axioms (3.6)- and (3.7) are satisfied.

For each $A\subset \lambda $ , we interpret $\dot A$ as A. Fix any collection $\mathcal {A} = \{A_\iota : \iota <\gamma \}$ of sets in F, where $\gamma <\kappa $ . Since F is $\kappa $ -complete, there is some ordinal $\delta <\lambda $ with

$$\begin{align*}\delta \in \bigcap_{\iota<\gamma} A_\iota.\end{align*}$$

We interpret the constant c as $\delta $ . The model then satisfies axiom (3.8) and axioms (3.10)–(3.12), as well as all axioms of the form (3.9) given by the $\gamma $ -many sets $A_\iota $ from the family $\mathcal {A}$ .

Finally, for each $\omega $ -sequence $s:\mathbb {N}\to \mathcal {P}(\lambda )$ , we interpret $\dot A^s$ as the graph of s. Then, all axioms (3.13) and (3.14) are satisfied. This completes the proof of the claim.

With Claims 4 and 5, one direction of the proof of the theorem is complete. For the other direction, we simply observe that by the argument in [Reference Aguilera1, Section 4], every Gödel logic $G_{v}$ can be interpreted in $L_{\omega _1,\omega }$ . Since the compactness number of $L_{\omega _1,\omega }$ is the least $\omega _1$ -strongly compact cardinal (see the proof of [Reference Gitman and Osinski10, Theorem 5.4]), this is an upper bound for that of $G_{v}$ , for any set of truth values $v \subset [0,1]$ . (This only needs the easy direction: that if $\kappa $ is $\omega _1$ -strongly compact, then $L_{\omega _1,\omega }$ is $\kappa $ -compact; see [Reference Bagaria and Magidor5].)

Let us now indicate how to modify the proof given above for other sets of truth values $v \subset [0,1]$ . Note that the fact that $v = [0,1]$ was not used at any point in the proof other than in Claim 5. It is used in Claim 5 in order to ensure that the model constructed satisfies axiom (3.5), since $\mathbb {N}^V$ needs to embed into the set of truth values, for which it suffices that v contain a subset order-isomorphic to $\mathbb {N}$ (which in our case was the set of all numbers of the form

$$\begin{align*}1 - \frac{1}{2+n},\end{align*}$$

and these served as the truth values of formulas $R(n)$ for $n\in \mathbb {N}^M$ and for identities $n = m$ between natural numbers). If v is infinite, it must contain a subset order-isomorphic to one of $\mathbb {N}$ or $\mathbb {Z}_{\leq 0}$ . In the second case, we modify axiom (3.5) to the following “dual” form:

$$ \begin{align*} \forall x\,\forall y\, \bigg[\Big(\lnot\lnot R(x) \wedge \lnot\lnot R(y)\Big) \to \Big( y <_{\mathbb{\mathbb{N}}} x \to R(x) \prec R(y)\Big)\bigg]. \end{align*} $$

With this modification, everything works.

Finally, if $v \subset [0,1]$ is a finite set of truth values, say $|v| = n$ , then given a first-order theory T, let $T'$ be the theory containing the following axioms:

1. (1) ${\mathsf {ZFC}}^*$ ,

2. (2) $\dot M$ is an n-valued model in the Gödel logic $G_v$ ,

3. (3) $\dot M\models \phi $ , for each $\phi \in T$ .

If T is finitely satisfiable, then so is $T'$ . If so, by the compactness theorem for classical logic, $T'$ has a model, and the interpretation of $\dot M$ in this model will be a model of T.