Making Logic Part 4 – Logic is Interesting from Here Non-Classical Logic Reading Notes

Making Logic Part 4 – Logic is Interesting from Here Non-Classical Logic Reading Notes

Logic is the study of the way humans think and argue, and in particular, it deals with the basic concepts of propositions and reasoning.

The basic concepts of logic include propositions, propositional logic, and the symbolic system of logic. A proposition is a statement that is determined to be true or false. Propositional logic is the field of logic that deals with propositions and uses logical operators to represent logical relations. The symbol system of logic is a system that defines symbols to express logical operations, and in propositional logic, logical operators such as “negation,” “logical conjunction,” and “logical disjunction” are used.

In addition to propositional logic, there are other fields of logic such as first-order predicate logic and higher-order logic. First-order predicate logic is a type of propositional logic that can express more complex logical relations by introducing predicates and variables. Higher-order logic deals with logic involving mathematical concepts such as sets and functions.

Logic also includes the study of methods for determining the truth or falsehood of propositions and for making correct inferences. For example, there are methods of determining the truth or falsity of propositions, such as truth tables and proofs. The truth table is a method of determining the truth of a proposition by testing all possible combinations of truth and falsehood for the proposition. Proof is the logical procedure for showing that a proposition is true, using axioms and rules of inference to derive the truth of the proposition.

Logic is also closely related to philosophy, mathematics, and artificial intelligence. In philosophy, the concepts of logic are used to make logical arguments, and in mathematics, logic is used to construct the basic system for deriving mathematical propositions. In artificial intelligence, it is the basis for reasoning and knowledge information processing techniques.

Mathematical theories on which logic is based include set theory, as described in “Overview of Set Theory and Reference Books,” algebra, as described in “Structures, Algorithms, and Functions,” and formal linguistics and semantics, as described in “Formal Languages and Mathematical Logic,” which can be found at See also.

we present reading notes from “Making Logic,” a well-known textbook on mathematical logic.

Following t he previous Part 3 – Another Look at Logic, this time I will discuss Part 4 – Logic is Interesting from Here on out Reading Notes on Non-Classical Logic.

Part IV: Logic gets interesting from here on out!　A roadmap for advanced topics

Chapter 11: Welcome to the Dazzling World of Non-Classical Logic!

Introduction
The logic that we have developed so far is called “classical logic.
I don’t mean old-fashioned logic.
The “classical” in “classical logic” means “basic” or “standard.
Classical logic means “basic” or “standard.”
Classical logic has reached a certain level of completion.
Frege’s Concept Notation, 1879
Why is classical logic considered to be standard?
It is idealized so that it has a basic and beautiful form.
Examples of idealization
(1) In classical logic, “we do not deal with couplings that are not truth functions.
All couplings can be defined in truth tables.
(2) Classical logic adopted the bivalence principle.
A (closed) logical formula always has a value that is either true or false
In this chapter, we will challenge this idealization.
What you will learn as a result
There is more than one logic.

11.1 Classical Logic is God’s Logic — The Disreputability of the Two-Valued Principle and the Law of Exhaustion

Introduction
Classical logic is based on the two-valued principle, which states that all logical expressions are either true or false.
This is straightforwardly expressed by the exclusion principle (P V ¬P is a tautology).
Does the law of exclusivity allow us to accept any proposition of P as unquestionably true at any time?
I want the future to be open.
Is the proposition about the future, “Chris will have a bacon lettuce barber for dinner tomorrow,” true or false?
If it’s either true or false, then the future is predetermined.
Determinism eliminates “accidental truth” and “free will”.
Doubts from Constructivism
“There are a,b such that ab is a rational number even though a and b are both irrational numbers.”
“Is √2√2 a rational number or an irrational number?” Judge it by its exhaustive form, without deciding.
Either √2√2 is a rational number or an irrational number.
Is it?
Can we make it up?
Mathematical things are already determined, whether we can know them or not.
There is only a mathematical counter-rain that we can create.
From the Logic of God to the Logic of Man
Classical logic is a logic from God’s point of view that can transcend time, list the history of the universe, never forget anything, complete infinite tasks, and know the truth of any proposition.
The beauty of classical logic is a reflection of the clarity of God’s perspective.
Isn’t there a logic from the perspective of finite human beings?

11.2 Multi-valued Logic

