Title: Theory / Unimportant / Math / Logic / Model theory / Finite model theory - Libkin / 1 Introduction
Tags: fromMath mathToDef mathToSee hasSeenConjDef toBinaryRelation
On every note of this deck, unless a note says otherwise:
Chapter: 2
Section: 1

Name: A vocabulary
Definition: A collection of constant symbols, relation/predicate symbols and function symbols, non-constant symbols are associated with an arity.
Page: 13
Kind: Def

Name: A \(\sigma\)-structure
Definition: \(\mathfrak A=\langle A,\{c_i^{\mathfrak A}\},\{P_i^{\mathfrak A}\},\{f_i^{\mathfrak A}\}\rangle\) with:
-\(A\) an universe,
-\(c_i^{\mathfrak A}\in A\),
-\(P_i^{\mathfrak A}\subseteq A^k\),
-\(f_i^{\mathfrak A}:A^k\to A\).
Page: 13
Variables: \(\sigma\) a vocabulary
Kind: Def
Name2: A \(\sigma\)-model

Name: A relational vocabulary
Definition: A vocabulary which does not contain function symbol.
Page: 14

Name: Purely relational vocabulary
Definition: A vocabulary which contains only relation symbol.
Page: 14

Q: Vocabularies are assumed to be:
-[...],
-[...].
A: at most countable; relational if we deal with finite structure
Page: 14
Chapter: 2
Section: 1
Variables: \(\sigma\) a vocabulary

The set of formula contain:
-Relation symbols applied to terms,
-equality of terms,
-boolean combination of formulae and
-quantication of variable followed by formulae.
Page: 14
Chapter: 2
Section: 1
Variables: \(\sigma\) a vocabulary.
Kind: Def

Name: A quantifier-free formula
Definition: A formula which does not contain quantifiers.
Page: 14
Variables: \(\phi\) a formula
Kind: Def

Name: The set of free variables of \(t\)
Definition: \(\{t\}\) if \(t\) is a variable
Page: 14
Variables: \(t\) a term
Definition2: \(\emptyset\) if \(t\) is a constant
Definition3: The union of the sets recursively computed on the \(t_i\)'s if \(t=f(t_1,\dots,t_k)\).

Name: The set of free variables of \(\phi\)
Definition: The union of the set of free variables of the \(t_i\) if \(\Phi=R(t_1,\dots,t_k)\) or \(\Phi\) is \(t_1=t_2\)
Page: 14
Variables: \(\phi\) a formula
Definition2: The union of the set of free variables of its subformula if \(\phi\) is a Boolean combination
Conjdef: Either
Definition3: The set of free variable of its subformula, apart from \(x\), if \(\phi\) is \(\exists x\psi\)

Name: A sentence
Definition: A formula whose set of free variable is empty.
Page: 15

Q: -[...] if \(t=c\),
-[...] if \(t=x_i\),
-[...] if \(t(\vec a)=f(t_1,\dots,t_k)\).
A: \(c^{\mathfrak A}\); \(a_i\); \(f^{\mathfrak A}(t_1^{\mathfrak A}(\vec a),\dots,t_k^{\mathfrak A}(\vec a))\)
Page: 15
Chapter: 2
Section: 1
Variables: \(t\) a term with free variables \(x_1,\dots,x_n\), \(\mathfrak A\) a structure and \(\vec a=a_1,\dots,a_n\in A\)
Notation: \(t(\vec a)^{\mathfrak A}\)

