Some observations on the FGH theorem

Taishi Kurahashi¹¹1Email: [email protected] ²²2Graduate School of System Informatics, Kobe University, 1-1 Rokkodai, Nada, Kobe 657-8501, Japan.

Abstract

We investigate the Friedman–Goldfarb–Harrington theorem from two perspectives. Firstly, in the frameworks of classical and modal propositional logics, we study the forms of sentences whose existence is guaranteed by the FGH theorem. Secondly, we prove some variations of the FGH theorem with respect to Rosser provability predicates.

1 Introduction

The notion of the weak representability of computably enumerable (c.e.) sets plays an important role in a proof of Gödel’s first incompleteness theorem. We say that a set $X$ of natural numbers is weakly representable in a theory $T$ if there exists a formula $\varphi_{X}(v)$ such that for any natural number $n$ , $n\in X$ if and only if $T\vdash\varphi_{X}(\overline{n})$ . If a set $X$ , which is c.e. but not computable, is weakly representable in a c.e. theory $T$ , then it is shown that there exists a natural number $n$ such that $T\nvdash\varphi_{X}(\overline{n})$ and $T\nvdash\neg\varphi_{X}(\overline{n})$ . Therefore, such a theory $T$ is incomplete.

It is easily shown that every c.e. set is weakly representable in every $\Sigma_{1}$ -sound c.e. extension of $\mathsf{PA}$ because of $\Sigma_{1}$ -soundness and $\Sigma_{1}$ -completeness. Furthermore, Ehrenfeucht and Feferman [3] proved the weak representability of c.e. sets in every consistent c.e. extension of $\mathsf{PA}$ (see also Shepherdson [14]).

Theorem 1.1 (Ehrenfeucht and Feferman).

Let $T$ be any consistent c.e. extension of $\mathsf{PA}$ . Then, every c.e. set of natural numbers is weakly representable in $T$ .

Ehrenfeucht and Feferman’s theorem is a metamathematical result, but is formalizable and also provable in $\mathsf{PA}$ . This fact is called the FGH theorem (see Smoryński [15, p.366], Visser [17, Theorem 4.1], [18, Section 3] and Lindström [11, Exercise 2.26 (a)]).

Theorem 1.2 (The FGH theorem).

Let $T$ be any consistent c.e. extension of $\mathsf{PA}$ . Then, for any $\Sigma_{1}$ sentence $\sigma$ , there exists a sentence $\varphi$ such that

\mathsf{PA}+\mathrm{Con}_{T}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner).

Here $\mathrm{Pr}_{T}(x)$ is a natural $\Sigma_{1}$ provability predicate of $T$ which expresses the provability of $T$ , and $\mathrm{Con}_{T}$ is the $\Pi_{1}$ sentence $\neg\mathrm{Pr}_{T}(\ulcorner 0=1\urcorner)$ expressing the consistency of $T$ . “FGH” stands for Friedman, Goldfarb and Harrington. Harrington and Friedman pointed out that $\varphi$ in the statement is found as $\Pi_{1}$ and $\Sigma_{1}$ , respectively. For a history of the FGH theorem, see Visser [18]. The FGH theorem has been used in the literature (for example, in papers by the author, it appears in [8, 10]).

A version of the FGH theorem with a parameter is also proved. That is, by modifying the usual proof of the FGH theorem, it is proved that for any $\Sigma_{1}$ formula $\sigma(v)$ with the only free variable $v$ , there exists a formula $\varphi(v)$ such that $\mathsf{PA}+\mathrm{Con}_{T}$ proves $\forall v\,\bigl{(}\sigma(v)\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\varphi(\dot{v})\urcorner)\bigr{)}$ . Here $\ulcorner\varphi(\dot{v})\urcorner$ is a primitive recursive term corresponding to a primitive recursive function calculating the Gödel number of $\varphi(\overline{n})$ from $n$ . If $T$ is consistent, then the theory $\mathsf{PA}+\mathrm{Con}_{T}$ is sound, and hence the weak representability of c.e. sets in $T$ follows from this parameterized version of the FGH theorem.

In the present paper, we analyze the FGH theorem from two perspectives. The first perspective is the “form” of the sentence $\varphi$ in the statement of the FGH theorem. Let $\mathrm{True}_{\Sigma_{1}}(v)$ be a partial truth definition for $\Sigma_{1}$ sentences, that is, $\mathrm{True}_{\Sigma_{1}}(v)$ is a $\Sigma_{1}$ formula such that for any $\Sigma_{1}$ sentence $\sigma$ , $\mathsf{PA}$ proves $\sigma\leftrightarrow\mathrm{True}_{\Sigma_{1}}(\ulcorner\sigma\urcorner)$ (cf. Lindström [11, Fact 10]). By the parameterized version of the FGH theorem, there exists a formula $\xi(v)$ such that $\mathsf{PA}+\mathrm{Con}_{T}\vdash\forall v\,\bigl{(}\mathrm{True}_{\Sigma_{1}}(v)\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\xi(\dot{v})\urcorner)\bigr{)}$ . Then, for any $\Sigma_{1}$ sentence $\sigma$ , $\mathsf{PA}+\mathrm{Con}_{T}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\xi(\ulcorner\sigma\urcorner)\urcorner)$ . Therefore, $\varphi$ in the FGH theorem can be taken in the form $\xi(\cdot)$ uniformly regardless of $\sigma$ .

From the above observation, we consider the following question: What form of the sentence $\varphi$ in the FGH theorem can we find? In Section 2, we investigate this question in the framework of classical propositional logic. Specifically, we study the following rephrased question: What is a propositional formula $A$ such that $\varphi$ in the FGH theorem can be taken uniformly in the form $A$ regardless of $\sigma$ ? In Section 3, we investigate this rephrased question in the framework of modal propositional logic. However, unlike the case of classical propositional logic, the formula $A$ may contain the modal operator $\Box$ . Therefore, the interpretation of $\Box$ in arithmetic should be clearly defined. As is usually done in the study of provability logic, in the present paper, $\Box$ is interpreted by $\mathrm{Pr}_{T}(x)$ . Then, our proofs of theorems in Section 3 are modifications of that of Solovay’s arithmetical completeness theorem [16] which is one of the most remarkable theorems in the research of provability logic.

The second perspective is the choice of provability predicates. Joosten [7] generalized the FGH theorem by proving similar statements concerning several nonstandard provability predicates such as a formula expressing the provability in $T$ together with all true $\Sigma_{n+2}$ sentences. In the last section, we study some variations of the FGH theorem with respect to Rosser provability predicates.

Sections 2, 3, and 4 can be read independently. We close the introduction with common preparations for reading these sections. Let $\mathcal{L}_{A}$ denote the language of first-order arithmetic containing the symbols $0,S,+,\times,\leq$ . We do not specify what exactly $\mathcal{L}_{A}$ is, but it may be assumed to have as many function symbols for primitive recursive functions as necessary. Throughout the present paper, we fix a consistent c.e. extension $T$ of Peano Arithmetic $\mathsf{PA}$ in the language $\mathcal{L}_{A}$ . Let $\omega$ denote the set of all natural numbers. For each $n\in\omega$ , let $\overline{n}$ denote the numeral $S(S(\cdots S(0)\cdots))$ ( $n$ times applications of $S$ ) for $n$ . We fix a primitive recursive formula $\mathrm{Proof}_{T}(x,y)$ naturally expressing that “ $y$ is a $T$ -proof of $x$ ”. Our $\Sigma_{1}$ provability predicate $\mathrm{Pr}_{T}(x)$ of $T$ is defined by $\exists y\,\mathrm{Proof}_{T}(x,y)$ , saying that “ $x$ is $T$ -provable”. Then, we may assume that the provability predicate $\mathrm{Pr}_{T}(x)$ satisfies the following clauses (see Boolos [2]):

•

If $T\vdash\varphi$ , then $\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)$ ,
•

$\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner\varphi\to\psi\urcorner)\to\bigl{(}\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\to\mathrm{Pr}_{T}(\ulcorner\psi\urcorner)\bigr{)}$ ,
•

If $\varphi$ is a $\Sigma_{1}$ sentence, then $\mathsf{PA}\vdash\varphi\to\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)$ .

We may also assume that $\mathsf{PA}$ verifies that every theorem of $T$ has infinitely many proofs, that is, $\mathsf{PA}\vdash\forall x\forall y\,\bigl{(}\mathrm{Proof}_{T}(x,y)\to\exists z\,{>}\,y\,\mathrm{Proof}_{T}(x,z)\bigr{)}$ .

We introduce witness comparison notation (cf. Lindström [11, Lemma 1.3]).

Definition 1.3 (Witness comparison notation).

Suppose that $\mathcal{L}_{A}$ -formulas $\varphi$ and $\psi$ are of the forms $\exists x\,\varphi^{\prime}(x)$ and $\exists y\,\psi^{\prime}(y)$ , respectively.

•

$\varphi\preccurlyeq\psi$ is an abbreviation for $\exists x\,\bigl{(}\varphi^{\prime}(x)\land\forall y\,{<}\,x\,\neg\psi^{\prime}(y)\bigr{)}$ .
•

$\varphi\prec\psi$ is an abbreviation for $\exists x\,\bigl{(}\varphi^{\prime}(x)\land\forall y\,{\leq}\,x\,\neg\psi^{\prime}(y)\bigr{)}$ .

It is easily verified that $\mathsf{PA}$ proves the formulas $\neg(\varphi\preccurlyeq\psi\land\psi\prec\varphi)$ and $\varphi\lor\psi\to(\varphi\preccurlyeq\psi\lor\psi\prec\varphi)$ .

2 On the form of a sentence in the FGH theorem
– the case of classical propositional logic

In this section, we investigate the following question mentioned in the introduction: What is a propositional formula $A$ such that $\varphi$ in the FGH theorem can be taken uniformly in the form $A$ regardless of $\sigma$ ?

The language of classical propositional logic consists of countably many propositional variables $p_{1},p_{2},\ldots,q_{1},q_{2},\ldots$ , propositional constants $\top,\bot$ , and propositional connectives $\land,\lor,\neg,\to,\leftrightarrow$ . For each propositional formula $A$ , let $\models A$ mean that $A$ is a tautology. We say $A$ is unsatisfiable if $\models\neg A$ . We say that a propositional formula is contingent if it is neither a tautology nor unsatisfiable.

For any propositional formula $A(p_{1},\ldots,p_{n})$ containing only the indicated propositional variables and any $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ , let $A(\varphi_{1},\ldots,\varphi_{n})$ denote the $\mathcal{L}_{A}$ -sentence obtained by simultaneously replacing all the occurrences of $p_{i}$ in $A$ by $\varphi_{i}$ , for each $i\in\{1,\ldots,n\}$ .

We introduce the following sets in order to simplify our descriptions.

Definition 2.1.

For each $\Sigma_{1}$ sentence $\sigma$ , let $\mathrm{FGH}_{T}(\sigma)$ be the set of all $\mathcal{L}_{A}$ -sentences $\varphi$ such that $\mathsf{PA}+\mathrm{Con}_{T}\vdash\sigma\leftrightarrow\Pr_{T}(\ulcorner\varphi\urcorner)$ .

Then, the FGH theorem states that for any $\Sigma_{1}$ sentence $\sigma$ , the set $\mathrm{FGH}_{T}(\sigma)$ is non-empty. We show that the set $\mathrm{FGH}(\sigma)$ is closed under the $T$ -provable equivalence.

Proposition 2.2.

For any $\Sigma_{1}$ sentence $\sigma$ and any $\mathcal{L}_{A}$ -sentences $\varphi$ and $\psi$ , if $\varphi\in\mathrm{FGH}_{T}(\sigma)$ and $T\vdash\varphi\leftrightarrow\psi$ , then $\psi\in\mathrm{FGH}_{T}(\sigma)$ .

Proof.

Suppose $\varphi\in\mathrm{FGH}_{T}(\sigma)$ and $T\vdash\varphi\leftrightarrow\psi$ . Then, the equivalence $\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\psi\urcorner)$ is provable in $\mathsf{PA}$ . Since $\mathsf{PA}+\mathrm{Con}_{T}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)$ , we obtain $\mathsf{PA}+\mathrm{Con}_{T}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\psi\urcorner)$ , and hence $\psi\in\mathrm{FGH}_{T}(\sigma)$ . ❑

First, we prove the following introductory theorem.

Theorem 2.3.

Let $A(p_{1},\ldots,p_{n})$ be any propositional formula with only the indicated propositional variables. Then, the following are equivalent:

1.

$A(p_{1},\ldots,p_{n})$ is contingent.
2.

For any $\Sigma_{1}$ sentence $\sigma$ , there exist $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ such that $A(\varphi_{1},\ldots,\varphi_{n})\in\mathrm{FGH}_{T}(\sigma)$ .

For each formula $A$ , let $A^{0}$ and $A^{1}$ be $\neg A$ and $A$ , respectively. Theorem 2.3 follows from the following lemma.

Lemma 2.4.

Let $A(p_{1},\ldots,p_{n})$ be any propositional formula with only the indicated propositional variables and let $r$ be any propositional variable not contained in $A$ . If $A(p_{1},\ldots,p_{n})$ is contingent, then there exist propositional formulas $B_{1}(r),\ldots,B_{n}(r)$ such that $\models r\leftrightarrow A(B_{1}(r),\ldots,B_{n}(r))$ .

Proof.

