Title: Theory / Unimportant / Math / Logic / Modal logic
Tags: fromMath mathToDef récupéré hasSeenConjDef mathToSee counterExample EquivalentButNoIntermediate addIntermediateCard examplesSwitchExample1 toBinaryRelation

Definition: well-formed formulae.
Page: 3
Chapter: 1
Notation: wff

Name: Propositional Calculus
Page: 3
Chapter: 1
Abbreviation: PC

Q: The symbols of PC are:
-[...],
-[...]
A: unlimited set of letters; \(\sim,\lor,(,)\)
Page: 3
Chapter: 1

Name: An expression
Definition: A sequence of symbols.
Page: 3
Chapter: 1

Name: The wff
Definition: Letters
Page: 3
Chapter: 1
Definition2: \(\sim{}\alpha\), for \(\alpha\) a wff
Conjdef: Either
Definition3: \((\alpha\lor\beta)\) for \(\alpha,\beta\) some wffs.

Definition: \(\sim(\sim \alpha\lor\sim\beta)\).
Page: 6
Chapter: 1
Variables: \(\alpha,\beta\) wff
Notation: \(\alpha\land\beta\)

Name: \(\alpha\) implies \(\beta\)
Definition: \(\sim\alpha\lor\beta\).
Page: 6
Chapter: 1
Variables: \(\alpha,\beta\) wff
Notation: \(\alpha\implies\beta\)

Page: 6
Definition: \((\alpha\subseteq\beta)\land (\beta\subseteq \alpha)\).
Chapter: 1
Variables: \(\alpha,\beta\) wff
Notation: \(\alpha\equiv\beta\)

Name: Valid wff
Definition: A wff which is true for any interpretation of its variables.
Page: 8
Chapter: 1

Name: Law of composition
Definition: \((p\implies q)\implies((p\implies r)\implies (p\implies (q\land r)))\).
Page: 13
Chapter: 1

Name: Law of Adjunction
Definition: \(p\implies (q\implies(p\land q))\).
Page: 13
Chapter: 1

Name: Law of Syllogism
Definition: \((p\implies q)\implies((q\implies r)\implies(p\implies r))\).
Page: 13
Chapter: 1
Extra: modus ponens

Name: Law of importation
Definition: \((p \implies (q\implies r))\implies((p\land q)\implies r)\).
Page: 13
Chapter: 1

Name: Law of double negation
Definition: \(p\equiv\sim\sim p\).
Page: 13
Chapter: 1

Name: De Morgan Laws
Definition: \((p\land q)\equiv \sim(\sim p\lor \sim q)\) and \((p\lor q)\equiv \sim(\sim p\land \sim q)\).
Page: 13
Chapter: 1

Name: Law of transposition
Definition: \((p\implies q)\equiv(\sim q\implies \sim p)\).
Page: 13
Chapter: 1

Name: Commutative laws
Definition: \((p\land q)\equiv (q\land p)\) and \((p\lor q)\equiv (q\lor p)\).
Page: 13
Chapter: 1

Name: Associative laws
Definition: \((p\land q)\land r\equiv p\land (q\land r)\) and \((p\lor q)\lor r\equiv p\lor (q\lor r)\).
Page: 13
Chapter: 1

Name: Monadic operator
Definition: An operator which takes one argument.
Page: 5
Chapter: 1
Extra: unary

Name: A dyadic operator
Definition: An operator which takes two arguments.
Page: 5
Chapter: 1
Extra: Binary

Name: Truth-functional operator
Definition: given truth value, it returns a truth value.
Page: 5
Chapter: 1
Context: Modal logic

Name: Truth table of \(\alpha\)
Definition: A table with one line by assignation to each variable, and a column by subformulae of \(\alpha\). In each case is the truth value of the subformulae, given this assignation.
Page: 5
Chapter: 1
Variables: \(\alpha\) a wff

Definition: The necessity operator.
Page: 14
Chapter: 1
Notation: L operator

Name: The operator M
Definition: The possibly operator.
Page: 15
Chapter: 1
Variables: \(\alpha\) a wff

Smaller0: \(Mp\)
Greater0: \(\sim L\sim p\)
Page: 15
Chapter: 1
Variables: \(p\) a wff
Smaller to greater: is equivalent to

Q: [...] is represented as [...].
A: \(p\) is impossible; \(\neg M p\) or \(L\neg p\)
Page: 15
Chapter: 1
Variables: \(p\) a wff

