The rules for assigning truth to sentences of
L
P
{\displaystyle {\mathcal {L_{P}}}\,\!}
∀
α
φ
{\displaystyle \forall \alpha \,\varphi \,\!}
is true if and only if
φ
{\displaystyle \varphi \,\!}
φ
{\displaystyle \varphi \,\!}
α
{\displaystyle \alpha \,\!}
α
{\displaystyle \alpha \,\!}
φ
{\displaystyle \varphi \,\!}
assignment of objects from the domain to each of the variables,specification of whether a model satisfies a formula with a particular assignment of variables. We can then define truth in a model in terms of satisfaction.
Given model
M
{\displaystyle {\mathfrak {M}}\,\!}
variable assignment, denoted
s
{\displaystyle \mathrm {s} \,\!}
|
M
|
{\displaystyle |{\mathfrak {M}}|\,\!}
L
P
{\displaystyle {\mathcal {L_{P}}}\,\!}
|
M
|
{\displaystyle |{\mathfrak {M}}|\,\!}
s
{\displaystyle \mathrm {s} \,\!}
x
{\displaystyle x}
s
(
x
)
=
7
{\displaystyle \mathrm {s} (x)=7}
In addition to variable assignment, we also have the assignment of domain members to constant symbols by the model's interpretation function
I
M
{\displaystyle I_{\mathfrak {M}}\,\!}
extended variable assignment, denoted
s
¯
{\displaystyle {\overline {\mathrm {s} }}\,\!}
I
M
{\displaystyle I_{\mathfrak {M}}\,\!}
L
P
{\displaystyle {\mathcal {L_{P}}}\,\!}
An extended variable assignment
s
¯
{\displaystyle {\overline {\mathrm {s} }}\,\!}
|
M
|
{\displaystyle |{\mathfrak {M}}|\,\!}
If
α
{\displaystyle \alpha \,\!}
variable , then:
s
¯
(
α
)
=
s
(
α
)
{\displaystyle {\overline {\mathrm {s} }}(\alpha )\ =\ \mathrm {s} (\alpha )\,\!}
If
α
{\displaystyle \alpha \,\!}
constant symbol (i.e., a 0-place operation letter), then:
s
¯
(
α
)
=
I
M
(
α
)
{\displaystyle {\overline {\mathrm {s} }}(\alpha )\ =\ I_{\mathfrak {M}}(\alpha )\,\!}
If
ζ
{\displaystyle \zeta \,\!}
n -place operation letter (n greater than 0) and
α
1
,
α
2
,
…
,
α
n
{\displaystyle \alpha _{1},\ \alpha _{2},\ \ldots ,\ \alpha _{n}\,\!}
terms , then:
s
¯
(
ζ
(
α
1
,
α
2
,
…
,
α
n
)
)
=
I
M
(
ζ
)
(
s
¯
(
α
1
)
,
s
¯
(
α
2
)
,
…
,
s
¯
(
α
n
)
)
{\displaystyle {\overline {\mathrm {s} }}{\big (}\,\zeta (\alpha _{1},\,\alpha _{2},\,\ldots ,\,\alpha _{n})\,{\big )}\ =\ I_{\mathfrak {M}}(\zeta )\,{\big (}\ {\overline {\mathrm {s} }}(\,\alpha _{1}),\,{\overline {\mathrm {s} }}(\alpha _{2}),\,\ldots ,\,{\overline {\mathrm {s} }}(\alpha _{n})\,{\big )}\,\!}
Some examples may help. Suppose we have model
I
M
{\displaystyle I_{\mathfrak {M}}\,\!}
|
M
|
=
{
1
,
2
,
3
}
.
{\displaystyle |{\mathfrak {M}}|\ =\ \{1,\,2,\,3\}\ .\,\!}
I
M
(
a
0
0
)
=
0
.
{\displaystyle I_{\mathfrak {M}}(a_{0}^{0})\ =\ 0\ .\,\!}
I
M
(
b
0
0
)
=
1
.
{\displaystyle I_{\mathfrak {M}}(b_{0}^{0})\ =\ 1\ .\,\!}
I
M
(
f
0
2
)
=
f
0
2
such that:
f
0
2
(
0
,
0
)
=
2
,
f
0
2
(
0
,
1
)
=
1
,
f
0
2
(
0
,
2
)
=
0
,
{\displaystyle I_{\mathfrak {M}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that:}}\quad {\mathfrak {f}}_{0}^{2}(0,\,0)=2,\ {\mathfrak {f}}_{0}^{2}(0,\,1)\ =\ 1,\ {\mathfrak {f}}_{0}^{2}(0,\,2)=0,\,\!}
f
0
2
(
1
,
0
)
=
1
,
f
0
2
(
1
,
1
)
=
0
,
f
0
2
(
1
,
2
)
=
2
,
f
0
2
(
2
,
0
)
=
0
,
{\displaystyle {\mathfrak {f}}_{0}^{2}(1,\,0)=1,\ {\mathfrak {f}}_{0}^{2}(1,\,1)\ =\ 0,\ {\mathfrak {f}}_{0}^{2}(1,\,2)=2,\ {\mathfrak {f}}_{0}^{2}(2,\,0)=0,\,\!}
f
0
2
(
2
,
1
)
=
2
,
and
f
0
2
(
2
,
2
)
=
1
.
{\displaystyle {\mathfrak {f}}_{0}^{2}(2,\,1)=2,\ {\mbox{and}}\ {\mathfrak {f}}_{0}^{2}(2,\,2)=1\ .\,\!}
On the previous page , it was noted that we want the following result:
f
(
a
,
b
)
resolves to
1
i
n
M
.
{\displaystyle f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}\ .\,\!}
We now have achieved this because we have for any
s
{\displaystyle \mathrm {s} \,\!}
I
M
{\displaystyle I_{\mathfrak {M}}\,\!}
s
¯
(
f
(
a
,
b
)
)
=
I
M
(
f
)
(
s
¯
(
a
)
,
s
¯
(
b
)
)
=
f
0
2
(
s
¯
(
a
)
,
s
¯
(
b
)
)
{\displaystyle {\overline {\mathrm {s} }}(f(a,b))\ =\ I_{\mathfrak {M}}(f)\,(\ {\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(b)\ )\ =\ {\mathfrak {f}}_{0}^{2}(\ {\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(b)\ )\,\!}
=
f
0
2
(
I
M
(
a
)
,
I
M
(
b
)
)
=
f
0
2
(
0
,
1
)
=
1
.
{\displaystyle =\ {\mathfrak {f}}_{0}^{2}(\ I_{\mathfrak {M}}(a),\,I_{\mathfrak {M}}(b)\ )\ =\ {\mathfrak {f}}_{0}^{2}(0,\,1)\ =\ 1\ .\,\!}
Suppose we also have a variable assignment
s
{\displaystyle \mathrm {s} \,\!}
s
(
x
0
)
=
0
.
{\displaystyle \mathrm {s} (x_{0})\ =\ 0\ .\,\!}
s
(
y
0
)
=
1
.
{\displaystyle \mathrm {s} (y_{0})\ =\ 1\ .\,\!}
Then we get:
s
¯
(
f
(
x
,
y
)
)
=
I
M
(
f
)
(
s
¯
(
x
)
,
s
¯
(
y
)
)
=
f
0
2
(
s
¯
(
x
)
,
s
¯
(
y
)
)
{\displaystyle {\overline {\mathrm {s} }}(f(x,y))\ =\ I_{\mathfrak {M}}(f)\,(\ {\overline {\mathrm {s} }}(x),\,{\overline {\mathrm {s} }}(y)\ )\ =\ {\mathfrak {f}}_{0}^{2}(\ {\overline {\mathrm {s} }}(x),\,{\overline {\mathrm {s} }}(y)\ )\,\!}
=
f
0
2
(
f
)
(
s
(
x
)
,
s
(
y
)
)
=
f
0
2
(
0
,
1
)
=
1
.
{\displaystyle =\ {\mathfrak {f}}_{0}^{2}(f)\,(\ \mathrm {s} (x),\,\mathrm {s} (y)\ )\ =\ {\mathfrak {f}}_{0}^{2}(0,\,1)\ =\ 1\ .\,\!}
A model, together with a variable assignment, can satisfy (or fail to satisfy) a formula. Then we will use the notion of satisfaction with a variable assignment to define truth of a sentence in a model. We can use the following convenient notation to say that the interpretation
M
{\displaystyle {\mathfrak {M}}\,\!}
φ
{\displaystyle \varphi \,\!}
s
{\displaystyle \mathrm {s} \,\!}
⟨
M
,
s
⟩
⊨
φ
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \varphi \,\!}
⟨
M
,
s
⟩
⊭
φ
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \,\varphi \,\!}
We now define satisfaction of a formula by a model with a variable assignment . In the following, 'iff' is used to mean 'if and only if'.
i.
For
σ
a sentence letter:
{\displaystyle {\mbox{i.}}\quad {\mbox{For}}\ \sigma \ {\mbox{a sentence letter:}}\,\!}
⟨
M
,
s
⟩
⊨
σ
iff
I
M
(
σ
)
=
T
r
u
e
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \sigma \quad {\mbox{iff}}\quad I_{\mathfrak {M}}(\sigma )\ =\ \mathrm {True} \ .\,\!}
ii.
For
π
an
n
--place predicate letter and for
α
0
,
α
1
,
…
,
α
n
any terms:
{\displaystyle {\mbox{ii.}}\quad {\mbox{For}}\ \pi \ {\mbox{an}}\ n{\mbox{--place predicate letter and for}}\ \alpha _{0},\,\alpha _{1},\,\ldots ,\,\alpha _{n}\ {\mbox{any terms:}}\,\!}
⟨
M
,
s
⟩
⊨
π
(
α
0
,
α
1
,
…
,
α
n
)
iff
⟨
s
¯
(
α
0
)
,
s
¯
(
α
1
)
,
…
,
s
¯
(
α
n
)
⟩
∈
I
M
(
π
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \pi (\alpha _{0},\,\alpha _{1},\,\ldots ,\,\alpha _{n})\quad {\mbox{iff}}\ \langle {\overline {\mathrm {s} }}(\alpha _{0}),\,{\overline {\mathrm {s} }}(\alpha _{1}),\,\ldots ,\,{\overline {\mathrm {s} }}(\alpha _{n})\rangle \ \in \ I_{\mathfrak {M}}(\pi )\ .\,\!}
iii.
For
φ
a formula:
{\displaystyle {\mbox{iii.}}\quad {\mbox{For}}\ \varphi \ {\mbox{a formula:}}\,\!}
⟨
M
,
s
⟩
⊨
¬
φ
iff
⟨
M
,
s
⟩
⊭
φ
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \lnot \varphi \quad {\mbox{iff}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \varphi \ .\,\!}
iv.
For
φ
and
ψ
formulae:
{\displaystyle {\mbox{iv.}}\quad {\mbox{For}}\ \varphi \ {\mbox{and}}\ \psi \ {\mbox{formulae:}}\,\!}
⟨
M
,
s
⟩
⊨
(
φ
∧
ψ
)
iff
⟨
M
,
s
⟩
⊨
φ
and
⟨
M
,
s
⟩
⊨
ψ
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash (\varphi \land \psi )\quad {\mbox{iff}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \varphi \ \ {\mbox{and}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \psi \ .\,\!}
v.
For
φ
and
ψ
formulae:
{\displaystyle {\mbox{v.}}\quad {\mbox{For}}\ \varphi \ {\mbox{and}}\ \psi \ {\mbox{formulae:}}\,\!}
⟨
M
,
s
⟩
⊨
(
φ
∨
ψ
)
iff
⟨
M
,
s
⟩
⊨
φ
or
⟨
M
,
s
⟩
⊨
ψ
(or both)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash (\varphi \lor \psi )\quad {\mbox{iff}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \varphi \ \ {\mbox{or}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \psi \ {\mbox{(or both)}}\ .\,\!}
vi.
For
φ
and
ψ
formulae:
{\displaystyle {\mbox{vi.}}\quad {\mbox{For}}\ \varphi \ {\mbox{and}}\ \psi \ {\mbox{formulae:}}\,\!}
⟨
M
,
s
⟩
⊨
(
φ
→
ψ
)
iff
⟨
M
,
s
⟩
⊭
φ
or
⟨
M
,
s
⟩
⊨
ψ
(or both)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash (\varphi \rightarrow \psi )\quad {\mbox{iff}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \varphi \ \ {\mbox{or}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \psi \ {\mbox{(or both)}}\ .\,\!}
vii.
For
φ
and
ψ
formulae:
{\displaystyle {\mbox{vii.}}\quad {\mbox{For}}\ \varphi \ {\mbox{and}}\ \psi \ {\mbox{formulae:}}\,\!}
⟨
M
,
s
⟩
⊨
(
φ
↔
ψ
)
iff
⟨
M
,
s
⟩
⊨
(
φ
∧
ψ
)
or
⟨
M
,
s
⟩
⊨
(
¬
φ
∧
¬
ψ
)
(or both)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash (\varphi \leftrightarrow \psi )\quad {\mbox{iff}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash (\varphi \land \psi )\ \ {\mbox{or}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash (\lnot \varphi \land \lnot \psi )\ {\mbox{(or both)}}\ .\,\!}
viii.
For
φ
a formula and
α
a variable:
{\displaystyle {\mbox{viii.}}\quad {\mbox{For}}\ \varphi \ {\mbox{a formula and}}\ \alpha \ {\mbox{a variable:}}\,\!}
⟨
M
,
s
⟩
⊨
∀
α
φ
iff
for every
d
∈
|
M
|
,
⟨
M
,
s
[
α
:
d
]
⟩
⊨
φ
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \forall \alpha \,\varphi \quad {\mbox{iff}}\ \ {\mbox{for every}}\ \mathrm {d} \ \in |{\mathfrak {M}}|,\ \langle {\mathfrak {M}},\ \mathrm {s[\alpha \!:\,d]} \rangle \ \vDash \varphi \ .\,\!}
where
s
[
α
:
d
]
differs from
s
only in assigning
d
to
α
.
{\displaystyle {\mbox{where}}\ \mathrm {s[\alpha \!:\,d]} \ {\mbox{differs from}}\ \mathrm {s} \ {\mbox{only in assigning}}\ \mathrm {d} \ {\mbox{to}}\ \alpha \ .\,\!}
ix.
For
φ
a formula and
α
a variable:
{\displaystyle {\mbox{ix.}}\quad {\mbox{For}}\ \varphi \ {\mbox{a formula and}}\ \alpha \ {\mbox{a variable:}}\,\!}
⟨
M
,
s
⟩
⊨
∃
α
φ
iff
for at least one
d
∈
|
M
|
,
⟨
M
,
s
[
α
:
d
]
⟩
⊨
φ
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \exists \alpha \,\varphi \quad {\mbox{iff}}\ \ {\mbox{for at least one}}\ \mathrm {d} \in |{\mathfrak {M}}|,\ \langle {\mathfrak {M}},\ \mathrm {s[\alpha \!:\,d]} \rangle \ \vDash \varphi \ .\,\!}
where
s
[
α
:
d
]
differs from
s
only in assigning
d
to
α
.
{\displaystyle {\mbox{where}}\ \mathrm {s[\alpha \!:\,d]} \ {\mbox{differs from}}\ \mathrm {s} \ {\mbox{only in assigning}}\ \mathrm {d} \ {\mbox{to}}\ \alpha \ .\,\!}
The following continue the examples used when describing extended variable assignments above. They are based on the examples of the previous page .
A model and variable assignment for examples
edit
Suppose we have model
I
M
{\displaystyle I_{\mathfrak {M}}\,\!}
|
M
|
=
{
0
,
1
,
2
}
.
{\displaystyle |{\mathfrak {M}}|\ =\ \{0,\,1,\,2\}\ .\,\!}
I
M
(
a
0
0
)
=
0
.
{\displaystyle I_{\mathfrak {M}}(a_{0}^{0})\ =\ 0\ .\,\!}
I
M
(
b
0
0
)
=
1
.
{\displaystyle I_{\mathfrak {M}}(b_{0}^{0})\ =\ 1\ .\,\!}
I
M
(
c
0
0
)
=
2
.
{\displaystyle I_{\mathfrak {M}}(c_{0}^{0})\ =\ 2\ .\,\!}
I
M
(
f
0
2
)
=
f
0
2
such that:
f
0
2
(
0
,
0
)
=
2
,
f
0
2
(
0
,
1
)
=
1
,
f
0
2
(
0
,
2
)
=
0
,
{\displaystyle I_{\mathfrak {M}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that:}}\quad {\mathfrak {f}}_{0}^{2}(0,\,0)=2,\ {\mathfrak {f}}_{0}^{2}(0,\,1)\ =\ 1,\ {\mathfrak {f}}_{0}^{2}(0,\,2)=0,\,\!}
f
0
2
(
1
,
0
)
=
1
,
f
0
2
(
1
,
1
)
=
0
,
f
0
2
(
1
,
2
)
=
2
,
f
0
2
(
2
,
0
)
=
0
,
{\displaystyle {\mathfrak {f}}_{0}^{2}(1,\,0)=1,\ {\mathfrak {f}}_{0}^{2}(1,\,1)\ =\ 0,\ {\mathfrak {f}}_{0}^{2}(1,\,2)=2,\ {\mathfrak {f}}_{0}^{2}(2,\,0)=0,\,\!}
f
0
2
(
2
,
1
)
=
2
,
and
f
0
2
(
2
,
2
)
=
1
.
{\displaystyle {\mathfrak {f}}_{0}^{2}(2,\,1)=2,\ {\mbox{and}}\ {\mathfrak {f}}_{0}^{2}(2,\,2)=1\ .\,\!}
I
M
(
F
0
2
)
=
{
⟨
0
,
1
⟩
,
⟨
1
,
2
⟩
,
⟨
2
,
1
⟩
}
.
{\displaystyle I_{\mathfrak {M}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle 0,\ 1\rangle ,\ \langle 1,\ 2\rangle ,\ \langle 2,\ 1\rangle \}\ .\,\!}
Suppose further we have a variable assignment
s
{\displaystyle \mathrm {s} \,\!}
s
(
x
0
)
=
0
.
{\displaystyle \mathrm {s} (x_{0})\ =\ 0\ .\,\!}
s
(
y
0
)
=
1
.
{\displaystyle \mathrm {s} (y_{0})\ =\ 1\ .\,\!}
s
(
z
0
)
=
2
.
{\displaystyle \mathrm {s} (z_{0})\ =\ 2\ .\,\!}
f
(
a
,
b
)
{\displaystyle f(a,b)\,\!}
f
(
x
,
y
)
{\displaystyle f(x,y)\,\!}
Examples without quantifiers
edit
Given model
M
{\displaystyle {\mathfrak {M}}\,\!}
the previous page noted the following further goals:
(
1
)
F
(
a
,
b
)
,
F
(
b
,
c
)
,
and
F
(
c
,
b
)
are True in
M
.
{\displaystyle (1)\quad \mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ {\mbox{are True in}}\ {\mathfrak {M}}\ .\,\!}
(
2
)
F
(
a
,
a
)
is False in
M
.
{\displaystyle (2)\quad \mathrm {F} (a,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!}
(
3
)
F
(
a
,
f
(
a
,
b
)
)
is True in
M
.
{\displaystyle (3)\quad \mathrm {F} (a,f(a,b))\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!}
(
4
)
F
(
f
(
a
,
b
)
,
a
)
is False in
M
.
{\displaystyle (4)\quad \mathrm {F} (f(a,b),a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!}
(
5
)
F
(
c
,
b
)
→
F
(
a
,
b
)
is True in
M
.
{\displaystyle (5)\quad \mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!}
(
6
)
F
(
c
,
b
)
→
F
(
b
,
a
)
is False in
M
.
{\displaystyle (6)\quad \mathrm {F} (c,b)\rightarrow \mathrm {F} (b,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!}
We are not yet ready to evaluate for truth or falsity, but we can take a step in that direction by seeing that these sentences are satisfied by
M
{\displaystyle {\mathfrak {M}}\,\!}
s
.
{\displaystyle \mathrm {s} .\,\!}
s
{\displaystyle \mathrm {s} \,\!}
M
{\displaystyle {\mathfrak {M}}\,\!}
M
{\displaystyle {\mathfrak {M}}\,\!}
⟨
M
,
s
⟩
⊨
F
(
a
,
b
)
,
F
(
b
,
c
)
,
and
F
(
c
,
b
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ .\,\!}
In particular:
⟨
M
,
s
⟩
⊨
F
(
a
,
b
)
because
⟨
s
¯
(
a
)
,
s
¯
(
b
)
⟩
=
⟨
0
,
1
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (a,b)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(b)\rangle \ =\ \langle 0,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
b
,
c
)
because
⟨
s
¯
(
b
)
,
s
¯
(
c
)
⟩
=
⟨
1
,
2
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (b,c)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(b),\,{\overline {\mathrm {s} }}(c)\rangle \ =\ \langle 1,\,2\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
c
,
b
)
because
⟨
s
¯
(
c
)
,
s
¯
(
b
)
⟩
=
⟨
2
,
1
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (c,b)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(c),\,{\overline {\mathrm {s} }}(b)\rangle \ =\ \langle 2,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊭
F
(
a
,
a
)
)
because
⟨
s
¯
(
a
)
,
s
¯
(
a
)
⟩
=
⟨
0
,
0
⟩
∉
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (a,a))\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(a)\rangle \ =\ \langle 0,\,0\rangle \ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
a
,
f
(
a
,
b
)
)
because
⟨
s
¯
(
a
)
,
s
¯
(
f
(
a
,
b
)
)
⟩
=
⟨
0
,
1
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (a,f(a,b))\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(f(a,b))\rangle \ =\ \langle 0,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊭
F
(
f
(
a
,
b
)
,
a
)
because
⟨
s
¯
(
f
(
a
,
b
)
,
s
¯
(
a
)
⟩
=
⟨
1
,
0
⟩
∉
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (f(a,b),a)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(f(a,b),\,{\overline {\mathrm {s} }}(a)\rangle \ =\ \langle 1,\,0\rangle \ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
c
,
b
)
→
F
(
a
,
b
)
because
⟨
M
,
s
⟩
⊨
F
(
a
,
b
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ \ {\mbox{because}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (a,b)\ .\,\!}
⟨
M
,
s
⟩
⊭
F
(
c
,
b
)
→
F
(
b
,
a
)
because
⟨
M
,
s
⟩
⊨
F
(
c
,
b
)
but
⟨
M
,
s
⟩
⊭
F
(
b
,
a
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (c,b)\rightarrow \mathrm {F} (b,a)\ \ {\mbox{because}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (c,b)\ {\mbox{but}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (b,a)\ .\,\!}
s
{\displaystyle \mathrm {s} \,\!}
s
{\displaystyle \mathrm {s} \,\!}
⟨
M
,
s
⟩
⊨
F
(
x
,
y
)
because
⟨
s
¯
(
x
)
,
s
¯
(
y
)
⟩
=
⟨
0
,
1
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (x,y)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(x),\,{\overline {\mathrm {s} }}(y)\rangle \ =\ \langle 0,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
y
,
z
)
because
⟨
s
¯
(
y
)
,
s
¯
(
z
)
⟩
=
⟨
1
,
2
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (y,z)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(y),\,{\overline {\mathrm {s} }}(z)\rangle \ =\ \langle 1,\,2\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
z
,
y
)
because
⟨
s
¯
(
z
)
,
s
¯
(
y
)
⟩
=
⟨
2
,
1
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (z,y)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(z),\,{\overline {\mathrm {s} }}(y)\rangle \ =\ \langle 2,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊭
F
(
x
,
x
)
)
because
⟨
s
¯
(
x
)
,
s
¯
(
x
)
⟩
=
⟨
0
,
0
⟩
∉
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (x,x))\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(x),\,{\overline {\mathrm {s} }}(x)\rangle \ =\ \langle 0,\,0\rangle \ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
x
,
f
(
x
,
y
)
)
because
⟨
s
¯
(
x
)
,
s
¯
(
f
(
x
,
y
)
)
⟩
=
⟨
0
,
1
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (x,f(x,y))\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(x),\,{\overline {\mathrm {s} }}(f(x,y))\rangle \ =\ \langle 0,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊭
F
(
f
(
x
,
y
)
,
x
)
because
⟨
s
¯
(
f
(
x
,
y
)
,
s
¯
(
x
)
⟩
=
⟨
1
,
0
⟩
∉
I
M
(
F
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (f(x,y),x)\ \ {\mbox{because}}\ \langle {\overline {\mathrm {s} }}(f(x,y),\,{\overline {\mathrm {s} }}(x)\rangle \ =\ \langle 1,\,0\rangle \ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
⟨
M
,
s
⟩
⊨
F
(
z
,
y
)
→
F
(
x
,
y
)
because
⟨
M
,
s
⟩
⊨
F
(
x
,
y
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (z,y)\rightarrow \mathrm {F} (x,y)\ \ {\mbox{because}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (x,y)\ .\,\!}
⟨
M
,
s
⟩
⊭
F
(
z
,
y
)
→
F
(
y
,
x
)
because
⟨
M
,
s
⟩
⊨
F
(
z
,
y
)
but
⟨
M
,
s
⟩
⊭
F
(
y
,
x
)
.
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (z,y)\rightarrow \mathrm {F} (y,x)\ \ {\mbox{because}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \mathrm {F} (z,y)\ {\mbox{but}}\ \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \mathrm {F} (y,x)\ .\,\!}
Examples with quantifiers
edit
Given model
M
{\displaystyle {\mathfrak {M}}\,\!}
the previous page also noted the following further goals:
(
7
)
∀
x
∀
y
(
F
(
x
,
y
)
→
F
(
y
,
x
)
)
is false in
M
.
{\displaystyle (7)\quad \forall x\,\forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\ {\mbox{is false in }}\ {\mathfrak {M}}\ .\,\!}
(
8
)
∃
x
∃
y
(
F
(
x
,
y
)
∧
F
(
y
,
x
)
)
is true in
M
.
{\displaystyle (8)\quad \exists x\,\exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\ {\mbox{is true in}}\ {\mathfrak {M}}\ .\,\!}
Again, we are not yet ready to evaluate for truth or falsity, but again we can take a step in that direction by seeing that the sentence in (7) is and the sentence in (8) is not satisfied by
M
{\displaystyle {\mathfrak {M}}\,\!}
s
.
{\displaystyle \mathrm {s} .\,\!}
(
9
)
⟨
M
,
s
⟩
⊭
∀
x
∀
y
(
F
(
x
,
y
)
→
F
(
y
,
x
)
)
{\displaystyle (9)\quad \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \not \vDash \forall x\,\forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!}
is true if and only if at least one of the following is true:
(
10
)
⟨
M
,
s
[
x
:
0
]
⟩
⊭
∀
y
(
F
(
x
,
y
)
→
F
(
y
,
x
)
)
{\displaystyle (10)\quad \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0]\rangle \ \not \vDash \forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!}
(
11
)
⟨
M
,
s
[
x
:
1
]
⟩
⊭
∀
y
(
F
(
x
,
y
)
→
F
(
y
,
x
)
)
{\displaystyle (11)\quad \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1]\rangle \ \not \vDash \forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!}
(
12
)
⟨
M
,
s
[
x
:
2
]
⟩
⊭
∀
y
(
F
(
x
,
y
)
→
F
(
y
,
x
)
)
{\displaystyle (12)\quad \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,2]\rangle \ \not \vDash \forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!}
The formula of (7) and (9) is satisfied by
⟨
M
,
s
⟩
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \,\!}
M
{\displaystyle {\mathfrak {M}}\,\!}
⟨
M
,
s
⟩
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \,\!}
⟨
M
,
s
[
x
:
0
,
y
:
0
]
⟩
⊭
F
(
x
,
y
)
→
F
(
y
,
x
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0,\ y\!:\,0]\rangle \ \not \vDash \mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x)\,\!}
⟨
M
,
s
[
x
:
0
,
y
:
1
]
⟩
⊭
F
(
x
,
y
)
→
F
(
y
,
x
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0,\ y\!:\,1]\rangle \ \not \vDash \mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x)\,\!}
⟨
M
,
s
[
x
:
0
,
y
:
2
]
⟩
⊭
F
(
x
,
y
)
→
F
(
y
,
x
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0,\ y\!:\,2]\rangle \ \not \vDash \mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x)\,\!}
Indeed, the middle one of these is true. This is because
⟨
0
,
1
⟩
∈
I
M
(
F
)
but
⟨
1
,
0
⟩
∉
I
M
(
F
)
.
{\displaystyle \langle 0,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ {\mbox{but}}\,\langle 1,\,0\rangle \ \not \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
Thus (9) is true.
(
13
)
⟨
M
,
s
⟩
⊨
∃
x
∃
y
(
F
(
x
,
y
)
∧
F
(
y
,
x
)
)
{\displaystyle (13)\quad \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \exists x\,\exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!}
is true if and only if at least one of the following is true:
⟨
M
,
s
[
x
:
0
]
⟩
⊨
∃
y
(
F
(
x
,
y
)
∧
F
(
y
,
x
)
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0]\rangle \ \vDash \exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!}
⟨
M
,
s
[
x
:
1
]
⟩
⊨
∃
y
(
F
(
x
,
y
)
∧
F
(
y
,
x
)
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1]\rangle \ \vDash \exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!}
⟨
M
,
s
[
x
:
2
]
⟩
⊨
∃
y
(
F
(
x
,
y
)
∧
F
(
y
,
x
)
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,2]\rangle \ \vDash \exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!}
The middle of these is true if and only if at least one of the following are true:
⟨
M
,
s
[
x
:
1
,
y
:
0
]
⟩
⊨
F
(
x
,
y
)
∧
F
(
y
,
x
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1,\ y\!:\,0]\rangle \ \vDash \mathrm {F} (x,y)\land \mathrm {F} (y,x)\,\!}
⟨
M
,
s
[
x
:
1
,
y
:
1
]
⟩
⊨
F
(
x
,
y
)
∧
F
(
y
,
x
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1,\ y\!:\,1]\rangle \ \vDash \mathrm {F} (x,y)\land \mathrm {F} (y,x)\,\!}
⟨
M
,
s
[
x
:
1
,
y
:
2
]
⟩
⊨
F
(
x
,
y
)
∧
F
(
y
,
x
)
{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1,\ y\!:\,2]\rangle \ \vDash \mathrm {F} (x,y)\land \mathrm {F} (y,x)\,\!}
Indeed, the last of these is true. This is because:
⟨
1
,
2
⟩
∈
I
M
(
F
)
and
⟨
2
,
1
⟩
∈
I
M
(
F
)
.
{\displaystyle \langle 1,\,2\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ {\mbox{and}}\,\langle 2,\,1\rangle \ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!}
Thus (13) is true.
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \forall \alpha \,\varphi \quad {\mbox{iff}}\ \ {\mbox{for every}}\ \mathrm {d} \ \in |{\mathfrak {M}}|,\ \langle {\mathfrak {M}},\ \mathrm {s[\alpha \!:\,d]} \rangle \ \vDash \varphi \ .\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7c631086d8f9f7cbec2219483df94a0bfd1ae69)
![{\displaystyle {\mbox{where}}\ \mathrm {s[\alpha \!:\,d]} \ {\mbox{differs from}}\ \mathrm {s} \ {\mbox{only in assigning}}\ \mathrm {d} \ {\mbox{to}}\ \alpha \ .\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/278c5e13beb24fdd1720e8b84b76c91d536f1f9a)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} \rangle \ \vDash \exists \alpha \,\varphi \quad {\mbox{iff}}\ \ {\mbox{for at least one}}\ \mathrm {d} \in |{\mathfrak {M}}|,\ \langle {\mathfrak {M}},\ \mathrm {s[\alpha \!:\,d]} \rangle \ \vDash \varphi \ .\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28adc8a563598602446e758b3dd8178a1f6ddda8)
![{\displaystyle (10)\quad \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0]\rangle \ \not \vDash \forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/248790c7c4850042ed0d3adb40f3df5f674beee6)
![{\displaystyle (11)\quad \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1]\rangle \ \not \vDash \forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78bef17e267c5461e9856197d59be3015aa467ea)
![{\displaystyle (12)\quad \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,2]\rangle \ \not \vDash \forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f1148d28e89d73cc5236b60e83e0d0e732bc911)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0,\ y\!:\,0]\rangle \ \not \vDash \mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f55e18b1a792cf431ebd038d24296711e6ac0952)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0,\ y\!:\,1]\rangle \ \not \vDash \mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df7ad3f9d46f3f1b942d0c14a61bcff4adf517b8)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0,\ y\!:\,2]\rangle \ \not \vDash \mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb8b6ee8001f5cf1b08f912b78e9e75022cdc61d)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,0]\rangle \ \vDash \exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33a6b8e1209d24aea00d5d54f5371da896c4ed47)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1]\rangle \ \vDash \exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8f97201239b90a398d7eab7e51c0a444efc3cb1)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,2]\rangle \ \vDash \exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34b4256bdc13fc42a5e5d1c3131a41704e4c816b)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1,\ y\!:\,0]\rangle \ \vDash \mathrm {F} (x,y)\land \mathrm {F} (y,x)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71c9eca8553a860f592cd8781a40119e1281e83c)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1,\ y\!:\,1]\rangle \ \vDash \mathrm {F} (x,y)\land \mathrm {F} (y,x)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32b6b5c86f378fe24d53965bb8b46e189779fcb3)
![{\displaystyle \langle {\mathfrak {M}},\ \mathrm {s} [x\!:\,1,\ y\!:\,2]\rangle \ \vDash \mathrm {F} (x,y)\land \mathrm {F} (y,x)\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82ee4fd3652bf7712775ca65075f3fb82157b0fb)