Suppose that $A(p_{1},\ldots,p_{n})$ is contingent. Let $f$ and $g$ be mappings from $\{1,\ldots,n\}$ to $\{0,1\}$ such that $\models A(\top^{f(1)},\ldots,\top^{f(n)})$ and $\models\neg A(\top^{g(1)},\ldots,\top^{g(n)})$ . For each $i$ ( $1\leq i\leq n$ ), let $B_{i}(r)$ be the propositional formula $(r\land\top^{f(i)})\lor(\neg r\land\top^{g(i)})$ . Then, $\models r\to(B_{i}(r)\leftrightarrow\top^{f(i)})$ and $\models\neg r\to(B_{i}(r)\leftrightarrow\top^{g(i)})$ hold. Thus, we have

\models r\to\bigl{(}A(B_{1}(r),\ldots,B_{n}(r))\leftrightarrow A(\top^{f(1)},\ldots,\top^{f(n)})\bigr{)}

and

\models\neg r\to\bigl{(}A(B_{1}(r),\ldots,B_{n}(r))\leftrightarrow A(\top^{g(1)},\ldots,\top^{g(n)})\bigr{)}.

Since $\models A(\top^{f(1)},\ldots,\top^{f(n)})$ and $\models\neg A(\top^{g(1)},\ldots,\top^{g(n)})$ , we obtain

\models r\to A(B_{1}(r),\ldots,B_{n}(r))\ \text{and}\ \models\neg r\to\neg A(B_{1}(r),\ldots,B_{n}(r)).

Proof of Theorem 2.3.

$(1\Rightarrow 2)$ : Suppose that $A(p_{1},\ldots,p_{n})$ is contingent and let $\sigma$ be any $\Sigma_{1}$ sentence. Then, by Lemma 2.4, there exist propositional formulas $B_{1}(r),\ldots,B_{n}(r)$ such that

\models r\leftrightarrow A(B_{1}(r),\ldots,B_{n}(r)).

(1)

By the FGH theorem, there exists an $\mathcal{L}_{A}$ -sentence $\varphi\in\mathrm{FGH}_{T}(\sigma)$ . For each $i$ ( $1\leq i\leq n$ ), let $\varphi_{i}$ be the $\mathcal{L}_{A}$ -sentence $B_{i}(\varphi)$ . Then, by the equivalence (1), we obtain

\mathsf{PA}\vdash\varphi\leftrightarrow A(\varphi_{1},\ldots,\varphi_{n}).

By Proposition 2.2, we conclude $A(\varphi_{1},\ldots,\varphi_{n})\in\mathrm{FGH}_{T}(\sigma)$ by Proposition 2.2.

$(2\Rightarrow 1)$ : Suppose that $A(p_{1},\ldots,p_{n})$ is not contingent. Then, for any $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ , either $A(\varphi_{1},\ldots,\varphi_{n})$ or $\neg A(\varphi_{1},\ldots,\varphi_{n})$ is provable in $\mathsf{PA}$ . Let $\sigma$ be any $\Sigma_{1}$ sentence independent of $\mathsf{PA}+\mathrm{Con}_{T}$ . Then, $A(\varphi_{1},\ldots,\varphi_{n})$ is not in $\mathrm{FGH}_{T}(\sigma)$ for all $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ . ❑

As mentioned in the introduction, the FGH theorem and the weak representability theorem are related to each other. In particular, we can also prove the following theorem by a similar proof.

Theorem 2.5.

Let $A(p_{1},\ldots,p_{n})$ be any propositional formula with only the indicated propositional variables. Then, the following are equivalent:

1.

$A(p_{1},\ldots,p_{n})$ is contingent.
2.

For any c.e. set $X$ , there exist $\mathcal{L}_{A}$ -formulas $\varphi_{1}(v),\ldots,\varphi_{n}(v)$ such that $A(\varphi_{1}(v),\ldots,\varphi_{n}(v))$ weakly represents $X$ in $T$ .

Theorem 2.3 will be extended to the framework of modal propositional logic in the next section. In this section, we further improve Theorem 2.3 in the framework of classical propositional logic. For any propositional formula $A(p_{1},\ldots,p_{n},q_{1},\ldots,q_{m})$ with the only indicated propositional variables, let $\mathsf{FGH}_{T}[A;q_{1},\ldots,q_{m}]$ denote the metamathematical statement “for any $\mathcal{L}_{A}$ -sentences $\psi_{1},\ldots,\psi_{m}$ and for any $\Sigma_{1}$ sentence $\sigma$ , there exist $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ such that $A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m})\in\mathrm{FGH}_{T}(\sigma)$ ”, and we provide a necessary and sufficient condition for $\mathsf{FGH}_{T}[A;q_{1},\ldots,q_{m}]$ . From this, we obtain more detailed information about the elements of $\mathrm{FGH}(\sigma)$ and the first incompleteness theorem (see Corollary 2.8).

Let $\mathcal{F}_{m}$ denote the set of all functions $f:\{1,\ldots,m\}\to\{0,1\}$ . We prove the following theorem which is one of main theorems of the present paper.

Theorem 2.6.

For any propositional formula $A(p_{1},\ldots,p_{n},q_{1},\ldots,q_{m})$ , the following are equivalent:

1.

For all $f\in\mathcal{F}_{m}$ , $A(p_{1},\ldots,p_{n},\top^{f(1)},\ldots,\top^{f(m)})$ are contingent.
2.

$\mathsf{FGH}_{T}[A;q_{1},\ldots,q_{m}]$ holds.

Theorem 2.6 also follows from the following lemma that is an improvement of Lemma 2.4. For the sake of simplicity, we sometimes abbreviate the tuples $p_{1},\ldots,p_{n}$ and $q_{1},\ldots,q_{m}$ as $\vec{p}$ and $\vec{q}$ , respectively.

Lemma 2.7.

Let $A(\vec{p},\vec{q})$ be any propositional formula with only the indicated propositional variables and let $r$ be any propositional variable not contained in $A$ . If $A(\vec{p},\top^{f(1)},\ldots,\top^{f(m)})$ is contingent for all $f\in\mathcal{F}_{m}$ , then there exist propositional formulas $B_{1}(r,\vec{q}),\ldots,B_{n}(r,\vec{q})$ such that

\models r\leftrightarrow A(B_{1}(r,\vec{q}),\ldots,B_{n}(r,\vec{q}),\vec{q}).

Proof.

For each $f\in\mathcal{F}_{m}$ , let $Q^{f}(\vec{q})$ denote the formula $q_{1}^{f(1)}\land\cdots\land q_{m}^{f(m)}$ . Notice that for each distinct elements $f,g$ of $\mathcal{F}_{m}$ , $\models\neg\bigl{(}Q^{f}(\vec{q})\land Q^{g}(\vec{q})\bigr{)}$ . Also $\models\bigvee_{f\in\mathcal{F}_{m}}Q^{f}(\vec{q})$ .

Suppose that $A(\vec{p},\top^{f(1)},\ldots,\top^{f(m)})$ is contingent for all $f\in\mathcal{F}_{m}$ . For each $g\in\mathcal{F}_{m}$ , there exist propositional formulas $C_{1}^{g}(r),\ldots,C_{n}^{g}(r)$ such that

\models r\leftrightarrow A(C_{1}^{g}(r),\ldots,C_{n}^{g}(r),\top^{g(1)},\ldots,\top^{g(m)})

(2)

by Lemma 2.4. For each $i$ ( $1\leq i\leq n$ ), let $B_{i}(r,\vec{q})$ be the propositional formla $\bigvee_{f\in\mathcal{F}_{m}}\bigl{(}C_{i}^{f}(r)\land Q^{f}(\vec{q})\bigr{)}$ . Then, $\models Q^{g}(\vec{q})\to\bigl{(}B_{i}(r,\vec{q})\leftrightarrow C_{i}^{g}(r)\bigr{)}$ and $\models Q^{g}(\vec{q})\to(q_{i}\leftrightarrow\top^{g(i)})$ . By the equivalence (2), we obtain

\models Q^{g}(\vec{q})\to\bigl{(}r\leftrightarrow A(B_{1}(r,\vec{q}),\ldots,B_{n}(r,\vec{q}),\vec{q})\bigr{)}.

Then,

\models\bigvee_{f\in\mathcal{F}_{m}}Q^{f}(\vec{q})\to\bigl{(}r\leftrightarrow A(B_{1}(r,\vec{q}),\ldots,B_{n}(r,\vec{q}),\vec{q})\bigr{)}.

Since $\models\bigvee_{f\in\mathcal{F}_{m}}Q^{f}(\vec{q})$ , we conclude

\models r\leftrightarrow A(B_{1}(r,\vec{q}),\ldots,B_{n}(r,\vec{q}),\vec{q}).

Proof of Theorem 2.6.

$(1\Rightarrow 2)$ : Suppose that $A(\vec{p},\top^{f(1)},\ldots,\top^{f(m)})$ is contingent for all $f\in\mathcal{F}_{m}$ . Let $\psi_{1},\ldots,\psi_{m}$ be any $\mathcal{L}_{A}$ -sentences and let $\sigma$ be any $\Sigma_{1}$ sentence. By Lemma 2.7, there exist propositional formulas $B_{1}(r,\vec{q}),\ldots,B_{n}(r,\vec{q})$ such that

\models r\leftrightarrow A(B_{1}(r,\vec{q}),\ldots,B_{n}(r,\vec{q}),\vec{q}).

(2)

\mathsf{PA}\vdash\varphi\leftrightarrow A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m}).

By Proposition 2.2, we have $A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m})\in\mathrm{FGH}_{T}(\sigma)$ . Therefore, we conclude that $\mathsf{FGH}_{T}[A;\vec{q}]$ holds.

$(2\Rightarrow 1)$ : Suppose that $A(p_{1},\ldots,p_{n},\top^{f(1)},\ldots,\top^{f(m)})$ is either a tautology or unsatisfiable for some $f\in\mathcal{F}_{m}$ . For $i\in\{1,\ldots,m\}$ , let $\psi_{i}$ be the $\mathcal{L}_{A}$ -sentence $0=0^{f(i)}$ . Then, for any $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ , the $\mathcal{L}_{A}$ -sentence $A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m})$ is either provable or refutable in $\mathsf{PA}$ . Let $\sigma$ be any $\Sigma_{1}$ sentence independent of $\mathsf{PA}+\mathrm{Con}_{T}$ . Then, $A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m})\notin\mathrm{FGH}_{T}(\sigma)$ . Therefore $\mathsf{FGH}_{T}[A;q_{1},\ldots,q_{m}]$ does not hold. ❑

For example, let $A(p,q)$ be the propositional formula $p\leftrightarrow q$ . Since both $p\leftrightarrow\top$ and $p\leftrightarrow\bot$ are contingent, $\mathsf{FGH}_{T}[A;q]$ holds by Theorem 2.6. That is, for any $\mathcal{L}_{A}$ -sentence $\psi$ and any $\Sigma_{1}$ sentence $\sigma$ , there exists an $\mathcal{L}_{A}$ -sentence $\varphi$ such that $\varphi\leftrightarrow\psi\in\mathrm{FGH}_{T}(\sigma)$ . Another interesting corollary to Theorem 2.6 is the following version of the first incompleteness theorem.

Corollary 2.8.

Let $A(p_{1},\ldots,p_{n},q_{1},\ldots,q_{m})$ be any propositional formula. If $A(p_{1},\ldots,p_{n},\top^{f(1)},\ldots,\top^{f(m)})$ are contingent for all $f\in\mathcal{F}_{m}$ , then for any $\mathcal{L}_{A}$ -sentences $\psi_{1},\ldots,\psi_{m}$ , there exist $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ such that $A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m})$ is independent of $T$ .

Proof.

Let $\sigma$ be a $\Sigma_{1}$ sentence independent of $\mathsf{PA}+\mathrm{Con}_{T}$ and $\psi_{1},\ldots,\psi_{m}$ be any $\mathcal{L}_{A}$ -sentences. By Theorem 2.6, there exist $\mathcal{L}_{A}$ -sentences $\varphi_{1},\ldots,\varphi_{n}$ such that

\mathsf{PA}+\mathrm{Con}_{T}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}(\ulcorner A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m})\urcorner).

Then, it is easy to show that $A(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\psi_{m})$ is independent of $T$ .

❑

Notice that we can also prove the parameterized version and the weak representability version of Theorem 2.6.

3 On the form of a sentence in the FGH theorem
– the case of modal propositional logic

In this section, we extend Theorem 2.3 to the framework of modal propositional logic. This section consists of three subsections. First, we give some preparations which are needed for our arguments. In the second subsection, we prove our modal version of Theorem 2.3. Finally, we also investigate our modal version for $\mathcal{L}_{A}$ -theories with finite heights.

Here we define the height of theories. The sequence $\langle\mathrm{Con}_{T}^{n}\rangle_{n\in\omega}$ of $\mathcal{L}_{A}$ -sentences is recursively defined as follows: $\mathrm{Con}_{T}^{0}$ is $0=0$ ; and $\mathrm{Con}_{T}^{n+1}$ is $\neg\mathrm{Pr}_{T}(\ulcorner\neg\mathrm{Con}_{T}^{n}\urcorner)$ . Notice that $\mathrm{Con}_{T}^{1}$ is $\mathsf{PA}$ -provably equivalent to $\mathrm{Con}_{T}$ . If there exists a natural number $k\geq 1$ such that $T\vdash\neg\mathrm{Con}_{T}^{k}$ , then the least such a number $k$ is called the height of $T$ . If not, we say that the height of $T$ is $\infty$ .

