Games in Logic
97
Goal: check which properties / languages are definable in a logic (e.g. FO)
Games in Logic
97
Goal: check which properties / languages are definable in a logic (e.g. FO)
Examples
• Is the property “Universe has even cardinality” definable in FO(E) ?
• Is the class of “Strongly connected graphs” definable in FO(E) ?
• Is the language L=(AA)* definable in FO(≤,A,B) ?
Warmup — The evaluation game
98
Goal: check whether M ⊨ φ
Model-check(φ, M)
if φ = R(x1,…,xk) then
if (x1M,…,xkM) ∈ RM then return true
else
return false
else if φ = φ1 ∨ φ2 then
return Model-check(φ1, M) OR Model-check(φ2, M)
else if …
…
else if φ = ∃x φ’ then for u ∈ UM do
if Model-check(φ’, M[x:=u]) then return true
return false
else if φ = ∀x φ’ then for u ∈ UM do
if NOT Model-check(φ’, M[x:=u]) then return false
return true
Warmup — The evaluation game
98
Goal: check whether M ⊨ φ
Model-check(φ, M)
if φ = R(x1,…,xk) then
if (x1M,…,xkM) ∈ RM then return true
else
return false
else if φ = φ1 ∨ φ2 then
return Model-check(φ1, M) OR Model-check(φ2, M)
else if …
…
else if φ = ∃x φ’ then for u ∈ UM do
if Model-check(φ’, M[x:=u]) then return true
return false
else if φ = ∀x φ’ then for u ∈ UM do
if NOT Model-check(φ’, M[x:=u]) then return false
return true
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Warmup — The evaluation game
99
Goal: check whether M ⊨ φ
Players: Eve, Adam
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Warmup — The evaluation game
99
Goal: check whether M ⊨ φ
Players: Eve, Adam
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
Recall: negations pushed inside
¬∀φ ⇝ ∃¬φ ¬∃φ ⇝ ∀¬φ
¬(φ ⋀ ψ) ⇝ ¬φ ⋁ ¬ψ …
Warmup — The evaluation game
99
(assume w.l.o.g. that φ is in Negation Normal Form)
Goal: check whether M ⊨ φ
Players: Eve, Adam
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
At each position (α, λ) of the arena
• if α = R(x1,…,xk) then game ends, Eve wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Adam wins
• if α = ¬R(x1,…,xk) then game ends, Adam wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Eve wins
Warmup — The evaluation game
99
(assume w.l.o.g. that φ is in Negation Normal Form)
Goal: check whether M ⊨ φ
Players: Eve, Adam
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
At each position (α, λ) of the arena
• if α = R(x1,…,xk) then game ends, Eve wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Adam wins
• if α = ¬R(x1,…,xk) then game ends, Adam wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Eve wins
Warmup — The evaluation game
99
(assume w.l.o.g. that φ is in Negation Normal Form)
Goal: check whether M ⊨ φ
Players: Eve, Adam
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
• if α = α1 ∨ α2 then Eve can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
At each position (α, λ) of the arena
• if α = R(x1,…,xk) then game ends, Eve wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Adam wins
• if α = ¬R(x1,…,xk) then game ends, Adam wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Eve wins
Warmup — The evaluation game
99
(assume w.l.o.g. that φ is in Negation Normal Form)
Goal: check whether M ⊨ φ
Players: Eve, Adam
• if α = α1 ⋀ α2 then Adam can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
• if α = α1 ∨ α2 then Eve can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
At each position (α, λ) of the arena
• if α = R(x1,…,xk) then game ends, Eve wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Adam wins
• if α = ¬R(x1,…,xk) then game ends, Adam wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Eve wins
Warmup — The evaluation game
99
(assume w.l.o.g. that φ is in Negation Normal Form)
Goal: check whether M ⊨ φ
Players: Eve, Adam
• if α = ∃x α’(x) then Eve can choose any element u ∈ UM to be bound to x, game continues at position (α’, λ’) where λ’=λ[x:=u]
• if α = α1 ⋀ α2 then Adam can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
• if α = α1 ∨ α2 then Eve can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
At each position (α, λ) of the arena
• if α = R(x1,…,xk) then game ends, Eve wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Adam wins
• if α = ¬R(x1,…,xk) then game ends, Adam wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Eve wins
Warmup — The evaluation game
99
(assume w.l.o.g. that φ is in Negation Normal Form)
Goal: check whether M ⊨ φ
Players: Eve, Adam
• if α = ∃x α’(x) then Eve can choose any element u ∈ UM to be bound to x, game continues at position (α’, λ’) where λ’=λ[x:=u]
• if α = ∀x α’(x) then Adam can choose any element u ∈ UM to be bound to x, game continues at position (α’, λ’) where λ’=λ[x:=u]
• if α = α1 ⋀ α2 then Adam can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
Construct a two-player game Gφ,M
whose winner determines whether M ⊨ φ
Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
• if α = α1 ∨ α2 then Eve can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
At each position (α, λ) of the arena
• if α = R(x1,…,xk) then game ends, Eve wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Adam wins
• if α = ¬R(x1,…,xk) then game ends, Adam wins if (λ(x1),…,λ(xk)) ∈ RM, otherwise Eve wins
Warmup — The evaluation game
99
(assume w.l.o.g. that φ is in Negation Normal Form)
Goal: check whether M ⊨ φ
Players: Eve, Adam
• if α = ∃x α’(x) then Eve can choose any element u ∈ UM to be bound to x, game continues at position (α’, λ’) where λ’=λ[x:=u]
• if α = ∀x α’(x) then Adam can choose any element u ∈ UM to be bound to x, game continues at position (α’, λ’) where λ’=λ[x:=u]
• if α = α1 ⋀ α2 then Adam can choose α’ ∈ {α1, α2}, game continues at position (α’, λ) Arena: subformulas α of φ
+ binding λ : FreeVars(α) → UM
• if α = α1 ∨ α2 then Eve can choose α’ ∈ {α1, α2}, game continues at position (α’, λ)
Lemma
M ⊨ φ iff Eve has a strategy to win Gφ,M
Definability vs elementary equivalence vs n-equivalence
100
Notation P : property (i.e. set of models), M : model, φ : FO formula
Definability vs elementary equivalence vs n-equivalence
100
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
Notation P : property (i.e. set of models), M : model, φ : FO formula
Definability vs elementary equivalence vs n-equivalence
100
M,M’ elementary equivalent if for every φ M ⊨ φ iff M’ ⊨ φ 2)
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
Notation P : property (i.e. set of models), M : model, φ : FO formula
intuitively,
no formula can distinguish M from M’
Definability vs elementary equivalence vs n-equivalence
100
M,M’ elementary equivalent if for every φ M ⊨ φ iff M’ ⊨ φ 2)
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
Lemma If
M ∈ P, M’ ∉ P, and M,M’
then P is not definable in FO elementary
Notation P : property (i.e. set of models), M : model, φ : FO formula
there are M,M’ such that
equivalent
intuitively,
no formula can distinguish M from M’
Definability vs elementary equivalence vs n-equivalence
101
M,M’ elementary equivalent if for every φ M ⊨ φ iff M’ ⊨ φ 2)
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
Lemma If
M ∈ P, M’ ∉ P, and M,M’
then P is there are M,M’ such thatnot definable in FO elementary
equivalent
Definability vs elementary equivalence vs n-equivalence
101
φ has quantifier rank n if it has at most n nested quantifiers 3)
Example φ = ∀x∀y (¬E(x,y) ⋁ (∃z E(x,z)) ⋁ (∃t E(t,y)) )
has quantifier rank 3 (q.r. can be ≪ # quantifiers) M,M’ elementary equivalent if for every φ M ⊨ φ iff M’ ⊨ φ
2)
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
Lemma If
M ∈ P, M’ ∉ P, and M,M’
then P is there are M,M’ such thatnot definable in FO elementary
equivalent
Definability vs elementary equivalence vs n-equivalence
101
φ has quantifier rank n if it has at most n nested quantifiers 3)
M,M’ are n-equivalent if for every φ with q.r. n M ⊨ φ iff M’ ⊨ φ 4)
M,M’ elementary equivalent if for every φ M ⊨ φ iff M’ ⊨ φ 2)
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
Lemma If
M ∈ P, M’ ∉ P, and M,M’
then P is there are M,M’ such thatnot definable in FO elementary
equivalent
Lemma If
M ∈ P, M’ ∉ P, and M,M’
then P is not definable in FO
Definability vs elementary equivalence vs n-equivalence
102
φ has quantifier rank n if it has at most n nested quantifiers 3)
M,M’ are n-equivalent if for every φ with q.r. n M ⊨ φ iff M’ ⊨ φ 4)
for every n
M,M’ elementary equivalent if for every φ M ⊨ φ iff M’ ⊨ φ 2)
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
there are M,M’ such thatn-
equivalent
Lemma If
M ∈ P, M’ ∉ P, and M,M’
then P is not definable in FO
Definability vs elementary equivalence vs n-equivalence
102
φ has quantifier rank n if it has at most n nested quantifiers 3)
M,M’ are n-equivalent if for every φ with q.r. n M ⊨ φ iff M’ ⊨ φ 4)
for every n
M,M’ elementary equivalent if for every φ M ⊨ φ iff M’ ⊨ φ 2)
P defined by φ if for every M M ∈ P iff M ⊨ φ 1)
there are M,M’ such thatn-
equivalent
New goal: check whether
M,M' are n-equivalent
Construct a new game GM,M’
whose winner determines whether M,M’ are n-equivalent
Ehrenfeucht-Fraïssé games
103
Spoiler Duplicator
Ehrenfeucht-Fraïssé games
103
Spoiler Duplicator
M, M’ are n-equivalent!
Ehrenfeucht-Fraïssé games
103
Spoiler Duplicator
No they’re NOT!!!!
M, M’ are n-equivalent!
Ehrenfeucht-Fraïssé games
103
Spoiler Duplicator
No they’re NOT!!!!
Play for n rounds on the arena whose positions are tuples
(u1,…,ui ,v1,…,vi) ∈ UM × … × UM × UM’ × … × UM’
At each round i
Spoiler chooses an element ui from UM (or vi from UM’)
Duplicator responds with an element vi from UM’ (resp. ui from UM) Duplicator survives if M | {u1,…,ui} and M’ | {v1,…,vi} are isomorphic
M, M’ are n-equivalent!
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
1
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
1 1
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
1
2 1
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
2
1
2 1
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
2
3 1
2 1
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
2
3 1
2 3
1
M’
M
Ehrenfeucht-Fraïssé games
104
Example How many rounds can Duplicator survive ?
2
3 1
2 3
1
M = (ℤ, <)
Ehrenfeucht-Fraïssé games
105
Example How many rounds can Duplicator survive ?
M’ = (ℝ, <)
M = (ℤ, <)
Ehrenfeucht-Fraïssé games
105
Example How many rounds can Duplicator survive ?
M’ = (ℝ, <) 1
M = (ℤ, <)
Ehrenfeucht-Fraïssé games
105
Example How many rounds can Duplicator survive ?
M’ = (ℝ, <) 1
1
M = (ℤ, <)
Ehrenfeucht-Fraïssé games
105
Example How many rounds can Duplicator survive ?
M’ = (ℝ, <) 1
1 2
M = (ℤ, <)
Ehrenfeucht-Fraïssé games
105
Example How many rounds can Duplicator survive ?
M’ = (ℝ, <)
1 2
1 2
M = (ℤ, <)
Ehrenfeucht-Fraïssé games
105
Example How many rounds can Duplicator survive ?
M’ = (ℝ, <)
1 3 2
1 2
M = (ℤ, <)
Ehrenfeucht-Fraïssé games
105
Example How many rounds can Duplicator survive ?
M’ = (ℝ, <)
1 3 2
1 2
Ehrenfeucht-Fraïssé games
106
On non-isomorphic finite models, Spoiler always wins, eventually… Why?
2n - 1 nodes 2n nodes
…and he often wins very quickly!
Ehrenfeucht-Fraïssé games
106
On non-isomorphic finite models, Spoiler always wins, eventually… Why?
2n - 1 nodes 2n nodes
…and he often wins very quickly!
Ehrenfeucht-Fraïssé games
106
On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
Ehrenfeucht-Fraïssé games
106
On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
2
On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
2
On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 3
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
2
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 3
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex)
2
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 3
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1
2
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 3
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1
2
1
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 3
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2
2
1
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 3
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2
2
1 2
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
1 3
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2
2
1 2
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
3
3 1
1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2
2
1 2
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
3
3 3
1 1
2n - 1 nodes 2n nodes
…and he often wins very quickly!
2
Ehrenfeucht-Fraïssé games
106
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2
2
1 2
Given n,
at each round i = 1, …, n,
pairs of marked nodes in M and M’
must be either at equal distance or at distance ≥ 2n - i
But there are non-isomorphic infinite models where
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!) On non-isomorphic finite models, Spoiler always wins, eventually… Why?
3
3 3
1 1
Ehrenfeucht-Fraïssé games
107
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2 1 2
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!)
3 3
Ehrenfeucht-Fraïssé games
107
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2 1 2
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!)
3 3
Ehrenfeucht-Fraïssé games
107
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé '50, Ehrenfeucht '60]
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2 1 2
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!)
3 3
Ehrenfeucht-Fraïssé games
107
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé '50, Ehrenfeucht '60]
In particular, P = {discrete orders} is not definable in FO, since ℤ ∈ P and {1,2}×ℤ ∉ P
M = (ℤ, <) M’ = ({1,2}×ℤ, <lex) 1 2 1 2
Duplicator can survive for arbitrarily many rounds (but not necessarily forever!)
3 3
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
…
…
M
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
…
…
M
…
…
…
…
M’
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
…
…
M
…
…
…
…
M’
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
1
…
…
M
…
…
…
…
M’
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
1 1
…
…
M
…
…
…
…
M’
2
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
1 1
…
…
M
…
…
…
…
M’
2
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
1 1
2
…
…
M
…
…
…
…
M’
2
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
1 1
2
3
…
…
M
3
…
…
…
…
M’
2
Ehrenfeucht-Fraïssé games
108
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={connected graphs}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
1 1
2
3
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
1
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
1 1
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
2 1 1
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
2
2 1 1
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
3 2
2 1 1
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
3 2 3
2 1 1
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
109
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Example P={even cardinality}. Given n, find M∈P, M’∉P where Duplicator survives n rounds
2n 2n+1
3 2 3
2 1 1
Rule of thumb If Spoiler plays “close” to previous pebbles,
then Duplicator responds isomorphically within the corresponding neighbourhoods otherwise Duplicator plays “far” but has freedom of choice
Lemma If for every n there are M,M’ such that
M ∈ P, M’ ∉ P, and M,M’ n-equivalent then P is not definable in FO
Ehrenfeucht-Fraïssé games
110
Several properties can be proved to be not definable in FO:
• connectivity
• parity (i.e. even / odd)
• 2-colorability
• finiteness
• acyclicity …
Ehrenfeucht-Fraïssé games
110
Your turn now!
Several properties can be proved to be not definable in FO:
• connectivity
• parity (i.e. even / odd)
• 2-colorability
• finiteness
• acyclicity …
Ehrenfeucht-Fraïssé games
110
Ehrenfeucht-Fraïssé games — soundness
111
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Ehrenfeucht-Fraïssé games — soundness
111
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games — soundness
111
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Ehrenfeucht-Fraïssé games — soundness
111
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Eve
• disjunction
evaluation game GM’,φ
Ehrenfeucht-Fraïssé games — soundness
111
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
which disjunct should I pick ?
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Eve
• disjunction
evaluation game GM’,φ
Ehrenfeucht-Fraïssé games — soundness
111
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
evaluation game GM,φ
which disjunct should I pick ? Here I know which
disjunct to pick!
Eve
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Eve
• disjunction
evaluation game GM’,φ
Ehrenfeucht-Fraïssé games — soundness
111
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
evaluation game GM,φ
I pick same disjunct Here I know which
disjunct to pick!
Eve
Ehrenfeucht-Fraïssé games
112
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
112
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Adam picked a conjunct
• conjunction
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
112
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
Eve wins the evaluation game GM,φ
Eve wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
Adam picks same conjunct
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Adam picked a conjunct
• conjunction
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
113
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
True wins the evaluation game GM,φ
True wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
113
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
True wins the evaluation game GM,φ
True wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
• existential quantification Eve
?
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
113
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
True wins the evaluation game GM,φ
True wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
binds x to u ∈ UM Eve
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
• existential quantification Eve
?
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
113
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
True wins the evaluation game GM,φ
True wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
EF game GM,M’
binds x to u ∈ UM Eve
Spoiler places pebble u
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
• existential quantification Eve
?
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
113
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
True wins the evaluation game GM,φ
True wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
EF game GM,M’
Duplicator responds with v
binds x to u ∈ UM Eve
Spoiler places pebble u
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
• existential quantification Eve
?
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
Ehrenfeucht-Fraïssé games
113
Theorem M,M’ n-equivalent iff Duplicator survives n rounds in GM,M’
[Fraïssé ’50, Ehrenfeucht ’60]
Proof (if direction — from Duplicator’s strategy to n-equivalence)
True wins the evaluation game GM,φ
True wins the evaluation game GM’,φ
evaluation game GM,φ evaluation game GM’,φ
EF game GM,M’
Duplicator responds with v
binds x to u ∈ UM Eve
Spoiler places pebble u
binds x to v ∈ UM’
• disjunction
• conjunction
• existential quantification
• universal quantification 4 cases based on subformula:
• existential quantification Eve
Consider φ in NNF and with quantifier rank n Suppose M ⊨ φ and Duplicator survives n rounds in GM,M’
Need to prove that M’ ⊨ φ
