Logic

1Suggested learning sequence(483w~3m)
2If we don't need function symbols, why do we have them?(57w~1m)
3Example(158w~1m)
4Semantics(29w~1m)
5Classification of logics(27w~1m)
6Model theory(152w~1m)
7Zeroth-order logic(1090w~6m)
8Mess 2(533w~3m)
9Probability logic(73w~1m)
10TODO Sameness is meaning-preserving universal substitutability?(58w~1m)
11What is a truth value?(120w~1m)

1Suggested learning sequence

1.1Preliminary metalearning(93w~1m)
1.2Naïve set theory: set, relation, and function(101w~1m)
1.3Formal languages, variables, binding(32w~1m)
1.4Formal systems, especially first-order logic(19w~1m)
1.5Meaning(26w~1m)
1.6Domain of discourse, interpretation, substitution(107w~1m)
1.7Signature, structure(38w~1m)
1.8Model, truth(59w~1m)
1.9Computational complexity theory(14w~1m)

1.1Preliminary metalearning

How do we learn formal logic? In the same way we learn a second language. We learn mostly by repeating examples, forming good habits, hoping that someday we become fluent. Unfortunately this method is somewhat frustrating because it involves forgetting and re-remembering. But the forgetting curve¹ offers some consolation: with spaced repetition², we will eventually remember something after a few days.

What makes formal logic hard is that there are many jargons. Fortunately these jargons form layers that we can begin to understand from the bottom upwards. This learning sequence follows those layers.

1.2Naïve set theory: set, relation, and function

name	meaning
set	a collection (see note below)
relation	domain + codomain + pairings
function	a relation whose each domain element is paired exactly once

Note: For practical purposes, we can pretend that a "set" is a collection. Although naïvely defining a "set" as a collection raises Russell's paradox³, mathematics works surprisingly well despite being built on such unsound foundation: we have flown people onto the moon and built nuclear power plants. There were some tragedies, but none of them seems to be due to Russell's paradox.

We assume familiarity with naïve set theory. We will not discuss set theory further in this document.

1.3Formal languages, variables, binding

name	meaning
alphabet	finite set
grammar	rules for making strings from alphabet
formal language	alphabet + grammar
formula	string in a formal language
sentence	formula with no free variables

A formula may contain free variables.

A variable is either free or bound.

1.4Formal systems, especially first-order logic

name	meaning
formal system⁴	formal language + axioms + inference rules
logical system	formal system
logic	logical system
logical symbol
non-logical symbol
term
function symbol
relation symbol

1.5Meaning

A formula such as \(p(x)\) only captures the form of an argument. The meaning of the formula depends on what we mean by \(p\) and \(x\).

1.6Domain of discourse, interpretation, substitution

name	meaning
domain of discourse	non-empty set
universe of discourse	domain of discourse
interpretation⁵	pairing between symbols and meanings

A domain of discourse is a non-empty set. Such domain does not have to be homogenous. For example, it may contain some personal names, some animal species, and some street addresses.

A variable can be substituted with an element of the domain of discourse.

Do not confuse "interpretation" and "interpretation function".

An interpretation is a mapping from syntax to semantics. The details of what an interpretation is depends on the logic.

An interpretation is a function that takes a term.

Example interpretation:

\[\begin{align*} I(a) &= 1 \\ I(b) &= 1 \\ I(c) &= 0 \\ I((A \alpha \beta)) &= I(\alpha) \wedge I(\beta) = \min(I(\alpha),I(\beta)) \\ I((N \alpha)) &= \neg I(\alpha) = 1 - I(\alpha) \end{align*} \]

where \(0\) means "false" and \(1\) means "true".

Applying the rules recursively to the example term gives

\[\begin{align*} I((A(Aab)(Nc))) &= I((Aab)) \wedge I((Nc)) \\ &= (I(a) \wedge I(b)) \wedge I((Nc)) \\ &= (1 \wedge I(b)) \wedge I((Nc)) \\ &= (1 \wedge 1) \wedge I((Nc)) \\ &= 1 \wedge I((Nc)) \\ &= 1 \wedge \neg I(c) \\ &= 1 \wedge \neg 0 \\ &= 1 \wedge 1 \\ &= 1. \end{align*} \]

1.7Signature, structure

name	meaning
signature⁶	function symbols + relation symbols + arity function
structure⁷	domain + signature + interpretation function
vocabulary[2]	signature

We often shorten "logical system" to "logic". It is an alias for "formal system".

"A theory consists of an axiomatic system and all its derived theorems."⁸