3.1 Preparations

The language of modal propositional logic is that of classical propositional logic equipped with the unary modal operation $\Box$ . For each modal formula $A$ , let $\mathsf{Sub}(A)$ be the set of all subformulas of $A$ . Let $\mathfrak{c}(A)$ be the cardinality of the set $\{B\in\mathsf{Sub}(A)\mid B$ is of the form $\Box C\}$ . The modal formula $\Box^{n}A$ is recursively defined as follows: $\Box^{0}A$ is $A$ ; and $\Box^{n+1}A$ is $\Box\Box^{n}A$ . The formula $\Diamond^{n}A$ is an abbreviation for $\neg\Box^{n}\neg A$ .

The base logic of our investigations in this section is the Gödel–Löb logic $\mathbf{GL}$ which is known as the logic of provability. The axioms of $\mathbf{GL}$ are as follows:

1.

All propositional tautologies in the language of modal propositional logic,
2.

$\Box(p\to q)\to(\Box p\to\Box q)$ ,
3.

$\Box(\Box p\to p)\to\Box p$ .

The inference rules of $\mathbf{GL}$ are modus ponens, necessitation, and uniform substitution.

A $\mathbf{GL}$ -frame is a tuple $\langle W,\sqsubset,r\rangle$ where $W$ is a nonempty finite set, $\sqsubset$ is a transitive irreflexive binary relation on $W$ and $r$ is an element of $W$ with $r\sqsubset x$ for all $x\in W\setminus\{r\}$ . Such an element $r$ is called the root of the frame. A $\mathbf{GL}$ -model is a tuple $M=\langle W,\sqsubset,r,\Vdash\rangle$ where $\langle W,\sqsubset,r\rangle$ is a $\mathbf{GL}$ -frame, and $\Vdash$ is a binary relation between $W$ and the set of all modal formulas satisfying the usual conditions for satisfaction and the following condition: $a\Vdash\Box A$ if and only if for all $b\in W$ , $b\Vdash A$ if $a\sqsubset b$ . It is known that $\mathbf{GL}$ is sound and complete with respect to the class of all $\mathbf{GL}$ -frames (cf. Segerberg [12]). Moreover, the proof of the Kripke completeness of $\mathbf{GL}$ given in the textbook [2] by Boolos shows that the following theorem holds.

Theorem 3.1.

For any modal formula $A$ , if $\mathbf{GL}\nvdash A$ , then there exists a $\mathbf{GL}$ -model $\langle W,\sqsubset,r,\Vdash\rangle$ such that $r\Vdash\Box^{\mathfrak{c}(A)+1}\bot$ and $r\nVdash A$ .

For each set $\Gamma$ of modal formulas, let $\mathbf{GL}+\Gamma$ denote the logic whose axioms are all theorems of $\mathbf{GL}$ and all elements of $\Gamma$ , and whose inference rules are modus ponens and uniform substitution. We identify each axiomatic system of modal propositional logic with the set of all its theorems. We introduce the following two extensions of $\mathbf{GL}$ which are studied in the context of the classification of propositional provability logics (cf. Artemov and Beklemishev [1]).

•

$\mathbf{GL}_{\omega}:=\mathbf{GL}+\{\Diamond^{n}\top\mid n\in\omega\}$ .
•

$\mathbf{S}:=\mathbf{GL}+\{\Box p\to p\}$ .

Notice $\mathbf{GL}\subseteq\mathbf{GL}_{\omega}\subseteq\mathbf{S}$ . To connect these logics with arithmetic, we introduce the notion of arithmetical interpretation.

Definition 3.2 (Arithmetical interpretations).

A mapping from the set of all propositional variables to a set of $\mathcal{L}_{A}$ -sentences is called an arithmetical interpretation. Each arithmetical interpretation $f$ is uniquely extended to the mapping $f_{T}$ from the set of all modal formulas to a set of $\mathcal{L}_{A}$ -sentences by the following clauses:

1.

$f_{T}(\bot)$ is $0=1$ ,
2.

$f_{T}(\neg A)$ is $\neg f_{T}(A)$ ,
3.

$f_{T}(A\circ B)$ is $f_{T}(A)\circ f_{T}(B)$ for $\circ\in\{\land,\lor,\to,\leftrightarrow\}$ ,
4.

$f_{T}(\Box A)$ is $\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ .

The logics $\mathbf{GL}$ , $\mathbf{GL}_{\omega}$ and $\mathbf{S}$ are sound with respect to arithmetical interpretations. Let $\mathbb{N}$ denote the standard model of arithmetic.

Fact 3.3 (Arithmetical soundness (cf. Artemov and Beklemishev [1])).

Let $A$ be any modal formula.

1.

If $\mathbf{GL}\vdash A$ , then $\mathsf{PA}\vdash f_{T}(A)$ for any arithmetical interpretation $f$ .
2.

If the height of $T$ is $\infty$ and $\mathbf{GL}_{\omega}\vdash A$ , then $\mathbb{N}\models f_{T}(A)$ for any arithmetical interpretation $f$ .
3.

If $T$ is sound and $\mathbf{S}\vdash A$ , then $\mathbb{N}\models f_{T}(A)$ for any arithmetical interpretation $f$ .

We show some interrelationships between these logics. For each modal formula $A$ , let $\mathrm{Rfn}(A)$ denote the set $\{\Box B\to B\mid\Box B\in\mathsf{Sub}(A)\}$ . Notice that the cardinality of the set $\mathrm{Rfn}(A)$ is exactly $\mathfrak{c}(A)$ .

Fact 3.4 (Solovay [16]).

For any modal formula $A$ , the following are equivalent:

1.

$\mathbf{S}\vdash A$ .
2.

$\mathbf{GL}\vdash\bigwedge\mathrm{Rfn}(A)\to A$ .

The following fact is a kind of folklore which is proved through arithmetical interpretations.

Fact 3.5.

For any modal formula $A$ , the following are equivalent:

1.

$\mathbf{GL}\vdash A$ .
2.

$\mathbf{GL}_{\omega}\vdash\Box A$ .
3.

$\mathbf{S}\vdash\Box A$ .

Lemma 3.6.

For any modal formula $A$ , the following are equivalent:

1.

$\mathbf{GL}\vdash\bigwedge\mathrm{Rfn}(\Box A)\to\neg\Box A$ .
2.

$\mathbf{GL}\vdash\Diamond^{\mathfrak{c}(A)+1}\top\to\neg\Box A$ .
3.

$\mathbf{GL}_{\omega}\vdash\neg\Box A$ .
4.

$\mathbf{S}\vdash\neg\Box A$ .

Proof.

$(1\Rightarrow 2)$ : Suppose $\mathbf{GL}\vdash\bigwedge\mathrm{Rfn}(\Box A)\to\neg\Box A$ . It is known that $\mathbf{GL}$ proves $\Diamond^{\mathfrak{c}(\Box A)}\top\to\bigwedge\mathrm{Rfn}(\Box A)\lor\Diamond\bigwedge\mathrm{Rfn}(\Box A)$ (cf. [1, Lemma 26]). Then, $\mathbf{GL}\vdash\Diamond^{\mathfrak{c}(\Box A)}\top\to\neg\Box A\lor\Diamond\neg\Box A$ . Since $\mathbf{GL}\vdash\Diamond\neg\Box A\to\neg\Box A$ , we have $\mathbf{GL}\vdash\Diamond^{\mathfrak{c}(\Box A)}\top\to\neg\Box A$ . Hence, $\mathbf{GL}\vdash\Diamond^{\mathfrak{c}(A)+1}\top\to\neg\Box A$ because $\mathfrak{c}(\Box A)=\mathfrak{c}(A)+1$ .

$(2\Rightarrow 3)$ and $(3\Rightarrow 4)$ : Obvious.

$(4\Rightarrow 1)$ : By Fact 3.4 and $\mathrm{Rfn}(\Box A)=\mathrm{Rfn}(\neg\Box A)$ . ❑

The conditions “ $\mathbf{GL}\vdash A$ ” and “ $\mathbf{GL}_{\omega}\vdash\neg\Box A$ ” are also characterized by provability in other extensions of $\mathbf{GL}$ .

Definition 3.7.

Let $F_{s}$ be the modal formula $\Box^{s+1}\bot\to\Box^{s}\bot$ .

Lemma 3.8.

For any modal formula $A$ and any natural number $s$ with $s>\mathfrak{c}(A)$ , the following are equivalent:

1.

$\mathbf{GL}\vdash A$ .
2.

$\mathbf{GL}+\{\neg F_{s}\}\vdash\Box A$ .

Proof.

$(1\Rightarrow 2)$ : Obvious.

$(2\Rightarrow 1)$ : If $\mathbf{GL}\nvdash A$ , then there exists a $\mathbf{GL}$ -model $\langle W,\sqsubset,r,\Vdash\rangle$ such that $r\Vdash\Box^{\mathfrak{c}(A)+1}\bot\land\neg A$ by Theorem 3.1. Let $\langle W^{\prime},\sqsubset^{\prime},r^{\prime},\Vdash^{\prime}\rangle$ be a $\mathbf{GL}$ -model obtained from $\langle W,\sqsubset,r,\Vdash\rangle$ by adding a chain of new elements below $r$ so that $r^{\prime}\Vdash^{\prime}\Box^{s+1}\bot\land\Diamond^{s}\top$ . Such a model exists because $s>\mathfrak{c}(A)$ . Since $r^{\prime}\Vdash^{\prime}\neg\Box A$ , we obtain $\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ . ❑

Lemma 3.9.

For any modal formula $A$ and any natural number $s$ with $s>\mathfrak{c}(A)$ , the following are equivalent:

1.

$\mathbf{GL}_{\omega}\vdash\neg\Box A$ .
2.

$\mathbf{GL}+\{\neg F_{s}\}\vdash\neg\Box A$ .

Proof.

$(1\Rightarrow 2)$ : If $\mathbf{GL}_{\omega}\vdash\neg\Box A$ , then by Lemma 3.6, $\Diamond^{\mathfrak{c}(A)+1}\top\to\neg\Box A$ is proved in $\mathbf{GL}$ , and thus $\mathbf{GL}+\{\neg F_{s}\}\vdash\neg\Box A$ because $s\geq\mathfrak{c}(A)+1$ .

$(2\Rightarrow 1)$ : Suppose $\mathbf{GL}+\{\neg F_{s}\}\vdash\neg\Box A$ , then $\mathbf{GL}\vdash\Box A\to F_{s}$ , that is, $\mathbf{GL}\vdash\Box A\to(\Box^{s+1}\bot\to\Box^{s}\bot)$ . Then, $\mathbf{GL}\vdash\Box\Box A\to\Box(\Box^{s+1}\bot\to\Box^{s}\bot)$ . By Löb’s principle, we get $\mathbf{GL}\vdash\Box\Box A\to\Box^{s+1}\bot$ . Then, $\mathbf{GL}\vdash\Box A\to\Box^{s+1}\bot$ , and hence $\mathbf{GL}\vdash\Diamond^{s+1}\top\to\neg\Box A$ . We obtain $\mathbf{GL}_{\omega}\vdash\neg\Box A$ . ❑

Here we introduce a notion that will be central in this section.

Definition 3.10.

A modal formula $A$ is said to be nontrifling if $\mathbf{GL}_{\omega}\nvdash\Box\Box A\to\Box A$ .

Then, this notion is characterized in many ways as follows.

Proposition 3.11.

For any modal formula $A$ and any number $s>\mathfrak{c}(A)$ , the following are equivalent:

1.

$A$ is nontrifling.
2.

$\mathbf{GL}_{\omega}\nvdash\Box A$ and $\mathbf{GL}_{\omega}\nvdash\neg\Box A$ .
3.

$\mathbf{S}\nvdash\Box A$ and $\mathbf{S}\nvdash\neg\Box A$ .
4.

$\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ and $\mathbf{GL}+\{\neg F_{s}\}\nvdash\neg\Box A$ .
5.

$\mathbf{GL}\nvdash A$ and $\mathbf{GL}\nvdash\bigwedge\mathrm{Rfn}(\Box A)\to\neg\Box A$ .

Proof.

$(1\Rightarrow 2)$ : We prove the contrapositive. If $\mathbf{GL}_{\omega}\vdash\Box A$ , then $\mathbf{GL}_{\omega}\vdash\Box\Box A\to\Box A$ is obvious. Suppose $\mathbf{GL}_{\omega}\vdash\neg\Box A$ . By Lemma 3.6, we have $\mathbf{GL}\vdash\Diamond^{\mathfrak{c}(A)+1}\top\to\neg\Box A$ . Then, $\mathbf{GL}\vdash\Diamond^{\mathfrak{c}(A)+2}\top\to\neg\Box\Box A$ . We obtain $\mathbf{GL}_{\omega}\vdash\neg\Box\Box A$ , and hence $\mathbf{GL}_{\omega}\vdash\Box\Box A\to\Box A$ .

$(2\Leftrightarrow 3\Leftrightarrow 4\Leftrightarrow 5)$ : By Fact 3.5 and Lemmas 3.6, 3.8, and 3.9.

