identity:restricted-quantifers
1
INTRODUCTION TO
IDENTITY AND ITS
PHILOSOPHY
Yoshihiro Maruyama
co-taught with Pascal Bercher
on the legacy of John Slaney
THE MEANING OF IDENTITY
➤
➤ They are different expressions, but mean / denote / refer to the same thing
(although they have different cognitive values).
➤ Remark: meaning is denotation in denotational semantics.
➤ Hesperus (the Evening Star) = Phosphorus (the Morning Star); Frege’s example.
➤ Because both of them are Venus (although they have different cognitive values).
210 = 1024.
2
asd
PHILOSOPHY OF LANGUAGE
➤ Frege distinguished between sense (i.e., modes of presentation) and reference (i.e.,
denotations; what expressions refer to). Hesperos and Phosporos have the same
reference (denotation), but different senses (modes of presentation).
➤ This sort of subtle differences in language are studied in Intensional Logic, which
we do not learn in this course, but is highly interesting, both mathematically and
philosophically. See, e.g., https://plato.stanford.edu/entries/logic-intensional/
➤ Frege is an origin of contemporary logic, and worked on both logical foundations
of mathematics and logical analyses of natural language.
➤ Sense is intensional meaning. Reference is extensional meaning.
➤ Cf. intensional vs. extensional definitions in math.
3
https://plato.stanford.edu/entries/logic-intensional/
HISTORY
➤ “Ancient Egyptians and Greeks had already discovered Venus, but thought it to be
two separate heavenly bodies: the morning star (visible in the morning, also
Phosporos) and the evening star (visible in the evening, also Hesperos). It was later
discovered by the Greeks that the two were two occurrences of the same object.”
➤ From: Rick Nouwen, Foundations of Semantics V: Intensionality, 2011, available
at: http://www.gist.ugent.be/file/220)
➤ Intensionality is intensively studied in formal linguistics and formal semantics.
Montague, known for Montague semantics in natural language semantics, was a
student of Tarski. (He was killed at 40, and the killer(s) are still unknown.)
➤ In his PhD thesis he has shown that set theory is not finitely axiomatisable.
4
asd
http://www.gist.ugent.be/file/220
INTENSIONALITY OF COMPUTATION
➤ Ordinary extensional logic is only concerned with extensional meaning, i.e., reference,
but intensional logic is concerned with sense as well as reference.
➤ Semantics of programs (or programming language as a whole) must be intensional,
since modes of presentation make huge differences in the meaning of programs
(e.g. their complexity). have different computational senses.
➤ The meaning of programs is not extensional functions but intensional processes.
➤ Intensional semantics of computation is one of the most important challenges in
theoretical computer science, concerned with fundamental questions such as when
two programs are equal to each other, what algorithms are as mathematical objects.
➤ No one has ever succeeded in mathematically defining what exactly algorithms are.
210 and 1024
5
➤ Let Fx be “John knows what x is”, and assume F(MorningStar).
➤ We have: MorningStar=EveningStar.
➤ Then we have F(EveningStar) via substitution, which is paradoxical:
➤ There can be someone who knows what MorningStar is, but knows nothing about
EveningStar (e.g., since he/she is always sleeping in the evening).
➤ Substitution does not always work in intensional contexts.
➤ It may be called the intensionality paradox.
THE INTENSIONALITY PARADOX
6
➤ Likewise: assume and , and K(A) meaning “Pascal knows A”. Then we can
prove: . Equivalent propositions are mutually substitutable; hence K(B).
➤ If you know one truth/theorem, then you know all truths/theorems. No way!
➤ It’s called the knowability paradox (cf. Hintikka’s “scandal of deduction”: “since
tautologies carry no information at all, no logical inference can yield an increase of
information” from D’Agostino-Floridi, Synthese, 2009).
⊢ A ⊢ B
⊢ A ↔ B
THE KNOWABILITY PARADOX
7
THEORY OF DEFINITE DESCRIPTIONS
➤ A definite description is a description that specifies exactly one entity: e.g., “the
present king of France” (Russell’s favourite).
➤ Is “the present king of France is hairy” true (when no such entity exists)?
➤ Russell’s analysis of its logical form: , which consists
of three parts: existence (of x s.t. Fx), uniqueness (of x s.t. Fx), and property (hairy).
➤ Then it’s false; any such sentence is false. Frege-Strawson argued it does not have a
truth value. How about “Pikachu (the mouse-like electrical Pokemon) is yellow”?
➤ It should be true. Both Russell and Frege-Strawson are wrong then? See also: G.
Priest, Towards Non-Being: The Logic and Metaphysics of Intentionality, OUP.
∃x(Fx ∧ ∀y(Fy → x = y) ∧ Hx)
8
https://en.wikipedia.org/wiki/Pikachu
THEORY OF DEFINITE DESCRIPTIONS (CONT’D)
➤ How about “the present king of France is not hairy”? Is it true?
➤ An analysis of its logical form: , which is true.
➤ Another analysis: , which is false.
➤ The scope of negation is ambiguous.
➤ How about “the present king of France is bald or not bald”? Is it true?
➤ For more on Russell’s theory of descriptions, see John’s logic notes.
➤ It’s a classic topic in analytic philosophy, i.e., philosophy via logical analysis.
¬∃x(Fx ∧ ∀y(Fy → x = y) ∧ Hx)
∃x(Fx ∧ ∀y(Fy → x = y) ∧ ¬Hx)
9
REMARKS ON INTEN*S*IONALITY AND INTEN*T*IONALITY
➤ Intensionality is one of the deepest issues across logic, computer science, linguistics,
and philosophy. Broadly, it even connects with philosophy of inten*t*ionality in the
continental tradition, such as Brentano and Husserl’s phenomenology.
➤ ANU’s School of Philosophy is steadily ranked within top 10 in the world, and well
known for philosophy of mind, in which intentionality is essential. One of the
greatest contemporary philosophers worked at the ANU: i.e., David Chalmers.
➤ There are different arguments to show the impossibility of AI (in the sense of
genuine AGI). Searle’s Chinese Room Argument is one of them, concerned with the
intentionality of mind (which, Searle argues, any AI cannot have).
➤ Another argument to show the impossibility of AI is Lucas-Penrose’s Gödelian
argument. Gödel’s second incompleteness theorem is concerned with the
intensionality of the so-called provability predicate in logical systems. 10
asd
11
IDENTITY
IDENTITY AND DENOTATION
➤ A = B means two (possibly different) expressions A and B actually denote (or refer
to) the same thing.
➤ “=” is the binary relation everything has with itself.
➤ , or if and only if .
➤ Note: abbreviates .
➤ What rules of inference govern identity (aka. equality)?
I( = ) is thus given by {(x, x) |x ∈ D} x = y x is y
A ≠ B ¬(A = B)
12
asd
➤ Everything is equal to itself.
➤ (If it sounds too obvious, remember that logic makes everything trivial, i.e.,
transparent, decomposing complex knowledge into trivial pieces or steps.)
➤ (If you have any objection, you may become a continental philosopher. Or logical
pluralism is common these days, so you can disagree and find your own logic.)
RULES FOR IDENTITY: INTRODUCTION
13
t = t
= I
asd
➤ The same things have the same property. (If two things have the same properties,
are they same? Cf. Leibniz’ Identity of Indiscernibles: .)
➤ This elim. rule should be less obvious than the introduction rule.
∀F(Fa ↔ Fb) → a = b
RULES FOR IDENTITY: ELIMINATION
14
t = uFt
Fu
= E
1. t = u
2. Ft
3. Fu 1,2 = E
RULES FOR IDENTITY: EXAMPLE
15
Fa ⊢ ∃x((x = a) ∧ Fx)
α1 (1) Fa A
(2) a = a = I
α1 (3) (a = a) ∧ Fa 1,2 ∧ I
α1 (4) ∃x((x = a) ∧ Fx) 3 ∃I
asd
UNIQUENESS
16
We can express “there exists exactly one…” (which is crucial in math) as follows:
The forward direction ( ) says, e.g., that:
There exists some ball such that for all balls, if a ball is red, then is itself. This is
the “at most one” condition because there might not be any red balls at all.
The backward direction ( ) says, e.g., that:
There exists some ball such that for all balls, if a ball is the same as , then must
be red. This is the “at least one” condition because in particular is red.
→
x y y x
←
x y x y
x
∃x∀y(Fy ↔ x = y)
asd
WHY IS IDENTITY USEFUL?
17
➤ Without identity we can formalise assertions such as “Ted is running”:
and such assertions as that “there exists a faster runner than Ted”:
➤ However, some things can only be expressed with identity, for example:
1. “The only person running is Ted” —
In other words, Ted is running and if x is running, then x is Ted.
2. “Everyone not Ted is running” —
Note that it makes no claim about whether Ted is running.
3. “Ted is the fastest” — . “Faster” plus identity gives “fastest”.
Rt ∧ ∀x (Rx → x = t)
∀x (x ≠ t → Rx)
∀x (x ≠ t → Ftx)
Rt
∃x Fxt
asd
WHY IS IDENTITY USEFUL? (CONT’D)
18
Without identity we cannot express there exists two or more distinct things of the
same kind. Note that:
does not assert the existence of two instances of because it could be the case that
.
With identity we may express the idea as:
A shorter formula expressing the same thing:
(Note: ordinary first-order logic assumes there exists at least one thing.)
F
x = y
∃x∃y(Fx ∧ Fy)
∀x∃y (Fy ∧ x ≠ y)
asd
∃x∃y ((Fx ∧ Fy) ∧ x ≠ y)
WHY IS IDENTITY USEFUL?
19
It may not be immediately evident why this shorter formula asserts the existence of at
least two Fs. Take as “is red”, let’s draw out some cases: F
This does not satisfy the formula
because: for the dot “a” there is no
other dot that is red even though for
all other dots the existential
condition is satisfied.
a
This clearly satisfies the formula. Notice the limiting case where there
are only two red dots “a” and “b”.
They can refer to each other to satisfy
the existential condition!
a
b
asd
∀x∃y (Fy ∧ x ≠ y)
NUMERICALLY DEFINITE QUANTIFIERS
20
➤ In the same manner we can say “there are at least three things”:
➤ We can say “there are at least n + 1 things” as follows:
➤ On the other hand: we can express “there are at most n things” as follows:
➤ Obviously, there are exactly n things if there are at least n and at most n things.
∀x∀y∃z(x ≠ z ∧ y ≠ z)
∃x1 . . . ∃xn ∀y(x1 = y ∨ . . . ∨ xn = y)
∀x1 . . . ∀xn ∃y(x1 ≠ y ∧ . . . ∧ xn ≠ y)
asd
LIMITATIONS OF IDENTITY IN FIRST ORDER LOGIC
➤ We are able to express the following “arithmetical” argument
I) “There are at most 70 guests at the party”
II) “At least 60 of them are students”
III) “Exactly 15 of the party guests are logicians”
IV) “Therefore, at least 5 students are logicians”
➤ This argument can be represented in a purely logical language with equality, and
does not require any arithmetic. To do things like , we need arithmetic.70 − 60 = 10
21
asd
https://www.chegg.com/homework-help/questions-and-answers/relation-u-greater-equal-v-natural-numbers-n-defined-formula-ez-u-z-v–give-formal-proof-u-q64888301
QUESTIONS AND REMARKS
➤ Is equality/identity a logical vocabulary?
➤ What part of language is logical (and what part is not)?
➤ How can we mathematically define the concept of being a logical vocabulary?
➤ Do we already have all logical vocabularies in our logic? Anything missing?
➤ If so, can we mathematically prove that all logical connectives are in our logic?
➤ Lots of questions on identity, such as:
➤ Our body changes everyday due to metabolism; are “we today” identical to “us
tomorrow”? What does it mean we are the same across time? 1 and 1 are located
in different points of space. Why can they be identical? What does it mean? 22
HIGHER REMARKS
➤ First-order logic does not allow us to express “there are finitely many things” or
“there are countably infinite things”, etc., which is the limitation of first-order logic.
➤ There are related to deeper theorems such as the compactness theorem and the
Löwenheim-Skolem theorem.
➤ They allow us to prove the existence of infinitary numbers in models of first-order
arithmetic and the existence of countable models of uncountable real numbers
(Skolem’s paradox).
➤ Some mathematicians don’t like logic because logic allows us to prove these strange
things in an even more rigorous manner than ordinary mathematics.
➤ Logic is interesting, at least to me, because it challenges human reason.
23
24
RESTRICTED
QUANTIFIERS
RESTRICTED QUANTIFIERS
➤ Restricted quantifiers: “every A is B” and “some A is B”.
“Some footballers are hairy”: .
➤ When included in the deduction system quantifiers were unrestricted: “everything is
A” or “something is A”.
➤ We now extend the deduction system to encompass restricted quantifiers.
∃(x : Fx)Hx
25
asd
DEDUCTIVE RULES FOR RESTRICTED QUANTIFIERS
➤ Formulae with restricted quantifier can be turned into unrestricted formulae via the
following equivalences:
➤ and .
➤ To get introduction rules and elimination rules for restricted quantifiers we can start
with the equivalent unrestricted version and proceed with the usual deductive rules.
∀(v : A) B ≡ ∀v(A → B) ∃(v : A) B ≡ ∃v(A ∧ B)
26
asd
INTRODUCTION RULE FOR RESTRICTED UNIVERSAL QUANTIFIER
➤ We can derive the introduction rule for restricted universal quantifier (with the side-
condition as usual) in the following way:
27
X, A ⊢ B
∀I
X ⊢ ∀v (A → B)
X ⊢ A → B
→ I
X, A ⊢ B
∀IR
X ⊢ ∀(v : A) B
asd
ELIMINATION RULE FOR RESTRICTED UNIVERSAL QUANTIFIER
➤ The elimination rule for restricted universal quantifier takes the formula
to a specific instance of .
➤ We can start with the equivalent formula and proceed with the usual
deductive rules:
∀(v : A) B
B
∀v(A → B)
28
∀v(A → B)
Atv
→ E
Btv
Atv → B
t
v
∀E
asd
ELIMINATION RULE FOR RESTRICTED UNIVERSAL QUANTIFIER
➤ With restricted quantifier we can collapse the two step into one:
➤ In particular this rule allows us to prove in one step.∀(x : Fx) Gx, Fa ⊢ Ga
29
Atv∀(v : A) B
∀ER
Btv
∀v(A → B)
Atv
→ E
Btv
Atv → B
t
v
∀E
asd
INTRODUCTION RULE FOR RESTRICTED EXISTENTIAL QUANTIFIER
➤ Likewise: through the equivalence , we have:∃(v : A) B ≡ ∃v(A ∧ B)
30
∧ I
∃I
Atv B
t
v
Atv ∧ B
t
v
∃v(A ∧ B)
∃IR
Atv B
t
v
∃(v : A) B
asd
ELIMINATION RULE FOR RESTRICTED EXISTENTIAL QUANTIFIER
➤ The elimination rule for restricted existential quantifier:
31
∃E
X ⊢ ∃v(A ∧ B) Y, A ∧ B ⊢ C
X, Y ⊢ C
∃ER
X ⊢ ∃(v : A) B Y, A, B ⊢ C
X, Y ⊢ C
asd
Here is a sample proof with restricted quantifiers. Note: when you are confused about
restricted quantifiers, consider what they stand for in terms of ordinary quantifiers.
EXAMPLE
32
∀(x : Fx)Gx ⊢ ∀(x : ¬Gx)¬Fx
(1) ∀(x : Fx) Gx Aα1
(2) ¬Ga Aα2
(3) Fa Aα3
(4) Ga 1,3 ∀ERα1, α3
(5) ¬Fa 2,4[α3] RAAα1, α2
(6) ∀(x : ¬Gx)¬Fx 5[α2] ∀IRα1
asd
RESTRICTED QUANTIFIER EXAMPLE
33
Classic syllogisms such as the following can be expressed via restricted quantifiers:
All F is G;
Some H is F;
Therefore some H is G
asd
Formally, we can prove the following sequent in the following manner:
FORMALLY
34
∀(x : Fx)Gx, ∃(x : Hx)Fx ⊢ ∃(x : Hx)Gx
(1) ∀(x : Fx) Gx Aα1
(2) ∃(x : Hx) Fx Aα2
(3) Fa Aα3
(4) Ga 1,3 ∀ERα1, α3
(5) Ha Aα4
(6) ∃(x : Hx) Gx 4,5 ∃IRα1, α3, α4
(7) ∃(x : Hx) Gx 2,6 [α3, α4] ∃ERα1, α2 asd
35
asd
Appendix
EXAMPLE: COMPLEX PROOF WITH IDENTITY
36
∀x∃y(Fy ∧ (x ≠ y)) ⊢ ∃x∃y((Fx ∧ Fy) ∧ (x ≠ y))
α1 (1) ∀x∃y(Fy ∧ (x ≠ y)) A
α1 (2) ∃y(Fy ∧ (a ≠ y)) 1 ∀E
α2 (3) Fb ∧ (a ≠ b) A
α2 (4) Fb 3 ∧ E
α1 (5) ∃y(Fy ∧ b ≠ y) 1∀E
α3 (6) Fc ∧ (b ≠ c) A
α3 (7) Fc 6 ∧ E
α3 (8) b ≠ c 6 ∧ E
α2, α3 (9) Fb ∧ Fc 4,7 ∧ I
α2, α3 (10) (Fb ∧ Fc) ∧ (b ≠ c) 8,9 ∧ I
α2, α3 (11) ∃y((Fb ∧ Fy) ∧ (b ≠ y)) 10∃I
α2, α3 (12) ∃x∃y((Fx ∧ Fy) ∧ (x ≠ y)) 11∃I
α1, α2 (13) ∃x∃y((Fx ∧ Fy) ∧ (x ≠ y)) 5,12[α3]∃E
α1 (14) ∃x∃y((Fx ∧ Fy) ∧ (x ≠ y)) 2,3[α2]∃E
∎
EXAMPLE: MIXING RESTRICTED AND UNRESTRICTED QUANTIFIERS
37
We can also mix restricted and unrestricted quantifiers:
∀(x : Fx) ∃y Rxy, ∀x∀(y : Rxy) (Ryx ∧ ∀(z : Ryz) Rxz) ⊢ ∀(x : Fx) Rxx
α1 (1) ∀(x : Fx) ∃y Rxy A
α2 (2) ∀x∀(y : Rxy)(Ryx ∧ ∀(z : Ryz) Rxz) A
α3 (3) Fa A
α1, α3 (4) ∃y Ray 1,3 ∀ER
α4 (5) Rab A
α2 (6) ∀(y : Ray)(Rya ∧ ∀(z : Ryz) Raz) 2 ∀E
α2, α4 (7) Rba ∧ ∀(z : Rbz) Raz 5,6 ∀ER
α2, α4 (8) Rba 7 ∧ E
α2, α4 (9) ∀(z : Rbz) Raz 7 ∧ E
α2, α4 (10) Raa 8,9∀E
α1, α2, α3 (11) Raa 4,10[α4] ∃E
α1, α2 (12) ∀(x : Fx) Rxx 11[α2] ∀IR
asd