relevance:vagueness
INTRODUCTION TO
NON-CLASSICAL
LOGIC
1
Yoshihiro Maruyama
co-taught with Pascal Bercher
on the legacy of John Slaney
PROS AND CONS FOR CLASSICAL LOGIC
What is wrong with classical logic?
➤ Is anything in the (classical) propositional truth table strange?
➤ Is anything in the (classical) natural deduction strange?
➤ Is anything in the (classical) sequent calculus strange?
➤ Is anything in the (classical) first-order semantics strange?
Or is everything fine with classical logic?
Is it your logic? Are you following that everyday?
2
asd
THE LIAR AND ITS REVENGE
3
asdhttps://sketchplanations.com/the-liar-paradox
A ↔ ¬A
Let A be “A is 0 (false)”
If A is 1, then A is 0
If A is 0, then A is 1
What if you have 1/2?
If A is 1/2, A is 1/2
Both are 1/2:
1/2 means half-true.
Then no contradiction.
1/2 ↔ 1/2
The Revenge Paradox:
Let A be “A is neither 1
nor 1/2”. If A is 1, it’s
contradiction. If A is 1/2,
it’s contradiction. If A is 0,
A is either 1 or 1/2; it’s
contradiction. What if you
have more truth values
(four or infinitely many)?
DEBATES IN LOGIC
➤ Non-classical logic is any logic that does not follow classical logic.
➤ Why do we have to follow classical logic? We are free. Is anyone around you
really following classical logic?
➤ Is there only one correct logic? Or are there many correct logics? The latter is
called logical pluralism.
➤ Is there no logic that we can safely rely on in any situation or context? If so,
how can we find each logic appropriate in each situation or context.
➤ Logic, from a naive point of view, should be context-independent and universally
applicable. But is such a conception of logic wrong or misguided?
➤ There are both pros and cons for logical pluralism. Many early logicians (e.g.,
Russell) was a logical monist, but many logicians today are logical pluralists.
4
asd
Graham Priest
Greg Restall
DOES LOGIC SAVE YOU?
➤ Natural language is inconsistent and/or too ambiguous.
➤ That’s one of the reasons why early logicians tried to formalise mathematics
within a rigorous formal language that does not allow any inconsistencies or
ambiguities.
➤ Even a recent Fields Medalist, Voevodsky, attempted to formalise mathematics
for the same reason; his well-known theorem turned out to be wrong.
➤ Even mathematicians sometimes disagree with the correctness of a proof, as in
the case of Mochizuki’s IUT proof of the ABC conjecture.
➤ Logic saves mathematics and science from paradoxes and disagreements.
5
asd
WHAT DOES IT MEAN TO SOLVE PARADOXES?
➤ What does it mean to solve paradoxes? Why do we have to?
➤ Why don’t we allow contradictions? What’s problematic with it?
➤ There are actually a lot of mathematical inconsistencies in physics, such as
Feynman integrals and renormalisation groups in quantum field theory.
➤ Even ordinary mathematicians use naive set theory, which is inconsistent due to
Russell’s Paradox, Cantor’s Paradox, etc. Let . Then we have
, which is contradictory just like the Liar Paradox.
➤ The paradoxes in set theory caused the consistency crisis of math in the early
20th C., during which the entire field of logic was created by Hilbert et al.
➤ Can’t we get along with paradoxes?
R = {x ; x ∉ x}
R ∈ R ↔ R ∉ R
6
asd
RELEVANT HISTORY
➤ Relevant logic is one of the logics of Australia or even the ANU.
➤ Both Routley and Meyer, eminent relevant logicians known for Routley-Meyer
semantics (which can be adapted for a broad variety of substructural logics),
worked at the ANU. John Slaney is in the same relevant tradition.
➤ Logic at the ANU started in philosophy, flourishing in computer science as well.
7
asd
https://ojs.victoria.ac.nz/ajl/issue/view/568 https://richardzach.org/2009/05/09/robert-k-meyer-1932-2009/
Richard Routley (Sylvan) Bob Meyer John Slaney
LOGIC AND PHYSICS
Classical logic is analogous to classical physics:
➤ Classical physics is a good simplification/idealisation that works in many ordinary
situations.
➤ If an object is too small, it does not hold. We need quantum mechanics.
➤ If an object is moving very fast, it does not hold. We need special relativity.
➤ If an object is too big/heavy, it does not hold. We need general relativity.
➤ If an object is a conscious being, it may not hold and we have nothing for that.
➤ It’s the same with classical logic. It’s a good simplification/idealisation that works in
many ordinary situations. It’s like the physicist considers one particle with no mass or
extension moving around in vacuum space, but the actual space is very rarely vacuum.
8
asd
PARADOXES OF
IMPLICATION
9
STRANGE VALID SEQUENTS
In the logic we learned, some strange sequents are valid:
➤
“I have $300, therefore if it rains on Tuesday then I have $300.”
➤
“I do not have $300, therefore if I have $300 it rains on Tuesday.”
➤
“The cat is dead and the cat is alive, therefore I am a chicken.”
p ⊢ q → p
¬p ⊢ p → q
p, ¬p ⊢ q
10
asd
PARADOXES OF MATERIAL IMPLICATION
➤ All of the previous sequents are semantically valid and are syntactically provable in
the logic we learned so far.
➤ However, these arguments do not make much sense.
➤ Especially, conclusions are irrelevant to premises.
➤ They are known as Paradoxes of Material Implication.
➤ Note that is equivalent to , which can, e.g., be verified via truth tables.
➤ Relevant logic saves us from the paradoxes of implication.
¬A A → ⊥
11
asd
PARADOXES OF MATERIAL IMPLICATION (CONT’D)
➤ A possible perspective on paradoxes of implication: assumptions are not used in any
relevant manner for deriving the conclusion.
➤ Consider a proof of . RAA in line 4 seemingly suggests the assumption
is what caused the contradiction. But is irrelevant to and .
➤ Relevant logic allows us to prohibit this sort of irrelevant reasoning.
p, ¬p ⊢ q ¬q
¬q p ¬p
12
p, ¬p ⊢ q
α1 (1) p
α2 (2) ¬p
α3 (3) ¬q
α1, α2 (4) ¬¬q
α1, α2 (5) q
A
A
A
1,2[α3] RAA
4 ¬¬E
➤ Note that these arguments are allowed in the logic of mathematics.
➤ Classical logic, the logic you learned, is basically the logic of mathematics. Frege,
Russell, and Whitehead (origins of formal logic) all tried to formalise mathematics.
➤ Is the logic of natural language the same as the logic of mathematics?
➤ No obvious answer to this.
➤ Natural language is seemingly richer and contextual than the logic of mathematics, so
they may be different from each other; if so, what is the logic of natural language?
➤ Relevant logic sheds light on relevance aspects of natural language reasoning.
THE LOGIC OF MATH VS. THE LOGIC OF NATURAL LANGUAGE
13
asd
➤ How to save logic from paradoxes of implications?
➤ In relevant logic, we reconsider the way assumptions are combined with each other.
SAVING LOGIC FROM PARADOXES
14
asd
➤ In the proof of the following sequent,
the assumptions and :
are put together by ;
are pulled apart by .
➤ Any of and is no problem on
its own, but the way they combine
assumptions are subtly different in the
following sense.
α1 α2
∧ I
→ I
∧ I → I
THE WAYS ASSUMPTIONS ARE COMBINED
15
q ⊢ p → q
α1 (1) q
α2 (2) p
α1, α2 (3) p ∧ q
α1, α2 (4) q
α1 (5) p → q
A
A
1,2 ∧ I
3 ∧ E
4[α2] → I
asd
➤ In the ∧I rule:
The two assumptions are just collected together and there is no requirement
that they interact with each other to yield the conclusion .
➤ Yet in the E rule:
The assumption is “applied” to so that they yield the conclusion while
disappears after the application. The same thing happens in I.
➤ To distinguish the two ways, we introduce a new symbol “;” (semicolon) besides “,”.
X, Y
A ∧ B
→
Y X B A
→
THE WAYS ASSUMPTIONS ARE COMBINED (CONT’D)
16
Y ⊢ BX ⊢ A
X, Y ⊢ A ∧ B
∧I
X ⊢ A → B
X, Y ⊢ B
→E
Y ⊢ A
asd
➤ We modify the rules by introducing the semicolon to distinguish the different ways
assumptions are combined. Here are ND rules for conjunction and implication:
RELEVANT LOGIC RULES
17
X ⊢ A Y ⊢ B
X, Y ⊢ A ∧ B
∧ I
X ⊢ A → B Y ⊢ A
X, Y ⊢ B
→ E
X, A ⊢ B
X ⊢ A → B
→ I
Classical Logic
X ⊢ A Y ⊢ B
X, Y ⊢ A ∧ B
∧ I
X ⊢ A → B Y ⊢ A
X; Y ⊢ B
→ E
X; A ⊢ B
X ⊢ A → B
→ I
Relevant Logic
asd
SAVING LOGIC FROM PARADOX
18
➤ With these new rules we can no longer
go from line (4) to line (5) as the new
rule requires “;” between the
assumptions:
➤ We can still prove something
meaningful via the modified rules: e.g.,
(as below)
→ I
p → (q → r) ⊢ (p ∧ q) → r
q ⊢ p → q
α1 (1) q
α2 (2) p
α1, α2 (3) p ∧ q
α1, α2 (4) q
α1 (5) p → q
A
A
1,2 ∧ I
3 ∧ E
4[α2] → I
X; A ⊢ B
X ⊢ A → B
→ I
asd
➤ Weakening below is not valid in relevant logic: it does not allow us to add irrelevant
assumptions, but it usually allows to reduce duplications, i.e., contraction below.
➤ (Note: Contraction is not valid in certain fuzzy logic: it does not allow us to reduce
two precious resources to just one resource, but it does allow to increase resources.)
➤ is not regarded as a set; it matters how many times the same formula appears in .
➤ Full proof theory is given in an additional chapter of the logic notes (see 8: Reference),
but in this course, you don’t have to understand all of them in detail.
X X
RELEVANT AND FUZZY LOGICS AS SUBSTRUCTURAL LOGICS
19
X; A; A ⊢ B
X; A ⊢ B
contraction
X ⊢ B
X; A ⊢ B
weakening
asd
CONTRACTION IS ALLOWED IN RELEVANT LOGIC (BUT NOT IN FUZZY LOGIC)
20
p → (q → r) ⊢ (p ∧ q) → r
p → (q → r)(1)α1 A
p ∧ q(2)α2 A
p(3)α2 2 ∧ E
q(4)α2 2 ∧ E
q → r(5)α1; α2 1,3 → E
r(6)α1; α2; α2 4,5 → E
r(7)α1; α2 6 contraction
(p ∧ q) → r(8)α1 7[α2] → I asd
➤ You have three dollars *and* you have three dollars, i.e., you have six dollars!
➤ This is a resource-sensitive interpretation of substructural conjunction.
➤ Having two Tim Tams is different from having one Tim Tam.
➤ This world is resource-sensitive (as well as computer science, in which
substructural logic has played essential roles, esp. in semantics of computation).
➤ John told me that there are two possible readings of “A;B”: “A and B” (B. Meyer) or
“A is compatible with B” (in the sense that “not (A implies not B)”; S. Read).
RESOURCE SENSITIVITY IN SUBSTRUCTURAL LOGIC
21
≠
https://www.arnotts.com/products/tim-tam
SAVING LOGIC FROM ANOTHER PARADOX
➤ Which step is wrong with the classical proof of the following sequent?
➤ We can get , but to derive , we need , which is not
allowed because we cannot add irrelevant assumptions without the weakening rule.
➤ This means contradictions don’t entail explosion (i.e., it is not possible to derive an
arbitrary formula from contradictions); it’s paraconsistent (contradiction-tolerant) logic.
p; ¬p ⊢ ⊥ ¬¬q p; ¬p; ¬q ⊢ ⊥
22
X ⊢ A X ⊢ ¬A
X; Y ⊢ ⊥
¬E
X; A ⊢ ⊥
X ⊢ ¬A
¬I
X ⊢ ¬¬A
X ⊢ A
¬¬E
Relevant Logic p, ¬p ⊢ q
α1 (1) p
α2 (2) ¬p
α3 (3) ¬q
α1, α2 (4) ¬¬q
α1, α2 (5) q
A
A
A
1,2[α3] RAA
4 ¬¬E
MODELLING RELEVANT LOGIC
➤ We have the following three-valued semantics for relevant logic:
We consider i to be a “confused” value between true and false. In a way, it can be
considered to be both true and false; it’s paraconsistent.
23
asd
T
i
F
F
i
T
¬AA∧ T i F
T
i
F
T i F
i i F
F F F
∨ T i F
T
i
F
T T T
T i i
T i F
→ T i F
T
i
F
T F F
T i F
T T T
MODELLING RELEVANT LOGIC
➤ The semicolon and comma are interpreted as follows:
➤ In the three-valued relevant logic, is valid iff in any assignment of values, the
value of A is at least as good as the value of X. Note: T better than i better than F.
➤ Concretely: the T i case is invalid, and the i F case is invalid; in contrast, the
i T case is valid; the F i case is valid.
➤ Tautologies (i.e., valid formulae) are those to which it is impossible to assign F.
X ⊢ A
⊢ ⊢
⊢ ⊢
24
, T i F
T
i
F
T i F
i i F
F F F
; T i F
T
i
F
T T F
T i F
F F F
INVALID SEQUENTS
➤ The following are not valid (and thus not provable because of soundness):
25
¬(p → q) ⊢ p ∧ ¬q
p ∧ q ⊢ p ↔ q
(p ∧ q) → r ⊢ p → (q → r)
p ⊢ q → p
(p ∨ q) ∧ ¬p ⊢ q
asd
INVALID SEQUENTS (CONT’D)
➤ Consider the last sequent:
➤ Classical logic make and be equivalent with each other.
If we assign T to p and i to both q and r, it is not valid in the three-valued semantics
for relevant logic because the premise of the sequent is i, while the conclusion is F.
➤ The converse sequent is valid.
(p ∧ q) → r p → (q → r)
p → (q → r) ⊢ (p ∧ q) → r
26
(p ∧ q) → r ⊢ p → (q → r)
(p ∧ q) → r ⊢ p → (q → r)
T i i i i T F i i i
asd
QUESTIONS
27
➤ Is relevant logic closer to natural language than classical logic?
➤ Vacuous discharge is not allowed in relevant logic since it cannot discharge
irrelevant assumptions.
➤ Can we do ordinary mathematics (e.g., arithmetic) with relevant logic?
➤ How many logics exist in the world?
asd
REMARKS
28
➤ The three-valued semantics is not complete for the relevant natural deduction
system; or the relevant proof system is not complete for the three-valued semantics.
➤ But three-valued semantics is useful for “getting a feel” for relevant logic, and for
refuting some sequents.
➤ Note that the soundness of the three-valued semantics for relevant logic can be
shown, in the same way as before, by verifying that semantic validity is preserved
by all the rules (including the assumption rule). It’s not complete, however.
➤ NB: , and are valid but not provable.
➤ The logic notes include more about relevant logic (highly recommended).
p ⊢ p → p ⊢ p ∨ (p → q) p ∧ ¬p ⊢ q ∨ ¬q
asd
VAGUENESS AND
THE SORITES
PARADOX
SORITES PARADOX 1
➤ grains are a heap (you can choose any sufficiently large number).
➤ If grains are a heap, then grains are a heap.
➤ If grains are a heap, grains are a heap.
In general: if grains are a heap, grains are a heap.
Removing a single grain does not change the qualitative status of being a heap.
➤ Thus: zero grains are a heap (by applying the above argument times).
The logical form of the argument (apply the E rule times):
. It’s called the Sorites Paradox.
1010
10
1010
10
1010
10
− 1
1010
10
− 1 (1010
10
− 1) − 1
n n − 1
1010
10
→ n
pn, (pn → pn−1), . . . , (p1 → p0) ⊢ p0
30
asd
SORITES PARADOX 2
➤ Suppose this strip is one hundred miles long, and I walk along it from left to right.
On the first step is a sign saying “green”.
At each step I record the colour of the current step and perform a logical test: If
the next step is not directly discriminable from the current step, then I conclude
the next step is the same colour as the current one.
➤ Clearly, by essentially applying the E rule repeatedly together with the initial
premises that the first step is green, at the end we will be calling a red step green!
→
31
asd
SORITES PARADOX 3
➤ Now suppose we have a dinosaur.
It mates and lays an egg. The egg hatches, releasing an almost identical offspring
of the dinosaur.
Perform a logical test; if the offspring is almost identical to its parent, then it is of
the same species.
Return to step one and repeat with the new, almost identical dinosaur.
➤ 200 million years later you have a chicken, yet according to the logical test with
repeatedly appealing to the E rule, it is a dinosaur. When did the dinosaur become
the chicken? (Supposing Darwin’s theory of evolution is correct.)
→
32
asd
THE PROBLEM
➤ The problem is: qualitative predicates, such as ‘… is a heap’, ‘… is green’, or ‘… is a
dinosaur’, are insensitive to small changes, but is sensitive to sufficiently large changes,
and yet there is no obvious borderline between negligible and significant changes.
33
asd
Populations, Race, and The Sorites Paradox
A PARTING OF THE WAYS
➤ Broadly, there are three kinds of responses:
1. Eliminate vague predicates; they are too vague and unimportant for logic, math, or
science. Most popular in ordinary science pursuing non-vague truths and clarity.
2. Identify problematic part of the argument, and modify logic so as to make it invalid.
Fuzzy logic and contraction-free relevant logic may arguably work for this purpose. Most
popular in formal logic.
3. Keep the truths of classical logic, yet give a logical account of vague predicates via the
precisification of vague predicates. Most popular in analytic philosophy.
➤ Option 1: vagueness does not matter for the pursuit of scientific truth; forget about it.
Option 2: revise logic to accommodate vagueness. Option 3: accommodate vagueness
while keeping classical logic as much as possible. Which one would you choose?
34
asd
OPTION 1: QUINE’S REGIMENTATION OF LANGUAGE
➤ Putnam (1983): “Quine has suggested that it really doesn’t matter if ordinary
language is vague (or even locally inconsistent), as long as we can think of ourselves
as approximating a scientific language which is free of these defects.”
➤ Putnam (1983): “In Quine’s view, statements in ordinary language aren’t true or
false; they are only true or false relative to a translation scheme (or ‘regimentation’)
which maps ordinary language onto an ideal language — and there is no fact of the
matter as to which is the ‘right’ translation”. Ideal language is fully logical and clear.
➤ Quine (1977): “Ordinary language is only loosely factual, and needs to be variously
regimented when our purpose is scientific understanding. The regimentation is
again not a matter of eliciting a latent content. It is again a free creation.”
➤ Simplistically: remove vagueness; it’s not part of any serious science or truth.
35
asd
W. V. O. Quine
H. Putnam
OPTION 2: WHAT IS LOGICALLY WRONG WITH THE SORITES ARGUMENT?
➤ What’s logically wrong with the Sorites Paradox argument?
Is the →E rule wrong?
Abandoning the →E rule entirely is problematic as Michael Dummett puts it:
“the validity of this rule of inference seems absolutely constitutive of the meaning … of ‘if ’.”
36
asd
CONTRACTION-FREE LOGIC APPROACH
➤ How can we resolve the paradox while maintaining something like the →E rule?
Relevant logic without contraction (logic without any of contraction and weakening)
would arguably work to address the paradox.
is not provable in it, hence no Sorites paradox.
Yet the →E rule with semicolon is allowed (which yields ).
➤ As far as the Sorites Paradox argument relies upon comma, it does not work in
relevant logic without contraction.
➤ Can we represent the argument using semicolon rather than comma? “And” in the
Sorites argument as represented by comma is arguably different from semicolon.
p, p → q ⊢ q
p; p → q ⊢ q
37
asd
THE FUZZY LOGIC APPROACH
➤ Fuzzy logic gives another perspective on the Sorites Paradox.
There are more than two truth values in fuzzy logic (possibly infinitely many).
We can then argue that each step in the Sorites argument is correct to
some degree, but not exactly correct, i.e., being of truth value in between 0 and 1.
➤ In general we can allow any real number between 0 and 1, but for simplicity, let us
think about three-valued fuzzy logic in this course.
➤ NB: fuzzy logic is also contraction-free, so the same proof-theoretic argument as for
contraction-free relevant logic works for fuzzy logic as well. Yet fuzzy logic also gives
a many-valued semantic account of invalidity of the Sorites argument.
pn → pn−1
38
asd
THE FUZZY LOGIC APPROACH (CONT’D)
➤ There are three three values, i.e., F, i, and T.
We may think of the intermediate value i as “half-true”, which is the same thing as
“half-false”.
Formally: F