$(5\Rightarrow 1)$ : Suppose $\mathbf{GL}\nvdash A$ and $\mathbf{GL}\nvdash\bigwedge\mathrm{Rfn}(\Box A)\to\neg\Box A$ . Then, $\mathbf{GL}\nvdash\Box A\to A$ . By Theorem 3.1, there exist $\mathbf{GL}$ -models $M=\langle W,\sqsubset,r,\Vdash\rangle$ and $M_{0}=\langle W_{0},\sqsubset_{0},r_{0},\Vdash_{0}\rangle$ such that $r\Vdash\Box A\land\neg A$ and $r_{0}\Vdash_{0}\mathrm{Rfn}(\Box A)\land\Box A$ . We merge these two models $M$ and $M_{0}$ into one model $M^{*}$ , which is illustrated in Fig 1. We give the precise definition of the $\mathbf{GL}$ -model $M^{*}=\langle W^{*},\sqsubset^{*},r^{*},\Vdash^{*}\rangle$ as follows:

•

$W^{*}=W\cup W_{0}\cup\{r_{i}\mid i\geq 1\}\cup\{r^{*}\}$ ,
•

$\sqsubset^{*}$ is the transitive closure of

$\sqsubset\cup\sqsubset_{0}\cup\{(r_{i},r_{j})\mid i>j\}\cup\{(r^{*},r_{i})\mid i\in\omega\}\cup\{(r^{*},r)\},$
•

for $a\in W$ , $a\Vdash^{*}p$ if and only if $a\Vdash p$ ,
for $a\in W_{0}$ , $a\Vdash^{*}p$ if and only if $a\Vdash_{0}p$ , and
for $a\in\{r_{i}\mid i\geq 1\}\cup\{r^{*}\}$ , $a\Vdash^{*}p$ if and only if $r_{0}\Vdash_{0}p$ .

Figure 1: The

\mathbf{GL}

-model

M^{*}

It is easy to show that $r\Vdash^{*}\Box A\land\neg A$ and $r_{0}\Vdash^{*}\mathrm{Rfn}(\Box A)\land\Box A$ . Since $r^{*}\Vdash^{*}\Diamond^{n}\top$ for all $n\in\omega$ , every theorem of $\mathbf{GL}_{\omega}$ is true in $r^{*}$ . Thus, it suffices to show that $r^{*}\nVdash^{*}\Box\Box A\to\Box A$ . For this purpose, we prove the following lemma.

Lemma 3.12.

For any $i\in\omega$ and any subformula $B$ of $\Box A$ , $r_{i}\Vdash^{*}B$ if and only if $r_{0}\Vdash^{*}B$ .

Proof.

We prove the lemma by induction on $i$ . For $i=0$ , the lemma is trivial. Suppose that the lemma holds for $i$ , and we prove the case of $i+1$ by induction on the construction of the subformula $B$ of $\Box A$ . The case that $B$ is a propositional variable is obvious from the definition of $\Vdash^{*}$ . The cases for propositional connectives are easily proved by the induction hypothesis. We only give a proof of the case that $B$ is of the form $\Box C$ , that is, we prove $r_{i+1}\Vdash^{*}\Box C$ if and only if $r_{0}\Vdash^{*}\Box C$ .

$(\Rightarrow)$ : Suppose $r_{i+1}\Vdash^{*}\Box C$ , then $r_{i+1}\Vdash^{*}\Box\Box C$ because $\sqsubset^{*}$ is transitive. Since $r_{i+1}\sqsubset^{*}r_{0}$ , we obtain $r_{0}\Vdash^{*}\Box C$ .

$(\Leftarrow)$ : Suppose $r_{i+1}\nVdash^{*}\Box C$ . Then, $a\nVdash^{*}C$ for some $a\in W^{*}$ with $r_{i+1}\sqsubset^{*}a$ . We distinguish the following three cases:

•

$r_{0}\sqsubset^{*}a$ .
Then, $r_{0}\nVdash^{*}\Box C$ trivially holds.
•

$a=r_{0}$ .
We have $r_{0}\Vdash^{*}\Box C\to C$ because $r_{0}\Vdash^{*}\mathrm{Rfn}(\Box A)$ . Thus, $r_{0}\nVdash^{*}\Box C$ .
•

$a=r_{j}$ for $0<j<i+1$ .
By the induction hypothesis for $j$ , we have $r_{0}\nVdash^{*}C$ . Then, $r_{j}\nVdash^{*}\Box C$ . By the induction hypothesis for $j$ again, we obtain $r_{0}\nVdash^{*}\Box C$ . ❑

We are ready to prove $r^{*}\nVdash^{*}\Box\Box A\to\Box A$ . Let $a\in W^{*}$ be any element such that $r^{*}\sqsubset^{*}a$ . If $a\in W$ , then $a\Vdash^{*}\Box A$ because $r\Vdash^{*}\Box A$ . If $a\in W_{0}$ , then $a\Vdash^{*}\Box A$ because $r_{0}\Vdash^{*}\Box A$ . If $a\in\{r_{i}\mid i\geq 1\}$ , then $a\Vdash^{*}\Box A$ by Lemma 3.12. Therefore, we obtain $r^{*}\Vdash^{*}\Box\Box A$ . Since $r^{*}\sqsubset^{*}r$ and $r\nVdash^{*}A$ , we get $r^{*}\nVdash^{*}\Box A$ . Thus, we conclude $r^{*}\nVdash^{*}\Box\Box A\to\Box A$ , and hence $A$ is nontrifling. ❑

If a formula $A$ does not contain $\Box$ , then the following proposition holds.

Proposition 3.13.

A propositional formula $A$ is contingent if and only if $A$ is nontrifling.

Proof.

$(\Rightarrow)$ : Let $\mathsf{v}_{0}$ be a truth assignment in classical propositional logic such that $\mathsf{v}_{0}(A)$ is false. Let $\langle W_{0},\sqsubset_{0},r_{0},\Vdash_{0}\rangle$ be a $\mathbf{GL}$ -model satisfying $W_{0}=\{r_{0}\}$ , $\sqsubset_{0}=\varnothing$ , and $r_{0}\Vdash_{0}p$ if and only if $\mathsf{v}_{0}(p)$ is true. Then $r_{0}\nVdash_{0}A$ , and hence $\mathbf{GL}\nvdash A$ .

Let $\mathsf{v}_{1}$ be a truth assignment such that $\mathsf{v}_{1}(A)$ is true. Let $\langle W_{1},\sqsubset_{1},r_{1},\Vdash_{1}\rangle$ be a $\mathbf{GL}$ -model satisfying $W_{1}=\{r_{1},a\}$ , $r_{1}\sqsubset_{1}a$ , and for each $w\in W_{1}$ , $w\Vdash_{1}p$ if and only if $\mathsf{v}_{1}(p)$ is true. Then, $r_{1}\Vdash_{1}\Diamond\top\land\Box A$ . Since $\mathfrak{c}(A)=0$ , we have $\mathbf{GL}\nvdash\Diamond^{\mathfrak{c}(A)+1}\top\to\neg\Box A$ . By Lemma 3.6, $\mathbf{GL}_{\omega}\nvdash\neg\Box A$ . By Proposition 3.11, $A$ is nontrifling.

$(\Leftarrow)$ : If $A$ is a tautology, then $\mathbf{GL}\vdash A$ . If $A$ is unsatisfiable, then $\mathbf{GL}\vdash\neg A$ , and $\mathbf{GL}\vdash\Diamond\top\to\neg\Box A$ . Hence, $\mathbf{GL}_{\omega}\vdash\neg\Box A$ . In either case, $A$ is not nontrifling by Proposition 3.11. ❑

3.2 A modal version of the FGH theorem

We are ready to prove an extension of Theorem 2.3.

Theorem 3.14.

For any modal formula $A$ , if $A$ is nontrifling, then for any $\Sigma_{1}$ sentence $\sigma$ , there exists an arithmetical interpretation $f$ such that

(a): $\mathsf{PA}\vdash\sigma\to f_{T}(\Box A)$ , and
(b): $\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash f_{T}(\Box A)\to\sigma$ .

Proof.

Suppose that $A$ is nontrifling and let $\sigma$ be any $\Sigma_{1}$ sentence. We may assume that $\sigma$ is of the form $\exists x\,\delta(x)$ for some $\Delta_{0}$ formula $\delta(x)$ . By Proposition 3.11, we have $\mathbf{GL}\nvdash A$ and $\mathbf{GL}\nvdash\bigwedge\mathrm{Rfn}(\Box A)\to\neg\Box A$ . By Theorem 3.1, there exist $\mathbf{GL}$ -models $M_{0}=\langle W_{0},\sqsubset_{0},r_{0},\Vdash_{0}\rangle$ and $M_{1}=\langle W_{1},\sqsubset_{1},r_{1},\Vdash_{1}\rangle$ such that $r_{0}\Vdash_{0}\Box^{\mathfrak{c}(A)+1}\bot\land\neg A$ and $r_{1}\Vdash_{1}\bigwedge\mathrm{Rfn}(\Box A)\land\Box A$ .

Let $\langle\cdot,\cdot\rangle$ be a natural injective mapping from $\omega^{2}$ to $\omega$ . Also let $\pi_{0}$ and $\pi_{1}$ be natural mappings such that $\pi_{0}(\langle i,j\rangle)=i$ and $\pi_{1}(\langle i,j\rangle)=j$ . We may assume that $0$ is not in the range of the mapping $\langle\cdot,\cdot\rangle$ and is not in the domain of the mappings $\pi_{0}$ and $\pi_{1}$ . Let $n_{0}$ and $n_{1}$ be the cardinalities of $W_{0}$ and $W_{1}$ , respectively. Without loss of generality, we may assume

•

$W_{0}=\{\langle 0,1\rangle,\langle 0,2\rangle,\ldots,\langle 0,n_{0}\rangle\}$ , $r_{0}=\langle 0,1\rangle$ , and
•

$W_{1}=\{\langle 1,1\rangle,\langle 1,2\rangle,\ldots,\langle 1,n_{1}\rangle\}$ , $r_{1}=\langle 1,1\rangle$ .

We merge the two models $M_{0}$ and $M_{1}$ into one $\mathbf{GL}$ -model $M$ , which is visualized in Figure 2. The definition of $M=\langle W^{\prime},\sqsubset^{\prime},0,\Vdash^{\prime}\rangle$ is as follows:

•

$W^{\prime}=W_{0}\cup W_{1}\cup\{0,\langle 0,0\rangle,\langle 1,0\rangle\}$ ,
•

$\sqsubset^{\prime}=\sqsubset_{0}\cup\sqsubset_{1}\cup\{(0,a)\mid a\in W^{\prime}\setminus\{0\}\}\cup\{(\langle i,0\rangle,a)\mid i\in\{0,1\},a\in W_{i}\}$ ,
•

For $\langle i,j\rangle\in W_{i}$ , $\langle i,j\rangle\Vdash^{\prime}p$ if and only if $\langle i,j\rangle\Vdash_{i}p$ .
Also $0\Vdash^{\prime}p$ , and $\langle i,0\rangle\Vdash^{\prime}p$ if and only if $\langle i,1\rangle\Vdash_{i}p$ .

Figure 2: The

\mathbf{GL}

-model

M^{\prime}

Then, it is easy to show that $\langle 0,1\rangle\Vdash^{\prime}\Box^{\mathfrak{c}(A)+1}\bot\land\neg A$ and $\langle 1,1\rangle\Vdash^{\prime}\bigwedge\mathrm{Rfn}(\neg\Box A)\land\Box A$ . As in the usual proof of Solovay’s arithmetical completeness theorem, we recursively define a primitive recursive function $h:\omega\to W^{\prime}$ by referring to $T$ -proofs. In the definition of $h$ , we use the formula $\lambda(x)\equiv\exists y\,\forall z\,{\geq}y\,(h(z)=x)$ and the sentence $f_{T}(A)$ for the arithmetical interpretation $f$ defined by $f(p)\equiv\bigvee_{\begin{subarray}{c}a\in W^{\prime}\\ a\Vdash^{\prime}p\end{subarray}}\lambda(\overline{a})$ . This is done by the aid of the Fixed Point Lemma or the recursion theorem as in the proof of Solovay’s theorem because such $\lambda(x)$ and $f_{T}(A)$ are effectively computable from $h$ (see Boolos [2]).

Here we give the definition of the function $h$ . Let $h(0):=0$ . Suppose that the value of $h(x)$ has already been defined. We define the value of $h(x+1)$ . If $\forall y\,{\leq}\,x\,\neg\delta(y)$ holds and there exists no $T$ -proof of $f_{T}(A)$ smaller than or equal to $x$ , let $h(x+1):=0$ . That is, the output of $h$ remains $0$ unless the smallest witness of $\delta(x)$ or the smallest $T$ -proof of $f_{T}(A)$ appears.

After such a witness appears, $h$ changes its value. At the first stage when the smallest witness $x$ of $\delta(x)$ or the smallest $T$ -proof $x$ of $f_{T}(A)$ appears, we distinguish the following two cases:

•

Case 1: $\forall y\,{<}\,x\,\neg\delta(y)$ holds and $x$ is the smallest $T$ -proof of $f_{T}(A)$ .
Let $h(x+1):=\langle 0,0\rangle$ .
•

Case 2: $\forall y\,{<}\,x\,\neg\delta(y)$ and $\delta(x)$ hold and there is no proof of $f_{T}(A)$ less than or equal to $x$ .
Let $h(x+1):=\langle 1,0\rangle$ .

That is, Cases 1 and 2 correspond to the situations $\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma$ and $\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ , respectively.

After that, we define the value of $h(x+1)$ as follows:

h(x+1):=\begin{cases}a&\text{if}\ h(x)\sqsubset^{\prime}a\ \&\ x\ \text{is a}\ T\text{-proof of}\ \neg\lambda(\overline{a});\\ h(x)&\text{otherwise.}\end{cases}

