edit
An interpretation is a pair
I
=
(
U
I
,
A
I
)
{\displaystyle {\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})}
U
I
{\displaystyle U_{\mathcal {I}}}
A
I
{\displaystyle A_{\mathcal {I}}}
a
k
{\displaystyle k}
k
{\displaystyle k}
U
I
{\displaystyle U_{\mathcal {I}}}
a
k
{\displaystyle k}
k
{\displaystyle k}
U
I
{\displaystyle U_{\mathcal {I}}}
a variable an element from the domain. Let
F
{\displaystyle F}
I
=
(
U
I
,
A
I
)
{\displaystyle {\mathcal {I}}=(U_{\mathcal {I}},A_{\mathcal {I}})}
I
{\displaystyle {\mathcal {I}}}
F
{\displaystyle F}
A
I
{\displaystyle {\mathcal {A}}_{\mathcal {I}}}
F
{\displaystyle F}
F
=
∀
x
p
(
x
,
f
(
x
)
)
∧
q
(
g
(
a
,
z
)
)
{\displaystyle F=\forall xp(x,f(x))\land q(g(a,z))}
F
{\displaystyle F}
I
1
=
(
N
0
,
A
1
)
{\displaystyle {\mathcal {I}}_{1}=(N_{0},A_{1})}
A
1
(
p
)
=
{
(
m
,
n
)
∣
m
,
n
∈
N
0
and
m
<
n
}
{\displaystyle A_{1}(p)=\{(m,n)\mid m,n\in N_{0}{\text{ and }}m<n\}}
A
1
(
q
)
=
{
n
∈
N
0
∣
n
is prime
}
{\displaystyle A_{1}(q)=\{n\in N_{0}\mid n{\text{ is prime}}\}}
A
1
(
f
)
(
n
)
=
n
+
1
∀
n
∈
N
0
{\displaystyle A_{1}(f)(n)=n+1\;\forall n\in N_{0}}
A
1
(
g
)
(
m
,
n
)
=
m
+
n
∀
n
,
m
∈
N
0
{\displaystyle A_{1}(g)(m,n)=m+n\;\forall n,m\in N_{0}}
A
1
(
a
)
=
2
{\displaystyle A_{1}(a)=2}
A
1
(
z
)
=
3
{\displaystyle A_{1}(z)=3}
Under this interpretation the formula
F
{\displaystyle F}
2
{\displaystyle 2}
3
{\displaystyle 3}
I
2
=
(
U
2
,
A
2
)
{\displaystyle {\mathcal {I}}_{2}=(U_{2},A_{2})}
U
2
=
{
a
,
f
(
a
)
,
g
(
a
,
a
)
,
f
(
g
(
a
,
a
)
)
,
g
(
f
(
a
)
,
f
(
a
)
)
,
⋯
}
{\displaystyle U_{2}=\{a,f(a),g(a,a),f(g(a,a)),g(f(a),f(a)),\cdots \}}
A
2
(
f
)
(
t
)
=
f
(
t
)
{\displaystyle A_{2}(f)(t)=f(t)}
t
∈
U
2
{\displaystyle t\in U_{2}}
A
2
(
g
)
(
t
1
,
t
2
)
=
g
(
t
1
,
t
2
)
{\displaystyle A_{2}(g)(t_{1},t_{2})=g(t_{1},t_{2})}
t
1
,
t
2
∈
U
2
{\displaystyle t_{1},t_{2}\in U_{2}}
A
2
(
a
)
=
a
{\displaystyle A_{2}(a)=a}
A
2
(
z
)
=
f
(
f
(
a
)
)
{\displaystyle A_{2}(z)=f(f(a))}
A
2
(
p
)
=
{
p
(
a
,
a
)
,
p
(
f
(
a
)
,
f
(
a
)
)
,
p
(
f
(
f
(
a
)
)
,
f
(
f
(
a
)
)
)
}
{\displaystyle A_{2}(p)=\{p(a,a),p(f(a),f(a)),p(f(f(a)),f(f(a)))\}}
A
2
(
q
)
=
{
g
(
t
1
,
t
2
)
∣
t
1
,
t
2
∈
U
2
}
{\displaystyle A_{2}(q)=\{g(t_{1},t_{2})\mid t_{1},t_{2}\in U_{2}\}}
I
=
(
U
,
A
)
{\displaystyle {\mathcal {I}}=(U,A)}
p
I
{\displaystyle p^{\mathcal {I}}}
A
(
p
)
{\displaystyle A(p)}
Let
F
{\displaystyle F}
I
{\displaystyle {\mathcal {I}}}
F
{\displaystyle F}
t
{\displaystyle t}
F
{\displaystyle F}
I
(
t
)
{\displaystyle {\mathcal {I}}(t)}
I
(
x
)
=
x
I
{\displaystyle {\mathcal {I}}(x)=x^{\mathcal {I}}}
I
(
f
(
t
1
,
⋯
,
t
k
)
)
=
f
I
(
I
(
t
1
)
,
⋯
,
I
(
t
k
)
)
{\displaystyle {\mathcal {I}}(f(t_{1},\cdots ,t_{k}))=f^{\mathcal {I}}({\mathcal {I}}(t_{1}),\cdots ,{\mathcal {I}}(t_{k}))}
t
1
,
⋯
,
t
k
{\displaystyle t_{1},\cdots ,t_{k}}
f
{\displaystyle f}
k
{\displaystyle k}
k
=
0
{\displaystyle k=0}
The value
I
(
F
)
{\displaystyle {\mathcal {I}}(F)}
F
{\displaystyle F}
I
(
p
(
t
1
,
⋯
,
t
k
)
)
=
{
t
r
u
e
if
(
I
(
t
1
)
,
⋯
,
I
(
t
k
)
)
∈
p
I
f
a
l
s
e
o
t
h
e
r
w
i
s
e
{\displaystyle {\mathcal {I}}(p(t_{1},\cdots ,t_{k}))={\begin{cases}\;\;\,true&{\text{ if }}({\mathcal {I}}(t_{1}),\cdots ,{\mathcal {I}}(t_{k}))\in p^{\mathcal {I}}\\\;\;\,false&\;otherwise\end{cases}}}
I
(
F
∧
G
)
)
=
{
t
r
u
e
if
I
(
F
)
=
t
r
u
e
a
n
d
I
(
G
)
=
t
r
u
e
f
a
l
s
e
o
t
h
e
r
w
i
s
e
{\displaystyle {\mathcal {I}}(F\land G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{and}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}}
I
(
(
F
∨
G
)
)
=
{
t
r
u
e
if
I
(
F
)
=
t
r
u
e
o
r
I
(
G
)
=
t
r
u
e
f
a
l
s
e
o
t
h
e
r
w
i
s
e
{\displaystyle {\mathcal {I}}((F\lor G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{or}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}}
I
(
¬
F
)
=
{
t
r
u
e
if
I
(
F
)
=
f
a
l
s
e
f
a
l
s
e
o
t
h
e
r
w
i
s
e
{\displaystyle {\mathcal {I}}(\lnot F)={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=false\\\;\;\,false&otherwise\end{cases}}}
I
(
∀
G
)
=
{
t
r
u
e
if for every
d
∈
U
:
I
[
x
/
d
]
(
G
)
=
t
r
u
e
f
a
l
s
e
o
t
h
e
r
w
i
s
e
{\displaystyle {\mathcal {I}}(\forall G)={\begin{cases}\;\;\,true&{\text{ if for every }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}}
I
(
∃
G
)
=
{
t
r
u
e
if there is a
d
∈
U
:
I
[
x
/
d
]
(
G
)
=
t
r
u
e
f
a
l
s
e
o
t
h
e
r
w
i
s
e
{\displaystyle {\mathcal {I}}(\exists G)={\begin{cases}\;\;\,true&{\text{ if there is a }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}}
where,
f
[
x
/
d
]
(
y
)
=
{
f
(
y
)
if
x
≠
y
d
o
t
h
e
r
w
i
s
e
{\displaystyle f_{[x/d]}(y)={\begin{cases}\;\;\,f(y)&{\text{ if }}x\neq y\\\;\;\,d&otherwise\end{cases}}}
⊨
{\displaystyle \models }
Semantic (Propositional logic) ).
0
{\displaystyle 0}
On the other hand, predicate calculus can be extended: If one allows
for quantifications over predicate and function symbols, we arrive at
a second order predicate calculus. E.g.
∀
p
∃
f
p
(
f
(
x
)
)
{\displaystyle \forall p\exists f\;p(f(x))}
Another example for a second order formula of is the induction principle from Induction .
edit
The interpretation
I
=
is given
(
U
I
,
A
I
)
{\displaystyle {\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})}
U
I
=
N
{\displaystyle U_{\mathcal {I}}=\mathbb {N} }
p
I
=
(
m
,
n
)
∣
m
<
n
{\displaystyle p^{\mathcal {I}}={(m,n)\mid m<n}}
f
I
(
m
,
n
)
=
m
+
n
{\displaystyle f^{\mathcal {I}}(m,n)=m+n}
x
I
=
5
;
y
I
=
7
{\displaystyle x^{\mathcal {I}}=5;y^{\mathcal {I}}=7}
Determine the value of following terms and formulae:
I
(
f
(
f
(
x
,
x
)
,
y
)
)
{\displaystyle {\mathcal {I}}(f(f(x,x),y))}
I
(
∀
x
∀
y
(
p
(
x
,
y
)
∨
p
(
y
,
x
)
)
{\displaystyle {\mathcal {I}}(\forall x\forall y(p(x,y)\lor p(y,x))}
I
(
p
(
x
,
x
)
→
p
(
y
,
x
)
)
{\displaystyle {\mathcal {I}}(p(x,x)\to p(y,x))}
I
(
∃
x
p
(
y
,
x
)
)
{\displaystyle {\mathcal {I}}(\exists xp(y,x))}
◻
{\displaystyle \Box }
edit
The interpretation
I
=
is given
(
U
I
,
A
I
)
{\displaystyle {\mathcal {I}}={\text{ is given }}(U_{\mathcal {I}},A_{\mathcal {I}})}
U
I
=
R
{\displaystyle U_{\mathcal {I}}=\mathbb {R} }
P
I
=
z
∣
z
≥
0
{\displaystyle P^{\mathcal {I}}={z\mid z\geq 0}}
f
I
(
z
)
=
z
2
{\displaystyle f^{\mathcal {I}}(z)=z^{2}}
x
I
=
2
{\displaystyle x^{\mathcal {I}}={\sqrt {2}}}
E
I
=
(
x
,
y
)
∣
x
=
y
{\displaystyle E^{\mathcal {I}}={(x,y)\mid x=y}}
g
I
(
x
,
y
)
=
x
+
y
{\displaystyle g^{\mathcal {I}}(x,y)=x+y}
y
I
=
−
1
{\displaystyle y^{\mathcal {I}}=-1}
Determine the value of following terms and formulae:
1.
I
(
g
(
f
(
x
)
,
f
(
y
)
)
)
{\displaystyle 1.{\mathcal {I}}(g(f(x),f(y)))}
2.
I
(
∀
x
P
(
f
(
x
)
)
)
{\displaystyle 2.{\mathcal {I}}(\forall x\,P(f(x)))}
3.
I
(
∃
z
∀
x
∀
y
E
(
g
(
x
,
y
)
,
z
)
)
{\displaystyle 3.{\mathcal {I}}(\exists z\forall x\forall y\,E(g(x,y),z))}
4.
I
(
∀
y
(
E
(
f
(
x
)
,
y
)
→
P
(
g
(
x
,
y
)
)
)
)
{\displaystyle 4.{\mathcal {I}}(\forall y(E(f(x),y)\to P(g(x,y))))}
◻
{\displaystyle \Box }
edit
The following formula is given:
F
=
∀
x
∀
y
∀
z
R
(
h
(
h
(
x
,
y
)
,
z
)
,
h
(
x
,
h
(
y
,
z
)
)
)
∧
∃
x
∃
y
¬
R
(
h
(
x
,
y
)
,
h
(
y
,
x
)
)
{\displaystyle F=\forall x\forall y\forall z\,R(h(h(x,y),z),h(x,h(y,z)))\ \land \ \exists x\exists y\,\lnot R(h(x,y),h(y,x))}
Indicate a structure
A
{\displaystyle {\mathcal {A}}}
F
{\displaystyle F}
B
{\displaystyle {\mathcal {B}}}
F
{\displaystyle F}
◻
{\displaystyle \Box }
![{\displaystyle {\mathcal {I}}(\forall G)={\begin{cases}\;\;\,true&{\text{ if for every }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7143ffe1cafd82e1c854b1b96079c4271350ad4f)
![{\displaystyle {\mathcal {I}}(\exists G)={\begin{cases}\;\;\,true&{\text{ if there is a }}d\in U\;:\;{\mathcal {I}}_{[x/d]}(G)=true\\\;\;\,false&otherwise\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f253d7bb347db47c82e3139b4f9f486f8bc304f)
![{\displaystyle f_{[x/d]}(y)={\begin{cases}\;\;\,f(y)&{\text{ if }}x\neq y\\\;\;\,d&otherwise\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9612887a7589a537816cfc1c48fcfad3da9f6824)