1.8Model, truth

The symbol \( A \models \phi \) reads "formula \(\phi\) is true in structure \(A\)". The proper syntax is \( (A,i) \models \phi \) where \(A\) is a structure, \(i\) is an interpretation, and \(\phi\) is a formula. If \(i = \emptyset\), then it can be omitted, and we write \( A \models \phi \) as an abbreviation of \( (A,\emptyset) \models \phi \). [2]

1.9Computational complexity theory

Computation-theory concepts?
name	meaning
problem	formula
machine	physical concretion (model) of problem
computation	concretion (model) of problem
machine model	abstraction of machine

2If we don't need function symbols, why do we have them?

Every function of arity \(n\) can be replaced with a functional relation of arity \(n+1\). For example, we can replace \(y = f(x)\) with \(F(x,y)\). For a more concrete example, we can replace \(x = 1 + 2\) with \(plus(1,2,x)\).

Why do we use function symbols at all?

3Example

Consider the first-order formula \( L(x,y) \). We may choose to read \( L(x,y) \) as "\(x\) likes \(y\)". We may define the domain of discourse as a set of two elements: Alice, Bob. We have four choices for the interpretation of \(L\).

A complete graph is a model of the sentence \( \forall x \forall y : E(x,y) \). To mean the same thing in symbols, we write \( G \models \forall x \forall y : E(x,y) \), if \(G\) is a complete graph. The symbol for "A models B" is \( A \models B \). The symbol \( \models \) is called a "double turnstile".⁹ ¹⁰

Here we exemplify model theory with logic of graphs¹¹.

The sentence \( \forall x \forall y : E(x,y) \) has many models: a complete graph with one vertex, a complete graph with two vertices, a complete graph with three vertices, and so on. The domain of discourse is the set of vertices of the graph. The only relation symbol is \(E\) with arity 2.

4Semantics

If \(f\) is a function symbol with arity \(n\) then \( I(f) : D^n \to D \).

If \(r\) is a relation symbol with arity \(n\) then \( I(r) \subseteq D^n \).

5Classification of logics

Logics can be classified by order, value, and sort, for example: first-order two-valued one-sorted logic, zeroth-order three-valued one-sorted logic.

What is the order of a formula?

6Model theory

6.1The confusing word "model"(43w~1m)
6.2Logic(109w~1m)

6.1The confusing word "model"

One source of confusion is that the word "model" itself has two opposite meanings. Model means concretion (exemplification) in "model theory" and "clay model"¹². Model means abstraction in "mathematical modeling". More about modeling is in file:philo.html.

An interpretation models a sentence[1].

6.2Logic

A logic has syntax (form) and perhaps also semantics (meaning). Grammar determines the well-formed formulas. Semantics maps a well-formed formulas to an interpretation. (What are the terms? Mathematical logic lecture notes or book?)

The extension of a predicate \(p\) is the set \(\{x~|~p(x)\}\).

A formula in first-order logic is Skolemized or is in Skolem normal form iff it has the form \(\forall x_1 \ldots \forall x_n ~ M\) where \(M\) is a quantifier-free formula in conjunctive normal form. A formula is in conjunctive normal form iff … http://mathworld.wolfram.com/SkolemizedForm.html

A Herbrand universe is …

Curry-Howard correspondence relates logic and type. A value \(x : T\) is a proof the logic formula isomorphic to \(T\).

7Zeroth-order logic

Let's study a propositional calculus, a formal language. It is important because we're going to build other formal languages on it.

A "calculus" is a set of rules.¹³ ¹⁴

A language has syntax (form) and semantics (meaning).

A formal language describes a set of strings by using an alphabet and some formation rules. The alphabet is the set of symbols that can be in the strings. The formation rules decide which strings are in the language.

A formula is a string in the language.

7.1Syntax of propositional calculus(192w~1m)
7.2Note to self)(32w~1m)
7.3Syntax of predicate calculus(352w~2m)
7.4Many-valued logics(438w~3m)

7.1Syntax of propositional calculus

For a propositional calculus:

The alphabet is the set of these five blackboard-bold logical symbols:
- \(\bbN\) (negation, "not"),
- \(\bbC\) (conjunction, "and"),
- \(\bbD\) (disjunction, "or"),
- the left parenthesis,
- and the right parenthesis;
- plus a set of non-logical symbols:
  - Anything can be non-logical symbols as long as it isn't already a logical symbol.
  - Usually a non-logical symbol is a Latin capital letter,
    - but we don't have to restrict ourselves to one letter per symbol.
      - We can freely decide that a symbol can be one word, or even a phrase.
        
        It may even be outside the Latin alphabet.
        
        It might be a Chinese character, or an emoticon, or a drawing.