11.2.1 Ukasiewicz’s Critique of Classical Theory and Three-Valued Logic
Introduction
How can we remove the law of exhaustion from logic?
Stopping the two-valued principle
Ukasiewicz’s three-valued logic
True, False, and the Third Truth “Possible
Definition of logical connectives and three-valued tautology
Logic with three truth values: true (1), false (0), and possible (0.5)
¬
→.
Why did we define it this way?
V
A V B = df(A → B) → B
Λ
AΛB=df¬(¬AⅤ¬B)
↔︎
A↔︎B=df(A→B)Λ(B→A)
In three-valued logic, a logical formula that always takes the truth value 1 is called a three-valued tautology (three-valued tautology)
A→A
The exclusivity rule is not a tautology
A:0.5
A ¬A:0.5
A V ¬A:0.5
Justification for the definition of logical connectives
Why did we define the combinator ‘→’ as above?
The interpretation is as follows
1: “Already determined to be true”
0: “Already determined to be false
0.5: “It may become true or false in the future.
0→0.5
0→0.5” could be “0→0” or “0→1”.
Both are 1, so “0→0.5″ becomes 1.
0.5→1″ could be
0→0.5→1” could be “0→1” or “1→1”.
0.5→1″ could be 0 or 1, so it becomes 0.5.
0.5→0.5″ is
The value 0.5→0.5 is probably set to 1 to make P→P a ternary tautology.
Does the value 0.5 mean “possible”?
Example
Let A be “My computer’s hard disk will crash tomorrow.
At this point, A is neither true nor false.
¬A is also neither true nor false.
Tomorrow my computer’s hard disk will break, and it will not break.
It seems to be false.
It does not seem to be 0.5.
11.2.2 Fuzzy Logic
Introduction
Multi-valued logic systems are
Many truth values can be considered, including 3-valued, 4-valued, and so on.
There are many ways to define logical connectives.
Multi-valued logic is so artificial that it fell out of favor after its inception in the 1920s and 1930s.
With the development of the field of fuzzy logic, it became of interest again.
Paradox of Chain Reasoning
Example
Consider the following three propositions
(a) A person with zero hair on his head is bald.
(b) A person with a million hairs on his head is not bald.
(c) For all natural numbers n, if a person with n hairs on his head is bald, then a person with n+1 hairs on his head is also bald.
If (c) is deduced consecutively, then all people with all numbers of hair are bald, which contradicts (b).
Fuzzy predicates and crisp predicates
These paradoxes include so-called fuzzy predicates such as “I am bald”.
English “fuzzy”.
Fuzzy means fluffy, like cotton wool.
The adjective “fuzzy” is used for blurry pictures, drawings, and unclear ideas.
Fuzzy predicates are sometimes referred to as “vague predicates.
The word “fuzzy” has so many meanings that it’s hard to tell which one is being used.
Fuzzy does not mean polysemous.
Example
The predicate “heavy” has a clear meaning.
The predicate “heavy” has a clear meaning, but there is no boundary between the two.
Fuzzy predicates do not mean the following
“The borderline is not clear as a whole, because different people place the borderline differently.”
When B is a fuzzy predicate, ∃n(B(n)Λ¬B(n+1)) is false.
Opposing notions of fuzzy predicates
Crisp predicates
Have clear boundaries.
Crisp
Adjectives used for food
Crisp, crunchy (and therefore delicious)
Relationship between fuzzy predicates, the two-valued principle, and the paradox of chain inference
Semantics of classical logic
Fuzzy predicates in the framework of two-valued logic
Degrees of truth
Forms we want to treat for fuzzy predicates
It is necessary to admit not only two kinds of truth values, 1 and 0, but also countless intermediate degrees of truth.
Fuzzy logic is a kind of infinite multi-valued logic
Semantics of fuzzy logic
Giving semantics among fuzzy propositional logics
Define a truth value assignment V to an atomic formula in FPL as follows
Definition.
Let F be the set consisting of atomic formulas of FPL
The truth-value assignment V to F is a function as follows
V : F→[0,1].
In classical logic, {1,0} becomes [1,0].
Example: Single logical formula
“A person with 0 hair on his head is bald.
“A person with 500 hairs on his head is bald.
“A person with 5,000 hairs on his head is bald.”
Defining truth values for compound logical expressions
Use inductive definitions
Let Ḟ be the set consisting of all logical formulas defined inductively from the atomic formulas in F.
Create a function Ṽ:Ḟ→[0,1] that assigns a degree of truth to all the logical expressions in Ḟ.
The definition then is
(F-atomic)
When A is an atomic formula, let Ṽ(A)=V(A)
To assign a degree of truth to any composite logical formula A and B in a coherent way, we define
(F¬) Ṽ(¬A) = 1 – Ṽ(A) (FΛ) Ṽ(AΛB) = min(Ṽ(A), Ṽ(B)) (FⅤ) Ṽ(AⅤB) = max( Ṽ(A), Ṽ(B))
min[x,y] is the smaller of x and y
max[x,y] is the larger of x and y
(F→) Ṽ(A→B) = {1 – (Ṽ(A) – Ṽ(B)) if Ṽ(A)>Ṽ(B) {1 otherwise
In classical logic, when A is 1 and B is 0, A→B is 0.
The first case was 1, but the second case is 0.
The degree of truth has been reduced by 1-0=1, so
The overall degree of truth has also decreased by 1, to 1-1=0.
Definition of Semantic Consequences
To complete the semantics, we need to define the concept of semantic consequence.
How do we capture the fact that a logical formula C is semantically consequent from a formula set Γ?
For simplicity, let the set of formulas Γ be a finite set
Define Ṽ(Γ) to be the smallest degree of truth of a logical formula belonging to Γ.
Definition 1
There is no truth-value assignment Ṽ such that Γ⊨C ⇔ Ṽ(Γ)=1 and Ṽ(C)=0.
Fuzzy logic cannot be used as is
This definition is also satisfied if the degrees of truth of the logical formulas that are elements of Γ are all 0.9 and the degree of truth of C is 0.1.
However, the degree of truth of the premise is significantly reduced in the conclusion
The degree of truth is not preserved
For fuzzy logic
Definition 2
There is no truth value assignment Ṽ such that Γ⊨C ⇔ Ṽ(Γ)=1 and Ṽ(C)<0
Definition 3
There is no truth-value assignment Ṽ such that Γ⊨C ⇔ Ṽ(C)<Ṽ(Γ).
More stringent conditions
Analysis of the Paradox of Chain Reasoning
How does the above semantics resolve the paradox of chain inference?
(1) Chain inference is not successful.
By (F→), we can say the following
The truth value of the carbonation assumption (B(n) → B(n+1)) in the inference in question is not 1
Due to the fuzzy nature of the predicate B, the degree of truth of B(n) is always higher than that of B(n+1)
Ṽ(B(n))>Ṽ(B(n;1))
Ṽ(B(n)→B(n+1))=1-(Ṽ(B(n))-Ṽ(B(n+1)))<1
Even if the inference is valid, we don’t have to accept that the conclusion is 1 (true)
(2) Chain inference is not even valid if we take a strong definition of logical consequence.
Chain reasoning is basically a repetition of an inference (MP) of the form “A → B, A, therefore B”.
The above inference is valid under definition 2, but becomes invalid if we adopt definition 3. Translated with www.DeepL.com/Translator (free version)

11.3 Intuitionistic Logic

11.3.1 The Formation of Intuitionistic Logic
Even when we take a constructivist position on mathematics, doubts about the law of exhaustion arise.
Intuitionistic mathematics” by Luitzen Egbertus Brouwer
Considers mathematics to be more connected to human mental activity.
Eliminated the unlimited use of the law of exclusivity and the back law
Since the essence of mathematics lies in the constitutive workings of the mind
Mathematics should be redesigned based on the workings of the mind.
Example
We can’t work through all the minority expansions of π
In intuitionistic mathematics, mathematical objects such as real numbers are not complete objects
but as something that is being generated.
Example 2
We have not yet found a place in the minority expansion of π where there are 100 7’s in a row.
As a matter of fact, it must either appear or not appear
We can claim P V ¬P even if we don’t know whether it is P or ¬P
The unrestricted application of the law of exhaustion is an abuse of logic.
The logic of intuitionistic mathematics has been taken out
Intuitionistic logic
11.3.2 Natural deduction for intuitionistic logic
Which rules can be modified to abandon the law of exhaustion?
Intuitionistic logic is
In the direction of preventing the law of exclusions from appearing as a theorem.
The goal is to eliminate the exclusionary rule
How do we do this?
Natural deduction ND (but with contradiction symbols) inference rules for classical logic
(1) Introduction and elimination rules for →Λ V →.
(2) ¬intro* and ¬elim*.
(3) Double negation elimination rule
Proof of the exclusion rule in natural deduction
The point is to use DN at the end of the double negation.
Without DN, there is no exclusion rule
Discard the DN inference rule
DN
Two “¬”s are the same as no “¬”s (rule)
Defining DNs gives “¬” a negative meaning
What is the problem with simply discarding the DN?
Two symbols appear in ¬intro* and ¬elim: “¬” and “⊥”
Without defining the DNs, the meanings of “¬” and “⊥” cannot be fixed
¬intro* is
If ⊥ appears from A, we can derive ¬A
¬elim* means
If you can say A and ¬A at the same time, you can derive ⊥
Remove DNs and add rules that are weak enough to prevent proof of the exhaustion rule
Contradiction rule: (absurdity rule : AB)
| ⊥ | B
Anything can come out of ⊥.
Inference rules for NJ (natural deduction for intuitionistic logic)
(1) Introduction rule and elimination rule for →Λ V →.
Common with ND
(2) ¬intro* and ¬elim*.
Common with ND
(3) Contradiction rule (AB)
Can be deduced by DN instead of AB (but not vice versa)
11.3.3 Expressions that are provable in ND but not in NJ
All expressions that are provable in NJ are also provable in ND
It does not mean the opposite (an expression provable in ND is also provable in NJ).
Other examples of expressions that are provable in ND but not in NJ
Law of exclusions
⊬NJP V¬P
⊢NJ¬¬(PⅤ¬P)
¬(PΛ¬P)
On double negation
(1) P cannot be deduced from ¬¬P
(2) ¬¬P can be deduced from P
(3) Double negation is not possible in NJ, but triple negation can be made into single negation
On de Morgan’s Law
One side of de Morgan’s law is valid in NJ
Versions that replace conjunction and declaration are not allowed
The Law of Opposites
Only half of the law of opposites is provable in NJ
On the definability of couplings
Cannot define → by ¬ and Λ, or ↔ by V, Λ, and ¬ in NJ
Λ cannot be defined by ¬ and V either, due to the failure of Morgan’s law.
In NJ, the connectives have independent meanings and cannot be defined in terms of each other
11.3.4 Rules equivalent to double negation
Adding either of the following to NJ will return to ND
(1) Admit the exclusion rule as an axiom
You can write an expression of the form A V ¬A at any time.
(2) Reduction ad absurdum (RAA)
If you can derive a contradiction by assuming the negation of A
A can be derived.
If the exclusion law is accepted as an axiom, it has the same effect as double negation elimination.
11.3.5 Intuitionistic Semantics
Multivalued Logic and Intuitionistic Logic
Many-valued logic and intuitionistic logic were both born from the question of the law of exhaustion.
Both discard the law of exhaustion in different ways
Multi-valued logic discards the bivalent principle
Intuitionistic logic changes the rules of inference so that the law of exhaustion can no longer be proved by natural deduction (from ND to AB)
The two are not in the same logical system
¬¬P→P is
Tautology in 3-valued logic
In intuitionistic logic, it is not a theorem
Proof interpretation and its limitations
Looking at the semantics of intuitionistic logic
The fundamental idea of intuitionistic logic
We cannot prove or disprove anything, but in the “world of numbers” it is wrong to think that it must be true or false.
It is pointless to think about truth or falsehood, which is independent of our cognitive abilities.
It is important whether we have a way to confirm the fact (proof in mathematics) or not.
Semantics of Classical Logic
The basic concept is “A is true,” which is true whether we know it or not.
Semantics of intuitionistic logic
Semantics based on “I have a way to prove A”.
Semantics of Intuitionistic Logic by Haitink
Meaning of the connectives given by Haitink
(1) AⅤB: either have a way to prove A or have a way to prove B
(2) AΛB: has a way to prove A and also has a way to prove B
(1) A→B: Given a proof of A, we have a way to produce a proof of B based on it.
(1) ¬A: Assuming the proof of A is given, I have a way to derive a contradiction based on it.
Using the proof interpretation, we can see why intuitionistic logic is forbidden
(1) Exhaustive law: A V ¬A
Have a way to prove A or derive a contradiction from A
Every proposition has a proof or disproof.
(2) Back law: ¬ A
Even if we can derive a contradiction from ¬A, it does not mean that we have a way to prove A directly
Limitations of the proof interpretation
¬¬¬We can’t use proof interpretation to explain why ¬¬A → ¬A is allowed in intuitionistic logic
Basic ideas of Kripkian semantics
Saul Kripke’s Kripke Semantics
(1) Basic idea
Think of mathematics and logic as activities that take place in the mind of a person who is perceived as idealized to some extent.
Let this person be α.
(2) α’s cognitive activity occurs along time.
At some point in time, α comes to know some facts by proving or verifying them.
However, it is assumed that α has a perfect memory and will never forget what he knows at a certain point in time.
(2) Time is assumed to be jumping around like a zero number.
(3) Assume that α always has the possibility of increasing its knowledge at each point in time.
The path of α’s knowledge is branched out as shown in the upper right.
Each node σ represents a possible state of knowledge for α.
We denote by σi≤σj that σ1 is earlier than σ2 and σi is earlier than σj in time.
The set S of all stages has a tree structure with branches in only one direction with respect to this ≤.
A set with this structure is called a “partially ordered set” in mathematics.
When considering intuitionistic predicate logic with quantifiers
Α does not only increase its knowledge at each point
It constructs various objects by making the next prime number or calculating the next term in a sequence of numbers.
(4) At each step, we will write the atomic formula known to α along with its nodes.
Example
Atomic formula A is known (proven/verified) in σi and σi≤σj ⇒ A is also known in σj
Definition of model structure
Definition
m=<σ0,S, ≤> is called the model structure.
σ0 is the starting point
S is a set of steps
≤ is a partially ordered set defined on S
Example
Model M on model structure m
Definition
A model M on a model structure m=<σo, S, ≤> is
is the following triplet
M=< m, V, ⫦ >
V: and a function that assigns to each element σ a set of atomic formulas
⫦: The relation between the stage σ and the logical formula A
A logical formula A is known at stage σ
If A is a composite formula
(1) σ⫦AΛB ⇔ σ⫦A and σ⫦B (2) σ⫦AⅤB ⇔ σ⫦A or σ⫦B (3) σ⫦A→B ⇔ σ’⫦A then σ’⫦B for all σ ≤ σ’ ∈ σ’⫦B (4) σ⫦¬A ⇔ σ’⊮A for all σ ≤ σ’ ∈ σ’⫦B
Let’s understand the aim of the definition.
Why did you define it this way?
(!) (1), (2) is true.
About (3), (4)
(3) Knowing that A → B is a step σ
(3) Knowing A → B at stage σ does not mean that you know anything definite about A or B at that stage.
What we can say is
If we have the proof of A much later, at stage σ’, then
If you get the proof of A at a later stage σ’, you can combine it with the proof of A → B that you got at stage σ
we also get the proof of B.
Given the proof of A, we have a way to produce the proof of B based on it.
About (4)
In intuitionistic logic, ¬A works the same as A → ⊥.
In intuitionistic logic, ¬A “has a way of producing a contradiction based on the proof of A, given the proof of A”
We can say
If the proof of A is available at a later stage σ’, then
If we get the proof of A at a later stage σ’, we can combine it with the proof of ¬A (how to derive a contradiction from A) that we had at stage σ
The contradiction will occur at stage σ’.
It is not possible to get an illumination of A at a later stage σ’.
Example of a model

Examples
(1) The only atomic formula illuminated at the starting point, σ0, is P
The possibility of obtaining further information is open.
(2) At stage σ0, Q is not proved.
(3) In order for σ0⫦¬Q, Q must not be illuminated at any stage after σ0.
Since Q is illuminated after σ2, it becomes σ0⊮¬Q
(4) Q is not illuminated at any stage after σ1, so σ1⫦¬Q
(5) For σ2 and σ4, it looks the same, but σ4 adds information that closes the option of illuminating R.
(6) σ2⊮R, and σ2⊮RⅤ¬R
At stage σ2, it is not possible to determine whether R is correct or not
At stage σ4, it is σ4⫦¬R, so σ4⫦RⅤ¬R
Semantic consequences in intuitionistically valid formulas and intuitionistic logic
Definition of logical truth from the perspective of intuitionistic logic
Intuitionistically valid formula (intuitionistically valid wff.)
Definition
A is intuitionistically valid
⇔
σ⫦A for all steps σ ∈ S of any model M on any model structure m = <σ0, S,≤>.
If we want to illuminate that some logical formula A is not an intuitionistically valid formula
If we want to illuminate that a formula A is not intuitionistically valid, we can create a model that contains some stage σ such that σ⊮A.
If you want to prove that some logical formula A is intuitionistically valid
If you want to prove that a formula A is intuitionistically valid, you can assume that such a model exists and derive a contradiction.
Such a model is called a “counter model of A”.
How can logical consequence be defined in intuitionistic logic?
The concept of syntactic consequence as defined from the syntax standpoint is deduction in NHJ.
Definition
Γ⊨C (a logical C is intuitionistically and semantically deduced from a set of logical formulas Γ).
At every stage σ of every model the following holds
σ⫦A for every logical formula A of the elements of Γ ⇒ σ⫦C
What happens next?
We have introduced the axioms of intuitionistic logic (natural deduction NJ) and semantics.
Two tasks to be done after this
(1) Completeness proof of intuitionistic logic
As for intuitionistic logic
The set of theorems in NJ coincides with the set of intuitionistically valid formulas.
Furthermore, we can prove the completeness of the following statement: “There is a deduction from the set of formulas Γ to C ⇔ The logical formula C is intuitionistically and semantically consequent from the set of formulas Γ.
(2) Decision Procedure of Intuitionistic Logic
A tableau of classical propositional logic (mechanical procedure)
Intuitionistic logic also has an algorithm that can tell us in a finite number of steps whether an arbitrary logical formula is intuitionistically valid or not

11.4 Modal Logic as an Extension of Classical Logic

11.4.1 Alternatives to Classical Logic or Extensions of Classical Logic
There are many axioms in classical logic (e.g. APL, ND).
The range of formulas that come out of it as theorems is the same
Both are a single axiomatic system of the same classical logic
APL and ND are apparently different, but they are the same system of logic
In non-classical logic
Some of the things that are considered truths in classical logic are not considered logical truths
Law of exclusions
Example
There is a discrepancy between the scope of theorem in classical logic ND and the scope of theorem in intuitionistic logic NJ.
Intuitionistic logic is “non-classical logic as an alternative” that seeks to replace classical logic
Another non-classical logic
All formulas that are considered true in classical logic are recognized as logical formula truths.
In addition, it can handle logical truths that cannot be handled by classical logic.
Modal logic
A logic formed by adding two modal operators to classical logic.
◇(possibility operator)
◇P(It is possible that P)
□Necessity operator
□P(P is a necessity)
If we use this operator
The proposition “It happens to be P” is
PΛ◇¬P
PΛ◇¬P
11.4.2 There are a lot of axiomatic systems in modal logic
In modal logic, there are many systems (axiomatic systems) with different sets of theorems.
More than 100
In the early days, it was not clear how to give a definition of truth to a logical formula containing a modal operator.
In the case of modal logic, what is the logical truth is much more blurred.
Example
(a) □P → ¬◇¬P (always P means that it is impossible for P not to be P)
(b) ◇P ↔ ¬¬□¬P (To say that something can be P is not to say that it must not be P.)
(c) □P→P (If it is always P, then it is actually P.)
(d) P → ◇P (If it is actually P, it can be P)
First, let’s characterize syntactically from the standpoint of syntax.
Enumerate the entire set of logical truths, including aspects, in an axiomatic way.
I will try to cover only some standard systems.
Axiomatic system K
The foundation of all axiomatic systems.
[This axiomatic scheme itself is also called K. [Transformation rule] R1 MP R2 ⊢A ⇒ ⊢□A (This rule is called the Necessitation rule. 　　　　　　　　(This rule is called Necessitation.) The hidden feeling is: “If A appears as a theorem, it is a logical truth, so it must be true. 　　　　　　　　So it’s OK to put □ on it.”)
A is introduced by definition.
Of course, P=df¬□¬P.
Logical formula provable in K
(1) □(PΛQ) ↔ ↔ (□PΛ□Q) (distributive law) (2) ◇(PⅤQ) ↔ ↔ (◇PⅤ◇Q) (distributive law) (3) □P ↔ ¬◇¬P
Axiom system T
Definition
The axiomatic system K with the following axioms is called T. □A → A (this axiomatic system is also called T)
A logical formula that is not provable in K but becomes provable only in T
(4) P → ◇P (5) ◇(P → □P)
Reduction laws and S4 and S5
All aspects are different in axiomatic system T

because
T does not contain any of the following reduction laws (theorems that have the effect of reducing the variety of multiple aspects)
There are infinitely many multiple aspects in T
(1) ◇P ↔︎ □◇P (2) □P ↔︎ ◇□P (3) ◇P ↔︎ ◇◇P (4) □P ↔︎ □□P
Reduce the variety of multiple aspects by adding some reduction laws to T
(5) ◇P → □◇P (6) ◇□P → □P (7) ◇◇P → ◇P (8) □P → □□P
The following new axiomatic system is born
Definition
The axiomatic system that adds (8) □A → □□A (this axiomatic scheme is called 4) to T is called S4 The axiomatic system that adds (5) ◇A → □◇A (this axiomatic scheme is called 5) to T is called S5
Axiom 4 is derived as theorem in S5
Every theorem in T is also a theorem in S4
Every theorem in S4 is also a theorem in S5
Introduction of another axiomatic system
Definition
The axiomatic system that adds A→□◇A (this axiom is called B) to T is called B
A→□◇ can be derived as a theorem in S5, but not in S4
Every theorem of T is also a theorem of B
Every theorem in B is also a theorem in S5
Correlation of each
In S4, there are 7 types of theorems
In S4, the following theorem is derived
(6) □P ↔ □□P (7) ◇P ↔ ◇◇P (8) □◇P ↔ □◇◇◇P (9) ◇□P ↔ ◇◇□P
Thanks to these theorems, S4 can be narrowed down to the following seven types
None, □, ◇, □◇, ◇□, □◇, ◇□, ◇□◇, ◇□◇.
In S5, there are three kinds of theorems
In S5, the following theorem is derived
(6) ◇P ↔︎ □◇P (7) □P ↔︎ ◇□P (8) ◇P ↔︎ ◇◇P (9) □P ↔︎ □□P
In S5, the three types are as follows
None, □, ◇.
Characterize S5 in a different way
P→□◇P (i.e. B) and ◇□P→P are both theorems of S5, but not of S4.
Add either of these to S4 to get S5
Adding B to T, which is weaker than S4, does not reach S5.
Lemmon code
Since there are many axiomatic systems in modal logic
It would be nice to have a classification code that can properly represent their interrelationships.
E.J. Lemmon, an early researcher of modal logic, proposed a classification code for Western-style logic systems called the Lemmon code in a paper published in 1977.
K…. which has the form
Example
KXYZ” is an axiom of “APL” with “K,X,Y,Z” added as axioms
K □(A→B)→(□A→□B) T □A→A 4 □A→□□A B A→□◇A 5 ◇A→□◇A
Using the lemon code, we can rename and organize the axiom systems that have appeared so far as follows
K = K T = KT S4 = KT4 B = KTB S5 = KT5 = KT4B Translated with www.DeepL.com/Translator (free version)

11.4.3 Semantics of Modal Logic
Getting Started
Next Steps
Create a semantics such that all theorems of the axiomatic system are valid.
Prove that the set of theorems in the axiomatic system overlaps exactly with the set that is valid in the created semantics (completeness proof).
This shows that both approaches (syntax and semantics) have successfully captured the logical truth about Western clothing.
In multi-valued logic, semantics was created first.
In modal logic, syntax has been developed to such an extent that many axioms have been created.
In modal logic, axioms are added to the core axiom system K one after another.
The semantics for each axiomatic system can be obtained by adding one condition after another to the semantics common to all axiomatic systems.
Saul Kripke’s possible-worlds semantics, which he developed in high school, is
For the first time, we can give semantics to all the different logical systems such as T, B, S4, S5, etc.
It was the first semantics that was able to give semantics to all the different logical systems such as T, B, S4, and S5.
It has become the standard semantics of modal logic.
Possible World Semantics
The basic idea of possible world semantics
Always P means that P is possible not only in this world, but in any world.
If P is possible, it means that even if P is not possible in this world, P is possible “in some other world.
<Basic Idea
(1)
Consider multiple worlds.
(1) Consider multiple worlds. Each world is called a possible world.
One of the possible worlds is called the real world.
A logical formula has a truth value in each possible world.
It can be different in each world.
(2)
A relation called accessibility is defined between the possible worlds.
From the point of view of world w, world w’ is reachable.
The world w’ is reachable from the point of view of the world w. It can be thought of as being able to be reflected in the world w’ by slightly changing the world w.
We can think of it as the fact that w’ can be “seen” from w.
(3)
After this, define the truth or falsehood of “□A” and “◇A” in each possible world as follows
□A is true in the possible world w
⇔
A is true in all possible worlds reachable from W.
◇A is true in the possible world w
⇔
A is true in any of the possible worlds reachable from W
By imposing various restrictions on the reachability relation between possible worlds, we try to obtain semantics for various axiomatic systems.
Definition: Kripke Frame
A pair F=<W,R> of a non-empty set W and a binary relation R on W is called a frame.
An element of W is called a “possible world”.
R is called a reachability relation.
Definition: A Kripkian model based on a frame F
For a frame F=<W,R>, we have
The triplet M=<W,R,V> is called the Kripki model M based on frame F
where V is called the additive function. It is a function that assigns a truth value to each of the primitive equations for each possible world.
The truth value that V assigns to the atomic formula A in the possible world w of model M is denoted as VM(w,A).
When there is no need to distinguish the name of the model, it is simply written as V(w,A).
The Klipki model consists of the following three elements
(1) A set of possible worlds W
(2) A reachability relation R among the possible worlds
(3) An additive function V that assigns to each of the present expressions the truth value that each possible world takes.
Even if the frame is the same, if V is different, what atomic formula is true in each possible world will be different, resulting in a different model.
Definition of truth in a model
Define the truth value ṼM(w,A) that a general logical formula A, including compound ones, takes in a possible world w of model M
Definition
(1) If A is an atomic formula, then ṼM(w,A)=1 ⇔ VM(w,A)=1 (2) If A is a logical formula of the form ¬B, then ṼM(w,A)=1 ⇔ ṼM(w,B)=0 (3) If A is a logical formula of the form B→C, then (3) When A is a logical formula of the form B→C, then ṼM(w,A)=1 ⇔ ṼM(w,B)=0 or ṼM(w,C)=1 (4) When A is a logical formula of the form □B, then ṼM(w,A)=1 ⇔ wRw’ for all possible worlds w’ such that (5) ṼM(w’,B)=1 in at least one possible world w’ such that ṼM(w,A)=1 ⇔ wRw’ when A is a logical formula of the form ◇B.
Example of a model
Let frame F=<W,R> be given by W={w1,w2,w3} and R={<w1,w2>,<w2,w3>}.
Assigning to the possible worlds of this frame F the truth value that each atomic formula takes in that world, the model M=<W, R, V> is established
V(w1,P)=1 V(w2,P)=1 V(w3,P)=0
(1) Is the logical formula P→□P true or not in the possible world w1?
The only world reachable from W1 is w2
Since P=1 (true) in W2
□ P is true in the possible world w1
Therefore
¬□P is false in the possible world w1
Since P is true in the possible world w1, P→¬□P is false in the possible world w1.
(2) Is the same expression true in the possible world w2?
The only world reachable from w2 is w3
Since P is P=0 (false) in W3
P is false in the possible world w2
Therefore
¬□P is true at w2
Since P is true in the possible world w2, P→¬□P is true in the possible world w2
(3) What is the truth value that this expression takes in w3?
Since P is false in w3, P→¬□P is true no matter what ¬□P is.
What is the truth value of □P in W3?
There is no world reachable from W3.
What are the truth values of □A and ◇A in such a world?
From the definition statement
For any world w’, if wRw’, then ṼM(w’,B)=1
If there is no world w’ reachable from W, then the preceding case of “if” is false and therefore vacuously valid
When W is a dead end, any logical formula A is true for □A
What is the truth value of ◇P in W3?
In a clogged world, ◇A is false for any logical formula.
In a deadlocked world, ◇A is false, but □A is true.
Final result
Validity in modal logic
Next, we define the logical truth “valid expression.
In the semantics of modal logic
In the semantics of modal logic, there are two steps: a frame and a model on top of it.
The concept of “validity” also needs to be considered in two steps
Definition of “valid in a model
In the model above, ¬P→¬□P is true in all possible worlds.
A formula that is valid in this model
Definition
The logical formula A is valid in the model M=<W, R, V>.
For all worlds w belonging to W, VM(w,A)=1
Valid in the frame
If we leave the frame of the above model and soften it to the value function V, we get a different model.
In this model, ¬P→¬□P becomes false in W2.
¬P→¬□P is not valid in this model.
Some expressions can be true in any model as long as the frame remains the same
We need to find a formula that is valid in all models that share the same frame but have different additive functions.
A formula that is true depending on the structure of the entire possible world, regardless of what is happening in each possible world.
Definition
The logical formula A is valid in the frame F=<W,R>.
A is valid in all models M=<W.R.V> based on frame F=<W,R>.
11.4.4 Correspondence between logical formulas and reachability relations
The reachability relation satisfies the reflexivity ∀x(wRw)
Each possible world is reachable to itself
In any possible world, if □A is true, then
If □A is true in any possible world, then it contains a self-lion among the worlds reachable from that world, so
A becomes true in that world.
In a model where R satisfies reflexivity, □A→A is always valid.
Theorem 46.
□A→A is valid in frame F=<W,R>.
⇔
R is reflexive
There is a correspondence between the validity of a logical formula and the reachability relation
Areas where correspondence is studied in detail
Typical results of correspondence theory
Definition
(1) The reachability relation R is serial ⇔ ∀w∃w'(wRw’) (i.e., every reachable world has at least one world reachable from it, i.e., the frame has no clogged worlds) (2) R is reflexive ⇔ ∀w(wRw) (3) R is contrastive (3) R is symmetric ⇔ ∀w∀w'(wRw’ → w’Rw) (4) R is transitive ⇔ ∀w∀w”[(wRw’ Λ w’Rw) → Rw’] (5) R is Euclidean ⇔ ∀w∀w”[(wRw’ Λ wRew”) → w’Rw”]. That is, worlds that are reachable from one world are also reachable from each other.
There is a correspondence between the representative axioms and the reachability relations as follows
Theorem 47
(1) The tautology is valid in any frame (2) K: □(A→B)→(□A→□B) is valid in any frame (3) D: □A→◇A is valid in frame F=<W,R> ⇔ R is serial (4) T: □A→A is valid in frame F=<W,R> ⇔ R is reflexive (5) 4: □A→□□A is valid in frame F=<W,R> ⇔ R is transitive (6) B: A→□◇A is valid in frame F=<W,R> ⇔ R is contrastive (7) 5: ◇A→□◇A is valid in frame F=<W,R> ⇔ R is Euclidean
11.4.5 Completeness of Axiomatic System of Modal Logic
There is a nice correspondence between the validity of a logical formula and the conditions of the reachability relation of a frame
(A)
(B)
Theorem 48.
(1) ⊢KA ⇔ A is valid in any frame (2) ⊢TA ⇔ A is valid in any reflective frame (3) ⊢S4A ⇔ A is valid in any reflective and transitive frame (4) ⊢BA ⇔ A is valid in any (5) ⊢S5A ⇔ A is valid in any reflective, transitive, and contrastive frame
From the semantics point of view, we can see that the aspect of S5 is simple Translated with www.DeepL.com/Translator (free version)

Chapter 12: There’s Still a Lot Left to Learn in Classical Logic
12.1 Language FOL in Fully Armed Predicate Logic

12.1.1 Language FOL
Introduction of Function Symbols
Starting with a simple language L and moving closer to an everyday language
MPL with the introduction of quantifiers
PPL with the introduction of multi-weighting
IPL with the addition of identities
One last extension to the logical language
About definite description clauses
“The director of The Terminator”
“Director of “The Seven Samurai””
“The director of…”
An operator that converts a name (a movie name) to another name (a person’s name)
Using Name-maker as a function
The name-maker “director of
James Cameron for “The Terminator”, Akira Kurosawa for “The Seven Samurai”, and so on.
For example, “James Cameron” for “Terminator” and “Akira Kurosawa” for “Seven Samurai.
A name-maker with more than one empty space is also possible.
Example
~ and …. A child born to ~ and
Vocabulary of the language FOL
An extension of the logic language with added function symbols
Vocabulary of FOL
f11, f12, f13,… f21, f22, f23,… f31, f32, f33,,…
The upper subscript indicates that it is an n-variable function.
The lower subscript indicates the number in the group of n-variable functions.
Use 𝞿n as a graphical symbol for any n-variable function
Definition of a term
The definition of a term changes dramatically when a function symbol is introduced.
So far, we have used
There were only two types of terms: individual variable terms and individual definite terms.
In FOL
With the introduction of function symbols
With the introduction of function symbols, the terms that refer to individuals become compound expressions.
Example
F11a, f11f11a, f12ab, f12f11bf11a
The definition of a term also becomes inductive
Definition of a term
(1) Individual definite terms and individual variable terms are terms. (1) Individual definite terms and individual variable terms are terms, which are called “atomic terms”. (2) If τ1,…,τn are terms, then φnτ1,…,τn are terms. , τn is a term. In other words, an n-variable function symbol φn followed by n terms is a term. (3) Only those terms that are considered to be terms by (1) and (2) are terms.
Tablature can be used as is.
There is little change in the rules of tableau.
(The order in which the expansion rules are applied requires a special commitment.)
12.1.2 Semantics of FOL
The semantics of FOL is simply the addition of a function symbol and the part that assigns meaning to the terms it contains
V assigns to the function symbol φn an n-variable function on D
That is
V(φn) = a function f, such that
f:Dn→D
(Note that the function f is assumed to be defined for all elements of Dn.)
With this, the definition of the assignment also undergoes a small change
In FOL, there is also a compound term that contains a function symbol as a term
So
The assignment σ to individual variable terms is extended to define σ’, and
and assign it not only to individual variable terms but also to these composite terms.
Definition
For every individual variational term 𝛏 in FOL
Assume we are given an assignment σ that assigns an individual in the discussion domain D
In this case, we have
extension of σ: σ’:T→D (where T is every term that can be made in FOL).
inductively as follows
(!) For the individual variational term 𝛏, σ'(𝛏)=σ(𝛏)
i.e., it matches the original assignment.
(2) For the individual definite term α, σ'(α) = V(α)
(3) where τ1,τ2,… (3) Let τ1, τ2,…, τn be terms and φn be an n-variable function symbol
In this case
σ'(φnτ1τ2…τn)=V(φn)(σ'(τ1),σ'(τ2),…,σ'(τn)) ,σ'(τn))
The next task of the semantics is
For each logical formula A
For each logical formula A, the next task of the semantics is to define what it means to say that “a model M satisfies A by an assignment σ”.
Once this satisfiability relation is defined
Avoid defining “A is true under model M” for a closed logical formula A
A valid formula, a logical consequence, a logical equivalence, etc. are defined one after another.
Even if the language is changed to FOL, the above can be used without any change at all.
However
The only difference is that the “term τ” in the definition now includes compound terms.

12.2 Completeness of AFOL and Some Results from It

12.2.1 Completeness Proofs for Predicate Logic
The next thing to be done is to prove the completeness of AFOL
Theorem 49: Strong Completeness Theorem
Γ⊢AFOLA ⇔ Γ⊨A
How is the completeness theorem proved (policy)?
Goethe was the first to prove the completeness theorem in predicate logic
The proof outlined below is a version that was re-proven by Henkin in 1949.
The basic principle remains the same as in the completeness proof of propositional logic
(1) First, we divide the proof into the following two directions
[Theorem 49-1] Γ⊢A ⇒ Γ⊨A (soundness)
[Theorem 49-2] Γ⊢A ⇐ Γ⊨A (completeness)
(2) Of these, soundness is easy to prove.
That all AFOL axioms are valid expressions.
(3) The variational rules preserve the property of semantic consequence.
In other words
We can show that A, A → B ⊨ B and A → B ⊨ A → ∀𝛏B
(3) Proofs of completeness are more difficult.
Here, as in the case of propositional logic, we prove a result that is equivalent to Theorem 49-2
Theorem 50: Henkin’s Theorem
The set of logical formulas Γ is syntactically consistent ⇒ Γ is satisfiable
(4) So, how do we prove it?
The basic idea is the same as in the case of propositional logic
Since it is difficult to construct a model directly from Γ
It is difficult to create a model directly from Γ, so we need to expand Γ to a convenient set (maximal consistent set) Γ* that contains Γ, and then create a model that satisfies Γ*.
After expanding Γ to a convenient set (maximal consistent set) Γ* that contains Γ, we can create a model that satisfies that Γ*.
Specifically, we prove the following two auxiliary theorems
[Auxiliary Theorem 50-1: Lindenbaum’s Auxiliary Theorem] When Γ is a consistent set of FOL formulas
There exists at least one maximal inconsistent set Γ* that makes Γ a subset.
[Auxiliary Theorem 50-2].
Given an extremally inconsistent set Γ*
Given an extreme-consistent set Γ*, we can construct a model (and assignments) that satisfies all the logical formulas in it.
In other words, the maximally consistent set is satisfiable.
Where do we get the materials to make such a model?
Proof plan of auxiliary theorem 50-1 (expansion of Γ)
The expansion of Γ to Γ* is done in three steps as follows
(1) Let Γ be a consistent set of logical formulas in FOL.
(2) The number of words in the formulas in Γ is not necessarily large enough to create the required model.
Add “countable infinite” individual definite terms to the vocabulary of formulas in Γ.
Even if we expand the language in this way, Γ will still remain consistent
If we can’t derive both A and ¬A from Γ using only the individual definite terms in the original vocabulary
If we can’t derive both A and ¬A from Γ using only the individual definite terms in the original vocabulary, then we still can’t derive a contradiction by increasing the number of individual definite terms we can use in the deduction process in this way.
(2) Now that the language has been expanded, for each logical formula A and each individual definite term 𝛏 in the language, we add to Γ a logical formula of the following form
¬∀𝛏A→¬A[α/𝛏] (where α is one of the individual definite terms added to this expanded language)
The aim of adding such a logical formula is
If Γ contains a logical formula to the effect that “not all things are A,” then
If there is a logical formula in Γ that says “not everything is A”, then let’s make sure that the expanded set of Γ contains some precedent “α is not A”.
Let Δ be the set of new formulas we add at this stage.
We can prove that Γ ∪ Δ is also uncorrelated.
(3) Expand Γ∪Δ in the same way as when we proved the completeness of APL.
In other words, take logical formulas one by one from the list of logical formulas, and add them.
If there is no contradiction in adding it, then add it.
Then, for the expanded set (let’s call it Γ*), we prove that the following facts hold
(a) Γ⊆ Γ* (b) Γ* is consistent (c) Γ* is maximal. (c) Γ* is maximal, i.e., for any logical formula A, A ∈ Γ* or ¬A ∈ Γ* (d) Γ* always contains at least one of the form ¬∀𝛏A→ ¬A{α/𝛏] for any logical formula A and any individual definite term 𝛏 (e) For any For a logical formula A, Γ*⊢A ⇒ A ∈ Γ*.
Proof plan of the auxiliary theorem 50-2 (How to build the model)
From Γ*, we construct the model and assignments as follows
First, to determine the model, we need to determine the domain of argument
The first thing to do is to assign a symbol to the very symbol that is making the logical formula
(1) The domain of discussion in Model M is the set of all terms in the expanded language.
The reason for defining the domain in this way is that
(1) The discussion domain of Model M is the set of all terms in the expanded language. The reason for defining the discussion domain in this way is that it aims to define and use an assignment that assigns a term-signature to every term.
In other words
The assignment is such that σ'(τ) = τ for any term τ.

It is given as σ(𝛏)=𝛏.
Next, we extend this assignment σ to define σ’, and let it assign not only individual variable terms but also individual definite terms and composite terms.
Define it inductively.
To make sure that any term is assigned its term earthquake when it is expanded to σ and σ’ according to that definition
We have to devise the definition of V(α) and V(Φn)
(3) It should be as follows
(A) For the individual definite term, we can set V(α)=α
This will give us σ'(α)=V(α)=α.
(B) For function symbols, we can set σ'(Φn,τ1,…,τn)=V(α). ,τn)=V(Φn)(σ'(τ1),… ,σ'(τn))=V(Φn)(τ1,…,τn)=Φn ,τn)=Φnτ1…. .τn, so we want
We want V(Φn) to be V(Φn)(τ1,τ2,… . τn)=Φnτ1τ2…. .τn.
(4) Assigning meanings to predicate symbols is done as follows
Let V(Φ) be a set that satisfies the following conditions
<τ1,…. . τn>∈V(Φn) ⇔ Φnτ1…. .τn∈Γ n
The reason for defining it this way is that we want the model and the assignments we are making to satisfy all the expressions in Γn.
(5) Finally, there is still the semantics of the identity symbol.
(5) Finally, there remains the semantics of the identity symbol, which is only valid when the same high cliffs are lined up on both sides.
VM,σ(τ1=τ2)=1 ⇔ σ(τ1)=σ(τ2) ⇔ the term τ1 and τ2 are the same term
Example
A valid example
a=a
fx=fx
Not valid example
1+1=2
(1) Consider a model in which each term is assigned its own center (2) Interpret “=” as an identity relation. (2) The “=” is interpreted as an identity relation, i.e., a relation that is satisfied when the terms on both sides of the “=” represent the same thing. We want to make sure that such expressions are also satisfied.
The three requirements are incompatible.
Adopt the strategy of discarding (2) for now.
For convenience, “=” is not a genuine identity relation.
For convenience, “=” is not a genuine identity relation, but a binary predicate that expresses some looser kinship relation.
Let V(=) be a set satisfying the following conditions
<τ1,τ2>∈V(=) ⇔ τ1=τ2∈Γ*
when the expression τ1=τ2 is in Γ*.
Then and only then is the relation between τ1 and τ2 defined to be what is meant by “=”.
(3) is satisfied, but the relation V(=) is no longer the same relation.
Transitivity (if τ1=τ2, τ2=τ3, then τ1=τ3) holds.
Reflexivity and symmetry also hold
Models and assignments constructed from Γ*.
<model M> (!) Argument goodness D= the set of all terms in the expanded language (2) Implications for the predicate symbol Φn V(Φn) is <τ1,τ2,… ,τn>∈V(Φn) ⇔ Φnτ1τ2…. (3) Implication to the binary predicate symbol “=” V(=) is a relation that satisfies <τ1,τ2>∈V(=) ⇔ τ1=τ2∈Γ* (4) Implication to the individual definite term α V(α) is an α-identity (5) Implication to the function symbol Φn V(Φn) is a relation that satisfies V(Φn)(τ1,τ2 ,… .τn)=Φnτ1τ2…. . Suppose that the assignment σ based on this model is a function that assigns to each individual variant its individual variant confidence. That is, σ(𝛏)=𝛏
Proof Plan for Auxiliary Theorem 50-2, Part 2 (“=” back to the identity symbol)
(1) For a model M and an assignment σ made as above
(1) For the model M and the assignment σ made above, we have that M satisfies all the equations contained in Γ* only by σ.
It follows that
VM,σ(A)=1 ⇔ A∈Γ*
(2) However, the model created above is still one that does not interpret “=” as a genuine identity relation
We need a model in which “=” is properly defined as an identity relation (a normal model). Ideas for this
(A) In Model M, the relation V(=) has been established even between two different individuals.
This is why the “=” is not interpreted as a genuine identity symbol
However, this relation is an equivalence relation, as already mentioned
As a characteristic of equivalence relations, the relation V(=) classifies the domain of discussion of model M into several exclusive equivalences (2.5 in Appendix A)
(B) So, as a new model, it does not assign to each term its own identity, but
Consider a new model that assigns to each term the equivalence class to which it belongs, rather than assigning to each term its own belief.
In the old model M, the relation V(=) holds between the terms τ1 and τ2
That is, if <τ1,τ2>∈ V(=)), then the two terms belong to the same equivalence class.
Now, let us write [τ] for the equivalence class to which τ1 belongs.
In the new model based on this idea, the terms τ1 and τ2 will be assigned the same single object [τ1
(C) The domain of discussion of this new model is a collection of equivalences created by classifying the individuals of the domain|M| of the old model by the relation V(=), that is, the “quotient set” of V(=) of|M|.
(3) In this way, the above is still true even if we create a new model M and an assertion σ’ based on it by changing the predicate symbols and other assignments in a timely manner.
The Completeness Theorem is a “surprising” theorem.
The completeness theorem states
The completeness theorem implies that the following concepts overlap without excess or deficiency in their extension
the notion of logical truth from the trust surface called theorem, and
and the concept of logical truth from the semantics of validity formulas.
Concepts such as validity and satisfiability are
The notions of validity and satisfiability are defined using models.
A discussion domain can contain infinitely many individuals.
The model itself can also be infinitely many.
A model is defined from the perspective of being able to see an infinite number of things at once.
Theorem, proof, and other syntax-derived concepts
Starting from a finite number of equations and transforming them step by step
Concepts defined from a finite standpoint
It’s amazing that we see the same thing.
The concept of semantics, which allows us to see all at once from a high place, and
and the concept of neotaxia, which makes us crawl step by step on the ground like a bald eagle.
12.2.3 Compactness Theorem and Levenheim-Skolem’s Theorem
Introduction.
By the completeness theorem
It is easy to show that the same compactness theorem holds for predicate logic as for propositional logic.
Theorem 5: The Compactness Theorem
Every finite subset of the set Γ of formulas in FOL is satisfiable ⇒ Γ is satisfiable
From this compactness theorem, the following theorem follows easily
Theorem 52.
Suppose that the set of formulas ∆ is satisfiable by any model with any large set as its domain of argument.
In this case, Δ is satisfiable by a model with an infinite set as the domain of discussion (we call it an infinite model for the sake of convenience).
Levenheim-Skolem’s Theorem
Let us look back at the model M constructed in the proof of the completeness theorem.
The domain of discussion of M consists of the following terms
the terms contained in the original Γ, and
and as many terms as can be made from the additional infinite number of individual definite terms added to it.
Since the number of terms in FOL is additive infinite
The domain of discussion of M has an additive infinite concentration.
The concentration of the discussion domain of model M’, which is the final model created by shrinking M in some sense, is obviously the same as or smaller than the concentration of M.
This leads to the following theorem
Theorem 53: Levenheim-Skolem’s Theorem
Suppose that the set of logical formulas Δ is satisfiable.
In this case, there exists a model that satisfies Δ and has a debate region consisting of at most additive individuals.
This discussion domain is called a countable model.

12.3 First-Order Theory

Can we create axiomatic systems in predicate logic?
An example
Axiom system AFOL
[Axioms A1-A3 Same as APL (except that it is the FOL formulae that are breamed into the schematic letters “A” and “B”) A4 ∀𝛏A→A[τ/𝛏] (But there is a restriction on the terms that can be substituted into τ here. But it is omitted.) A5 ∀𝛏(𝛏=𝛏) A6 (𝛏=𝛇) → (φn(. . 𝛏…) =φn(… . 𝛇….)) (Note that φn is an arbitrary n-variable function symbol, and φn(. . 𝛏…) is the term φn(…. . 𝛇….) R1 Given MP A and A→B, derive B R2 Given GEN (Generalization) A→B, derive A→∀ Given A → B, we may derive A → ∀B (but A must not contain x as a free variable term)
We can define dediction from proofs, theorems, and assumptions in AFOL in the same way as in APL, and
The same deduction theorem holds as in APL. What is axiomatic theory?
First order theory (FOL)
Axiomatic theory is a theory of the first order that uses the vocabulary allowed in FOL and the logical formulas that can be defined in FOL.
Using the vocabulary allowed in FOL and the logical formulas that can be defined in FOL, it is possible to summarize the basic knowledge of a field in the form of an axiomatic system.
Note
Do not mix up theory and logic.
Examples of theory
Robinson arithmetic
Grammar of Q
(1) Vocabulary
(1) Atomic term Individual definite term () Individual variable term x, y, z, … (2) Predicate logic is not used (3) Function symbols One-variable function symbols S Two-variable function symbols +, * (4) Logical definite terms Combiners →, V, Λ, ¬ Quantifiers ∀, ∃ Identity symbols = (5) Auxiliary symbols (, )
(2) Definition of terms and logical expressions
From these vocabulary, the symbolic sequence created by following the definition of terms and logical expressions in FOL is the logical expression of Q.
Formula of Q
Not “provable in Q or axiomatic in Q”.
A formula that can be created in the vocabulary of Q
Axioms of Q
The axioms of Q consist of the following two groups
(1) Logical axiom
Axioms that all first-order theories have in common.
Specifically, the six axioms of AFOL can be taken as the logical axioms of Q.
However, the symbols that can be substituted for the AFOL diagram letters (A, 𝛏, τ) are
However, the symbols that can be substituted into the AFOL graphic characters (A, 𝛏, τ) are limited to the vocabulary of Q and the terms and formulas of Q that are created based on them.
(2) Proper axiom
Axioms that are unique to each theory.
This gives “meaning” to the symbols unique to the theory (individual definite terms other than function symbols, predicate symbols).
This part is different for each theory
In Robinson arithmetic Q, we have the following seven axioms
Q1 ∀𝛏∀𝛇(𝛏≠𝛇 → S𝛏≠S𝛇) Q2 ∀𝛏(0≠S𝛏) Q3 ∀ 𝛏(𝛏≠0 → ∃𝛇(𝛏=S𝛇) Q4 ∀𝛏(𝛏+0=𝛏) Q5 ∀ 𝛏∀𝛇(𝛏+S𝛇=S(𝛏+𝛇)) Q6 ∀𝛏(𝛏*0=0) Q7 ∀ 𝛏∀𝛇(𝛏・S𝛇=((𝛏・𝛇)+𝛏))
Model of Q
When we say “arithmetic” in mathematics
It does not mean “reading, writing, and arithmetic”.
It means the theory of natural numbers and the operations of addition and multiplication.
Q is an axiomatic theory of arithmetic in this sense.
The intrinsic axioms of Q become true in the following model
<Model M> Discussion domain = set of natural numbers V(S): a function that maps any natural number n to its next natural number n+1 (this is called the successor function) V(+): a function that maps the sum of natural numbers n and m to their pairs V(*): a function that maps the product of natural numbers n and m to their pairs V( 0):Natural number 0
When interpreted with this model M, we can say that it states the following
Q1: “The following vehicles of different natural numbers are also different from each other”
Q2: “0 is not a trailing car of any natural number”
Q3: “Each non-zero natural number has a preceding natural number”
Definition.
As in model M for theory Q.
A model that makes all the axioms of theory K true is simply called a “model of theory K”
Or a theory K is said to have a model M.
Definition in Theorem, Inconsistency, etc.
Some concepts that have been defined for AFL, AFOL, etc. can be defined for axiomatic theories in the same way.
Definition
The following conditions are satisfied
There is a finite sequence Bq,B2,…,Bn of logical formulas in Q. ,Bn (suppose that this last Bn is C)
The condition Bi (but 1≤i≤n) is one of the following
(1) It is an axiom of Q.
(2) It is an expression drawn from the preceding B1 and B2 by the transformation rule (MP).
When there is a proof of C
C is a theorem in Q
Or we say that C is provable in Q, and write ⊢QC
Example of theorem in Q
Can we derive “1+1=2” as a theorem from Q?
Q doesn’t have a symbol for 1 or 2.
1 is the latter of 0. S0
2 is SS0
The equation to derive is “S0+S0=SS0
Show that ⊢QS0+S0=SS0 (1) ∀x∀y)x+Sy=S(x+y)) Q5 (2) ∀y(S0+Sy=S(S0+y)) (1)A4 (3) S0+S0=S(S0+0) (2)A4 (4) ∀x(x+0=x) Q4 (5) S0+0=S0 (4)A4 (6 ) S0+S0=SS0

12.4 Isomorphism between Models

12.4.1 Models that are similar to each other and models that are not
<Model M1> D=N (set of all natural numbers, including 0) V(P)=(0,3,6,9,…) V(P)=(0,3,6,9,…), i.e., set of multiples of 3 V(f)=following car function V(g)=function that maps x and y to their sum x+y V(a)=0
<Model M2> D={1, 1/2, 1/4, 1/8,…} , i.e. {1/2n |n∈N} V(P)={1, 1/8, 1/64, 1/512,…} V(P)={1, 1/8, 1/64, 1/512,…}, i.e. {1/23n|n∈N} V(f)=function mapping x to x/2 V(g)=function mapping x and y to their product x×y V(a)=1
Compare the truth values taken by the following logical expressions in the above two models
(1) Pa
(2) Pfa
(3) gaffa=ffa
(4) a≠fffa
(5) ∃x∀y(fy≠x)
12.4.2 Isomorphic Models
The similarity is the structure
What is it about M1 and M2 that makes them similar?
The similarity is not in what the model is made of.
It is the structure of the model that is similar.
Both models have the following features
(1)
The domain of discussion starts from a single starting point (0 in M1, 1 in M2), which is named by the individual definite term a.
(1) The domain of discussion starts from one starting point (0 in M1, 1 in M2), which is named by the individual fixed point a, and the other elements appear in the form of an infinite sequence of the next, and the next, and so on.
In both cases, the function f is a function that gives the “next to”.
(2)
The predicate P applies to all and only the elements that appear every second including the starting point in the sequence Ω in both cases.
(3)
The function g is a function that assigns the n+m-1th element to the nth and mth elements in the ω sequence.
Definitions
(1)
Let M=<D,V> and M’=<D’,V’> be the given models for a set of logical formulas Γ in FOL, respectively.
Now, when there is a map h:D→D’ between the argument domains D and D’ of the two models, and the following condition is satisfied
This map h is called a homomorphism from model M into M’.
(A)
For each n-term predicate symbol Φn and n arbitrarily ordered pairs of elements of D <a1,… ,an> and
<a1,… ,an>∈V(Φn) ⇔ <h(a1),… ,h(an)>∈V'(Φ)
(B)
For each n-term predicate symbol Φn and any ordered n pairs of elements <a1,…,an> in D ,an> and
h(V(Φn)(a1,… ,an))=V(Φn)(h(a1),… ,h(an))
(C)
For each individual definite term α
h(V(α))=V(α)
(2)
In addition to the above conditions, if the map h is a one-to-one map
h is called an isomorphism.
(3)
Also, when there is an “upward isomorphism” from model M=<D,V> to model M'<D’,V’>, then
We say that the models M and M’ are isomorphic, and write M≡M’.
To say that two models are isomorphic is to say
To put it crudely
There is no structural difference between the two models.
Theorem 54: The isomorphism theorem
Assume that models M and M’ are isomorphic.
That is, there is an upward isomorphism map between them.
Let σ be the assignment of individuals in the argument domain D of model M to the individual fixed term 𝛏.
Then the following holds
For any logical formula A, M satisfies A by σ
⇔
M’ satisfies A by h=σ
Let h=σ denote the composite map of the assignment σ and the quasi-isomorphism h.
First map the individual variant 𝛏 to an individual in D that can be mapped by σ
which is then further mapped by h to an individual in D’.
12.4.3 Normality of theories and non-standard models
Defining the categorical nature of a theory
Isomorphic models satisfy the same set of logical formulas
Does the converse hold?
Are all models that satisfy a given set of formulas isomorphic to each other?
The answer is
Sometimes they are, and sometimes they are not.
Definition
A theory K is m-categorical (m is an arbitrary radix).
⇔
Any two canonical (i.e., where “=” is interpreted as the same surname) models of K such that the concentration of the domain of discussion is m are always isomorphic to each other.
Example
(1) Logical axioms AFOL axioms (2) Unique axioms K1 ∃𝛏∃𝛇(𝛏≠𝛇Λ∀𝜼( 𝛏=𝛈Ⅴ𝛇=𝜼))
This theory K is 2-categorical
Any canonical model of K has a domain of argumentation consisting of two individuals
Robinson arithmetic is not categorical
Looking back again at Robinson arithmetic Q
The aim of creating Q
Have a set of natural numbers as the argument domain
A model that assigns a posterior, an additive, a multiplicative function, and a zero to each of the symbols S, +, *, and 0 (let this be M)
All of its axioms will be true
Gains and Losses of Q
Can derive propositions about individual numbers such as “SS0+S0=SSS0”.
It is weak in general propositions.
Example
0+S0=S0+0″ and “0+SS0=SS0+0” are all provable
The generalization “∀x(x+y=y+x)”, i.e. the additive exchange rule, is not a theorem of Q
The main logical formulas that are not provable in Q
(A) ∀x(0+x=x)
(B) ∀x(x+y=y+x)
(C) ∀x(x≠Sx)
(D) ∀x∀y∀z(x+(y+z)=(x+y)+z)
(E) ∀x(0*x=0)
(F) ∀x∀y(x*y=y*x)
(1) (a)-(f) are true in model M
(2) But these are not theorems of Q
Example
⊬Q∀x(x+y=y+x)
It means that there are models in which all the axioms of Q are true, but ∀x(x+y=y+x) is false
Robinson arithmetic also has models that are not isomorphic to the entire set of natural numbers, but have a different structure.
Such models are called “non-standard models”.
Robinson arithmetic is not the only bad thing.
The existence of non-standard models is a consequence of the fact that Q is a first-order theory.
Theorem 55.
There can be no first-order theory of arithmetic that has only models that are isomorphic to the entire set of natural numbers.
In other words, every first-order theory of arithmetic has a non-standard model

12.5 Second-Order Logic

12.5.1 Are there propositions that cannot be expressed in FOL?
Closed Critics
We introduced FOL as a full-featured language, but
However, there are propositions that cannot be expressed in any way even with FOL.
Example
There are critics who only praise each other.
Cannot be written using only FOL vocabulary
∃xMxΛ∀x∀y((MxΛAxy)→(x≠yMy))
Mx:x belongs to the Maron school
Axy:x compliments y
Argument domain is the set of all critics
∃xMx:Some people belong to the Maron school
If we don’t say this, when there is no one belonging to the Maron school, the back of Λ becomes unconditionally Shin
∃X(∃xXxΛ∀x∀y((XxΛAxy)→(x≠yΛXy))))
Cannot be created with MPL, PPL, IPL, or FOL
Because in addition to the usual quantifiers, there are now symbols like ∃X that quantify the position of the predicate symbol.
Logical languages that allow for variants (X, Y, etc.) and quantifiers that quantify predicates
In contrast to this
A language that can only express quantification on individuals
There are infinitely many of them.
Second-order languages have richer expressive power than first-order languages
Representation of FOLs
There are at least n things
Second-order languages
There are infinitely many things
How do we express the fact that there are infinitely many things?
Think of it this way
God arranges the things in the world in a line and touches them in order.
The predicate “Rxy” means “God touches x and then touches y”.
If there is no end to this line, we can say that there are infinitely many things in this world.
As for R, the above must be true.
It is an indispensable condition for the fact that God touches them in order.
This is not enough to say that there are infinitely many things.
Even “touch three things and that’s it” would be true.
In order for there to be an infinite number of things
God must say, “How many things can I touch and there will be another?
In the (finite) case of the doughnut structure, the above condition is also true
After touching x, he comes back around and touches x again.
We can negate the above.
The conjunction of (1), (2), and (3) is true if there are infinitely many.
We are talking about a particular relation called R
There are infinitely many of them.
For example, there is some final unoriginal ordering, like R
(5) ∃X[∀x∀y∀z((XxyΛXyz→Xxz)Λ∀x∃yXxyΛ∀x¬Xxx].
12.5.2 Semantics of Second-Order Logic
The “second-order language” that results from extending the language of logic in a direction that allows quantification such as ∀X and ∃X to bind the space formerly occupied by predicate symbols is called “SOL.
What SOL adds is
Quantification like ∀X and ∃F.
How do I do that?
Take a cue from the semantics of traditional quantification (first-order quantification) such as ∀x or ∃y
(1) First, define the model.
Determine the discussion domain D, and assign meaning to predicate symbols and others.
(2) Next, define the assignments.
Assignment is a function that assigns some individual in the discussion domain D to every individual variable 𝛏.
(3) Next, for the atomic formula A, we define that the model M satisfies A by the assignment σ.
(4) Using the above definition as a basis, we can functionally define the satisfaction relation for complex logical formulas including connectives and quantifiers.
This is where the quantifiers are given meaning.
When defining satisfaction relations for formulas containing quantification, we use the “Assignment Variant”.
How do we extend this to languages with second-order quantification?
(1) as is
(2) is
Variant of the first term (x,y,z,…) Assign individuals to the first variable (x,y,z,…) and use the assignment σ as is
The first term refers to the elements of D, i.e., individuals, without specifying which ones.
To make sense of the quantification of the second term, we need an assignment that can be used for the variant (X,Y,…) of the second term. (X,Y,…) of the second term.
We write this assignment as σ2
What exactly should σ2 assign to each of the variables of the second term?
The second term can be thought of as referring to a property, a relation
In the model interpretation, all of these have to be created from D
Recall that we have been thinking of properties as subsets of D and n-term relations as subsets of Dn
The assignments we seek are
Definition
For any second term variant of SOL
If it is an nth term predicate variant, then
Consider a function σ2 that assigns some subset of Dn
Let this σ2 be the model-based second-order assignment.
Second-order logic is a logic that talks about the existence or non-existence of not only individuals, but also sets of individuals
Instead of referring to individuals as being or not being, we now refer to the set of individuals as being or not being.
What I don’t like about second-order logic
The first-order world
There are many things in this world.
Anyway, everything that exists is an individual.
So we can say that individual people exist.
Example
Let’s say there are three people in this world.
The Second Floor World
There is no such thing as a set consisting of three people.
A kind of abstract fiction
A person who believes that there are individuals, but no such thing as a collection of individuals.
12.5.3 The Second Beano Arithmetic
A theory put together in the form of an axiomatic system using the means of representation given by SOL.
Representative example
Second order Peano arithmetics (PA2)
Eigen axioms of PA2 are the eigen axioms of Robinson arithmetic Q plus the axioms above.
MI2: Because this axiom is called the principle of second-order mathematical induction
First-order Peano arithmetic (PA1)
MI1 For any logical formula Ax in PA1 with x as a free term (A0Λ∀x(Ax→ASx))→∀xAx)
Theorem 56.
Any two models of the second-order Peano arithmetic PA2 are isomorphic to each other
That is, PA2 is categorical.
12.5.4 Special features of second-order logic
What first-order logic can do and second-order logic cannot do
Theorem 57.
Compactness does not hold for second-order logic.
That is, any finite set of them is satisfiable, but
There exists an infinite set of logical formulas that are themselves unsatisfiable.
Theorem 58.
There are formulas in second-order languages that are true only in models with non-countable infinite concentration domains of argument.
Levenheim-Skolem’s theorem does not hold.
Theorem 59.
It is not possible to create an axiomatic system in which all of the logical formulas that are supposed to stand in the standard semantics for second-order logic appear as theorems.
The completeness theorem does not hold for second-order logic.

Summary of Part IV

Appendix
A. A little bit of mathematics

About different kinds of numbers
1.1 From natural numbers to rational numbers
1.2 Real numbers
2. basic knowledge of set theory
2.1 Sets and their notation
A set is a collection of “things”.
A “thing” can be anything
The only thing we need to be able to define is whether a thing belongs to a set or not.
There are two ways to represent a set
The way to list the elements
A={2,5,8,11,14,17,20,23,26,29}
If the elements have a common property, represent the set by that property
A={n|n is a natural number smaller than 30 and divisible by 3 to give an extra 2}
We write a ∈ A to indicate that “something” called a is an element of set A.
We write a∉A to mean that a ∈ A does not occur.
2.2 What is the identity of a set?
Empty set
A set that does not have any elements is called “empty set”.
The empty set is denoted by 𝛟
∀x(x∉𝛟)
Extendibility of sets
<definition> Given a set A and a set B, if all the elements in each are common, i.e., ∀x(x∈A⟷x∈B), then the sets A and B are said to be identical and written as A=B
Whether two sets are the same depends on whether they consist of only the same elements, not on how they have been defined.
A={x|x is a multiple of 6}, B={x|x is an even number divisible by 3}, and C={x|x is a common divisor of 3 and 2} are different sets by definition, but they have the same elements, so they are the same set
2.3 Operations on sets
Subsets
<definition> Given sets A and B, if every element of A is also an element of B, then A is said to be a “subset” of B, and is written A⊆B. That is, A⊆B ⇔ ∀x(x∈A→x∈B)
x∈B→x∈B is always true. Therefore, the set B itself is a subset of B.
The empty set 𝛟 is a subset of any set A
If a set A is a subset of a set B but A=B, then A is said to be a “true subset” of B, denoted by A⊂B
Common set
<definition> Given sets A and B, the set constructed by collecting only those elements that are contained in both of them is called the common set (inetrsection) of A and B, denoted by A⋂B. That is, A⋂B={x|x∈A∧x∈B}
Merged sets
<definition> Given a set A and a set B, the set created by collecting only the elements contained in at least one of them is called the merged set (union) of A and B, denoted by A⋃B. That is, A⋃B={x|x∈A∨x∈B}
Common sets and merged sets of infinitely many sets
Common sets and merged sets can be considered for more than three sets
2.4 Ordered pairs and Cartesian products
Ordered pairs
A pair considered without ignoring the order in which the elements are arranged is called an ordered pair.
Coordinate data, etc.
Ordinal n pairs
A pair of n elements considered in an ordered manner
Cartesian product
From two sets A={1, 2}, B={a, b, c}, create an ordered pair such that the elements of A are in the front and the elements of B are in the back
<1,a><1,b><1,c><2,a><2,b><2,c>.
Or call it Cartesian product and represent it by AXB
The set that should be
<definition> Suppose there is a set A. At this time, the set (or more precisely, the set of sets) created by collecting all the subsets of set A is called the powerset of A and denoted by P(A).
2.5 Equivalence relations and equivalence classes
Equivalence relations
A relation that satisfies reflexivity, symmetry, and transitivity.
All the elements in a subgroup are connected to each other by a relation R, and the elements in a subgroup that are connected to some other element in the subgroup by the relation R always belong to the same subgroup.
Equivalence
Subgroups P1,…,Pn…Pn…Pn…Pn…Pn…Pn…Pn. , Pn… are called equivalence class
quatinentb set
Equivalence class P1,…,Pn,… P1,…,Pn,… The set that collects all of
3 Functions
3.1 Definition of a function
An expression is just one representation of a function
<definition> Given a set A and B, and a mapping f that assigns an element of B to each element of A and satisfies the following conditions, f is called a function or mapping from the set A to B. (1) f assigns some element of B to every element in A. (2) f assigns only one element of B to every element of A. (2) f assigns only one element of B to every element of A.
<Definitions> (1) The element of B that the function f from A to B assigns to an element a of A is written f(a), and is called the mapping of a by the function f(a) (iamge) (2) The fact that f is a function from a set A to B is written f:A→B. The set A is called the domain of f, and B is called the range of f. (3) The following set is called the image of A by the function f from A to B, and is denoted by f(A). f(A)={b|f(a)=b for some a∈A}. In other words, the set of all elements of B that are images of some element of A by f is f(A). Of course, f(A) ⊆ B is valid.
3.2 Various Functions
Single projections and one-to-one mappings
<definition> When a function f:A→B has the following properties, we call f an injection from A to B or a one-to-one mapping. f assigns different elements of B to different elements of A, i.e., x≠y ⇒ f(x)≠f(y) We say that f is a projection from A to B. f:A(1-1)→B
All projections and upward mappings
<definition> A function f:A→B is called a surjection from A to B or an ont-mapping of B if it has the following properties: every element of B is mapped by some element f of A. f(A)=B
Mapping into
<definition> A function f:A→B is said to be an into-mapping onto B if f(A) ⊂ B, that is, there is at least one element of B that is not the image of any element f of A.
All simplexes and bijections
<definition> If f:A→B is both a monjection and an alljection, then f is called an alljection or bijection from A to B.
4 Measuring the size of a set
4.1 Density of a set
4.2 Countable and non-countable sets
4.3 Series of cardinalities
4.4 All logical expressions are enumerable

B. Answers to the exercises
C. Book Guide