The definition of $h$ is hereby completed.

We introduce three lemmas. The first lemma concerns the general properties of the function $h(x)$ , the formula $\lambda(x)$ , and the arithmetical interpretation $f_{T}$ .

Lemma 3.15.

Let $a,b\in W^{\prime}$ .

1.

If $a\neq b$ , then $\mathsf{PA}\vdash\lambda(\overline{a})\to\neg\lambda(\overline{b})$ ,
2.

$\displaystyle\mathsf{PA}\vdash h(x)=\overline{a}\to\lambda(\overline{a})\lor\bigvee_{a\sqsubset^{\prime}c}\lambda(\overline{c})$ ,
3.

$\displaystyle\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma\leftrightarrow\bigvee_{\pi_{0}(c)=0}\lambda(\overline{c})$ ,
4.

$\displaystyle\mathsf{PA}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\leftrightarrow\bigvee_{\pi_{0}(c)=1}\lambda(\overline{c})$ ,
5.

If $a\sqsubset^{\prime}b$ , then $\mathsf{PA}\vdash\lambda(\overline{a})\to\neg\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{b})\urcorner)$ ,
6.

If $\pi_{1}(a)\geq 1$ , then $\mathsf{PA}\vdash\lambda(\overline{a})\to\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{a})\urcorner)$ ,
7.

If $\pi_{1}(a)\geq 1$ , then $\mathsf{PA}\vdash\lambda(\overline{a})\to\mathrm{Pr}_{T}(\ulcorner\bigvee_{a\sqsubset^{\prime}c}\lambda(\overline{c})\urcorner)$ .

Proof.

Except the implications $\leftarrow$ in Clauses 3 and 4, these statements are proved in a similar way as in the usual proof of Solovay’s arithmetical completeness theorem (cf. [1, 2, 6, 16]).

For the implication $\leftarrow$ in Clause 3, we argue in $\mathsf{PA}$ : Suppose that $\lambda(\overline{c})$ holds and $\pi_{0}(c)=0$ . Then, $h(k)=c$ for some $k$ . If $\neg\sigma$ and $\neg\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ hold, then $\forall x\,h(x)=0$ holds, a contradiction. Hence, $\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma$ or $\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ holds. By Clause 1, we have $\neg\bigvee_{\pi_{0}(d)=1}\lambda(\overline{d})$ . Then, by the implication $\to$ in Clause 4, $\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ does not hold. Therefore, $\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma$ holds.

The implication $\leftarrow$ in Clause 4 is also proved similarly. ❑

The second lemma states that the satisfaction relation for $a\in W^{\prime}$ with $\pi_{1}(a)\geq 1$ is embedded into $\mathsf{PA}$ .

Lemma 3.16.

Let $a\in W^{\prime}$ with $\pi_{1}(a)\geq 1$ and let $B$ be a modal formula.

1.

If $a\Vdash^{\prime}B$ , then $\mathsf{PA}\vdash\lambda(\overline{a})\to f_{T}(B)$ .
2.

If $a\nVdash^{\prime}B$ , then $\mathsf{PA}\vdash\lambda(\overline{a})\to\neg f_{T}(B)$ .

Proof.

Clauses 1 and 2 are proved by induction on the construction of $B$ simultaneously as in the usual proof of Solovay’s theorem. ❑

The third lemma concerns the satisfaction relation for the element $\langle 1,1\rangle$ .

Lemma 3.17.

Let $B$ be any subformula of $\Box A$ .

1.

If $\langle 1,1\rangle\Vdash^{\prime}B$ , then $\mathsf{PA}\vdash\lambda(\overline{\langle 1,0\rangle})\to f_{T}(B)$ ,
2.

If $B$ is $\Box C$ and $\langle 1,1\rangle\Vdash^{\prime}\Box C$ , then $\mathsf{PA}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\to f_{T}(\Box C)$ ,
3.

If $\langle 1,1\rangle\nVdash^{\prime}B$ , then $\mathsf{PA}\vdash\lambda(\overline{\langle 1,0\rangle})\to\neg f_{T}(B)$ .

Proof.

We prove Clauses 1, 2 and 3 by induction on the construction of $B\in\mathsf{Sub}(\Box A)$ simultaneously. We only give a proof of the case that $B$ is $\Box C$ .

1 and 2: Suppose $\langle 1,1\rangle\Vdash^{\prime}\Box C$ . Since $\Box C\in\mathsf{Sub}(\Box A)$ , we have $\langle 1,1\rangle\Vdash^{\prime}\Box C\to C$ because $\langle 1,1\rangle\Vdash^{\prime}\bigwedge\mathrm{Rfn}(\Box A)$ . Then, $\langle 1,1\rangle\Vdash^{\prime}C$ . Hence, for all $a\in W^{\prime}$ with $\pi_{0}(a)=1$ and $\pi_{1}(a)\geq 1$ , we have $a\Vdash^{\prime}C$ . By Lemma 3.16.1, $\mathsf{PA}\vdash\bigvee_{\begin{subarray}{c}\pi_{0}(a)=1\\ \pi_{1}(a)\geq 1\end{subarray}}\lambda(\overline{a})\to f_{T}(C)$ . Also, by the induction hypothesis, $\mathsf{PA}\vdash\lambda(\overline{\langle 1,0\rangle})\to f_{T}(C)$ . Thus,

\mathsf{PA}\vdash\bigvee_{\pi_{0}(a)=1}\lambda(\overline{a})\to f_{T}(C).

By Lemma 3.15.4,

\mathsf{PA}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\to f_{T}(C).

Then,

\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\urcorner)\to f_{T}(\Box C).

Since $\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ is a $\Sigma_{1}$ sentence, we have

\mathsf{PA}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\to f_{T}(\Box C).

This completes the proof of Clause 2. $\mathsf{PA}\vdash\lambda(\overline{\langle 1,0\rangle})\to\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ by Lemma 3.15.4, and hence Clause 1 also holds.

3: Suppose $\langle 1,1\rangle\nVdash^{\prime}\Box C$ . Then, $a\nVdash^{\prime}C$ for some $a\in W^{\prime}$ with $\langle 1,1\rangle\sqsubset^{\prime}a$ . By Lemma 3.16.2, we have

\mathsf{PA}\vdash\lambda(\overline{a})\to\neg f_{T}(C).

Then,

\mathsf{PA}\vdash\neg\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{a})\urcorner)\to\neg f_{T}(\Box C).

Since $\langle 1,0\rangle\sqsubset^{\prime}a$ , by Lemma 3.15.5,

\mathsf{PA}\vdash\lambda(\overline{\langle 1,0\rangle})\to\neg\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{a})\urcorner).

Therefore, $\mathsf{PA}\vdash\lambda(\overline{\langle 1,0\rangle})\to\neg f_{T}(\Box C)$ . ❑

We are ready to show the required two statements: (a) $\mathsf{PA}\vdash\sigma\to f_{T}(\Box A)$ and (b) $\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash f_{T}(\Box A)\to\sigma$ .

(a): Since $\langle 1,1\rangle\Vdash^{\prime}\Box A$ , by Lemma 3.17.2,

\mathsf{PA}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\to f_{T}(\Box A).

Since

\mathsf{PA}\vdash\sigma\land\neg f_{T}(\Box A)\to\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner),

we have

\mathsf{PA}\vdash\sigma\land\neg f_{T}(\Box A)\to f_{T}(\Box A),

and hence we obtain $\mathsf{PA}\vdash\sigma\to f_{T}(\Box A)$ .

(b): Since $\langle 0,1\rangle\Vdash^{\prime}\Box^{\mathfrak{c}(A)+1}\bot$ , for all $a\in W^{\prime}$ with $\pi_{0}(a)=0$ and $\pi_{1}(a)\geq 1$ , we have $a\Vdash^{\prime}\Box^{\mathfrak{c}(A)+1}\bot$ . By Lemma 3.16.1,

\mathsf{PA}\vdash\bigvee_{\begin{subarray}{c}\pi_{0}(a)=0\\ \pi_{1}(a)\geq 1\end{subarray}}\lambda(\overline{a})\to\neg\mathrm{Con}_{T}^{\mathfrak{c}(A)+1},

and thus

\displaystyle\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash\bigwedge_{\begin{subarray}{c}\pi_{0}(a)=0\\ \pi_{1}(a)\geq 1\end{subarray}}\neg\lambda(\overline{a}).

(3)

Since

\mathsf{PA}\vdash f_{T}(\Box A)\land\neg\sigma\to\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma,

by Lemma 3.15.3, we have

\mathsf{PA}\vdash f_{T}(\Box A)\land\neg\sigma\to\bigvee_{\pi_{0}(a)=0}\lambda(\overline{a}).

By combining this with (3), we obtain

\displaystyle\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash f_{T}(\Box A)\land\neg\sigma\to\lambda(\overline{\langle 0,0\rangle}).

(4)

Since $\langle 0,1\rangle\nVdash^{\prime}A$ , by Lemma 3.16.2, $\mathsf{PA}\vdash\lambda(\overline{\langle 0,1\rangle})\to\neg f_{T}(A)$ . Then,

\mathsf{PA}\vdash\neg\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{\langle 0,1\rangle})\urcorner)\to\neg f_{T}(\Box A).

Since $\langle 0,0\rangle\sqsubset^{\prime}\langle 0,1\rangle$ , by Lemma 3.15.5,

\mathsf{PA}\vdash\lambda(\overline{\langle 0,0\rangle})\to\neg\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{\langle 0,1\rangle})\urcorner),

and hence we have $\mathsf{PA}\vdash\lambda(\overline{\langle 0,0\rangle})\to\neg f_{T}(\Box A)$ . From this with (4), we obtain $\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash f_{T}(\Box A)\land\neg\sigma\to\neg f_{T}(\Box A)$ . We conclude $\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash f_{T}(\Box A)\to\sigma$ . ❑

If the height of $T$ is larger than $\mathfrak{c}(A)$ , then the converse of Theorem 3.14 also holds.

Proposition 3.18.

Let $A$ be any modal formula. Suppose that the height of $T$ is larger than $\mathfrak{c}(A)$ and, for any $\Sigma_{1}$ sentence $\sigma$ , there exists an arithmetical interpretation $f$ such that $\mathsf{PA}\vdash\sigma\to f_{T}(\Box A)$ and $\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash f_{T}(\Box A)\to\sigma$ . Then, $A$ is nontrifling.

Proof.

Since $0=1$ is a $\Sigma_{1}$ sentence, there exists an arithmetical interpretation $f$ such that $\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash f_{T}(\Box A)\to 0=1$ . Since $\mathbb{N}\models\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}$ , we have $\mathbb{N}\models\neg f_{T}(\Box A)$ . Thus, $T\nvdash f_{T}(A)$ . By Fact 3.3.1, $\mathbf{GL}\nvdash A$ .

Also, since $0=0$ is a $\Sigma_{1}$ sentence, there exists an arithmetical interpretation $g$ such that $\mathsf{PA}\vdash 0=0\to g_{T}(\Box A)$ . Then, $\mathsf{PA}\vdash g_{T}(\Box A)$ . Since $\mathbb{N}\models\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}$ , $\mathsf{PA}\nvdash\neg\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}$ , and thus $\mathsf{PA}\nvdash\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\to\neg g_{T}(\Box A)$ . By Fact 3.3.1, $\mathbf{GL}\nvdash\Diamond^{\mathfrak{c}(A)+1}\top\to\neg\Box A$ . By Lemma 3.6, $\mathbf{GL}_{\omega}\nvdash\neg\Box A$ . Then, by Proposition 3.11, $A$ is nontrifling. ❑

For any classical propositional formula $A$ , we have $\mathfrak{c}(A)=0$ . So Proposition 3.13 shows that Theorem 3.14 is actually an extension of Theorem 2.3.

For a variable $v$ of first-order logic, an $v$ -arithmetical interpretation $f$ is a mapping where for each propositional variable $p$ , $f(p)$ is an $\mathcal{L}_{A}$ -formula $\varphi(v)$ with only the free variable $v$ . Each $v$ -arithmetical interpretation $f$ is uniquely extended to the mapping $f_{T}$ from the set of all modal formulas to a set of $\mathcal{L}_{A}$ -formulas with at most the free variable $v$ as the usual arithmetical interpretations with the clause $f_{T}(\Box A)(v)\equiv\mathrm{Pr}_{T}(\ulcorner f_{T}(A)(\dot{v})\urcorner)$ . By tracing the proof of Theorem 3.14 entirely using the function $h(x,v)$ and the formula $\lambda(x,v)$ , the following parameterized version of Theorem 3.14 is also proved.

Theorem 3.19.

For any modal formula $A$ , if $A$ is nontrifling, then for any $\Sigma_{1}$ formula $\sigma(v)$ , there exists an $v$ -arithmetical interpretation $f$ such that

1.

$\mathsf{PA}\vdash\forall v\,\bigl{(}\sigma(v)\to f_{T}(\Box A)(v)\bigr{)}$ , and
2.

$\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash\forall v\,\bigl{(}f_{T}(\Box A)(v)\to\sigma(v)\bigr{)}$ .

From Theorem 3.19, we obtain an extension of Theorem 2.5 to the framework of modal logic.

Theorem 3.20.

Let $A$ be any modal formula $A$ . If $A$ is nontrifling and the height of $T$ is larger than $\mathfrak{c}(A)$ , then for any c.e. set $X$ , there exists an $v$ -arithmetical interpretation $f$ such that $f_{T}(A)(v)$ weakly represents $X$ in $T$ .

