Non-finite Axiomatizability and Undecidability of $\mathsf{Cheq}$

1 Introduction

• Whether the logic of chequered subsets L∞ is finitely axiomatizable is a longstanding open problem, and it is important in the study of modal logics of topological spaces.L∞ was introduced in 2003 by van Benthem, Guram Bezhanishvili, and Gehrke [38].Source: §1 · p. 1
• Litak denoted the intermediate analogue by Cheq and established several of its properties, including that Cheq is contained in Medvedev logic Med.Fontaine later proved that Med is not finitely axiomatizable over Cheq, while Shatrov’s claimed proof that Cheq is not finitely axiomatizable was never published.Source: §1 · p. 1
• L∞ also arises in research on modal logics of forcing, including the study of modal logics of c.c.c. forcing.The introduction notes prior work placing the modal logic of c.c.c. forcing inside S4.FPFA under an additional set-theoretical assumption.Source: §1 · p. 1

1.1 Outline of the paper

• The paper outlines a self-contained proof that Cheq is not finitely axiomatizable and a result showing that Med undecidability implies Cheq undecidability.It also discusses modal companions and earlier strategies for the non-finite axiomatizability problem.Source: §1.1 · p. 2

2 Definitions

• The paper assumes familiarity with intermediate and modal logics, uses IPC for intuitionistic propositional calculus, and considers finite posets as frames.Source: §2 · p. 2

2.1 Posets as Kripke frames

• A poset’s generated subframes, roots, depth, and branching degree provide terminology for describing its structure.A generated subframe is upward closed; the depth of a frame is the length of its longest chain.Source: §2.1 · p. 2

2.2 Morphisms

• A p-morphism preserves the order structure, and an onto p-morphism makes the target a p-morphic image of the source.For models, the valuation must also agree under the map; truth is preserved across p-morphic images.Source: §2.2 · pp. 2–3

2.3 Modal companions

• Modal companions relate an intermediate logic to modal extensions of S4 via the Gödel translation, with least and greatest companions described by τ and σ.The modal logic L∞ is the greatest companion of Cheq, while S4.FPFA is its least companion; finite axiomatizability transfers between an intermediate logic and its greatest companion.Source: §2.3 · pp. 3–4

2.4 Friedman translation

• Friedman translation relativizes formulas to a formula ρ, and pruning points that force ρ makes the translated formula correspond to the original formula on the resulting submodel.Source: §2.4 · p. 4

2.5 The logic Cheq

• Cheq is characterized by the class of finite products Vn of the two-fork frame, and the section identifies the partial-function algebras An with those frames.The proof defines a map from An to Vn and establishes that it is an isomorphism.Source: §2.5 · pp. 4–5

3.1 Medvedev logic

• Med is the logic of all Medvedev frames, whose points are nonempty subsets of [n] ordered by reverse inclusion.A Medvedev frame is obtained from the n-fold product of the 2-chain by removing its greatest element.Source: §3.1 · p. 5, §3.3 · p. 6

3.2 Inamdar logic

• Inam is the logic of spiked Boolean algebras, formed by adding a spike node {js} corresponding to each co-atom {j}.Each added node lies above exactly the Boolean-algebra nodes lying below its corresponding co-atom.Source: §3.2 · p. 5

3.3 Generalized Medvedev logics

• Generalized Medvedev logics arise from topless products of non-singleton finite rooted frames with a top.The section frames this class as extending the topless-product perspective on Medvedev logic.Source: §3.3 · p. 6

3.4 Comparison of the relevant logics

• S4.FPFA is strictly included in both S4.tBA and S4.sBA, while neither S4.tBA nor S4.sBA contains the other.The section proves the two strict inclusions separately and gives a formula distinguishing S4.tBA from S4.sBA.Source: §3.4 · pp. 8–9
• Cheq is contained in both Med and Inam, and L∞ is contained in both tBA and sBA.The modal companion S4.FPFA is also contained in both S4.tBA and S4.sBA.Source: §3.4 · p. 10
• The Bowtie Lemma states that for any finite rooted frame F, F ⊕ W is a p-morphic image of some Vn.The lemma is identified as a tool for analyzing finite Cheq-frames.Source: §3.4 · p. 10