The formation rules are:
1. Every non-logical symbol alone is a formula.
2. If \(\alpha\) is a formula, then \((\bbN ~ \alpha)\) ("not \(\alpha\)") is a formula.
3. If \(\alpha\) is a formula and \(\beta\) is a formula, then \((\bbC ~ \alpha ~ \beta)\) ("\(\alpha\) and \(\beta\)") is a formula.
4. If \(\alpha\) is a formula and \(\beta\) is a formula, then \((\bbD ~ \alpha ~ \beta)\) ("\(\alpha\) or \(\beta\)") is a formula.

Examples for propositional calculus:

An example formula is \((\bbC ~ X ~ Y)\).
An example of a string that is not a formula is \(\bbC ~ X ~ Y\) because it lacks the parentheses.

7.2Note to self)

We should be less formal.
We should teach the formation rules by example.
We should use standard symbols \(\neg, \wedge, \vee\).
Should we use \(\&\) instead of \(\wedge\)?
- Do \(\wedge\) and \(\vee\) confuse newcomers?

7.3Syntax of predicate calculus

Now that we are familiar with the syntax of propositional calculus, we can move on to a predicate calculus.

To the logical symbols, we add two quantifier symbols:
- \(\forall\) ("for all", universal quantifier),
- \(\exists\) ("there exists", existential quantifier).
Every capital letter in italic font is called a relation symbol. Every relation symbol has an arity that is a natural number; the arity is the number of parameters taken by the relation symbol. If the arity is zero, the relation symbol is also called a constant symbol.
The non-logical symbols of a predicate calculus is a set of relation symbols; each relation symbol looks like \(A^n\) where \(n\) is the symbol's arity; it is the number of arguments.
- For example, we can define a predicate calculus whose set of relation symbols is \(\{ E^2 \}\).
  - An example formula is then \(E(x,y)\).
  - An example sentence is then \(\forall x ~ E(x,x)\).
We call a predicate calculus has order one iff the quantifiers can only take constant symbols.
To the formation rules, we add:
1. if \(\rho^n\) is a relation symbol of arity \(n\), and \(\alpha_1, \ldots, \alpha_n\) are variables, then \((\rho^n \alpha_1 \ldots \alpha_n)\) is a formula;
2. if \(\rho^0\) is a relation symbol of arity zero, then \(\rho^0\) is a formula;
3. if \(\alpha\) is a formula and \(\beta\) is a formula, then \((\bbC \alpha \beta)\) is a formula.
4. if \(v\) is a variable, \(Q\) is a quantifier, and \(F\) is a formula, then \((Q v ~ F)\) is a formula.

A sentence is something that can be given a truth value; in propositional calculus, it is a formula; in first-order predicate calculus, it is a formula with no free variables. An example of a first-order predicate calculus sentence is \(\forall x : E(x,x)\). An example of a first-order predicate calculus formula that is not a sentence is \(E(x,x)\).

An interpretation of a language is a function that takes a sentence of that language and gives a truth value. For example, if we have a graph, then we may map every term \(x\) to a vertex \(I(x)\) of the graph, and we may map the formula \(R(x,y)\) \(I(R(x,y))\), that is whether \((I(x), I(y))\) is an edge of the graph.

\[\begin{align*} I(R(x,y)) = E(I(x),I(y)) \end{align*} \]

7.4Many-valued logics

How many truth values are there? It depends on the logic. In classical logic, there are two truth values: false and true. In SQL (a language used to interact with relational databases), there are three truth values: false, null, and true. There are also four-valued logic¹⁵. In the IEEE 1164¹⁶ standard, there are nine truth values. In fuzzy logic, there are as many truth values as there are real numbers in \([0,1]\).

A metalanguage is a language that describes a language. We used English as a metalanguage to describe propositional calculus.

Now we formalize. Let \(L\) be a language, let \(F\) be the set of formulas of \(L\), and let \(T\) be the set of truth values of this interpretation. Let \(T = (\{0,1\},\neg,\wedge,\vee)\) be a Boolean algebra. (???)

An interpretation of a language \(L\) is a function \(I : F \to T\). This function must satisfy \(I((\bbN x)) = \neg I(x)\), and \(I((\bbC x y)) = I(x) \wedge I(y)\), and \(I((\bbD x y)) = I(x) \vee I(y)\).

For example, \(\{ x, y \}\) is a model of \(x\).

