💻 computer science

Knowing-Value Logic with Successor Arithmetic

This paper extends conditional knowing-value logic with equality and successor arithmetic to handle reasoning involving arithmetic operations, establishing finite model property and completeness results over non-standard and standard models while demonstrating its application in solving the "Consecutive Numbers" puzzle through public announcement operators.

Original authors: Hongyi Wang (Department of Philosophy, Peking University)

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hongyi Wang (Department of Philosophy, Peking University)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a mystery, but instead of just knowing that something is true (like "The butler did it"), you need to know what the specific value is (like "The butler's name is John"). This is the core of "Knowing-Value" logic.

For a long time, logicians had a toolkit to handle "knowing-that," but when it came to "knowing-what," especially when numbers were involved, their tools were a bit blunt. They could say, "S knows the password is a 4-digit number," but they couldn't easily explain the internal math of why that matters or how the numbers relate to each other (like how 5 is the next number after 4).

This paper, by Hongyi Wang, builds a new, sharper toolkit that combines epistemic logic (the logic of knowledge) with arithmetic (specifically, counting and the "next number" rule).

Here is a breakdown of what the paper does, using simple analogies:

1. The Problem: The "Blunt Knife"

Think of the old logic systems as a blunt knife. They could chop up a sentence like "Anne knows the numbers are consecutive," but they had to treat "consecutive" as a single, unbreakable block (like a whole potato). They couldn't see the slices inside.

The Issue: In real life, we often reason about numbers. If Anne knows the numbers are consecutive, and she knows her number is 5, she should instantly know Bill's number is 4 or 6. The old logic couldn't capture this internal math structure. It treated "5" and "6" as just random labels, not as numbers that have a specific relationship (one is the "successor" of the other).

2. The Solution: A "Laser Cutter"

Wang introduces a new logic called ELKvSAr. Think of this as a laser cutter that can slice right through the math.