Proof.

Let $\sigma(v)$ be a $\Sigma_{1}$ formula defining $X$ over $\mathbb{N}$ . By Theorem 3.19, there exists an $v$ -arithmetical interpretation $f$ such that

1.

$\mathsf{PA}\vdash\forall v\,\bigl{(}\sigma(v)\to f_{T}(\Box A)(v)\bigr{)}$ , and
2.

$\mathsf{PA}+\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}\vdash\forall v\,\bigl{(}f_{T}(\Box A)(v)\to\sigma(v)\bigr{)}$ .

Since $\mathbb{N}\models\mathrm{Con}_{T}^{\mathfrak{c}(A)+1}$ , we have $\mathbb{N}\models\forall v\,\bigl{(}\sigma(v)\leftrightarrow f_{T}(\Box A)(v)\bigr{)}$ . Then, for any $k\in\omega$ , $k\in X$ if and only if $T\vdash f_{T}(A)(\overline{k})$ . This means that $f_{T}(A)(v)$ weakly represents $X$ in $T$ . ❑

3.3 A modal version of the FGH theorem for theories with finite heights

Notice that Theorem 3.20 requires the assumption that the height of $T$ is larger than $\mathfrak{c}(A)$ . In this subsection, we investigate variations of Theorems 3.14 and 3.20, keeping in mind theories with finite heights.

It is already proved in Proposition 3.11 that for any natural number $s$ with $s>\mathfrak{c}(A)$ , $A$ is nontrifling if and only if $\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ and $\mathbf{GL}+\{\neg F_{s}\}\nvdash\neg\Box A$ . On the other hand, even for a natural number $s$ with $s\leq\mathfrak{c}(A)$ , we prove the following version of the FGH theorem concerning the condition “ $\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ and $\mathbf{GL}+\{\neg F_{s}\}\nvdash\neg\Box A$ ”.

Theorem 3.21.

For any modal formula $A$ , if $\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ and $\mathbf{GL}+\{\neg F_{s}\}\nvdash\neg\Box A$ , then for any $\Sigma_{1}$ sentence $\sigma$ , there exists an arithmetical interpretation $f$ such that

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\leftrightarrow f_{T}(\Box A).

Proof.

Suppose $\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ and $\mathbf{GL}+\{\neg F_{s}\}\nvdash\neg\Box A$ , that is, $\mathbf{GL}\nvdash\Box^{s+1}\bot\land\Diamond^{s}\top\to\Box A$ and $\mathbf{GL}\nvdash\Box^{s+1}\bot\land\Diamond^{s}\top\to\neg\Box A$ . By the Kripke completeness of $\mathbf{GL}$ , there exist $\mathbf{GL}$ -models $M_{0}=\langle W_{0},\sqsubset_{0},r_{0},\Vdash_{0}\rangle$ and $M_{1}=\langle W_{1},\sqsubset_{1},r_{1},\Vdash_{1}\rangle$ such that $r_{0}\Vdash_{0}\Box^{s+1}\bot\land\Diamond^{s}\top\land\neg\Box A$ and $r_{1}\Vdash_{1}\Box^{s+1}\bot\land\Diamond^{s}\top\land\Box A$ . Let $n_{0}$ and $n_{1}$ be the cardinalities of $W_{0}$ and $W_{1}$ respectively, and we may assume that

•

$W_{0}=\{\langle 0,1\rangle,\langle 0,2\rangle,\ldots,\langle 0,n_{0}\rangle\}$ , $r_{0}=\langle 0,1\rangle$ , and
•

$W_{1}=\{\langle 1,1\rangle,\langle 1,2\rangle,\ldots,\langle 1,n_{1}\rangle\}$ , $r_{1}=\langle 1,1\rangle$ .

Let $M^{\prime}=\langle W^{\prime},\sqsubset^{\prime},0,\Vdash^{\prime}\rangle$ be the $\mathbf{GL}$ -model obtained from $M_{0}$ and $M_{1}$ as in the proof of Theorem 3.14. Then, $\langle 0,1\rangle\Vdash^{\prime}\Box^{s+1}\bot\land\Diamond^{s}\top\land\neg\Box A$ and $\langle 1,1\rangle\Vdash^{\prime}\Box^{s+1}\bot\land\Diamond^{s}\top\land\Box A$ .

We can define a function $h$ , a formula $\lambda(x)$ , and an arithmetical interpretation $f$ from the $\mathbf{GL}$ -model $M^{\prime}$ in the same way as in the proof of Theorem 3.14. Then, the same results as Lemmas 3.15, 3.16 and 3.17 can also be proved.

For each $a\in W^{\prime}$ with $\pi_{1}(a)>1$ , since $a\Vdash^{\prime}\Box^{s}\bot$ , we have that $\mathsf{PA}$ proves $\lambda(\overline{a})\to\neg\mathrm{Con}_{T}^{s}$ , and thus

\mathsf{PA}+\mathrm{Con}_{T}^{s}\vdash\bigwedge_{\pi_{1}(a)>1}\neg\lambda(\overline{a}).

Also, since $\langle i,1\rangle\Vdash^{\prime}\Diamond^{s}\top$ , we have $\mathsf{PA}\vdash\lambda(\overline{\langle i,1\rangle})\to\mathrm{Con}_{T}^{s}$ . Then, $\mathsf{PA}$ proves $\neg\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{\langle i,1\rangle})\urcorner)\to\mathrm{Con}_{T}^{s+1}$ . Also, $\mathsf{PA}\vdash\lambda(\overline{\langle i,0\rangle})\to\neg\mathrm{Pr}_{T}(\ulcorner\neg\lambda(\overline{\langle i,1\rangle})\urcorner)$ because $\langle i,0\rangle\sqsubset^{\prime}\langle i,1\rangle$ , and hence $\mathsf{PA}\vdash\lambda(\overline{\langle i,0\rangle})\to\mathrm{Con}_{T}^{s+1}$ . Therefore, we obtain

\displaystyle\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\bigwedge_{\pi_{1}(a)\neq 1}\neg\lambda(\overline{a}).

(5)

We prove $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\leftrightarrow f_{T}(\Box A)$ .

$(\rightarrow)$ : Since $\mathsf{PA}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\to\bigvee_{\pi_{0}(a)=1}\lambda(\overline{a})$ , from (5), we have

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\to\lambda(\overline{\langle 1,1\rangle}).

Since $\langle 1,1\rangle\Vdash^{\prime}\Box A$ , we have $\mathsf{PA}\vdash\lambda(\overline{\langle 1,1\rangle})\to f_{T}(\Box A)$ . Hence,

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\to f_{T}(\Box A).

Here $\mathsf{PA}\vdash\sigma\land\neg f_{T}(\Box A)\to\sigma\prec\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)$ , and thus

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\land\neg f_{T}(\Box A)\to f_{T}(\Box A).

We obtain $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\to f_{T}(\Box A)$ .

$(\leftarrow)$ : Since $\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma\to\bigvee_{\pi_{0}(a)=0}\lambda(\overline{a})$ , from (5),

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma\to\lambda(\overline{\langle 0,1\rangle}).

Since $\langle 0,1\rangle\nVdash^{\prime}\Box A$ , $\mathsf{PA}\vdash\lambda(\overline{\langle 0,1\rangle})\to\neg f_{T}(\Box A)$ . Therefore,

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\mathrm{Pr}_{T}(\ulcorner f_{T}(A)\urcorner)\preccurlyeq\sigma\to\neg f_{T}(\Box A),

and hence

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash f_{T}(\Box A)\land\neg\sigma\to\neg f_{T}(\Box A).

We conclude $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash f_{T}(\Box A)\to\sigma$ . ❑

If the height of $T$ is larger than or equal to $s$ , then the converse of Theorem 3.21 also holds.

Proposition 3.22.

Suppose that the height of $T$ is larger than or equal to $s$ . For any modal formula $A$ , if for any $\Sigma_{1}$ sentence $\sigma$ , there exists an arithmetical interpretation $f$ such that $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\leftrightarrow f_{T}(\Box A)$ , then $\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ and $\mathbf{GL}+\{\neg F_{s}\}\nvdash\neg\Box A$ .

Proof.

If the height of $T$ is larger than $s$ , then $T\nvdash\neg\mathrm{Con}_{T}^{s}$ . By Löb’s theorem, $T\nvdash\neg\mathrm{Con}_{T}^{s+1}\to\neg\mathrm{Con}_{T}^{s}$ . Thus, the theory $T+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}$ is consistent. Also, if the height of $T$ is exactly $s$ , then $\mathbb{N}\models\neg\mathrm{Con}_{T}^{s+1}\land\mathrm{Con}_{T}^{s}$ . Thus, $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}$ is consistent. In either case, the theory $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}$ is consistent.

Let $\sigma$ be any $\Sigma_{1}$ sentence independent of $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}$ . Then, we have an arithmetical interpretation $f$ such that

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\sigma\leftrightarrow f_{T}(\Box A).

Then, $\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}$ proves neither $f_{T}(\Box A)$ nor $\neg f_{T}(\Box A)$ . By Fact 3.3.1, $\mathbf{GL}$ proves neither $\neg F_{s}\to\Box A$ nor $\neg F_{s}\to\neg\Box A$ . ❑

In the same way as in the proof of Theorem 3.21, the parameterized version of Theorem 3.21 can also be proved, and hence we obtain the following theorem.

Theorem 3.23.

Suppose that the height of $T$ is $s$ . For any modal formula $A$ , if $\mathbf{GL}+\{\neg F_{s}\}\nvdash\Box A$ and $\mathbf{GL}+\{\neg F_{s}\}\nvdash\neg\Box A$ , then for any c.e. set $X$ , there exists an $v$ -arithmetical interpretation $f$ such that $f_{T}(A)(v)$ weakly represents $X$ in $T$ .

Proof.

Let $\sigma(v)$ be a $\Sigma_{1}$ formula defining $X$ over $\mathbb{N}$ . Then, from the parameterized version of Theorem 3.21, there exists an $v$ -arithmetical interpretation $f$ such that

\mathsf{PA}+\neg\mathrm{Con}_{T}^{s+1}+\mathrm{Con}_{T}^{s}\vdash\forall v\,\bigl{(}\sigma(v)\leftrightarrow f_{T}(\Box A)(v)\bigr{)}.

Since the height of $T$ is $s$ , $\mathbb{N}\models\neg\mathrm{Con}_{T}^{s+1}\land\mathrm{Con}_{T}^{s}$ . Then, we have that $\mathbb{N}\models\forall v\,\bigl{(}\sigma(v)\leftrightarrow f_{T}(\Box A)(v)\bigr{)}$ . It follows that $f_{T}(A)(v)$ weakly represents $X$ in $T$ . ❑

We close this section with two problems. In Section 2, we proved Theorem 2.3 by using Lemma 2.4. On the other hand, in this section, we proved Theorem 3.14 that is a modal extension of Theorem 2.3 without using modal version of Lemma 2.4. If a modal version of Lemma 2.4 is proved, then a proof of Theorem 3.14, as well as the proof of our Theorem 2.3 in Section 2, would be substantially simplified.

Problem 3.24.

Can we prove a modal version of Lemma 2.4?

In Section 2, we proved Theorem 2.6 that is an improvement of Theorem 2.3. Then, it is natural to ask the following problem.

Problem 3.25.

Can we extend Theorem 2.6 to the framework of modal propositional logic?

4 Rosser-type FGH theorems

In this section, we investigate some variations of Rosser-type FGH theorems. Recall that $\mathrm{Proof}_{T}(x,y)$ is a natural formula saying that $y$ is a $T$ -proof of $x$ and $\mathrm{Pr}_{T}(x)$ is of the form $\exists y\,\mathrm{Proof}_{T}(x,y)$ . Besides $\mathrm{Proof}_{T}(x,y)$ , we consider formulas that witness $\mathrm{Pr}_{T}(x)$ . We say a formula $\mathrm{Prf}_{T}(x,y)$ is a proof predicate of $T$ if $\mathrm{Prf}_{T}(x,y)$ satisfies the following conditions:

1.

$\mathrm{Prf}_{T}(x,y)$ is a primitive recursive formula,
2.

$\mathsf{PA}\vdash\forall x\,\bigl{(}\mathrm{Pr}_{T}(x)\leftrightarrow\exists y\,\mathrm{Prf}_{T}(x,y)\bigr{)}$ ,
3.

$\mathsf{PA}\vdash\forall x\,\forall x^{\prime}\,\forall y\,\bigl{(}\mathrm{Prf}_{T}(x,y)\land\mathrm{Prf}_{T}(x^{\prime},y)\to x=x^{\prime}\bigr{)}$ .

For each proof predicate $\mathrm{Prf}_{T}(x,y)$ of $T$ , the $\Sigma_{1}$ formula $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ defined by

\mathrm{Pr}_{T}^{\mathrm{R}}(x):\equiv\exists y\,\bigl{(}\mathrm{Prf}_{T}(x,y)\land\forall z\,{<}\,y\,\neg\mathrm{Prf}_{T}(\dot{\neg}x,z)\bigr{)}