For example, \( \{ x, y, (\bbC x y) \} \models (\bbC x y) \).

For example, \(\{ (\bbC x y) \}\) is not an interpretation of \(L\), because if \((\bbC x y)\) is in \(I\), then both \(x\) and \(y\) must also be in \(I\).

We say that \(I\) models \(p\) or \(I\) is a model of \(P\), written \(I \models p\), iff \(I(p)\) is true. We say that \(p\) is satisfiable iff \(p\) has a model, that is, iff there exists \(I\) such that \(I \models p\). The symbol \(\models\) is called a "double turnstile". Why do we bother inventing another notation (\(\models\)) for a notation that already exists (\(\in\))?

For example, we may choose to map \(x\) to "true" and everything else to "false".

Extensions of first-order logic: modal logic

Given the formation rules of a language, we can (1) generate all formulas (2) decide whether a given string is a formula.

The logics form a hierarchy.

propositional logic
first-order logic
second-order logic

This first-order language can describe itself, where \(L(\alpha)\) is true iff \(\alpha\) is a string that is a Latin small letter alone:

\[\begin{align*} \forall \alpha : L(\alpha) &\implies W(\alpha) \\ \forall \alpha : \forall \beta : W(\alpha) &\implies W((N \alpha)) \\ \forall \alpha : \forall \beta : W(\alpha) \wedge W(\beta) &\implies W((C \alpha \beta)) \\ \forall \alpha : \forall \beta : W(\alpha) \wedge W(\beta) &\implies W((D \alpha \beta)) \end{align*} \]

and that can also be written using sequent calculus notation with implicit universal quantification over free variables:

\[\begin{align*} L(\alpha) &\vdash W(\alpha) \\ W(\alpha) &\vdash W((N \alpha)) \\ W(\alpha), W(\beta) &\vdash W((C \alpha \beta)) \\ W(\alpha), W(\beta) &\vdash W((D \alpha \beta)) \end{align*} \]

Related Wikipedia articles¹⁷ ¹⁸ ¹⁹ ²⁰ ²¹.

Gödel's theorems²² ²³.

"Propositional logic: models and proofs", by C. R. Ramakrishnan, 2016
Rough summary of first order logic, Finite Model Theory wikibook
Model theory
- Finite model theory
  - Elements of finite model theory by Leonid Libkins
  - WP:Finite model theory
- Short course on model theory
- WP:Löwenheim–Skolem theorem
- WP:Model theory
Formal logic
- Introduction to formal logic, philosophy
  - Turnstile symbol
Ungrouped
- WP:Mathematical logic
- Logic and probability, Stanford Encyclopedia of Philosophy
- WP:Semantic theory of truth
- WP:Tarski's definition of truth: T-schema
- Computational Logic Course Material
- WP:List of first-order theories
- WP:Realizability
- WP:Universal quantification, universal closure
- Math fonts
  - WP:Fraktur
  - WP:Blackboard bold

8Mess 2

In propositional logic, it takes at most \(O(n)\) steps to determine whether a string of length \(n\) is a formula.

A variable is any of the 26 Latin small letters from \(a\) to \(z\).

In propositional logic, we represent a sentence with a letter. For example, we can use the letter \(p\) to represent "John is lecturing" and the letter \(q\) to represent "John is awake". From those two sentences, we can construct another sentence \(p \to q\) that represents "If John is lecturing, then John is awake".

A logical system (a "logic") is a formal system and an interpretation. A formal system has a syntax and some inference rules. The syntax tells us how to form formulas. A syntax is a set of rules that determine which strings are formulas. The inference rules tell us how we can rewrite a formula to another formula while preserving the truth of the formula. A formula has no inherent meaning, but we can give meaning to it by defining an interpretation. An interpretation maps a formal system to a model.

A sentence is a formula with no free variables. A formula is a statement whose truth can be determined, that is either true or false. For example, "John is lecturing" and \(1+1 = 2\) are statements. Later we will see that there are other ways of defining "truth".

A signature \(\sigma\) is a triple of a set of relation symbols, a set of function symbols, and an arity function. A structure \(\struc{A}\) is a triple \((A,\sigma,I)\) where \(A\) is a domain, \(\sigma\) is a signature, and \(I\) is an interpretation function.

A formal argument is an argument that is made by blindly following the rules, by mechanically following the rules to manipulate symbols, without any meaning, without any guesswork. This allows computers to help us.

Readings?
- Model theory, 1970 article, Howard Jerome Keisler. It is accessible and it still gives a good and relevant introduction in 2017.
- Logic terms and concepts
  - Must distinguish logic and meta-logic.