The New Tool: It adds a "Successor" function (let's call it S). If you have the number 0, S(0) is 1, S(1) is 2, and so on.
The Result: Now, the logic can say, "Anne knows that Bill's number is S of Anne's number." It preserves the internal structure of the math, allowing for much more precise reasoning.

3. The "Parallel Universe" Trick (Non-Standard Models)

Here is where it gets a bit tricky, but the paper uses a clever workaround.

The Problem: When you try to prove that this new logic works perfectly for all standard numbers (1, 2, 3...), you run into a mathematical wall. It's like trying to fit an infinite ocean into a finite bucket; the math gets "too big" to handle in the standard way. The paper proves that you cannot have a perfect, complete rulebook for just the standard numbers.
The Workaround: The author builds a Parallel Universe (called "non-standard models"). Imagine a universe that looks exactly like our number line, but it has extra "loops" or "chains" of numbers attached to it.
The Magic: In this parallel universe, the math works perfectly. The author proves that if a statement is true in this parallel universe, it is also true in our standard world. It's like testing a bridge design in a wind tunnel (the parallel universe) to ensure it will hold up in the real city (the standard world).

4. The "Consecutive Numbers" Puzzle

To show off this new tool, the author solves a classic riddle:

The Setup: Two people, Anne and Bill, are told they have two consecutive natural numbers (like 5 and 6). Anne whispers her number to herself, Bill whispers his. They can't see each other's numbers.
The Conversation:
1. Anne says: "I don't know your number." (This tells us her number isn't 0, because if she had 0, she'd know Bill must have 1).
2. Bill says: "I don't know your number." (This tells us his number isn't 0 or 1).
3. Anne says: "Now I know your number!"
4. Bill says: "Now I know yours!"
The Logic: Using the new "laser cutter" logic, the paper formalizes exactly how each sentence peels away layers of possibility, using the "Successor" rule to eliminate numbers one by one until only the correct pair (1 and 2, or 2 and 3) remains. It proves that the logic can handle this step-by-step deduction perfectly.

5. The Bottom Line

The paper achieves three main things:

It built the tool: It created a new logic system that understands "knowing a value" combined with "counting."
It proved the tool works: It showed that the system is logically sound and complete (meaning it can prove everything that is true) by using the "Parallel Universe" trick.
It proved the tool is usable: It showed that you can actually solve these puzzles with a computer (the system is "decidable"), meaning you won't get stuck in an infinite loop trying to solve them.

In short: The author took a logic system that was good at "knowing facts" and upgraded it to be good at "knowing numbers," using a clever mathematical trick to ensure the upgrade is solid, and then used it to solve a classic brain teaser about consecutive numbers.

Technical Summary: Knowing-Value Logic with Successor Arithmetic

Problem Statement
This paper addresses limitations in existing "knowing-value" logics, specifically the conditional knowing-value logic ($ELKvr$) and its public announcement extension ($PALKvr$) proposed by Wang and Fan. While these systems formalize statements like "Agent $i$ knows the value of $c$ given $\phi$ ," they lack the syntactic machinery to handle arithmetic operations and equality directly. Consequently, they cannot capture the internal structure of propositions involving numbers, such as the relationship between consecutive integers. In natural language scenarios and logic puzzles (e.g., the "Consecutive Numbers" puzzle), reasoning often relies on the interaction between epistemic operators, equality, and arithmetic functions (specifically the successor function). The existing frameworks treat numerical conditions as opaque propositional letters, failing to derive implications that are obvious in natural language (e.g., that knowing a number is 4-digit and knowing the implication "if 4-digit then 1111" should entail knowing the value is 1111). Furthermore, the standard semantics for these logics, based on unstructured sets of objects, are insufficient for modeling specific mathematical structures like the natural numbers with a successor function.

Methodology
The author introduces a new logic, $ELKvSAr$ (the announcement-free fragment of $PALKvSAr$), which extends conditional knowing-value logic with:

Terms: Including a rigid constant $0$, non-rigid constants $C$ , and the successor function $S$ .
Atomic Formulas: Equality between terms ( $t_1 \approx t_2$ ).
Semantics: The paper defines two distinct classes of models:
- Standard Models: Based on the standard natural numbers $(\mathbb{N}, S)$ .
- Non-Standard Models: Based on a specific non-standard model of successor arithmetic $(\mathbb{N}^\star, S^\star)$ , where $\mathbb{N}^\star$ includes the standard natural numbers plus infinitely many "Z-chains" (copies of the integers). This extension is necessary because the logic is not compact over the class of standard models.

The technical approach involves:

Axiomatization: Proposing the system $ELKVSAr$, which includes axioms for equality, successor arithmetic (e.g., $\neg Sx \approx 0$ , injectivity of $S$ ), and specific axioms/rules bridging knowing-value and arithmetic (e.g., $KvrS$, $KVE1$, $KVE2$). A key feature is the $Kvr$-Elim rule, which functions analogously to existential elimination in first-order logic, allowing the removal of relativized knowing-value operators during derivation.
Completeness Proof: Proving strong completeness with respect to non-standard models. The proof utilizes a novel construction of a tree-like canonical frame rather than a standard canonical model. This involves constructing histories of maximal consistent sets and defining a valuation function that maps constants to elements in $\mathbb{N}^\star$ while respecting the equivalence relations induced by the knowing-value operator and the arithmetic structure.
Finite Model Property and Decidability: Demonstrating that any satisfiable formula has a finite non-standard model, which can then be mapped to a finite standard model via an injective mapping that preserves arithmetic distances and separates components. This establishes the finite model property and decidability.
Application: Formalizing the "Consecutive Numbers" puzzle using public announcement operators ($PALKvSAr$) to show how agents' knowledge evolves through arithmetic deductions.

Key Contributions and Results

Logic Extension: The introduction of $ELKvSAr$ and $PALKvSAr$, integrating equality and the successor function into conditional knowing-value logic.
Axiomatic System: The definition of $ELKVSAr$, which is proven to be:
- Strongly complete with respect to the class of non-standard models.
- Weakly complete with respect to the class of standard models.
Meta-logical Properties:
- Finite Model Property (FMP): The logic possesses the FMP with respect to both standard and non-standard models.
- Decidability: The satisfiability problem for $ELKvSAr$ is decidable.
Non-Compactness: The paper proves that $ELKvSAr$ is not compact with respect to standard models, motivating the introduction of non-standard models for the completeness proof.
Puzzle Solution: The "Consecutive Numbers" puzzle is successfully formalized and solved within the system, demonstrating that the logic can capture the step-by-step elimination of possibilities based on arithmetic constraints and epistemic updates.

Significance
The paper claims to provide a novel framework for integrating epistemic logic with arithmetic. By enriching knowing-value logic with the successor function, the system overcomes the coarse-grained nature of previous approaches, allowing for the formalization of reasoning that depends on the internal structure of numerical propositions. The work establishes a balance between expressiveness (handling arithmetic and epistemic interaction) and computational complexity (maintaining decidability). The authors note that this framework lays the groundwork for future extensions involving more complex arithmetic structures (addition and multiplication), which would be necessary for solving puzzles like "Sum and Product," though such extensions present significant challenges regarding completeness and decidability.

1. The Problem: The "Blunt Knife"

2. The Solution: A "Laser Cutter"

3. The "Parallel Universe" Trick (Non-Standard Models)

4. The "Consecutive Numbers" Puzzle

5. The Bottom Line

More like this