Name: A seating
Definition: A pair \(\langle W,R\rangle\) with \(R\) a dyadic relation on \(W\).
Page: 18, 37
Chapter: 1
Name2: A frame

Name: A setting based on \(\langle W,R\rangle\)
Definition: A function \(V:W\times X\to\{0,1\}\).
Page: 18, 38
Chapter: 1
Variables: \(X\) a set of predicate and
\(\langle W,R\rangle\) a seating/frame
Name2: A model based on \(\langle W,R\rangle\)

Name: \(L\alpha\) is true for \(w\)
Definition: \(\alpha\) is true for each player viewed by \(w\).
Page: 18, 38
Chapter: 1
Variables: \(\alpha\) a wff with set of predicates \(X\),
\(\langle W,R,V\rangle\) a setting/model
\(w\in W\).

Name: \(M\alpha\) is true for \(w\)
Definition: \(\alpha\) is true for at least one player viewed by \(w\).
Page: 18, 39
Chapter: 1
Variables: \(\alpha\) a wff with set of predicates \(X\),
\(\langle W,R,V\rangle\) a setting/model
\(w\in W\).

Name: A wff successfull in this setting
Definition: A wff which holds for each \(w\in W\).
Page: 19
Chapter: 1
Variables: \(X\) a set of predicates,
\(\langle W,R,V\rangle\) a setting/model.

Name: A wff valid in this seating/frame
Definition: A wff which is successful for each setting/model based on this seating/frame.
Page: 19
Chapter: 1
Variables: \(X\) a set of predicates
\(\langle W,R\rangle\) a setting/frame

Name: Axomatic basis
Definition: a specification of the language
Page: 23
Chapter: 2
Definition2: a selected set of wff: the axioms
Definition3: a set of transformation rules from wff to wff

Name: A validity preserving transformation rule from wffs to wff
Definition: A rule which transforms formula which are valid (for some interpretation of this word) to valid formulae.
Page: 24
Chapter: 2

Name: A theorem of \(S\)
Definition: an axiom
Page: 23
Chapter: 2
Variables: \(S\) an axiomatic system
\(p\) a wff
Definition2: the result of a transformation rules applied to theorems.
Conjdef: Either
Name2: A wff which belongs to \(S\)