is called the Rosser provability predicate of $\mathrm{Prf}_{T}(x,y)$ or a Rosser provability predicate of $T$ . Here $\dot{\neg}x$ is a primitive recursive term corresponding to a primitive recursive function calculating the Gödel number of $\neg\varphi$ from the Gödel number of an $\mathcal{L}_{A}$ -formula $\varphi$ such that $\mathsf{PA}$ proves $\dot{\neg}\ulcorner\psi\urcorner=\ulcorner\neg\psi\urcorner$ for each $\mathcal{L}_{A}$ -formula $\psi$ . In view of witness comparison, we also introduce an auxiliary $\Sigma_{1}$ formula $\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\dot{\neg}x)$ as follows:

\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\dot{\neg}x):\equiv\exists y\,\bigl{(}\mathrm{Prf}_{T}(\dot{\neg}x,y)\land\forall z\,{\leq}\,y\,\neg\mathrm{Prf}_{T}(x,z)\bigr{)}.

Then, for any $\mathcal{L}_{A}$ -formula $\varphi$ , $\mathsf{PA}$ proves $\neg\bigl{(}\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\land\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)\bigr{)}$ and $\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\lor\mathrm{Pr}_{T}(\ulcorner\neg\varphi\urcorner)\to\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\lor\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)$ .

In a study of Rosser-type Henkin sentences, the following result was proved.

Fact 4.1 (Kurahashi [9, Theorem 3.5]).

For any $\Sigma_{1}$ sentence $\sigma$ , the following are equivalent:

1.

There exists a $\Sigma_{1}$ sentence $\sigma^{\prime}$ such that $\mathsf{PA}\vdash\neg(\sigma\land\sigma^{\prime})$ and $\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner\sigma\urcorner)\lor\mathrm{Pr}_{T}(\ulcorner\sigma^{\prime}\urcorner)\to\sigma\lor\sigma^{\prime}$ .
2.

There exists a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ such that $\mathsf{PA}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\sigma\urcorner)$ .

This fact can be seen as a kind of the FGH theorem for Rosser provability predicates because it deals with the equivalence $\sigma\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ where $\varphi$ is in particular $\sigma$ . Inspired by this fact, we prove the following theorem.

Theorem 4.2.

For any $\Sigma_{1}$ sentences $\sigma_{0}$ and $\sigma_{1}$ , the following are equivalent:

1.

$\mathsf{PA}\vdash\neg(\sigma_{0}\land\sigma_{1})$ and $\mathsf{PA}\vdash\neg\mathrm{Con}_{T}\to\sigma_{0}\lor\sigma_{1}$ .

There are a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and an $\mathcal{L}_{A}$ -sentence $\varphi$ such that

\mathsf{PA}\vdash\sigma_{0}\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\ \text{and}\ \mathsf{PA}\vdash\sigma_{1}\leftrightarrow\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner).

Proof.

$(2\Rightarrow 1)$ : This implication follows from the properties of witness comparison formulas.

$(1\Rightarrow 2)$ : We may assume that $\sigma_{0}$ and $\sigma_{1}$ are of the forms $\exists x\,\tau_{0}(x)$ and $\exists x\,\tau_{1}(x)$ for some $\Delta_{0}$ formulas $\tau_{0}(x)$ and $\tau_{1}(x)$ , respectively. By the Fixed Point Lemma, let $\varphi$ be a $\Sigma_{1}$ sentence satisfying the following equivalence:

\mathsf{PA}\vdash\varphi\leftrightarrow\exists y\,\bigl{[}(\mathrm{Proof}_{T}(\ulcorner\neg\varphi\urcorner,y)\lor\tau_{0}(y))\land\forall z\,{\leq}\,y\,(\neg\mathrm{Proof}_{T}(\ulcorner\varphi\urcorner,z)\land\neg\tau_{1}(z))\bigr{]}.

Also, let $\varphi^{*}$ be the $\Sigma_{1}$ sentence

\exists z\,\bigl{[}(\mathrm{Proof}_{T}(\ulcorner\varphi\urcorner,z)\lor\tau_{1}(z))\land\forall y\,{<}\,z\,(\neg\mathrm{Proof}_{T}(\ulcorner\neg\varphi\urcorner,y)\land\neg\tau_{0}(y))\bigr{]}.

Lemma 4.3.

$\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\lor\mathrm{Pr}_{T}(\ulcorner\neg\varphi\urcorner)\to\sigma_{0}\lor\sigma_{1}$ .

Proof.

Let $\mathrm{Prov}_{T}^{\mathrm{R}}(x)$ be the Rosser provability predicate of $\mathrm{Proof}_{T}(x,y)$ . Then, $\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\lor\mathrm{Pr}_{T}(\ulcorner\neg\varphi\urcorner)\to\mathrm{Prov}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\lor\mathrm{Prov}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)$ . By the definition of $\varphi^{*}$ ,

\mathsf{PA}\vdash\mathrm{Prov}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\land\neg\sigma_{0}\to\varphi^{*}.

Then,

\mathsf{PA}\vdash\mathrm{Prov}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\land\neg\sigma_{0}\to\mathrm{Pr}_{T}(\ulcorner\varphi^{*}\urcorner)

because $\varphi^{*}$ is a $\Sigma_{1}$ sentence. Since $\mathsf{PA}\vdash\neg(\varphi\land\varphi^{*})$ , we have

\displaystyle\mathsf{PA}\vdash\mathrm{Prov}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\land\neg\sigma_{0}\to\neg\mathrm{Con}_{T}.

(6)

By the choice of $\varphi$ ,

\mathsf{PA}\vdash\mathrm{Prov}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)\land\neg\sigma_{1}\to\varphi,

and we also obtain

\mathsf{PA}\vdash\mathrm{Prov}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)\land\neg\sigma_{1}\to\neg\mathrm{Con}_{T}.

From this with (6),

\mathsf{PA}+\mathrm{Con}_{T}\vdash\mathrm{Prov}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\lor\mathrm{Prov}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)\to\sigma_{0}\lor\sigma_{1}.

Thus,

\mathsf{PA}+\mathrm{Con}_{T}\vdash\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\lor\mathrm{Pr}_{T}(\ulcorner\neg\varphi\urcorner)\to\sigma_{0}\lor\sigma_{1}.

Since $\mathsf{PA}+\neg\mathrm{Con}_{T}\vdash\sigma_{0}\lor\sigma_{1}$ , we conclude

\mathsf{PA}\vdash\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\lor\mathrm{Pr}_{T}(\ulcorner\neg\varphi\urcorner)\to\sigma_{0}\lor\sigma_{1}.

We proceed with the main proof. We recursively define a primitive recursive function $h$ and an increasing sequence $\langle k_{i}\rangle_{i\in\omega}$ of natural numbers simultaneously by referring to $T$ -proofs in stages. The function $h$ will be defined to output all theorems of $T$ and the Rosser predicate of the proof predicate $x=h(y)$ will be a required one. At the beginning of Stage $m$ , the values of $k_{0},\ldots,k_{m-1},k_{m}$ and $h(0),\ldots,h(k_{m-1})$ have already been defined.

Here we give our definition of the function $h$ . In the definition, we identify each $\mathcal{L}_{A}$ -formula with its Gödel number. First, let $k_{0}=0$ .

At Stage $m$ ,

•

If $m$ is not a $T$ -proof of any $\mathcal{L}_{A}$ -formula, then let $k_{m+1}:=k_{m}$ and go to Stage $m+1$ .
•

If $m$ is a $T$ -proof of an $\mathcal{L}_{A}$ -formula $\xi$ which is neither $\varphi$ nor $\neg\varphi$ , then let $k_{m+1}:=k_{m}+1$ and $h(k_{m}):=\xi$ , and go to the next stage.
•

If $m$ is a $T$ -proof of an $\mathcal{L}_{A}$ -sentence $\xi$ which is either $\varphi$ or $\neg\varphi$ , and $h$ already outputs at least one of $\varphi$ or $\neg\varphi$ before Stage $m$ , then let $k_{m+1}:=k_{m}+1$ and $h(k_{m}):=\xi$ , and go to Stage $m+1$ .
•

If $m$ is a $T$ -proof of either $\varphi$ or $\neg\varphi$ , and $f$ does not output $\varphi$ and $\neg\varphi$ before Stage $m$ , then we distinguish the following three cases:

(a)

If $\exists z\,{\leq m}\,\tau_{0}(z)$ holds, then let $k_{m+1}:=k_{m}+1$ and $h(k_{m}):=\varphi$ .

(b)

If $\exists z\,{\leq m}\,\tau_{1}(z)$ holds, then let $k_{m+1}:=k_{m}+1$ and $h(k_{m}):=\neg\varphi$ .

(c)

Otherwise, let $k_{m+1}:=k_{m}$ .

Go to the next Stage $m+1$ .

This completes our definition the function $h$ . Since $\mathsf{PA}\vdash\neg(\sigma_{0}\land\sigma_{1})$ , we have that $\mathsf{PA}$ proves that there is no $m$ satisfying both $\exists z\,{\leq}\,m\,\tau_{0}(z)$ and $\exists z\,{\leq}\,m\,\tau_{1}(z)$ . Thus Cases (a) and (b) in the definition of $h$ are mutually exclusive.

We show that the formula $x=h(y)$ is a proof predicate of $T$ . It suffices to show the following lemma:

Lemma 4.4.

$\mathsf{PA}\vdash\forall x\,\bigl{(}\mathrm{Pr}_{T}(x)\leftrightarrow\exists y\,(x=h(y))\bigr{)}$ .

Proof.

We argue in $\mathsf{PA}$ .

$(\rightarrow)$ : Suppose that $\xi$ is provable in $T$ .

If $\xi$ is neither $\varphi$ nor $\neg\varphi$ , then for a $T$ -proof $m$ of $\xi$ , $h(k_{m})=\xi$ .

If $\xi$ is either $\varphi$ or $\neg\varphi$ , then by Lemma 4.3, $\sigma_{0}\lor\sigma_{1}$ holds. However, $\sigma_{0}$ and $\sigma_{1}$ cannot be true at the same time. We show that $\xi$ is output by $h$ . We distinguish the following two cases:

•

Case 1: $\sigma_{0}$ holds.
Let $n$ be the least number such that $\tau_{0}(n)$ holds, and let $m$ be the least number such that $m\geq n$ and $m$ is a $T$ -proof of either $\varphi$ or $\neg\varphi$ . Then, $h(k_{m})=\varphi$ by the definition of $h$ . If $\xi$ is $\varphi$ , we are done. If $\xi$ is $\neg\varphi$ , then let $m^{\prime}>m$ be a $T$ -proof of $\neg\varphi$ . Such an $m^{\prime}$ exists because $\neg\varphi$ has infinitely many $T$ -proofs. Since $h$ already outputs $\varphi$ before Stage $m^{\prime}$ , by the definition of $h$ , $h(k_{m^{\prime}})=\neg\varphi$ .
•

Case 2: $\sigma_{1}$ holds.
It is proved that $h$ outputs $\xi$ as in the proof of Case 1 by considering the least number $n$ such that $\tau_{1}(n)$ holds.

$(\leftarrow)$ : Suppose that $\xi$ is output by $h$ . If $\xi$ is neither $\varphi$ nor $\neg\varphi$ , then $h(k_{m})=\xi$ implies that $m$ is a $T$ -proof of $\xi$ , and so $\xi$ is provable in $T$ .

If $\xi$ is $\varphi$ or $\neg\varphi$ , then let $m$ be the least number such that $h(k_{m})$ is either $\varphi$ or $\neg\varphi$ . We show that $\xi$ is provable in $T$ . We distinguish the following four cases:

•

Case 1: $\xi$ is $\varphi$ and $h(k_{m})=\varphi$ .
By the definition of $h$ , $\exists z\,{\leq}\,m\,\tau_{0}(z)$ holds. Then, $\sigma_{0}$ and $\neg\sigma_{1}$ hold. Suppose that $\varphi$ is not provable in $T$ , then $\varphi$ holds by the definition. Since $\varphi$ is a $\Sigma_{1}$ sentence, it is provable in $T$ , a contradiction. Therefore, $\varphi$ is provable in $T$ .
•

Case 2: $\xi$ is $\varphi$ and $h(k_{m})=\neg\varphi$ .
Then, $h(k_{m^{\prime}})=\varphi$ for some $m^{\prime}>m$ . Since $\neg\varphi$ is already output before Stage $m^{\prime}$ , we find that $m^{\prime}$ is a $T$ -proof of $\varphi$ , and hence $\varphi$ is provable in $T$ .
•

Case 3: $\xi$ is $\neg\varphi$ and $h(k_{m})=\varphi$ .
Then, for some $T$ -proof $m^{\prime}>m$ of $\neg\varphi$ , $h(k_{m^{\prime}})=\neg\varphi$ . Thus, $\neg\varphi$ is provable in $T$ .
•

Case 4: $\xi$ is $\neg\varphi$ and $h(k_{m})=\neg\varphi$ .
Then, $\exists z\,{\leq}\,m\,\tau_{1}(z)$ holds, and so $\sigma_{1}$ and $\neg\sigma_{0}$ hold. Suppose that $\neg\varphi$ is not provable in $T$ . Then, $\varphi^{*}$ holds, and is provable in $T$ . Since $\varphi^{*}\to\neg\varphi$ is $T$ -provable, $\neg\varphi$ is also $T$ -provable. This is a contradiction. Therefore, $\neg\varphi$ is provable in $T$ . ❑

We resume the main proof. Let $\mathrm{Pr}_{h}^{\mathrm{R}}(x)$ be the Rosser provability predicate of the proof predicate $x=h(y)$ of $T$ . Finally, we show that $\mathsf{PA}$ proves $\sigma_{0}\leftrightarrow\mathrm{Pr}_{h}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ . A proof of $\mathsf{PA}\vdash\sigma_{1}\leftrightarrow\mathrm{Pr}_{h}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)$ is similar, and we omit it. We argue in $\mathsf{PA}$ .

