Title: Theory / Unimportant / Math / Logic / Model theory / Finite model theory - Libkin / 2 game
Tags: fromMath mathToDef examplesSwitchExample1 toBinaryRelation

Name: Not definable in FO
Page: 23
Chapter: 3
Section: 1
Kind: Prop
Example: Connectivity of arbitrary graph.

Name: Theory without finite model, whose finite subset has finite model
Page: 24
Chapter: 3
Section: 1
Index: 2
Kind: Prop
Example: \(\{\exists x_1,\dots,x_n\bigwedge_{i\ne j}x_i\ne x_j\mid n\in\mathbb N\}\)

Definition: The query which holds over finite structure of even cardinality.
Page: 24
Chapter: 3
Section: 1
Notation: \(\text{EVEN}\)

Name: Not FO-definable query over empty vocabulary
Page: 25
Chapter: 3
Section: 1
Kind: Prop
Example: EVEN

Definition: A query defining the structures isomorphic to \(\mathfrak A\).
Page: 25
Chapter: 3
Section: 1
Variables: \(\sigma\) a vocabulary
\(\mathfrak A\in\text{STRUC}[\sigma]\)
Notation: \(\Phi_{\mathfrak A}\)
Index: 4
Kind: Lem

Page: 27
Definition: Two vectors \(\vec a=(a_1,\dots,a_n)\) and \(\vec b=(b_1,\dots,b_n)\) of elements of \(\mathfrak A\) and \(\mathfrak B\) respectively, such that:
-\(a_i=a_j\) iff \(b_i=b_j\),
-for every constant \(c\in\sigma\), \(c^{\mathfrak A}=a_i\) iff \(c^{\mathfrak B}=b_i\),
-For every \(k\)-ary relation symbol \(P\) from \(\sigma\) and every sequence \((i_1,\dots,i_k)\) of numbers from \([1,n]\), \((a_{i_1},\dots,a_{i_k})\in P^{\mathfrak A})\) iff \((b_{i_1},\dots,b_{i_k})\in P^{\mathfrak B})\).
Chapter: 3
Section: 2
Variables: \(\sigma\) a relational vocabulary,
\(\mathfrak{A,B}\) two \(\sigma\)-structures
Name: A partial isomorphism between \(\mathfrak A\) and \(\mathfrak B\)
Kind: Def
Index: 5

Smaller0: \(a_i\mapsto b_i\) is a partial isomorphism
Greater0: \(a_i\mapsto b_i\) is an isomorphism between the substructures generated by \(\{a_1,\dots,a_n\}\) and \(\{b_1,\dots,b_n\}\)
Page: 27
Chapter: 3
Section: 2
Variables: \(\sigma\) a purely relational vocabulary,
\(\mathfrak{A,B}\) two \(\sigma\)-structures,
Two vectors \(\vec a=(a_1,\dots,a_n)\) and \(\vec b=(b_1,\dots,b_n)\) of elements of \(\mathfrak A\) and \(\mathfrak B\) respectively.
Index: 5
Kind: Def
Smaller to greater: iff

Name: A state of the Ehrenfeucht-Fraı̈ssé game
Definition: Two vectors \(\vec a=(a_1,\dots,a_n)\) and \(\vec b=(b_1,\dots,b_n)\) of elements of \(\mathfrak A\) and \(\mathfrak B\) respectively.
Page: 27
Chapter: 3
Section: 2
Variables: \(\sigma\) a relational vocabulary,
\(\mathfrak{A,B}\) two \(\sigma\)-structures,
Index: 5
Kind: Def

Name: A winning position for the duplicator
Definition: Two vectors \(\vec a=(a_1,\dots,a_n)\) and \(\vec b=(b_1,\dots,b_n)\) of elements of \(\mathfrak A\) and \(\mathfrak B\) respectively, such that \(((\vec a,\vec c^{\mathfrak A}),(\vec b,\vec c^{\mathfrak B}))\) is a partial isomorphism, where&nbsp\(\vec c\) is the set of constants in \(\sigma\).
Page: 27
Chapter: 3
Section: 2
Variables: \(\sigma\) a relational vocabulary,
\(\mathfrak{A,B}\) two \(\sigma\)-structures,
Index: 5
Kind: Def

Name: A step of the Ehrenfeucht-Fraı̈ssé Game
Definition: The spoiler picks \(i\in\{0,1\}\) and an element \(b^i\in\mathfrak A^i\).
Duplicator picks \(b^{1-i}\in\mathfrak A^{i-1}\). The new state is \((\vec a^0b^0,\vec a^1b^1)\).
Page: 26-27
Chapter: 3
Section: 2
Variables: \(\sigma\) a relational vocabulary,
\(\mathfrak{A^0,A^1}\) two \(\sigma\)-structures,
\(\vec a^0,\vec a^1\) a state of the Ehrenfeucht-Fraı̈ssé Game

Name: Duplicator has an \(n\)-round winning strategy in the Ehrenfeuch-Fraïssé game on \(\mathfrak A \) and \(\mathfrak B\)
Definition: Duplicator can play in a way that guarantees a winning position after \(n\) rounds, no matter how the spoiler plays.
Page: 27-28, 29
Chapter: 3
Section: 2
Variables: \(\sigma\) a relational vocabulary,
\(\mathfrak{A,B}\) two \(\sigma\)-structures,
\(n\in\mathbb N\)
Notation: \(\mathfrak A\equiv _n \mathfrak B\)
Index: , 6
Kind: , Theo
Example: \(n\) is the least of their cardinality
Example2: \(n\) is the logarithm of the least of their cardinality.
Applied to: \(\sigma=\emptyset\), \(\mathfrak A\equiv_ n\mathfrak B\)
Applied to2: \(\sigma=\{<\}\), \(\mathfrak A\equiv_n\mathfrak B\)

Definition: The substructures of \(L\) that constist of all the elements \(b\le a\) (\(b\ge a\)).
Page: 31
Chapter: 3
Section: 2
Variables: \(L\) a linear ordering,
\(a\in L\)
Notation: \(L^{\le a}\), \(L^{\ge a}\)

Smaller0: \(L_1^{\le a_1}\equiv_kL_2^{\ge a_2}\) and \(L_1^{\ge a_1}\equiv_kL_2^{\ge a_2}\)
Greater0: \((L_1,a_1)\equiv_k(L_2,a_2)\)
Page: 31
Chapter: 3
Section: 2
Variables: \(L_1,L_2\) linear orderings,
\(a_i\in L_i\)
Hide middle: yes
Name: Composition methods
Context: Game theory