Definition: if \(\phi\) is \(t_1=t_2\) then \(t_1^{\mathfrak A}=t_2^{\mathfrak A}\)
Page: 15
Variables: \(\phi\) a formula with free variables \(x_1,\dots,x_n\), \(\mathfrak A\) a structure and \(\vec a=a_1,\dots,a_n\in A\)
Notation: \({\mathfrak A}\models \phi\)
Definition2: if \(\phi\) is \(\exists y\phi(y,\vec x)\) (respectively, \(\forall y\phi(y,\vec x)\)) then \({\mathfrak A}\models \phi(a',\vec a)\) for some (respectively, for all) \(a'\in A\).
Definition3: if \(\phi\) is conjonction/disjonction/negation of formulas, then \({\mathfrak A}\) is a model of both/at least one/ is not a model of them
Definition4: if \(\phi\) is \(P(t_1,\dots,t_k)\) then \((t_1^{\mathfrak A},\dots,t_k^{\mathfrak A})\in R^{\mathfrak A}\)

Name: The substructure of \(A\) generated by \(A_0\)
Definition: A \(\sigma\)-structure \(\mathfrak B\) whose universe is \(B=A_0\cup\{c^{\mathfrak A}\mid c\text{ a constant symbol in $\sigma$}\}\), with \(R^{\mathfrak B}=R^{\mathfrak A}\cap A_0^k\).
Page: 15
Variables: \(\sigma\) a vocabulary, \(\mathfrak A\in\text{STRUCT}[\sigma]\) and \(A_0\subseteq A\).
Extra: Not assumed to be relational in the text

Definition: The \(\sigma_0\cup \sigma_1\)-structure on \(A\) in which all constant and relation symbols in \(\sigma_i\) are intepreted as in \(\mathfrak A_i\).
Page: 15
Variables: \(\sigma_0,\sigma_1 \) vocabularies, \(\mathfrak A_i\in\text{STRUCT}[\sigma_i]\).
Notation: \((\mathfrak{A_0,A_1})\)

Definition: The vocabulary \(\sigma\cup \{c_1,\dots,c_n\}\) with \(c_i\) a new constant symbol.
Page: 16
Variables: \(\sigma \) a vocabularie
\(n\in\mathbb N\)
Notation: \(\sigma_n\)

Smaller0: \(\mathfrak\models\phi(\vec a)\)
Greater0: \((\mathfrak A,a_1,\dots,a_n)\models\Phi\) where \(\Phi\) is the \(\sigma_n\)-formula obtained from \(\phi\) by replacing \(x_i\) by \(c_i\) and \(x_i\)'s is interpreted by \(a_i\)
Page: 16
Chapter: 2
Section: 1
Variables: \(\sigma \) a vocabulary,
\(\phi(\vec x)\) a formula,
\(\mathfrak A\in\text{STRUC}[\sigma]\)
\(\vec a\in A^n\)
Index: 3
Kind: Lem
Smaller to greater: iff

Name: A theory over \(\sigma\)
Definition: A set of sentences.
Page: 16
Variables: \(\sigma \) a vocabulary.
Index: 4
Kind: Def

Name: \(\mathfrak A\) is a model of \(T\)
Definition: For every sentence \(\Phi\in T\), \(\mathfrak A\models \Phi\).
Page: 16
Variables: \(\sigma \) a vocabulary
\(T\) a theory
\(\mathfrak A\in\text{STRUC}[\sigma]\)
Index: 4
Kind: Def

Name: Consistent theory
Definition: A theory which have a model.
Page: 16
Variables: \(\sigma \) a vocabulary.
Index: 4
Kind: Def
Extra: satisfiable is for formula, not theory
Does not lead to contradiction ?

Smaller0: \(T\) is consistent
Greater0: every finite subset of \(T\) is consistent
Page: 16
Chapter: 2
Section: 1
Variables: \(\sigma \) a vocabulary
\(T\) a theory
Index: 5
Kind: Theo
Smaller to greater: iff
Name: Compactness

Name: Satisfiable formula
Definition: A formula which has a model.
Page: 16
Variables: \(\sigma \) a vocabulary

Name: A valid formula
Definition: A formula which is true in every structure.
Page: 16
Variables: \(\sigma \) a vocabulary

Smaller0: \(\Phi\) is not valid
Greater0: satisfiable
Page: 16
Chapter: 2
Section: 1
Variables: \(\sigma \) a vocabulary, let \(\Phi\) a formula
Smaller to greater: iff
Prefix Greater: \(\neg\Phi\) is

Name: A homomorphism between \(\mathfrak A\) and \(\mathfrak B\)
Definition: A mapping \(h:A\to B\) such that \(h(c^{\mathfrak A})=c^{\mathfrak B}\), and for each \((a_1,\dots,a_k)\in R^{\mathfrak A}\), \((h(a_1),\dots,h(a_k))\in R^{\mathfrak B}\).
Page: 16
Variables: \(\sigma \) a vocabulary, let \(\mathfrak{A,B}\in\text{STRUC}[\sigma]\)

Name: An isomorphism
Definition: A bijective homomorphism whose inverse is an homomorphism.
Page: 17
Variables: \(\sigma \) a vocabulary, let \(\mathfrak{A,B}\in\text{STRUC}[\sigma]\)

Page: 17
Definition: There is an isomorphism between \(\mathfrak A\) and \(\mathfrak B\).
Chapter: 2
Section: 1
Variables: \(\sigma \) a vocabulary, let \(\mathfrak{A,B}\in\text{STRUC}[\sigma]\).
Notation: \(\mathfrak A\cong\mathfrak B\)

Name: An \(m\)-ary query on \(\sigma\)-structure
Definition: A mapping \(Q\) associating to each \(\mathfrak A\in\text{STRUC}[\sigma]\) a subset of \(A^m\) such that \(Q\) is closed under isomorphism.
Page: 17
Variables: \(\sigma \) a vocabulary, \(m\in\mathbb N\)
Index: 7
Kind: Def

Name: A \(m\)-ary query definable in \(\mathcal L\)
Definition: A \(m\)-ary query \(Q\) such that there is a formula \(\phi(x_1,\dots,x_m)\in\mathcal L\) in vocabulary \(\sigma\) such that for every \(\mathfrak A\), \(Q(\mathfrak A)=\{(a_1,\dots,a_m)\in A^m\mid \mathfrak A\models \phi(a_1,\dots,a_m)\}\).
Page: 17
Variables: \(\sigma\) a vocabulary,
\(\mathcal L\) a logic,
\(m\in\mathbb N\)
Index: 7
Kind: Def

Definition: \(\{(a_1,\dots,a_m)\in A\mid \mathfrak A\models \phi(a_1,\dots,a_m)\}\).
Page: 17
Variables: \(\sigma \) a vocabulary,
\(\mathcal L\) a logic,
\(m\in\mathbb N\)
\(\phi(\vec x)\) a formula
Notation: \(\Phi(\mathfrak A)\)
Index: 7
Kind: Def

Definition: \(\{(a_1,\dots,a_m)\in A^m\mid \mathfrak A\models \phi(a_1,\dots,a_m,\vec b)\}\).
Page: 17
Variables: \(\sigma \) a vocabulary,
\(\mathcal L\) a logic,
\(m\in\mathbb N\)
\(\phi(\vec x,\vec y)\) a formula
\(\vec b\in A^{k'}\)
Notation: \(\Phi(\mathfrak A,\vec b)\)
Index: 7
Kind: Def

Name: A Boolean query
Definition: A \(0\)-ary query.
Page: 17
Variables: \(\sigma \) a vocabulary.
Index: 7
Kind: Def

Name: The set of terms
Definition: variables
Page: 14
Variables: \(\sigma\) a vocabulary.
Kind: Def
Definition2: constants
Conjdef: The least set containing
Definition3: function applied to terms.

Smaller0: \(T\) has an infinite model
Greater0: \(T\) has a countable model
Page: 16
Chapter: 2
Section: 1
Variables: \(\sigma \) a vocabulary
\(T\) a theory.
Index: 6
Kind: Theo
Name: Löwenheim-Skolem