$(\rightarrow)$ : Suppose that $\sigma_{0}$ holds. Let $n$ be the least number such that $\tau_{0}(n)$ holds. Then, either $\varphi$ or $\varphi^{*}$ holds, and hence either one of them is provable in $T$ . Then, either $\varphi$ or $\neg\varphi$ is $T$ -provable. Let $m$ be the least number such that $m\geq n$ and $m$ is a $T$ -proof of $\varphi$ or $\neg\varphi$ . Then, $h$ does not output $\neg\varphi$ before Stage $m$ , and $h(k_{m})=\varphi$ . This means $\mathrm{Pr}_{h}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ holds.

$(\leftarrow)$ : Suppose that $h(k_{m})=\varphi$ and before Stage $m$ , $h$ does not output $\neg\varphi$ . For the least such an $m$ , $\exists z\,{\leq}\,m\,\tau_{0}(z)$ holds, and thus $\sigma_{0}$ holds. ❑

Corollary 4.5.

For any $\Sigma_{1}$ sentence $\sigma$ , the following are equivalent:

1.

There exists a $\Sigma_{1}$ sentence $\sigma^{\prime}$ such that $\mathsf{PA}\vdash\neg(\sigma\land\sigma^{\prime})$ and $\mathsf{PA}\vdash\neg\mathrm{Con}_{T}\to\sigma\lor\sigma^{\prime}$ .
2.

There exists a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and an $\mathcal{L}_{A}$ -sentence $\varphi$ such that $\mathsf{PA}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ .

Proof.

$(1\Rightarrow 2)$ : Immediate from Theorem 4.2.

$(2\Rightarrow 1)$ : This implication is derived by letting $\sigma^{\prime}$ be the $\Sigma_{1}$ sentence $\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner)$ . ❑

The $(\mathsf{PA}+\mathrm{Con}_{T})$ -provable equivalence in the statement of the FGH theorem is equivalent to $\mathsf{PA}\vdash(\sigma\lor\neg\mathrm{Con}_{T})\leftrightarrow\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)$ . In this viewpoint, the following corollary seems to be a natural counterpart of the FGH theorem in terms of Rosser provability predicates.

Corollary 4.6.

For any $\Sigma_{1}$ sentence $\sigma$ , there exist a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and an $\mathcal{L}_{A}$ -sentence $\varphi$ such that

\mathsf{PA}\vdash(\sigma\lor\neg\mathrm{Con}_{T})\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner).

Proof.

For the $\Sigma_{1}$ sentences $\sigma\lor\neg\mathrm{Con}_{T}$ and $0=1$ , we have that $\mathsf{PA}$ proves $\neg\bigl{(}(\sigma\lor\neg\mathrm{Con}_{T})\land 0=1\bigr{)}$ and $\neg\mathrm{Con}_{T}\to(\sigma\lor\neg\mathrm{Con}_{T})\lor 0=1$ . By Corollary 4.5, there exist a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and an $\mathcal{L}_{A}$ -sentence $\varphi$ such that $\mathsf{PA}\vdash(\sigma\lor\neg\mathrm{Con}_{T})\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ . ❑

Since $\mathsf{PA}+\mathrm{Con}_{T}\vdash\mathrm{Pr}_{T}(\ulcorner\varphi\urcorner)\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ , the FGH theorem directly follows from Corollary 4.6.

We show a version of the FGH theorem with respect to Rosser provability predicates corresponding to the representability of computable sets.

Corollary 4.7.

For any $\Delta_{1}(\mathsf{PA})$ sentence $\delta$ , there exist a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and an $\mathcal{L}_{A}$ -sentence $\varphi$ such that

\mathsf{PA}\vdash\delta\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\ \text{and}\ \mathsf{PA}\vdash\neg\delta\leftrightarrow\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner).

Proof.

Since $\delta$ is $\Delta_{1}(\mathsf{PA})$ , there exist $\Sigma_{1}$ sentences $\sigma_{0}$ and $\sigma_{1}$ such that $\mathsf{PA}\vdash\delta\leftrightarrow\sigma_{0}$ and $\mathsf{PA}\vdash\neg\delta\leftrightarrow\sigma_{1}$ . Then, we have $\mathsf{PA}\vdash\neg(\sigma_{0}\land\sigma_{1})$ and $\mathsf{PA}\vdash\sigma_{0}\lor\sigma_{1}$ . By Theorem 4.2, there exists a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and an $\mathcal{L}_{A}$ -sentence $\varphi$ such that

\mathsf{PA}\vdash\sigma_{0}\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)\ \text{and}\ \mathsf{PA}\vdash\sigma_{1}\leftrightarrow\mathrm{Pr}_{T}^{\scriptsize{\reflectbox{{\rm R}}}}(\ulcorner\neg\varphi\urcorner).

Corollary 4.7 says that if a $\Sigma_{1}$ sentence $\sigma$ is $\Delta_{1}(\mathsf{PA})$ , then there exist a Rosser provability predicate $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and an $\mathcal{L}_{A}$ -sentence $\varphi$ such that $\mathsf{PA}\vdash\sigma\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ . Does this hold for all $\Sigma_{1}$ sentences? By Corollary 4.5, this question is rephrased as follows: For any $\Sigma_{1}$ sentence $\sigma$ , does there exists a $\Sigma_{1}$ sentence $\sigma^{\prime}$ such that $\mathsf{PA}\vdash\neg(\sigma\land\sigma^{\prime})$ and $\mathsf{PA}\vdash\neg\mathrm{Con}_{T}\to\sigma\lor\sigma^{\prime}$ ? We show that this is not the case.

Proposition 4.8.

There exists a $\Sigma_{1}$ sentence $\sigma$ such that for all $\Sigma_{1}$ sentences $\sigma^{\prime}$ , neither $\mathsf{PA}\vdash\neg(\sigma\land\sigma^{\prime})$ nor $\mathsf{PA}\vdash\neg\mathrm{Con}_{T}\to\sigma\lor\sigma^{\prime}$ . That is, for all Rosser provability predicates $\mathrm{Pr}_{T}^{\mathrm{R}}(x)$ of $T$ and all $\mathcal{L}_{A}$ -sentences $\varphi$ , $\mathsf{PA}\nvdash\sigma\leftrightarrow\mathrm{Pr}_{T}^{\mathrm{R}}(\ulcorner\varphi\urcorner)$ .

Proof.

Let $\sigma$ be a $\Sigma_{1}$ sentence which is $\Pi_{1}$ -conservative over $\mathsf{PA}$ such that $\mathsf{PA}+\neg\mathrm{Con}_{T}\nvdash\sigma$ . The existence of such a sentence is proved by Guaspari [4, Theorem 2.4] (see also Lindström [11, Exercise 5.5 (b)]). Suppose that for some $\Sigma_{1}$ sentence $\sigma^{\prime}$ , $\mathsf{PA}\vdash\neg(\sigma\land\sigma^{\prime})$ and $\mathsf{PA}\vdash\neg\mathrm{Con}_{T}\to\sigma\lor\sigma^{\prime}$ . Then, $\mathsf{PA}+\sigma\vdash\neg\sigma^{\prime}$ , and hence $\mathsf{PA}\vdash\neg\sigma^{\prime}$ by $\Pi_{1}$ -conservativity. Thus, $\mathsf{PA}+\neg\mathrm{Con}_{T}\vdash\sigma$ . This is a contradiction.

❑

Guaspari and Solovay [5] introduced the logic $\mathbf{R}$ of witness comparison formulas, and also Shavrukov [13] introduced the bimodal logic $\mathbf{GR}$ of usual and Rosser provability predicates. As in our observations in Section 3, it may also be possible to extend Theorem 4.2 to the framework of modal logic via these logics. For example, for $\mathbf{R}$ , we expect that the condition $\mathbf{R}+\{\Diamond^{n}\top\mid n\in\omega\}\nvdash\Box\Box A\to\Box A$ works well.

Acknowledgements

This work was partly supported by JSPS KAKENHI Grant Number JP19K14586. The author would like to thank Sohei Iwata, Haruka Kogure, and Yuya Okawa for their helpful comments. The author would also like to thank the anonymous referees for their valuable comments and suggestions. In particular, the current proofs of Theorems 2.3 and 2.6 using Lemmas 2.4 and 2.7 are based on the ideas of one of the referees, which made the proofs significantly simpler and easier to understand.

References

[1] Sergei N. Artemov and Lev D. Beklemishev. Provability logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, volume 13, pages 189–360. Springer, Dordrecht, 2nd edition, 2005.
[2] George Boolos. The logic of provability. Cambridge: Cambridge University Press, 1993.
[3] Andrzej Ehrenfeucht and Solomon Feferman. Representability of recursively enumerable sets in formal theories. Archiv für Mathematische Logik und Grundlagenforschung, 5:37–41, 1961.
[4] David Guaspari. Partially conservative extensions of arithmetic. Transactions of the American Mathematical Society, 254:47–68, 1979.
[5] David Guaspari and Robert M. Solovay. Rosser sentences. Annals of Mathematical Logic, 16:81–99, 1979.
[6] Giorgi Japaridze and Dick de Jongh. The logic of provability. In Handbook of proof theory, pages 475–546. Amsterdam: Elsevier, 1998.
[7] Joost J. Joosten. Turing jumps through provability. In Evolving computability. 11th conference on computability in Europe, CiE 2015, Bucharest, Romania, June 29 – July 3, 2015. Proceedings, pages 216–225. Cham: Springer, 2015.
[8] Makoto Kikuchi and Taishi Kurahashi. Illusory models of Peano arithmetic. The Journal of Symbolic Logic, 81(3):1163–1175, 2016.
[9] Taishi Kurahashi. Henkin sentences and local reflection principles for Rosser provability. Annals of Pure and Applied Logic, 167(2):73–94, 2016.
[10] Taishi Kurahashi. Provability logics relative to a fixed extension of Peano arithmetic. The Journal of Symbolic Logic, 83(3):1229–1246, 2018.
[11] Per Lindström. Aspects of incompleteness., volume 10. Natick, MA: Association for Symbolic Logic, 2003.
[12] Krister Segerberg. An essay in classical modal logic. Vol. 1, 2, 3. Filosofiska Studier. No. 13. Uppsala: University of Uppsala., 1971.
[13] V. Yu. Shavrukov. On Rosser’s provability predicate. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 37(4):317–330, 1991.
[14] John C. Shepherdson. Representability of recursively enumerable sets in formal theories. Archiv für Mathematische Logik und Grundlagenforschung, 5:119–127, 1961.
[15] Craig Smoryński. Fifty years of self-reference in arithmetic. Notre Dame Journal of Formal Logic, 22:357–374, 1981.
[16] Robert M. Solovay. Provability interpretations of modal logic. Israel Journal of Mathematics, 25:287–304, 1976.
[17] Albert Visser. The provability logics of recursively enumerable theories extending Peano arithmetic at arbitrary theories extending Peano arithmetic. Journal of Philosophical Logic, 13:97–113, 1984.
[18] Albert Visser. Faith & falsity. Annals of Pure and Applied Logic, 131(1-3):103–131, 2005.

Some observations on the FGH theorem

Abstract

1 Introduction

Theorem 1.1 (Ehrenfeucht and Feferman).

Theorem 1.2 (The FGH theorem).

Definition 1.3 (Witness comparison notation).

2 On the form of a sentence in the FGH theorem – the case of classical propositional logic

Definition 2.1.

Proposition 2.2.

Proof.

Theorem 2.3.

Lemma 2.4.

Proof.

Proof of Theorem 2.3.

Theorem 2.5.

Theorem 2.6.

Lemma 2.7.

Proof.

Proof of Theorem 2.6.

Corollary 2.8.

Proof.

3 On the form of a sentence in the FGH theorem – the case of modal propositional logic

3.1 Preparations

Theorem 3.1.

Definition 3.2 (Arithmetical interpretations).

Fact 3.3 (Arithmetical soundness (cf. Artemov and Beklemishev [1])).

Fact 3.4 (Solovay [16]).

Fact 3.5.

Lemma 3.6.

Proof.

Definition 3.7.

Lemma 3.8.

Proof.

Lemma 3.9.

Proof.

Definition 3.10.

Proposition 3.11.

Proof.

Lemma 3.12.

Proof.

Proposition 3.13.

Proof.

3.2 A modal version of the FGH theorem

Theorem 3.14.

Proof.

Lemma 3.15.

Proof.

Lemma 3.16.

Proof.

Lemma 3.17.

Proof.

Proposition 3.18.

Proof.

Theorem 3.19.

Theorem 3.20.

Proof.

3.3 A modal version of the FGH theorem for theories with finite heights

Theorem 3.21.

Proof.

Proposition 3.22.

Proof.

Theorem 3.23.

Proof.

Problem 3.24.

Problem 3.25.

4 Rosser-type FGH theorems

Fact 4.1 (Kurahashi [9, Theorem 3.5]).

Theorem 4.2.

Proof.

Lemma 4.3.

Proof.

Lemma 4.4.

Proof.

Corollary 4.5.

Proof.

Corollary 4.6.

Proof.

Corollary 4.7.

Proof.

Proposition 4.8.

2 On the form of a sentence in the FGH theorem
– the case of classical propositional logic

3 On the form of a sentence in the FGH theorem
– the case of modal propositional logic