A note on Grigoriev and Zaitsev's system CNL$^2_4$

Basic Information

• Paper ID: 2501.00500
• Title: A note on Grigoriev and Zaitsev's system CNL$^2_4$
• Authors: Hitoshi Omori (Tohoku University), Jonas R. B. Arenhart (Federal University of Santa Catarina)
• Classification: cs.LO (Logic)
• Publication Time/Conference: NCL'24 (Non-Classical Logics Theory and Applications), EPTCS 415, 2024
• Paper Link: https://arxiv.org/abs/2501.00500

Abstract

This paper provides an in-depth investigation of the four-valued logical system CNL$^2_4$ recently proposed by Oleg Grigoriev and Dmitry Zaitsev. The authors not only clarify the connections between this system and related systems developed by Paul Ruet and Norihiro Kamide, but also discuss two important philosophical issues that emerge: the first is the "Haackian theme"—how to understand the meaning of connectives and the nature of truth values in multi-valued logics; the second is a deepening of the "Carnap problem"—the same proof system can admit at least four distinct and incompatible interpretations.

Research Background and Motivation

Core Issues

1. Intelligibility of Connective Meaning: How to make classical logicians understand the meaning of non-classical connectives and the nature of truth values in multi-valued logical systems.
2. Semantic Indeterminacy Problem: A single formal system may admit multiple incompatible semantic interpretations, leading to indeterminacy of meaning.

Research Significance

• Non-classical logical systems deviate from classical standards, yet we need to maintain understanding of connectives and logical consequence relations
• Susan Haack's strategy: eliminating the mystique of non-classical systems by providing "quasi-classical" interpretations
• Exploring the relationship between formal systems and their interpretations, a core issue in the philosophy of logic

Limitations of Existing Approaches

• Lack of systematic analysis of the relationship between CNL$^2_4$ and other related four-valued logical systems
• Insufficient philosophical discussion of the multiple interpretation problem
• Need for better strategies to enhance the intelligibility of non-classical logical systems

Core Contributions

1. Provided a natural deduction proof system for CNL$^2_4$ and proved its soundness and completeness
2. Proved definitional completeness and Post completeness of CNL$^2_4$
3. Revealed four distinct interpretations of CNL$^2_4$, each corresponding to different semantic understandings
4. Established precise connections between CNL$^2_4$ and the Ruet and Kamide systems
5. Provided in-depth analysis of how the "Carnap problem" and "Haackian theme" manifest in this system
6. Proposed relational semantics methods to enhance classical intelligibility of the system

Detailed Methodology

System Definition

Language: The language L of CNL$^2_4$ contains:

• Set of connectives: {∼, ∧, ∨}
• Countable set of propositional variables: Prop

Semantics:

• Four truth values: {1, i, j, 0}
• Interpretation function: I: Prop → {1, i, j, 0}
• Designated value set: D = {1, i}

Truth Tables:

A  ∼A     A∧B  1 i j 0     A∨B  1 i j 0
1   i      1   1 i j 0      1   1 1 1 1
i   0      i   i i 0 0      i   1 i 1 i
j   1      j   j 0 j 0      j   1 1 j j
0   j      0   0 0 0 0      0   1 i j 0

Proof System

The authors provided a natural deduction system RCNL$^2_4$ containing the following rules:

Standard Rules:

• Conjunction introduction/elimination
• Disjunction introduction/elimination

Special Rules:

• (∼∼1): A ∼∼A / B
• (∼∼2): A∨∼∼A
• Various forms of De Morgan's laws

Four Interpretations

The authors discovered that CNL$^2_4$ can admit four distinct interpretations:

Where: t = true, f = false, b = both true and false, n = neither true nor false

Technical Innovations

1. Unified Framework

Through relational semantics (Dunn semantics), a unified framework is provided to understand the four interpretations, rewriting the four values {1, i, j, 0} as .

2. Functional Completeness Proof

The authors proved that CNL$^2_4$ is functionally complete, meaning all possible four-valued functions can be defined, including:

• All delta functions: δₐ(b) = 1 if and only if a = b
• All constant functions: Cₐ(b) = a

3. Definability of Classical Negation

Classical negation can be defined within the system, providing classical logicians with familiar tools.

Experimental Setup

Theoretical Verification

The authors verified theoretical results through:

1. Soundness and Completeness Proofs:
   • Using the standard Lindenbaum lemma
   • Constructing canonical valuations
   • Proving extension lemmas
2. Functional Completeness Verification:
   • Applying Słupecki's theorem
   • Verifying definability of all unary functions
   • Proving existence of essential binary functions