4 Geometric perspective

• V_n and P_0(n) are respectively dual face posets of the n-cube and n-simplex.The section also characterizes the n-cube face lattice by its size, number of atoms, atomisticity, and a unique complementary atom for each atom.Source: §4 · p. 11

4.1 Polychromatic colorings of n-cube

• A G-polychromatic coloring assigns colors to hypercube edges so every embedded copy of G contains every color; Offner gives the exact polychromatic number for Q_d.This coloring framework underlies the strategies discussed in the following subsections.Source: §4.1 · p. 11

4.2 Fontaine’s structures and Shatrov’s structures

• A 3-full partition of D(i,1) relative to D(i,2) would make Fon_m a Cheq-frame for every m and imply that Cheq is not finitely axiomatizable.Fontaine's construction extends such a partition at depth 1 to partitions at every higher depth.Source: §4.2 · p. 13
• For sufficiently large N, Q_N cannot have a Q_2-polychromatic 3-coloring, so the partition assumption required by Fontaine's proposition fails.The partition condition would require a 3-coloring in which every face contains every color.Source: §4.2 · p. 13
• The proposed 4-full-partition route for Shatrov's frames fails because p(Q_2)=2, and his unpublished proof leaves its concrete assumptions unknown.Shatrov's strategy concerned showing that the relevant frames are Cheq-frames.Source: §4.2 · pp. 13–14

4.3 Kuznetsov’s alternative

• Every Kuznetsov frame E_s is a Cheq-frame, contrary to the proposed strategy of showing these frames are not Cheq-frames.The proof uses the Bowtie Lemma and the fact that E_s is a linear sum of a finite rooted frame and the Bowtie frame.Source: §4.3 · p. 14

• The construction draws on Vn’s combinatorics, coloring points by parity counts of w1 on either side of the w0 sequence.The map’s definition also distinguishes cases by the number of w0 symbols and the parity of the relevant counts.Source: §5 · pp. 14–16
• For every s ≥2, C2s−1+1,2s is a Cheq-frame because it is a p-morphic image of V2s−1+1.The construction defines a map from V2s−1+1 onto the target frame and verifies its order behavior.Source: §5 · pp. 15–16
• The frame Cs,2×3^s is not a Cheq-frame: its root exceeds the branching bound for p-morphic images of Vn.The bound applies to finite frames that are p-morphic images of some Vn.Source: §5 · pp. 16–17
• Cheq is not finitely axiomatizable, and L∞ is not finitely axiomatizable as well.The proof rules out an axiomatization of Cheq using any fixed finite number of variables.Source: §5 · p. 17
• A fixed s-variable axiom would fail on a frame with many red points, then remain refuted as the points are successively identified, contradicting the Cheq-frame family.The argument uses the pigeonhole principle to find red points agreeing on all s variables, reduces their number, and reaches C2s−1+1,2s.Source: §5 · pp. 15, 17

6.1 Reduction

• Geometrically, the construction carves a simplex from a subhypercube or uses a simplex to reconstruct a hypercube.The paper describes the Friedman translation as making φ and φψ0 correspond to different geometric objects.Source: §6.1 · p. 17
• The paper suggests extending this translation approach to logics characterized by geometric objects, reducing their undecidability to that of known logics such as Med and Cheq.Source: §6.1 · p. 18
• The translation C(φ) = (φψ0 →ψ1) →ψ1 satisfies φ ∈Med iff C(φ) ∈Cheq.The proof establishes the equivalence by constructing countermodels in both directions.Source: §6.1 · pp. 17–18
• If Med is undecidable, then Cheq is undecidable and, by its finite model property, is not finitely axiomatizable.The paper also proves directly that Cheq is undecidable.Source: §6.1 · p. 18