Name: (Deductively) equivalent axiomatic systems
Definition: Axiomatic systems having the same theorems.
Page: 24
Chapter: 2
Variables: \(S,S'\) two axiomatic systems

Name: \(S'\) contains \(S\)
Definition: Each theorem of \(S\) belongs to \(S'\).
Page: 24
Chapter: 2
Variables: \(S,S'\) two axiomatic systems

Name: Axiom \(\mathbf K\)
Definition: \(L(p\implies q)\implies (Lp\implies Lq)\).
Page: 25
Chapter: 2

Name: Uniform substitation transformation rule
Definition: The result of uniformly replacing any variable(s) in a theorem by any wff is itself a theorem.
Page: 25
Chapter: 2
Abbreviation: US transformation rule

Name: Necessity
Definition: If \(\alpha\) is a theorem, so is \(L\alpha\).
Page: 25
Chapter: 2
Abbreviation: N
Typ: transformation rule

Name: Modus Ponens
Definition: If (\(\alpha\) implies \(\beta\)) and \(\alpha\) are theorems, so is \(\beta\).
Page: 25
Chapter: 2
Context: Modal logic
Abbreviation: MP transformation rule

Name: \(\mathbf K\) axiom system
Definition: Language:PC and L
Page: 25
Chapter: 2
Definition2: Axioms: every valid PC wff and the \(\mathbf K\) axiom
Conjdef: axiom system with
Definition3: transformation rules: US, MP, N.

Definition: \(\alpha\) where \(p_i\) is replaced by \(\beta_i\).
Page: 25
Chapter: 2
Variables: \(\alpha\) a wff with variables \(p_1,\dots,p_n\)
\(\beta_1,\dots,\beta_n\) be wff.
Notation: \(\alpha[\beta_1/p_1,\dots,\beta_n/p_n]\)

Definition: \(\alpha\) is a theorem of \(S\).
Page: 25
Chapter: 2
Variables: \(\alpha\) a wff and \(S\) an axiomatic system
Notation: \(\vdash_S\alpha\)

Definition: \(\alpha\) is derivable from the \(\beta_i\).
Page: 25
Chapter: 2
Variables: \(\alpha,\beta_1,\dots,\beta_n \) wffs
Notation: \(\vdash\beta_1,\dots,\beta_n\to \vdash_s\alpha\)

Name: \(\mathbf{K}\)-valid wff
Definition: A wff valid in every frame.
Page: 20
Chapter: 1

Name: A proof of \(\alpha\)
Definition: A list of lines, each line containing:
-a wff
-an identifier
-either:
--its identifier as axiom or as already proven theorem
--the identifier of the (derived) transformation rule and the identifiers of the theorems on which it is applied.
The last line's wff is \(\alpha\)
Page: 26
Chapter: 1
Variables: \(S\) an axiomatic system
\(\alpha\) a wff in the language of \(S\)

Smaller0: \(\alpha\) can be derived, adding the \(\beta_i\)'s as axiom
Greater0: a derived transformation rule of \(S\)
Page: 29
Chapter: 1
Variables: \(S\) an axiomatic system, \(\alpha,\beta_1,\dots,\beta_n\) wffs in the language of \(S\)
Hide middle: yes
Prefix Greater: \(\vdash \beta_1,\dots,\vdash\beta_n\to \vdash\alpha\) is

Name: The pair is complete
Definition: Every wff valid in \(V\) is a theorem in \(S\).
Page: 36
Chapter: 1
Variables: \(S\) an axiomatic system
\(V\) a notion of validity

Name: This pair \(S, V\) is sound
Definition: Every theorem in \(S\) is valid in \(V\).
Page: 36
Chapter: 1
Variables: \(S\) an axiomatic system
\(V\) a notion of validity
Context: Modal logic

Name: Normal modal system
Definition: A modal system which extends \(\mathbf K\).
Page: 40
Chapter: 2

Name: A wff which is \(\mathcal C\)-valid
Definition: A wff which is valid in all frames of \(\mathcal C\).
Page: 40
Chapter: 2
Variables: \(\mathcal C\) a set of frame

Name: A system which is characterized by \(\mathcal C\)
Definition: A system whose wff are exactly the one which are \(\mathcal C\)-valid.
Page: 40
Chapter: 2
Variables: \(\mathcal C\) a set of frame

Name: Axiom of necessity
Definition: \(Lp\implies p\).
Page: 42
Chapter: 2
Context: Modal logic axiom
Notation: T

Name: A reflexive frame
Definition: A frame \(\langle W,R\rangle\) such that \(R\) is reflexive.
Page: 43
Chapter: 2

Smaller0: \(\phi\) is \(T\)-valid
Greater0: \(\phi\) is valid on every reflexive frame
Page: 43
Chapter: 2
Variables: \(\phi\) a wff
Smaller to greater: iff
Hide middle: yes

Name: Deontic
Definition: \(Lp\implies Mp\).
Page: 43
Chapter: 2
Context: Axiom
Abbreviation: D

Name: A dead end
Definition: A world which can not see any world.
Page: 43
Chapter: 2
Variables: \(\langle W,R\rangle\) a frame

Name: A serial relation
Definition: A binary relation \(R\subseteq S\times S\) for some set \(S\) such that, for each \(x\), there exists \(y\) such that \(xRy\).
Page: 45
Chapter: 2

Smaller0: \(p\) is \(D\)-valid
Greater0: \(p\) is valid on every serial frame
Page: 45
Chapter: 2
Variables: \(p\) a wff
Smaller to greater: iff
Hide middle: yes

Extending a system:
-preserve theorems
-do no preserve transformation rules.
Page: 46
Chapter: 2

Smaller0: an axiomatic system in which there exists wff which are not theorems
Greater0: no negation of theorem is a theorem (assuming PC)
Page: 46
Chapter: 2
Smaller to greater: iff
Hide middle: yes
Name: Consistent axiomatic system
Suffix Smaller: ,
Smallest: No variable is a theorem (assuming PC)

Name: A constant wff
Definition: A formula whose value does not depend on the assignment of its predicate.
Page: 47
Chapter: 2

Definition: A false constant formula.
Page: 47
Chapter: 2
Context: Modal logic
Notation: \(\bot\)

Definition: A true constant formula.
Page: 47
Chapter: 2
Notation: \(\top\)

Name: \(S'\) properly contains \(S\)
Definition: \(S'\) contains \(S\) and \(S\) does not contain \(S'\)
Page: 24
Chapter: 2
Variables: \(S,S'\) two axiomatic systems
Name2: \(S'\) is stronger than \(S\)

Name: Iterated modalities
Definition: A sequence of successive operators.
Page: 51
Chapter: 3

Name: A reduction law
Definition: A law allowing to replace an iterated modalities by a smaller iterated modalities.
Page: 52
Chapter: 3

Question: The number of reduction law of \(T\) is
Answer: 0.
Page: 52
Chapter: 3

Name: The axiom 4
Definition: \(Lp\implies LLp\).
Page: 53
Chapter: 3

Definition: \(Lp\equiv LLp\)
Page: 53
Chapter: 3
Notation: S4(2)

Name: A modality
Definition: A sequence of operators M, L, \(\sim\).
Page: 54
Chapter: 3

Name: A modality in standard form
Definition: A modality with at most one negation, starting the sequence.
Page: 54
Chapter: 3

Definition: The empty modality.
Page: 54
Chapter: 3
Context: Modal logic
Notation: [latex]--[/latex]

Name: An iterated modality
Definition: A modality with at least two modal operators.
Page: 54
Chapter: 3

Name: Equivalent modalities in \(S\)
Definition: Two modalities, such that replacing one by the other in any formula leads to an equivalent formula in this system.
Page: 54
Chapter: 3
Variables: \(S\) a system

Name: Non-equivalent modalities
Definition: Two modalities which are not equivalent.
Page: 54
Chapter: 3
Variables: \(S\) a system
Name2: Distinct modalities

Name: S4
Definition: \(T+4\)
Page: 53
Chapter: 3

Question: In S4, the non-equivalent modalities are:
Answer: -, L, M, LM, ML, LML, MLM and their negations.
Page: 55
Chapter: 3

Name: An S4-frame
Definition: A reflexive transitive frame.
Page: 57
Chapter: 3
Extra: 4 cap T frame ?

Smaller0: \(LML\alpha\)
Greater0: \(MLM\alpha\)
Page: 56, 57
Chapter: 3
Variables: \(\alpha\) a wff
Assuming: S4
Smallest: \(L\alpha\)
Greatest: \(M\alpha\)
Intermediate: \(ML\alpha\) and/or \(LM\alpha\)

Name: The axiom \(E\)
Definition: \(Mp\implies LMp\)
Page: 58
Chapter: 3

Name: The S5 axiom system
Definition: T+E
Page: 58, 62
Chapter: 3
Definition2: S4+B
Definition3: S4+DR4

Definition: \(MLp\equiv Mp\)
Page: 58
Chapter: 3
Notation: S5(3)

Definition: \(LMp\equiv Lp\)
Page: 58
Chapter: 3
Notation: S5(2)

Question: The distinct modalities in S5 are
Answer: -, L, M and their negations.
Page: 59
Chapter: 3

Smaller0: \(R\) is transitive
Greater0: 4
Page: 57
Chapter: 3
Variables: \(\langle W,R\rangle\) a frame
Counterexample: model \((\{a,b,c\},\{(a,b),(b,c)\}\),
0 propositional variables
4 but not transitive
Suffix Greater: is valid in this frame

Smaller0: \(R\) is transitive and reflexive/symmetrical
Greater0: \(E\) is valid in this frame
Page: 60
Chapter: 3
Variables: \(\langle W,R\rangle\) a frame

Name: A \(S5\)-frame
Definition: whose relation is an equivalence relation
Page: 61, 65
Chapter: 3
Conjdef: A frame,

Name: Brouwerian axiom
Definition: \(p\implies LMp\)
Page: 62
Chapter: 3
Abbreviation: The axiom \(\mathbf B\)

Name: The axiom system B
Definition: T+B
Page: 62
Chapter: 3

Name: A serial frame
Definition: A frame \(\langle W,R\rangle\) such that \(R\) is serial.
Page: 43
Chapter: 2

Name: Contingent wff
Definition: Neither necessary nor impossible wff
Page: 15
Chapter: 1
Variables: \(p\) a wff
Example: \(Lp\implies p\),
Valid iff everyone see itself. Not valid in a game with one player not seeing himself
Counterexample: p ? not valid in any frame, even if valid in some model

Name: \(x\) view \(y\)
Definition: \((x,y)\in V\).
Page: 18, 37
Chapter: 1
Variables: \(\langle W,R\rangle\) a seating/frame, \(x,y\in W\)
Name2: \(y\) is accessible from \(x\)
Name3: \(y\) is possible relative to \(x\)

Smaller0: \(E\)
Greater0: \(\mathbf B\)
Page: 62
Chapter: 3
Assuming: \(T\)
Counterexample: \((\{a,b\},\{(a,b),(b,a)\})\) \(p\) holds on \(a\),
E:\(Mp\) holds at \(p\), not \(LMp\)

Smaller0: \(B\)
Greater0: \(S4\)
Page: 63
Chapter: 3
Smaller to greater: is independant from
Assuming: \(T\)
Counterexample: \(p\) on \(w_1,w_2\), \(\mathbf B\) holds, not \(4\)
Counterexample2: \((\{a,b\}, \{(a,b)\}\) with \(p\) valid on \(a\)
\(4\) holds,
not \(\mathbf B\)

Definition: \(Lp\equiv MLp\)
Page: 58
Chapter: 3
Notation: R2
Assuming: S5

Smaller0: \(E\)
Greater0: \(4\)
Page: 58
Chapter: 3
Assuming: T

Smaller0: \(K+\Lambda\) is sound with respect to \(\mathcal C\)
Greater0: all sentences of \(\Lambda\) are valid on every frame in \(\mathcal C\)
Page: 40
Chapter: 2
Variables: \(\mathcal C\) a set of frame
\(\Lambda\) a system
Smaller to greater: iff

Definition: Transformation rule \(\vdash M\alpha\implies \beta\implies \vdash \alpha\subseteq L\beta\)
Page: 62
Chapter: 3
Notation: \(DR4\)

Name: A \(B\)-frame
Definition: A frame which, equivalently is reflexive symmetric
Page: 63
Chapter: 3
Variables: \(X\) a set of predicates,
Intuition: every formula \(B\)-valid are valid on this frame

Definition: The system \(K+B\)
Page: 64
Chapter: 3
Notation: \(KB\)

Definition: The system \(K+4\)
Page: 64
Chapter: 3
Notation: \(K4\)

Definition: The system \(D+B\)
Page: 64
Chapter: 3
Notation: \(KDB\)

Definition: The system \(K+D+4\)
Page: 64
Chapter: 3
Notation: \(KD4\)

Name: A \(KDB\)-frame
Definition: symmetrical and serial
Page: 64
Chapter: 3
Definition2: such that each \(KDB\)-valid formula holds
Conjdef: A frame

Name: A \(K4\)-frame
Definition: reflexive
Page: 64
Chapter: 3
Definition2: such that each \(K4\)-valid formula holds
Conjdef: A frame

Name: A \(KB\)-frame
Definition: symmetrical
Page: 64
Chapter: 3
Definition2: such that each \(KB\)-valid formula holds
Conjdef: A frame

Name: A \(KD4\)-frame
Definition: which is serial transitive
Page: 64
Chapter: 3
Definition2: such that each \(KD4\)-valid formula holds
Conjdef: A frame

Name: The PC-transform of \(\alpha\)
Definition: \(\alpha\) without its \(L\)'s and \(M\)'s
Page: 65
Chapter: 3
Variables: \(\alpha\) a wff
Notation: \(\tau(\alpha)\)

Name: A system which collapse into PC
Definition: An axiomatic system in which each modalities is equivalent to \(\_\)
Page: 65
Chapter: 3
Definition2: A system equivalent to \(Triv\)

Name: Trivial axiom
Definition: \(p\equiv Lp\)
Page: 65
Chapter: 3
Context: Model theory
Abbreviation: \(\mathrm{Triv}\)

Name: Trivial system
Definition: \(D+(p\implies Lp)\)
Page: 65
Chapter: 3
Context: Modal logic
Definition2: \(K+Triv\)
Conjdef: Equivalently
Abbreviation: \(Triv\)

Name: Verum system
Definition: \(K+\mathbf{Ver}\)
Page: 67
Chapter: 3
Abbreviation: \(\text{Ver}\)

Definition: \(L\alpha\)
Page: 67
Chapter: 3
Notation: \(\mathbf{Ver}\)

Question: \(\alpha\) is equivalent to
Answer: the same formula with \(Lp\) replaced by \(\top\) and \(Mp\) replaced by \(\bot\)
Page: 67
Chapter: 3
Variables: \(\alpha \) a wff
Assuming: \(Ver\)

Name: A maximal system
Definition: A system in which adding a formula leads to an inconsistent system.
Page: 67
Chapter: 3
Kind: Le
Example: Triv
Name2: Ver