Experimental Results

Main Theoretical Results

Theorem 1 (Soundness): For all Γ∪{A} ⊆ Form, if Γ ⊢ A, then Γ |=CNL$^2_4$ A

Theorem 2 (Completeness): For all Γ∪{A} ⊆ Form, if Γ |=CNL$^2_4$ A, then Γ ⊢ A

Theorem 5 (Definitional Completeness): CNL$^2_4$ is definitionally complete

Corollary 1 (Post Completeness): CNL$^2_4$ is Post complete

Validity Results

Proposition 1: The following hold in CNL$^2_4$:

• B |=CNL$^2_4$ (A∨∼∼A)
• B |=CNL$^2_4$ ∼(A∨∼∼A)
• A∧∼∼A |=CNL$^2_4$ B
• ∼(A∧∼∼A) |=CNL$^2_4$ B

Proposition 2: The following do not hold in CNL$^2_4$:

• q ⊭CNL$^2_4$ p∨∼p
• p∧∼p ⊭CNL$^2_4$ q
• ∼∼p ⊭CNL$^2_4$ p
• p ⊭CNL$^2_4$ ∼∼p

Related Work

Four-Valued Logical Systems

1. FDE (First-Degree Entailment): Foundation of Belnap-Dunn logic
2. Ruet System: Adding special negation operators to FDE
3. Kamide System: An alternative approach to four-valued logic

Philosophical Background

1. Susan Haack's Strategy: Enhancing intelligibility of non-classical systems through classical interpretations
2. Carnap Problem: Proof systems cannot uniquely determine intended interpretations
3. Quine's Thesis of Meaning Variance: Whether logical change entails meaning change

Conclusions and Discussion

Main Conclusions

1. System Equivalence: CNL$^2_4$ under different interpretations is equivalent to known logical systems (Ruet, Kamide, etc.)
2. Meaning Indeterminacy: The same proof system can support four fundamentally different semantic understandings, constituting a deepening of the Carnap problem
3. Classical Intelligibility: Through Haackian strategy and relational semantics, classical logicians can understand the system
4. Status of Negation: Whether ∼ is a genuine negation depends on which interpretation is adopted and what requirements are placed on negation

Limitations

1. Interpretation Selection Problem: There are no purely logical reasons to choose any one of the four interpretations
2. Communication Difficulty: Different people using the same system may have completely different understandings without realizing it
3. Meaning Fixation Problem: The system itself cannot fix the meaning of connectives

Future Directions

1. Extension to Other Multi-Valued Systems: Applying the analytical method to other non-classical logics
2. Practical Standards: Developing practical standards for choosing specific interpretations
3. Philosophical Deepening: Further exploring the relationship between formal systems and meaning

In-Depth Evaluation

Strengths

1. Profound Theoretical Contribution: Provides not only technical results but also deep discussion of important philosophical issues in logic
2. Comprehensive Analysis: Analyzes the system from multiple perspectives including proof theory, semantics, and philosophy
3. Clear Connections: Explicitly establishes relationships with existing systems
4. Methodological Innovation: Applies Haackian strategy to the analysis of four-valued logic

Weaknesses

1. Limited Practical Applicability: Primarily theoretical analysis with limited consideration of applications
2. Incomplete Solutions: While identifying problems, does not fully resolve the semantic indeterminacy issue
3. Technical Complexity: The complexity of four interpretations may limit practical application of the system

Impact

1. High Theoretical Value: Provides new perspectives for philosophical analysis of multi-valued logics
2. Methodological Contribution: Demonstrates how to systematically analyze non-classical logical systems
3. Interdisciplinary Significance: Connects formal logic and philosophy of logic

Applicable Scenarios

1. Philosophy of Logic Research: Provides case studies for discussing meaning, truth values, and the relationship between logical systems
2. Multi-Valued Logic Theory: Provides methodology for analyzing other multi-valued systems
3. Formal System Design: Alerts designers to semantic indeterminacy issues

References

The paper cites 24 important references, including:

• Susan Haack's Philosophy of Logics
• Quine's classical work on logical deviation
• Related research on Belnap-Dunn logic
• Ruet and Kamide's four-valued logical systems
• Classical results on functional completeness (Słupecki's theorem)

Overall Assessment: This is a high-quality theoretical paper in logic that provides not only solid technical results but also deep exploration of important philosophical questions. The paper's main value lies in revealing the deep problem of semantic indeterminacy in formal logical systems and providing strategies to enhance intelligibility. Although primarily theoretical, it makes significant contributions to the development of logic and philosophy of logic.