Introduction
IPAL — the intuitionistic public announcement logic introduced in [22, 23] — constitutes the subject of numerous discussions from the point of view of its model theory, the point of view of its proof theory, etc [26, 27]. In all these discussions, strong hypotheses concerning the birelational models (W,≤,R,V) in which the formulas are interpreted are made in order to be able to achieve four essential objectives. The first and second objectives date back to [12, 31]. They respectively consist of interpreting the modal operators □ and ◊ of “necessity” and “possibility” in the way Kripke [18] interprets the first-order quantifiers ∀ and ∃ in his definition of the possible-worlds semantics of intuitionistic first-order logic. That is to say, for all formulas C, in a birelational model (W,≤,R,V), given s∈W, □C holds at s if for all t∈W, if s≤t then for all u∈W, if tRu then C holds at u and ◊C holds at s if there exists t∈W such that sRt and C holds at t. The third objective is specific to logics based on public announcement operators [9]. It concerns the existence of reduction axioms which make it possible to associate with each formula a semantically equivalent formula containing no occurrence of these operators. For instance, the reduction axiom for atoms [A]p↔(A→p), the reduction axiom for “false” [A]⊥↔¬A, etc.1 The fourth objective — probably the most important — is specific to logics based on intuitionist implication. Indeed, it concerns the property of heredity which requires the truth sets associated to each formula to be increasing relative to the preorders which equip the birelational models. That is to say, for all formulas C, in a birelational model (W,≤,R,V), given s,t∈W such that s≤t, if C holds at s then C holds at t. To achieve these objectives, all authors without exception choose to only interpret formulas in backward and forward confluent birelational models, i.e. birelational models (W,≤,R,V) such that R∘≤⊆≤∘R and R−1∘≤⊆≤∘R−1, seeing that these hypotheses guarantee the validity of the reduction axiom for “necessity” [A]□C↔(A→□[A]C) and the property of heredity for ◊-formulas.
Today, we want to depart from the tradition by proposing a minimalist approach to IPAL for which no hypothesis about the structures underlying its model theory is made. Unfortunately, that is easier said than done, seeing that without the hypotheses of backward and forward confluence, the reduction axiom for “necessity” [A]□C↔(A→□[A]C) is no longer valid whereas the property of heredity for ◊-formulas is no longer verified. Indeed, it does not seem possible to achieve our goal without modifying the language of IPAL.5 In this article, leaving aside for the moment all considerations regarding the operator ◊ of “possibility”, we replace the operator □ of “necessity” with a new binary operator ▹ of “relativized necessity” interpreted as follows in a birelational model (W,≤,R,V): given s∈W, C▹D holds at s if for all t∈W, if s≤t then for all u∈W, if tRu and C holds at u then D holds at u. The reader may easily verify that □ is definable in terms of ▹, seeing that for all formulas D, □D holds exactly where ⊤▹D holds. More importantly, a reduction axiom for “relativized necessity” can be proposed: the reduction axiom [A](C▹D)↔(A→((A∧[A]C)▹[A]D)) whose validity does not require the hypothesis of backward confluence. Together with the modal axioms (MA1), (MA2) and (MA3) and the necessitation rule (NEC) presented in § 4 and characterizing the properties of ▹, the reduction axiom for “relativized necessity” — when added to the reduction axioms already known for atoms, for “false”, etc — makes it possible to axiomatize the validities determined by the class of all birelational models. The addition in § 4 of two other modal axioms (MA4) and (MA5) characterizing further properties of ▹ makes it possible to axiomatize the validities determined by the class of all birelational models where the modal accessibility relation is an equivalence relation.
In Sections 2 and 3, we introduce the syntax and the semantics of our version of IPAL. In § 4, we present the definitions of our intuitionistic public announcement logics Lmin and Lequ. In Section 5, we present results needed for the proofs developed in Section 6 of the completeness of Lmin with respect to validity in the class Cmin of all birelational models and the completeness of Lequ with respect to validity in the class Cequ of all birelational models where the modal accessibility relation is an equivalence relation.6 That is to say, in Section 6, we prove the following completeness results:
Proposition 10. Lmin is complete with respect to Cmin.
Proposition 12. Lequ is complete with respect to Cequ.
We assume the reader is at home with the basic tools and techniques in intuitionistic logic and modal logic. See [6, 7, 17] for more on them. See [28, 29, 34] for an introduction to intuitionistic modal logic and [9, 11, 25] for an introduction to epistemic logic and dynamic epistemic logic.
Syntax
Let At be a countably infinite set (with typical members called atoms and denoted p, q, etc). Let FOR be the countably infinite set (with typical members called formulas and denoted A, B, etc) defined as follows:
where p ranges over At. We follow the standard rules for omission of the parentheses. In particular, for all formulas A, B, C, when we write A∨B▹C, A∧B▹C, A▹B∨C and A▹B∧C, we mean (A∨B)▹C, (A∧B)▹C, A▹(B∨C) and A▹(B∧C). For all formulas A, B, we write ¬A as the abbreviation of A→⊥, A↔B as the abbreviation of (A→B)∧(B→A), □A as the abbreviation of ⊤▹A and ■A as the abbreviation of A▹⊥. Let sf:FOR→℘(FOR) be the function associating to each formula A the set sf(A) of all A’s subformulas. A formula A is simple if for all formulas B, C, B▹C∈/sf(A) and [B]C∈/sf(A). Let FORs be the set of all simple formulas. A simple substitution is a function σ:FORs→FOR such that for all simple formulas A, B, σ(⊥)=⊥, σ(⊤)=⊤, σ(A∨B)=σ(A)∨σ(B), σ(A∧B)=σ(A)∧σ(B) and σ(A→B)=σ(A)→σ(B). A formula A is direct if for all formulas B, C, if B▹C∈sf(A) then B=⊤. Let FORd be the set of all direct formulas. Obviously, direct formulas can also be considered as formulas of the language of IPAL. A formula A is modal if for all formulas B, C, [B]C∈/sf(A). Let FORm be the set of all modal formulas. Obviously, direct modal formulas can also be considered as ◊-free formulas of the language of intuitionistic modal logics developed in [12, 31, 33]. Let deg:FOR→N be the function defined as follows: deg(p)=deg(⊥)=deg(⊤)=0, deg(A∨B)=deg(A∧B)=deg(A→B)=deg(A▹B)=max{deg(A),deg(B)} and $\deg([A]B)=\deg(A)+2 ×deg(B)+1. Let ∥⋅∥:FOR⟶N be the function associating to each formula A the number ∥A∥ of occurrences of symbols in A. Let ≺ be the binary relation on FOR such that for all formulas A, B, A≺B if and only if deg(A)<deg(B), or deg(A)=deg(B) and ∥A∥<∥B∥. Obviously, ≺ is a strict order on FOR. In other respect, FOR has no infinite ≺-descending chain.
Proposition 1. For all formulas A, B, C and for all atoms p, A≺A∨B, B≺A∨B, A≺A∧B, B≺A∧B, A≺A→B, B≺A→B, A≺A▹B, B≺A▹B, A≺[A]p, A≺[A]⊥, A≺[A](B∨C), [A]B≺[A](B∨C), [A]C≺[A](B∨C), [A]B≺[A](B∧C), [A]C≺[A](B∧C), [A]B≺[A](B→C), [A]C≺[A](B→C), A≺[A](B▹C), [A]B≺[A](B▹C), [A]C≺[A](B▹C) and [A∧[A]B]C≺[A][B]C.
The intuitive reading of A▹B is “from now on, the agent knows that B holds when A holds”. As a result, the intuitive reading of □A is “from now on, the agent knows that A holds” and the intuitive reading of ■A is “from now on, the agent knows that A does not hold”. In other respect, the intuitive reading of [A]B is “from now on, B holds after it has been publicly announced that A holds”.
Semantics
A frame is a structure of the form (W,≤,R) where W is a nonempty set (with typical members denoted s, t, etc), ≤ is a preorder on W and R is a binary relation on W.7 Let Cmin be the class of all frames. Let Cequ be the class of all frames (W,≤,R) where R is an equivalence relation on W, i.e. R is reflexive, symmetric and transitive. For all frames (W,≤,R), a subset U of W is increasing if for all s,t∈W, if s∈U and s≤t then t∈U. A valuation on a frame (W,≤,R) is a function V:At⟶℘(W) such that for all atoms p, V(p) is increasing. A model is a structure of the form (W,≤,R,V) where (W,≤,R) is a frame and V:At⟶℘(W) is a valuation on (W,≤,R). Obviously, for all models (W,≤,R,V) and for all subsets U of W, if U is nonempty then the restriction of (W,≤,R,V) to U is a model. In other respect, for all models (W,≤,R,V) based on a frame in Cequ and for all subsets U of W, if U is nonempty then the restriction of (W,≤,R,V) to U is a model based on a frame in Cequ. For all formulas C, given a model (W,≤,R,V) and s∈W, the truth condition of C in (W,≤,R,V) at s (in symbols (W,≤,R,V),s⊨C) is defined as follows:8
(W,≤,R,V),s⊨p if and only if s∈V(p),
(W,≤,R,V),s⊨A→B if and only if for all t∈W, if s≤t then (W,≤,R,V),t⊨A, or (W,≤,R,V),t⊨B,
(W,≤,R,V),s⊨A▹B if and only if for all t∈W, if s≤t then for all u∈W, if tRu then (W,≤,R,V),u⊨A, or (W,≤,R,V),u⊨B,9
(W,≤,R,V),s⊨[A]B if and only if for all t∈W, if s≤t then (W,≤,R,V),t⊨A, or (W,≤,R,V)+A,t⊨B,
where (W,≤,R,V)+A denotes the restriction of (W,≤,R,V) to the set of all v∈W such that (W,≤,R,V),v⊨A. The reader may easily verify by induction on the formula C that for all models (W,≤,R,V) and for all s,t∈W, if (W,≤,R,V),s⊨C and s≤t then (W,≤,R,V),t⊨C.10
Proposition 2. Given a model (W,≤,R,V), for all s∈W and for all formulas A, B, (W,≤,R,V),s⊨¬A if and only if for all t∈W, if s≤t then (W,≤,R,V),t⊨A, (W,≤,R,V),s⊨A↔B if and only if for all t∈W, if s≤t then (W,≤,R,V),t⊨A if and only if (W,≤,R,V),t⊨B, (W,≤,R,V),s⊨□A if and only if for all t∈W, if s≤t then for all u∈W, if tRu then (W,≤,R,V),u⊨A and (W,≤,R,V),s⊨■A if and only if for all t∈W, if s≤t then for all u∈W, if tRu then (W,≤,R,V),u⊨A.11
Obviously, for all formulas A, B, for all models (W,≤,R,V) and for all s∈W, if s belongs to (W,≤,R,V)+A and (W,≤,R,V)+A,s⊨B then (W,≤,R,V),s⊨[A]B. Moreover, for all formulas A, B, for all models (W,≤,R,V) and for all s∈W, s belongs to (W,≤,R,V)+A∧[A]B if and only if s belongs to (W,≤,R,V)+A and s belongs to (W,≤,R,V)+A+B. In other respect, when these conditions hold, (W,≤,R,V)+A∧[A]B=(W,≤,R,V)+A+B. A formula C is true in a model (W,≤,R,V) (in symbols (W,≤,R,V)⊨C) if for all s∈W, s⊨C. A formula C is valid in a frame (W,≤,R) (in symbols (W,≤,R)⊨C) if for all valuations V:At→P(W) on (W,≤,R), (W,≤,R,V)⊨C. A formula C is valid on a class C of frames (in symbols C⊨C) if for all frames (W,≤,R) in C, (W,≤,R)⊨C.
Axiomatization
A logic is a set L of formulas such that
(IPL) for all simple substitutions σ:FORs→FOR and for all intuitionistically valid simple formulas A, L contains σ(A),
(MP) for all formulas A, B, if A∈L and A→B∈L then B∈L,
(MA) for all formulas A, B, C, D, L contains
(MA1) A▹A,
(MA2) (A▹C)∧(B▹C)→(A∨B▹C),
(MA3) (A▹B)∧(C▹D)→(A∧(B→C)▹D),
(NEC) for all formulas A, B, C, if A→B∈L then (C▹A)→(C▹B)∈L and (B▹C)→(A▹C)∈L,
(RA) for all formulas A, B, C and for all atoms p, L contains
(RA1) [A]p↔(A→p),
(RA2) [A]⊥↔¬A,
(RA3) [A]⊤↔⊤.
(RA4)[A](B∨C)↔(A→[A]B∨[A]C),9
(RA5)[A](B∧C)↔[A]B∧[A]C,
(RA6)[A](B→C)↔([A]B→[A]C),
(RA7)[A](B▹C)↔(A→(A∧[A]B▹[A]C)),10
(RA8)[A][B]C↔[A∧[A]B]C.
Let Σref be the least set of formulas containing all formulas of the form
(MA4)(A▹B)→(A→B),
where A, B range over FOR. Let Σsym be the least set of formulas containing all formulas of the form
(MA5)(A▹B∨(C▹D))→((D→(A▹B))→(C→(A▹B))),
where A, B, C, D range over FOR. Let Lmin be the least logic. Let Lequ be the least logic containing Σref∪Σsym. A logic L is consistent if ⊥∈/L. Obviously, for all logics L, L is consistent if and only if L=FOR. A logic L is sound with respect to a class C of frames if for all formulas A, if A∈L then C⊨A. A logic L is complete with respect to a class C of frames if for all formulas A, if C⊨A then A∈L.
Proposition 3 says that the standard rule of replacement by equivalent is admissible in any logic.
Proposition 3. Let L be a logic. For all formulas A, B, C, D, if A↔B∈L and C↔D∈L then (A∨C)↔(B∨D)∈L, (A∧C)↔(B∧D)∈L, (A→C)↔(B→D)∈L and (A▹C)↔(B▹D)∈L.
Proof. Let A, B, C, D be formulas. Suppose A↔B∈L and C↔D∈L. We only consider the last fact. Since A↔B∈L and C↔D∈L, therefore A→B∈L, B→A∈L, C→D∈L and D→C∈L. Hence, using (NEC), (A▹C)→(B▹C)∈L, (B▹C)→(B▹D)∈L, (B▹D)→(A▹D)∈L and (A▹D)→(A▹C)∈L. Thus, (A▹C)→(B▹D)∈L and (B▹D)→(A▹C)∈L. Consequently, (A▹C)↔(B▹D)∈L.
Proposition 4 says that as for public announcement logic PAL [9], reduction axioms provide in any logic, a deterministic algorithm producing given a formula, a provably equivalent modal formula.
Proposition 4. Let L be a logic. There exists a deterministic algorithm producing given a formula A, a modal formula B such that A↔B∈L.
Proof. By Proposition 1, let τ:FOR⟶FORm be the function defined as follows: τ(p)=p, τ(⊥)=⊥, τ(⊤)=⊤, τ(A∨B)=τ(A)∨τ(B), τ(A∧B)=τ(A)∧τ(B), τ(A→B)=τ(A)→τ(B), τ(A▹B)=τ(A)▹τ(B), τ([A]p)=τ(A)→p, τ([A]⊥)=¬τ(A), τ([A]⊤)=⊤, τ([A](B∨C))=τ(A)→(τ([A]B)∨τ([A]C)), τ([A](B∧C))=τ([A]B)∧τ([A]C), τ([A](B→C))=τ([A]B)→τ([A]C), τ([A](B▹C))=τ(A)→(τ(A)∧τ([A]B)▹τ([A]C)) and τ([A][B]C)=τ([A∧[A]B]C). The reader may easily verify by induction on the formula A that A↔τ(A)∈L.
Our goal is to show the equivalences “for all formulas A, A∈Lmin if and only if Cmin⊨A” and “for all formulas A, A∈Lequ if and only if Cequ⊨A”. With Propositions 5 and 6, we show the implications “for all formulas A, if A∈Lmin then Cmin⊨A” and “for all formulas A, if A∈Lequ then Cequ⊨A”. The converse implications “for all formulas A, if Cmin⊨A then A∈Lmin” and “for all formulas A, if Cequ⊨A then A∈Lequ” will be shown in Section 6 with Propositions 10 and 12.
Proposition 5 (Soundness of Lmin). Lmin is sound with respect to Cmin.
Proof. It suffices to demonstrate that (IPL), (MP), (MA1), (MA2), (MA3), (NEC) and (RA1)–(RA8) give rise to Cmin-valid formulas. We only consider the “left to right” direction of the cases of (RA7) and (RA8).
Case of (RA7): For the sake of the contradiction, suppose there exists formulas A, B, C such that [A](B▹C)→(A→(A∧[A]B▹[A]C)) is not Cmin-valid. Hence, there exists a model (W,≤,R,V) and there exists s∈W such that (W,≤,R,V),s⊨[A](B▹C), (W,≤,R,V),s⊨A and (W,≤,R,V),s⊨A∧[A]B▹[A]C. Thus, (W,≤,R,V)+A,s⊨B▹C. Moreover, there exists t∈W such that s≤t and there exists u∈W such that tRu, (W,≤,R,V),u⊨A∧[A]B and (W,≤,R,V),u⊨[A]C. Since (W,≤,R,V),s⊨A, therefore (W,≤,R,V),t⊨A.14 Moreover, (W,≤,R,V),u⊨A and (W,≤,R,V),u⊨[A]B. Consequently, (W,≤,R,V)+A,u⊨B. Since (W,≤,R,V)+A,s⊨B▹C, s≤t, tRu, (W,≤,R,V),t⊨A and (W,≤,R,V),u⊨A, therefore (W,≤,R,V)+A,u⊨C. Hence, (W,≤,R,V),u⊨[A]C: a contradiction.
Case of (RA8): For the sake of the contradiction, suppose there exists formulas A, B, C such that [A][B]C→[A∧[A]B]C is not Cmin-valid. Thus, there exists a model (W,≤,R,V) and there exists s∈W such that (W,≤,R,V),s⊨[A][B]C and (W,≤,R,V),s⊨[A∧[A]B]C. Consequently, there exists t∈W such that s≤t, (W,≤,R,V),t⊨A∧[A]B and (W,≤,R,V)+A∧[A]B,t⊨C. Hence, (W,≤,R,V),t⊨A and (W,≤,R,V)+A,t⊨[A]B. Thus, (W,≤,R,V)+A,t⊨B. Moreover, since (W,≤,R,V),s⊨[A][B]C and s≤t, therefore (W,≤,R,V)+A,t⊨[B]C. Consequently, (W,≤,R,V)+A+B,t⊨C. Since t belongs to (W,≤,R,V)+A∧[A]B, t belongs to (W,≤,R,V)+A and t belongs to (W,≤,R,V)+A+B, therefore (W,≤,R,V)+A∧[A]B=(W,≤,R,V)+A+B. Since (W,≤,R,V)+A+B, t⊨C, therefore (W,≤,R,V)+A∧[A]B,t⊨C: a contradiction.
Proposition 6 (Soundness of Lequ). Lequ is sound with respect to Cequ.
Proof. It suffices to demonstrate that (IPL), (MP), (MA1)–(MA5), (NEC) and (RA1)–(RA8) give rise to Cequ-valid formulas. We only consider the cases of (MA4) and (MA5).
Case of (MA4): For the sake of the contradiction, suppose there exists formulas A, B such that (A▹B)→(A→B) is not Cequ-valid. Hence, there exists a model (W,≤,R,V) based on a frame in Cequ and there exists s∈W such that (W,≤,R,V),s⊨A▹B, (W,≤,R,V),s⊨A and (W,≤,R,V),s⊨B. Since R is reflexive, therefore (W,≤,R,V),s⊨B: a contradiction.
Case of (MA5): For the sake of the contradiction, suppose there exists formulas A,B,C,D such that (A▹B∨(C▹D))→((D→(A▹B))→(C→(A▹B))) is not Cequ-valid. Thus, there exists a model (W,≤,R,V) based on a frame in Cequ and there exists s∈W such that (W,≤,R,V),s⊨A▹B∨(C▹D), (W,≤,R,V),s⊨D→(A▹B), (W,≤,R,V),s⊨C and (W,≤,R,V),s⊨A▹B. Consequently, there exists t∈W such that s≤t and there exists u∈W such that tRu, (W,≤,R,V),u⊨A and (W,≤,R,V),u⊨B. Since (W,≤,R,V),s⊨C, therefore (W,≤,R,V),t⊨C. Moreover, since (W,≤,R,V),s⊨A▹B∨(C▹D), therefore (W,≤,R,V),u⊨B∨(C▹D). Thus, (W,≤,R,V),u⊨B, or (W,≤,R,V),u⊨C▹D. Since (W,≤,R,V),u⊨B, therefore (W,≤,R,V),u⊨C▹D. Since R is symmetric, tRu and (W,≤,R,V),t⊨C, therefore (W,≤,R,V),t⊨D. Since (W,≤,R,V),s⊨D→(A▹B) and s≤t, therefore (W,≤,R,V),t⊨(A▹B). Since tRu and (W,≤,R,V),u⊨A, therefore (W,≤,R,V),u⊨B: a contradiction.
Theories
In this section, we provide definitions and results concerning the elements composing the canonical frame of Lmin and the canonical frame of Lequ defined in Section 6.
Let L be a consistent logic. A L-theory is a set Γ of formulas such that L⊆Γ and for all formulas A, B, if A∈Γ and A→B∈Γ then B∈Γ. A L-theory Γ is proper if ⊥∈/Γ. Obviously, for all L-theories Γ, Γ is proper if and only if Γ=FOR. A proper L-theory Γ is prime if for all formulas A, B, if A∨B∈Γ then A∈Γ, or B∈Γ. For all L-theories Γ and for all formulas A, let Γ+A={B∈FOR:A→B∈Γ}. It immediately follows from these definitions that for all L-theories Γ and for all formulas A, Γ+A is the least Lwe show with Propositions 7 and 8 results that will play for Lmin and for Lequ the role played by the Existence Lemma in classical modal logic [6 Lemma 4.20].
Proposition 7. For all L-theories Γ and for all formulas A, B, if A▹B∈/Γ then there exists a prime L-theory Δ such that (i) for all formulas C, D, if C▹D∈Γ then C∈/Δ, or D∈Δ, (ii) A∈Δ and (iii) B∈/Δ.
Proof. 15 Let Γ be a L-theory and A, B be formulas. Suppose A▹B∈/Γ. Notice that using (MA1), B▹B∈Γ. Let S={(Δ,Λ):Δ is a L-theory and Λ is a set of formulas such that for all C∈Δ, for all n∈N and for all D1,…,Dn∈Λ, C▹(D1∨…(Dn∨⊥)…)∈/Γ, A∈Δ and B∈Λ}.
We claim that (L+A,{B})∈S. If not, there exists C∈L+A, there exists n∈N and there exists D1,…,Dn∈{B} such that C▹(D1∨…(Dn∨⊥)…)∈Γ. Hence, A→C∈L. Moreover, (D1∨…(Dn∨⊥)…)→B∈L. Thus, using (NEC), (C▹(D1∨…(Dn∨⊥)…))→(A▹(D1∨…(Dn∨⊥)…))∈L and (A▹(D1∨…(Dn∨⊥)…))→(A▹B)∈L. Consequently, (C▹(D1∨…(Dn∨⊥)…))→(A▹B)∈L. Since C▹(D1∨…(Dn∨⊥)…)∈Γ, therefore A▹B∈Γ: a contradiction. Therefore (L+A,{B})∈S. Hence, S is nonempty. Moreover, obviously, for all nonempty chains (Δi,Λi)i∈I of elements of S, (⋃{Δi:i∈I},⋃{Λi:i∈I}) is an element of S. Thus, by Kuratowski-Zorn Lemma, S possesses a maximal element (Δ,Λ). Consequently, Δ is a L-theory and Λ is a set of formulas such that
(∗) for all C∈Δ, for all n∈N and for all D1,…,Dn∈Λ, C▹(D1∨…(Dn∨⊥)…)∈/Γ,
(∗∗) A∈Δ,
(∗∗∗) B∈Λ.
We claim that Δ is proper. If not, Δ=FOR. Hence, B∈Δ. Since (∗) and (∗∗∗), therefore B▹B∈/Γ: a contradiction. Therefore Δ is proper.
We claim that Δ is prime. If not, there exists formulas E, F such that E∨F∈Δ, E∈/Δ and F∈/Δ. Thus, by the maximality of (Δ,Λ) in S, (Δ+E,Λ)∈/S and (Δ+F,Λ)∈/S. Consequently, there exists C′∈Δ+E, there exists n′∈N and there exists D1′,…,Dn′′∈Λ such that C′▹(D1′∨…(Dn′′∨⊥)…)∈Γ and there exists C′′∈Δ+F, there exists n′′∈N and there exists D1′′,…,Dn′′′′∈Λ such that C′′▹(D1′′∨…(Dn′′′′∨⊥)…)∈Γ. Hence, E→C′∈Δ and F→C′′∈Δ. Thus, E∨F→C′∨C′′∈Δ. Since E∨F∈Δ, therefore C′∨C′′∈Δ. Since (D1′∨…(Dn′′∨⊥)…)→(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…)∈L and (D1′′∨…(Dn′′′′∨⊥)…)→(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…)∈L, therefore using (NEC), (C′▹(D1′∨…(Dn′′∨⊥)…))→(C′▹(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…))∈L and (C′′▹(D1′′∨…(Dn′′′′∨⊥)…))→(C′′▹(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…))∈L. Since C′▹(D1′∨…(Dn′′∨⊥)…)∈Γ and C′′▹(D1′′∨…(Dn′′′′∨⊥)…)∈Γ, therefore C′▹(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…)∈Γ and C′′▹(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…)∈Γ. Consequently, using (MA2), C′∨C′′▹(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…)∈Γ. Since (∗), D1′,…,Dn′′∈Λ, D1′′,…,Dn′′′′∈Λ and C′∨C′′∈Δ, therefore C′∨C′′▹(D1′∨…(Dn′′∨(D1′′∨…(Dn′′′′∨⊥)…))…)∈/Γ: a contradiction.
We claim that for all formulas C, D, if C▹D∈Γ then C∈/Δ, or D∈Δ. If not, there exists formulas C,D such that C▹D∈Γ, C∈Δ and D∈/Δ. Hence, by the maximality of (Δ,Λ) in S, (Δ+D,Λ)∈/S. Thus, there exists C′∈Δ+D, there exists n′∈N and there exists D1′,…,Dn′′∈Λ such that C′▹(D1′∨…(Dn′′∨⊥)…)∈Γ. Consequently, D→C′∈Δ. Since C∈Δ, therefore C∧(D→C′)∈Δ. Since (∗) and D1′,…,Dn′′∈Λ, therefore C∧(D→C′)▹(D1′∨…(Dn′′∨⊥)…)∈/Γ. Since C▹D∈Γ and C′▹(D1′∨…(Dn′′∨⊥)…)∈Γ, therefore using (MA3), C∧(D→C′)▹(D1′∨…(Dn′′∨⊥)…)∈Γ: a contradiction.
We claim that B∈/Δ. If not, since (∗) and (∗∗∗), therefore B▹B∈/Γ: a contradiction. Therefore B∈/Δ.
Proposition 8. If L contains Lequ then for all L-theories Γ and for all formulas A,B, if A▹B∈/Γ then there exists a prime L-theory Δ such that Γ⊆Δ and there exists a prime L-theory Λ such that (i) for all formulas C,D, if C▹D∈Δ then C∈/Λ, or D∈Λ, (ii) for all formulas C,D, if C▹D∈Λ then C∈/Δ, or D∈Δ, (iii) A∈Λ and (iv) B∈/Λ.
Proof. 16 Suppose L contains Lequ. Let Γ be a L-theory and A,B be formulas. Suppose A▹B∈/Γ. Let S={Δ:Δ is a L-theory such that Γ⊆Δ and A▹B∈/Δ}. Since A▹B∈/Γ, therefore Γ∈S. Hence, S is nonempty. Moreover, obviously, for all non-empty chains (Δi)i∈I of elements of S, ⋃{Δi:i∈I} is an element of S. Thus, by Kuratowski-Zorn Lemma, S possesses a maximal element Δ. Consequently, Δ is a L-theory such that Γ⊆Δ and A▹B∈/Δ. Imitating the standard results about theories in intuitionistic propositional logic, the reader may easily demonstrate that Δ is proper and prime. Notice that using (MA1), B▹B∈Δ. Let T={(Λ,Θ):Λ is a L-theory and Θ is a set of formulas such that for all C∈Λ, for all n∈N and for all D1,…,Dn∈Θ, C▹(D1∨…(Dn∨⊥)…)∈/Δ, for all C∈Δ and for all D∈FOR∖Δ, C▹D∈Θ, A∈Λ and B∈Θ}.
We claim that (L+A,{B}∪{C▹D:C∈Δ and D∈FOR∖Δ})∈T. If not, there exists E∈L+A, there exists n∈N and there exists F1,…,Fn∈{B}∪{C▹D:C∈Δ and D∈FOR∖Δ} such that E▹(F1∨…(Fn∨⊥)…)∈Δ. Hence, A→E∈L. Moreover, there exists n′∈N, there exists C1,…,Cn′∈Δ and there exists D1,…,Dn′∈FOR∖Δ such that (F1∨…(Fn∨⊥)…)→B∨((C1▹D1)∨…((Cn′▹Dn′)∨⊥)…)∈L. Thus, using (NEC), (E▹(F1∨…(Fn∨⊥)…))→(A▹(F1∨…(Fn∨⊥)…))∈L. Moreover, (C1∧…(Cn′∧⊤)…)∈Δ and (D1∨…(Dn′∨⊥)…)∈/Δ. Consequently, by the maximality of Δ in S, Δ+(D1∨…(Dn′∨⊥)…)∈/S. Hence, A▹B∈Δ+(D1∨…(Dn′∨⊥)…). Thus, (D1∨…(Dn′∨⊥)…)→(A▹B)∈Δ. Since for all k∈(n′), (C1∧…(Cn′∧⊤)…)→Ck∈L and Dk→(D1∨…(Dn′∨⊥)…)∈L, therefore using (NEC), for all k∈(n′), (Ck▹Dk)→((C1∧…(Cn′∧⊤)…)▹(D1∨…(Dn′∨⊥)…))∈L. Since (F1∨…(Fn∨⊥)…)→B∨((C1▹D1)∨…((Cn′▹Dn′)∨⊥)…)∈L, therefore (F1∨…(Fn∨⊥)…)→B∨((C1∧…(Cn′∧⊤)…)▹(D1∨…(Dn′∨⊥)…))∈L. As a result, using (NEC), (A▹(F1∨…(Fn∨⊥)…))→(A▹B∨((C1∧…(Cn′∧⊤)…)▹(D1∨…(Dn′∨⊥)…)))∈L. Since E▹(F1∨…(Fn∨⊥)…)∈Δ and (E▹(F1∨…(Fn∨⊥)…))→(A▹(F1∨…(Fn∨⊥)…))∈L, therefore A▹B∨((C1∧…(Cn′∧⊤)…)▹(D1∨…(Dn′∨⊥)…))∈Δ. Hence, using (MA5), ((D1∨…(Dn′∨⊥)…)→(A▹ B)→((C1∧⋯(Cn′∧⊤)⋯)→(A▹B))∈Δ. Since (D1∨⋯(Dn′∨⊥)⋯)→(A▹B)∈Δ, therefore (C1∧⋯(Cn′∧⊤)⋯)→(A▹B)∈Δ. Since (C1∧⋯(Cn′∧⊤)⋯)∈Δ, therefore A▹B∈Δ: a contradiction. Therefore (L+A,{B}∪{C▹D:C∈Δ and D∈FOR∖Δ})∈T. Thus, T is nonempty. Moreover, obviously, for all nonempty chains (Λi,Θi)i∈I of elements of T, (⋃{Λi:i∈I},⋃{Θi:i∈I}) is an element of T. Consequently, by Kuratowski-Zorn Lemma, T possesses a maximal element (Λ,Θ). Hence, Λ is a L-theory and Θ is a set of formulas such that
(∗) for all C∈Λ, for all n∈N and for all D1,…,Dn∈Θ, C▹(D1∨⋯(Dn∨⊥)⋯)∈/Δ,
(∗∗) for all C∈Δ and for all D∈FOR∖Δ, C▹D∈Θ,
(∗∗∗) A∈Λ and (∗∗∗∗) B∈Θ.
We claim that Λ is proper. If not, Λ=FOR. Thus, B∈Λ. Since (∗) and (∗∗∗∗), therefore B▹B∈/Δ: a contradiction. Therefore Λ is proper.
We claim that Λ is prime. If not, there exists formulas G, H such that G∨H∈Λ, G∈/Λ and H∈/Λ. Consequently, by the maximality of (Λ,Θ) in T, (Λ+G,Θ)∈/T and (Λ+H,Θ)∈/T. Hence, there exists C′∈Λ+G, there exists n′∈N and there exists D1′,…,Dn′′∈Θ such that C′▹(D1′∨⋯(Dn′′∨⊥)⋯)∈Δ and there exists C′′∈Λ+H, there exists n′′∈N and there exists D1′′,…,Dn′′′′∈Θ such that C′′▹(D1′′∨⋯(Dn′′′′∨⊥)⋯)∈Δ. Thus, G→C′∈Λ and H→C′′∈Λ. Consequently, G∨H→C′∨C′′∈Λ. Since G∨H∈Λ, therefore C′∨C′′∈Λ. Since (D1′∨⋯(Dn′′∨⊥)⋯)→(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯)∈L and (D1′′∨⋯(Dn′′′′∨⊥)⋯)→(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯)∈L, therefore using (NEC), (C′▹(D1′∨⋯(Dn′′∨⊥)⋯))→(C′▹(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯))∈L and (C′′▹(D1′′∨⋯(Dn′′′′∨⊥)⋯))→(C′′▹(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯))∈L. Since C′▹(D1′∨⋯(Dn′′∨⊥)⋯)∈Δ and C′′▹(D1′′∨⋯(Dn′′′′∨⊥)⋯)∈Δ, therefore C′▹(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯)∈Δ and C′′▹(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯)∈Δ. Hence, using (MA2), C′∨C′′▹(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯)∈Δ. Since (∗), D1′,…,Dn′′∈Θ, D1′′,…,Dn′′′′∈Θ and C′∨C′′∈Λ, therefore C′∨C′′▹(D1′∨⋯(Dn′′∨(D1′′∨⋯(Dn′′′′∨⊥)⋯))⋯)∈/Δ: a contradiction. Therefore Λ is prime.
We claim that for all formulas C, D, if C▹D∈Δ then C∈/Λ, or D∈Λ. If not, there exists formulas C, D such that C▹D∈Δ, C∈Λ and D∈/Λ. Thus, by the maximality of (Λ,Θ) in T, (Λ+D,Θ)∈/T. Consequently, there exists C′∈Λ+D, there exists n′∈N and there exists D1′,…,Dn′′∈Θ such that C′▹(D1′∨⋯(Dn′′∨⊥)⋯)∈Δ. Hence, D→C′∈Λ. Since C∈Λ, therefore C∧(D→C′)∈Λ. Since (∗) and D1′,…,Dn′′∈Θ, therefore C∧(D→C′)▹(D1′∨⋯(Dn′′∨⊥)⋯)∈/Δ. Since C▹D∈Δ and C′▹(D1′∨⋯(Dn′′∨⊥)⋯)∈Δ, using (MA3), C∧(D→C′)▹(D1′∨⋯(Dn′′∨⊥)⋯)∈Δ: a contradiction. Therefore for all formulas C, D, if C▹D∈Δ then C∈/Λ, or D∈Λ.
We claim that for all formulas C, D, if C▹D∈Λ then C∈/Δ, or D∈Δ. If not, there exists formulas C, D such that C▹D∈Λ, C∈Δ and D∈/Δ. Notice that using (MA1), (C▹D)▹(C▹D). Since (∗), C∈Δ and D∈/Δ, therefore C▹D∈/Δ. Since (∗) and C▹D∈Λ, therefore (C▹D)▹(C▹D)∈/Δ: a contradiction. Therefore for all formulas C, D, if C▹D∈Λ then C∈/Δ, or D∈Δ.
We claim that B∈/Λ. If not, since (∗) and (∗∗∗∗), therefore B▹B∈/Δ: a contradiction. Therefore B∈/Λ.
Completeness
Now, we are ready to show the completeness of Lmin and the completeness of Lequ. With this aim, we introduce the canonical model (Wmin,≤min,Rmin,Vmin) for Lmin and the canonical model (Wequ,≤equ,Requ,Vequ) for Lequ. With Propositions 9 and 11, we show results that will play for Lmin and for Lequ the role played by the Truth Lemma in classical modal logic [6 Lemma 4.21].
Firstly, we consider the proof of completeness of Lmin.
The canonical frame of Lmin is the structure (Wmin,≤min,Rmin) where Wmin is the nonempty set of all prime Lmin-theories, ≤min is the preorder on Wmin such that for all Γ,Δ∈Wmin, Γ≤minΔ if and only if Γ⊆Δ and Rmin is the binary relation on Wmin such that for all Γ,Δ∈Wmin, ΓRminΔ if and only if for all formulas A,B, if A▹B∈Γ then A∈/Δ, or B∈Δ. The canonical valuation of Lmin is the valuation Vmin:At→℘(Wmin) on (Wmin,≤min,Rmin) such that for all atoms p, Vmin(p)={Γ∈Wmin:p∈Γ}. The model (Wmin,≤min,Rmin,Vmin) is called canonical model of Lmin.
Proposition 9. Let A be a modal formula. For all Γ∈Wmin, (Wmin,≤min,Rmin,Vmin),Γ⊨A if and only if A∈Γ.
Proof. By induction on A. We only consider the “left to right” direction of the case A=B▹C. Let Γ∈Wmin. Suppose (Wmin,≤min,Rmin,Vmin),Γ⊨B▹C. For the sake of the contradiction, suppose B▹C∈/Γ. Consequently, by Proposition 7, there exists a prime L-theory Δ such that for all formulas D,E, if D▹E∈Γ then D∈/Δ, or E∈Δ, B∈Δ and C∈/Δ. Hence, Δ∈Wmin and ΓRminΔ. Since B∈Δ and C∈/Δ, therefore by induction hypothesis, (Wmin,≤min,Rmin,Vmin),Δ⊨B and (Wmin,≤min,Rmin,Vmin),Δ⊨C. Since (Wmin,≤min,Rmin,Vmin),Γ⊨B▹C and ΓRminΔ, therefore (Wmin,≤min,Rmin,Vmin),Δ⊨C: a contradiction.
Proposition 10 (Completeness of Lmin). Lmin is complete with respect to Cmin.
Proof. For the sake of the contradiction, suppose Lmin is not complete with respect to Cmin. Hence, there exists a formula A such that Cmin⊨A and A∈/Lmin. Thus, by Propositions 4 and 5, Cmin⊨τ(A) and τ(A)∈/Lmin. Consequently, by Proposition 9, there exists a prime Lmin-theory Γ such that (Wmin,≤min,Rmin,Vmin),Γ⊨τ(A). Hence, Cmin⊨τ(A): a contradiction. Therefore Lmin is complete with respect to Cmin.
Secondly, we consider the proof of completeness of Lequ.
The canonical frame of Lequ is the structure (Wequ,≤equ,Requ) where Wequ is the nonempty set of all prime Lequ-theories, ≤equ is the preorder on Wequ such that for all Γ,Δ∈Wequ, Γ≤equΔ if and only if Γ⊆Δ and Requ is the reflexive symmetric binary relation on Wequ such that for all Γ,Δ∈Wequ, ΓRequΔ if and only if for all formulas A,B, if A▹B∈Γ then A∈/Δ, or B∈Δ and for all formulas A,B, if A▹B∈Δ then A∈/Γ, or B∈Γ.17 The canonical valuation of Lequ is the valuation Vequ:At→℘(Wequ) on (Wequ,≤equ,Requ) such that for all atoms p, Vequ(p)={Γ∈Wequ:p∈Γ}. The model (Wequ,≤equ,Requ,Vequ) is called canonical model of Lequ.
Proposition 11. Let A be a modal formula. For all Γ∈Wequ, (Wequ,≤equ,Requ,Vequ),Γ⊨A if and only if A∈Γ.
Proof. Similar to the proof of Proposition 9 where the use of Proposition 7 is replaced by a use of Proposition 8.
Proposition 12 (Completeness of Lequ). Lequ is complete with respect to Cequ.
Proof. For the sake of the contradiction, suppose Lequ is not complete with respect to Cequ. Hence, there exists a formula A such that Cequ⊨A and A∈/Lequ. Thus, by Propositions 4 and 6, Cequ⊨τ(A) and τ(A)∈/Lequ. Consequently, by Proposition 11, there exists a prime Lequ-theory Γ such that (Wequ,≤equ,Requ,Vequ),Γ⊨τ(A). As mentioned above, Requ is a reflexive symmetric binary relation on Wequ. Unfortunately, there is no reason to believe that Requ is an equivalence relation on Wequ. Let (W′,≤′,R′) be the frame where W′ is the nonempty set of all couples of the form (Δ,{Λ,Θ}) where Δ,Λ,Θ∈Wequ are such that Δ∈{Λ,Θ} and ΛRequΘ, ≤′ is the preorder on W′ such that for all (Δ,{Λ,Θ}),(Φ,{Ψ,Π})∈W′, (Δ,{Λ,Θ})≤′(Φ,{Ψ,Π}) if and only if Δ≤equΦ and R′ is the equivalence relation on W′ such that for all (Δ,{Λ,Θ}),(Φ,{Ψ,Π})∈W′, (Δ,{Λ,Θ})R′(Φ,{Ψ,Π}) if and only if {Λ,Θ}={Ψ,Π}. Let V′:At→℘(W′) be the valuation on (W′,≤′,R′) such that for all atoms p, V′(p)={(Δ,{Λ,Θ})∈W′:p∈Δ}.
Lemma. Let B be a modal formula. For all (Δ,{Λ,Θ})∈W′, (W′,≤′,R′,V′),(Δ,{Λ,Θ})⊨B if and only if (Wequ,≤equ,Requ,Vequ),Δ⊨B.
Proof. By induction on B. We only consider the “left to right” direction of the case B=C▹D. Let (Δ,{Λ,Θ})∈W′. Suppose (W′,≤′,R′,V′),(Δ,{Λ,Θ})⊨C▹D. For the sake of the contradiction, suppose (Wequ,≤equ,Requ,Vequ),Δ⊨C▹D. Hence, there exists Φ∈Wequ such that Δ≤equΦ and there exists Ψ∈Wequ such that ΦRequΨ, (Wequ,≤equ,Requ,Vequ),Ψ⊨C and (Wequ,≤equ,Requ,Vequ),Ψ⊨D. Obviously, (Φ,{Φ,Ψ}) and (Ψ,{Φ,Ψ}) are in W′. Moreover, (Δ,{Λ,Θ})≤′(Φ,{Φ,Ψ}) and (Φ,{Φ,Ψ})R′(Ψ,{Φ,Ψ}). Since (Wequ,≤equ,Requ,Vequ),Ψ⊨C and (Wequ,≤equ,Requ,Vequ),Ψ⊨D, therefore by induction hypothesis, (W′,≤′,R′,V′),(Ψ,{Φ,Ψ})⊨C and (W′,≤′,R′,V′),(Ψ,{Φ,Ψ})⊨D. Since (Δ,{Λ,Θ})≤′(Φ,{Φ,Ψ}) and (Φ,{Φ,Ψ})R′(Ψ,{Φ,Ψ}), therefore (W′,≤′,R′,V′),(Δ,{Λ,Θ})⊨C▹D: a contradiction.
Since (Wequ,≤equ,Requ,Vequ),Γ⊨τ(A), then (W′,≤′,R′,V′),(Γ,{Γ})⊨τ(A). Thus, Cequ⊨τ(A): a contradiction. Therefore Lequ is complete with respect to Cequ.
And in the end, we compare Lmin and Lequ to the intuitionistic public announcement logics studied in [22, 23].
Proposition 13. (1) Lmin∩FORd is strictly contained in IPAL interpreted over the class of all backward and forward confluent models,
(2) Lequ∩FORd is strictly contained in IPAL interpreted over the class of all backward and forward confluent models where the modal accessibility relation is an equivalence relation.
Proof. (1) It suffices to notice that the instance [p]□r↔(p→□[p]r) of the reduction axiom for “necessity” [A]□C↔(A→□[A]C) considered in the literature of IPAL is not valid in the class of all models. Indeed, the reader may easily verify that 0⊨[p]□r and 0⊨p→□[p]r in the model (W,≤,R,V) such that W={0,1,2}, ≤={(0,0),(1,1),(1,2),(2,2)}, R={(0,0),(0,1),(1,0),(1,1),(2,2)}, V(p)={0,2} and V(r)={0}.
(2) Similar to the proof of Item (1).
Conclusion
Much remains to be done.
First, recall that direct modal formulas can also be considered as ◊-free formulas of the language of intuitionistic modal logics. In particular, the restriction of Lmin to the set of all its direct modal formulas is equal to the so-called “intuitionistic modal logic K without ◊” considered by Simpson [33 Chapter 3], an intuitionistic modal logic called iK by Almeida et al. [1] and van der Giessen [13]. Therefore the restriction of Lmin to the set of all its modal formulas deserves to be studied for its own sake. In doing so, one should not forget to compare the new binary operator ▹ of “relativized necessity” and the connective of strict implication firstly developed in [20] and recently studied in [14, 21].
Second, recall that the dual ◊ of □ introduced by Pˇrenosil [32] and developed by Balbiani and Gencer [4, 5] is such that for all formulas A, given a model (W,≤,R,V) and s∈W, (W,≤,R,V),s⊨◊A if and only if there exists t∈W such that t≤s and there exists u∈W such that tRu and (W,≤,R,V),u⊨A. Therefore the extension of Lmin by the dual ◃ of ▹ deserves to be studied for its own sake. It could be such that for all formulas A, B, given a model (W,≤,R,V) and s∈W, (W,≤,R,V),s⊨A◃B if and only if there exists t∈W such that t≤s and there exists u∈W such that tRu, (W,≤,R,V),u⊨A and (W,≤,R,V),u⊨B.
Third, in order to evaluate the computability of Lmin and the computability of Lequ, one may design tableau calculi or sequent calculi for these intuitionistic public announcement logics, following the lines of reasoning adopted in [2, 19] with respect to the classical setting and in [3, 8, 27] with respect to the intuitionistic setting. Calculi for the restrictions of Lmin and Lequ to the sets of all their modal formulas deserve to be studied for their own sake as well.
Fourth, one may develop the multi-agent version with common knowledge, or distributed knowledge of Lmin and Lequ. In this multi-agent version, one has to determine which reduction axioms make it possible to associate with each formula a semantically equivalent formula containing no public announcement operators. See [16, 26, 35, 36] for various multi-agent version with common knowledge, or distributed knowledge of intuitionistic modal logics.
Fifth, in a multi-agent version with common knowledge, or distributed knowledge of Lmin and Lequ, a successful announcement is a formula that always becomes known after being announced. Many dynamic phenomena can be explained by analyzing successful announcements [10]. As a result, one may investigate the syntactic characterization of the successful announcements within the context of intuitionistic public announcement logic.
Acknowledgements
Special acknowledgement is granted to our colleagues of the Toulouse Institute of Computer Science Research for many stimulating discussions about the subject of this article. We also thank the reviewers for their feedback: their insightful suggestions were essential in improving the readability of an earlier version of this work.