Within this sequence of posts I will outline a procedure for logical counterfactuals based on something similar to proof length. In this post I present a reimagining of propositional logic in which proving a theorem is taking a walk around a graph of equivalent proposititions.
Within this post, I will use Latin symbols, for specific symbols within proof strings. I will sometimes use symbols like ∀ to represent a function with particular properties.
I will use Greek letters to represent an arbitrary symbol, upper case for single symbols, lower case for strings.
Respecifying Propositional logic
The goal of this first section is to reformulate first order logic in a way that makes logical counterfactuals easier. Lets start with propositional logic.
We have a set of primitive propositions p,q,r,... as well as the symbols ⊤,⊥. We also have the symbols ∨,∧ which are technically functions from Bool2→Bool but will be written p∨q not ∨(p,q) . There is also ¬:Bool→Bool
Consider the equivalence rules.
1. α≡¬¬α
2. α∧β≡β∧α
3. (α∧β)∧γ≡α∧(β∧γ)
4. ¬α∧¬β≡¬(α∨β)
5. α∧⊤≡α
6. ¬α∨α≡⊤
7. ⊥≡¬⊤
8. α∧(β∨γ)≡(α∧β)∨(α∧γ)
9. ⊥∧α≡⊥
10.α≡α∧α
Theorem
Any tautology provable in propositional logic can be created by starting at ⊤ and repeatedly applying equivalence rules.
Proof
First consider α⟹β to be shorthand for ¬α∨β.
Lemma
We can convert ⊤ into any of the 3 axioms.
α⟹(β⟹α) is a shorthand for
¬α∨(¬β∨α)≡1
¬¬(¬α∨(¬β∨α))≡4
¬(¬¬α∧¬(¬β∨α))≡4
¬(¬¬α∧(¬¬β∧¬α))≡1
¬(¬¬α∧(β∧¬α))≡2
¬(¬¬α∧(¬α∧β))≡3
¬((¬¬α∧¬α)∧β)≡4
¬(¬(¬α∨α)∧β)≡6
¬(¬⊤∧β)≡7
¬(⊥∧β)≡9
¬⊥≡7
⊤
Similarly
(α⟹(β⟹γ))⟹((α⟹β)⟹(α⟹γ))
(¬α⟹¬β)⟹(β⟹α)
(if these can't be proved, add that they ≡⊤ as axioms)
End Lemma
Whenever you have α∧(α⟹β), that is equiv to
α∧(¬α∨β)≡8
(α∧¬α)∨(α∧β)≡1
(¬¬α∧¬α)∨(α∧β)≡4
¬(¬α∨α)∨(α∧β)≡6
¬⊤∨(α∧β)≡1
¬¬(¬⊤∨(α∧β))≡4
¬(¬¬⊤∧¬(α∧β))≡1
¬(⊤∧¬(α∧β))≡2
¬(¬(α∧β)∧⊤)≡5
¬¬(α∧β)≡1
α∧β
This means that you can create and apply axioms. For any tautology, look at the proof of it in standard propositional logic. Call the statements in this proof p1,p2,p3...
suppose we have already found a sequence of substitutions from ⊤ to p1∧p2...∧pi−1
Whenever pi is a new axiom, use (5.) to get p1∧p2...∧pi−1∧⊤, then convert ⊤ into the instance of the axiom you want. (substitute alpha and beta with arbitrary props in above proof schema)
Using substitution rules (2.) and (3.) you can rearrange the terms representing lines in the proof and ignore their bracketing.
Whenever pi is produced by modus ponus from the previous pj and pk=pj⟹pi then duplicate pk with rule (10.), move one copy next to pj and use the previous procedure to turn pj∧(pj⟹pi) into pj∧pi. Then move pi to end.
Once you reach the end of the proof, duplicate the result and unwind all the working back to ⊤, which can be removed by rule (5.)
Corollary
{p,q,r}⊢s then p∧q∧r≡p∧q∧r∧s
Because p∧q∧r⟹s is a tautology and can be applied to get s.
Corollary
Any contradiction is reachable from ⊥
The negation of any contradiction k is a tautology.
⊥≡¬⊤≡¬¬k≡k
Intuitive overview perspective 1
An illustration of rule 4. ¬α∧¬β≡¬(α∨β) in action.
We can consider a proposition to be a tree with a root. The nodes are labeled with symbols. The axiomatic equivalences become local modifications to the tree structure, which are also capable of duplicating and merging identical subtrees by (10.). Arbitrary subtrees can be created or deleted by (5.).
We can merge nodes with identical subtrees into a single node. This produces a directed acyclic graph, as shown above. Under this interpretation, all we have to do is test node identity.
Intuitive overview perspective 2
Consider each possible expression to be a single node within an infinite graph.
Each axiomatic equivalence above describes an infinite set of edges. To get a single edge, substitute the generic α,β... with a particular expression. For example, if you take (2. α∧β≡β∧α ) and substitute α:=p∨q and β:=¬q. We find a link between the node (p∨q)∧¬q and ¬q∧(p∨q).
Here is a connected subsection of the graph. Note that, unlike the previous graph, this one is cyclic and edges are not directed.
All statements that are provably equivalent in propositional logic will be within the same connected component of the graph. All statements that can't be proved equivalent are in different components, with no path between them.
Finding a mathematical proof becomes an exercise in navigating an infinite maze.
In the next Post
We will see how to extend the equivalence based proof system to an arbitrary first order theory. We will see what the connectedness does then. We might even get on to infinite dimensional vector spaces and why any of this relates to logical counterfactual.
Within this sequence of posts I will outline a procedure for logical counterfactuals based on something similar to proof length. In this post I present a reimagining of propositional logic in which proving a theorem is taking a walk around a graph of equivalent proposititions.
Within this post, I will use Latin symbols, for specific symbols within proof strings. I will sometimes use symbols like ∀ to represent a function with particular properties.
I will use Greek letters to represent an arbitrary symbol, upper case for single symbols, lower case for strings.
Respecifying Propositional logic
The goal of this first section is to reformulate first order logic in a way that makes logical counterfactuals easier. Lets start with propositional logic.
We have a set of primitive propositions p,q,r,... as well as the symbols ⊤,⊥. We also have the symbols ∨,∧ which are technically functions from Bool2→Bool but will be written p∨q not ∨(p,q) . There is also ¬:Bool→Bool
Consider the equivalence rules.
1. α≡¬¬α
2. α∧β≡β∧α
3. (α∧β)∧γ≡α∧(β∧γ)
4. ¬α∧¬β≡¬(α∨β)
5. α∧⊤≡α
6. ¬α∨α≡⊤
7. ⊥≡¬⊤
8. α∧(β∨γ)≡(α∧β)∨(α∧γ)
9. ⊥∧α≡⊥
10.α≡α∧α
Theorem
Any tautology provable in propositional logic can be created by starting at ⊤ and repeatedly applying equivalence rules.
Proof
First consider α⟹β to be shorthand for ¬α∨β.
Lemma
We can convert ⊤ into any of the 3 axioms.
α⟹(β⟹α) is a shorthand for
¬α∨(¬β∨α)≡1
¬¬(¬α∨(¬β∨α))≡4
¬(¬¬α∧¬(¬β∨α))≡4
¬(¬¬α∧(¬¬β∧¬α))≡1
¬(¬¬α∧(β∧¬α))≡2
¬(¬¬α∧(¬α∧β))≡3
¬((¬¬α∧¬α)∧β)≡4
¬(¬(¬α∨α)∧β)≡6
¬(¬⊤∧β)≡7
¬(⊥∧β)≡9
¬⊥≡7
⊤
Similarly
(α⟹(β⟹γ))⟹((α⟹β)⟹(α⟹γ))
(¬α⟹¬β)⟹(β⟹α)
(if these can't be proved, add that they ≡⊤ as axioms)
End Lemma
Whenever you have α∧(α⟹β), that is equiv to
α∧(¬α∨β)≡8
(α∧¬α)∨(α∧β)≡1
(¬¬α∧¬α)∨(α∧β)≡4
¬(¬α∨α)∨(α∧β)≡6
¬⊤∨(α∧β)≡1
¬¬(¬⊤∨(α∧β))≡4
¬(¬¬⊤∧¬(α∧β))≡1
¬(⊤∧¬(α∧β))≡2
¬(¬(α∧β)∧⊤)≡5
¬¬(α∧β)≡1
α∧β
This means that you can create and apply axioms. For any tautology, look at the proof of it in standard propositional logic. Call the statements in this proof p1,p2,p3...
suppose we have already found a sequence of substitutions from ⊤ to p1∧p2...∧pi−1
Whenever pi is a new axiom, use (5.) to get p1∧p2...∧pi−1∧⊤, then convert ⊤ into the instance of the axiom you want. (substitute alpha and beta with arbitrary props in above proof schema)
Using substitution rules (2.) and (3.) you can rearrange the terms representing lines in the proof and ignore their bracketing.
Whenever pi is produced by modus ponus from the previous pj and pk=pj⟹pi then duplicate pk with rule (10.), move one copy next to pj and use the previous procedure to turn pj∧(pj⟹pi) into pj∧pi. Then move pi to end.
Once you reach the end of the proof, duplicate the result and unwind all the working back to ⊤, which can be removed by rule (5.)
Corollary
{p,q,r}⊢s then p∧q∧r≡p∧q∧r∧s
Because p∧q∧r⟹s is a tautology and can be applied to get s.
Corollary
Any contradiction is reachable from ⊥
The negation of any contradiction k is a tautology.
⊥≡¬⊤≡¬¬k≡k
Intuitive overview perspective 1
An illustration of rule 4. ¬α∧¬β≡¬(α∨β) in action.
We can consider a proposition to be a tree with a root. The nodes are labeled with symbols. The axiomatic equivalences become local modifications to the tree structure, which are also capable of duplicating and merging identical subtrees by (10.). Arbitrary subtrees can be created or deleted by (5.).
We can merge nodes with identical subtrees into a single node. This produces a directed acyclic graph, as shown above. Under this interpretation, all we have to do is test node identity.
Intuitive overview perspective 2
Consider each possible expression to be a single node within an infinite graph.
Each axiomatic equivalence above describes an infinite set of edges. To get a single edge, substitute the generic α,β... with a particular expression. For example, if you take (2. α∧β≡β∧α ) and substitute α:=p∨q and β:=¬q. We find a link between the node (p∨q)∧¬q and ¬q∧(p∨q).
Here is a connected subsection of the graph. Note that, unlike the previous graph, this one is cyclic and edges are not directed.
All statements that are provably equivalent in propositional logic will be within the same connected component of the graph. All statements that can't be proved equivalent are in different components, with no path between them.
Finding a mathematical proof becomes an exercise in navigating an infinite maze.
In the next Post
We will see how to extend the equivalence based proof system to an arbitrary first order theory. We will see what the connectedness does then. We might even get on to infinite dimensional vector spaces and why any of this relates to logical counterfactual.