- ???
  - Model theory, 1989 book, Chang and Keisler
- Barwise 1989 handbook of mathematical logic 8th impression 1999
  - Understand logic terms by formalizing group theory
- A short course on finite model theory by Jouko Väänänen

Here we will review mathematical logic and model theory.

Mathematical logic allows us to represent English in symbols without ambiguity. Logic also works with other human languages, not only English.

A key idea in logic is the separation between form and meaning. The validity of an argument depends only on its form?

Every argument of this form (modus ponens) is valid:

\[\begin{align*} p, ~ p \to q \vdash q \end{align*} \]

Abductive reasoning (physics?):

\[\begin{align*} p, ~ q \vdash_? p \to q \end{align*} \]

In classical deductive logic, there is only one way to reach valid conclusion: by valid premises and valid argument. There are three ways to arrive at an invalid conclusion: - by invalid premises but valid argument, - by valid premises but invalid argument, - by invalid premises and invalid argument.

In logic, an interpretation assigns truth value to well-formed formulas.

A system is sound iff every provable sentence is true: \(A \vdash B \implies A \models B\).

A system is complete iff every true sentence is provable \(A \models B \implies A \vdash B\).

https://en.wikibooks.org/wiki/Formal_Logic/Predicate_Logic/Satisfaction

Intended interpretation is synonym for standard model.

We use s-expressions to simplify parsing.

Greek letters are part of the metalanguage (the language describing the object language).

Example term: \((A (A a b) (N c))\).

9Probability logic

First-order probability logic (FOPL) shares the same syntax as first-order logic (FOL), but different interpretation:
- FOL interpretation maps FOL wff to truth value \(\{0,1\}\).
- FOPL interpretation maps FOL wff to probability \([0,1]\).
Boolean algebra is a special case of fuzzy logic?
- Replace \(\\{0,1\\}\) (the set of Boolean values) with \([0,1]\) (the set of real numbers in the unit line).
- WP:Boolean algebra
- WP:Fuzzy logic

\[\begin{align*} t(p \wedge q) &= \min(t(p), t(q)) \\ t(p \vee q) &= \max(t(p), t(q)) \\ t(\neg p) &= 1 - t(p) \end{align*} \]

Fuzzy logic is a special case of probability space?
- WP:probability space.
- What should \(t(p \to q)\) be?

Classical logic:

\[\begin{align*} t(p \to q) &= t(\neg p \vee q) = \max(1 - t(p), t(q)) \end{align*} \]

Bayesian:

\[\begin{align*} t(p \to q) &= t(q|p) = \frac{t(q \wedge p)}{t(p)} \end{align*} \]

Induction:

\[\begin{align*} \exists a (p(a) \wedge q(a)) \vdash_i \forall x (p(x) \wedge q(x)) \\ T(p) \subseteq T(q) \vdash_i \forall x (p(x) \implies q(x)) \\ T(p) = \{ x ~|~ p(x) \} \end{align*} \]

10TODO Sameness is meaning-preserving universal substitutability?

<2018-11-06> X is the same as Y iff every occurence of X can be replaced with Y while preserving the meaning of the containing statement.

What is the relationship between sameness and the principle of the identity of indiscernibles ("there cannot be separate objects or entities that have all their properties in common")? https://en.wikipedia.org/wiki/Identity_of_indiscernibles

11What is a truth value?

11.1As degree of certainty(54w~1m)
11.2As information transfer, as contagiousness of ascertainment(63w~1m)

11.1As degree of certainty

Let \(\tau(p) \in [0,1]\) describe how certain we are about the sentence \(p\). If \(\tau(p) = 0\), then we don't know anything about \(p\). If \(\tau(p) = 1\), then we know \(p\) for sure.

Note that \(\tau(p) = 0\) does not mean that \(p\) is false; it means that we don't know.

11.2As information transfer, as contagiousness of ascertainment

\(\tau(p \to q)\) measures the amount of information transferred from our knowledge of \(p\) to our knowledge of \(q\).

It measures how reducing the uncertainty of \(p\) reduces the uncertainty of \(q\).

[1] Hodges, W. 2018. Model theory. The stanford encyclopedia of philosophy. E.N. Zalta, ed. https://plato.stanford.edu/archives/fall2018/entries/model-theory/; Metaphysics Research Lab, Stanford University. url: <https://plato.stanford.edu/archives/fall2018/entries/model-theory/>.

[2] Immerman, N. 1999. Descriptive complexity.