Definition 4 (Semantics of predicate logic - Interpretation)
[edit | edit source]
An interpretation is a pair
, where
is an arbitrary nonempty set, called domain, or universe.
is a mapping which associates to
- a
-ary predicate symbol, a
-ary predicate over
,
- a
-ary function symbol, a
-ary function over
, and
- a variable an element from the domain.
Let
be a formula and
be an
interpretation. We call
an interpretation for
, if
is defined for every predicate and function symbol, and for
every variable, that occurs free in
.
Example: Let
and
assume the varieties of the symbols as written down. In the following
we give two interpretations for
:
, such that
![{\displaystyle A_{1}(p)=\{(m,n)\mid m,n\in N_{0}{\text{ and }}m<n\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89b6a7074dff024e36404192ff7709061be46a84)
![{\displaystyle A_{1}(q)=\{n\in N_{0}\mid n{\text{ is prime}}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63a244b70af92764288f083031892bc01c39e521)
![{\displaystyle A_{1}(f)(n)=n+1\;\forall n\in N_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b997db1e0ee03f4476b2b881be841effa066bcd9)
![{\displaystyle A_{1}(g)(m,n)=m+n\;\forall n,m\in N_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a73c6d93b553184fe287aa05314702856fdb44a0)
![{\displaystyle A_{1}(a)=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04bba9d62d8f3271c6c61279ac79a3be0f9bc8aa)
![{\displaystyle A_{1}(z)=3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85ccfed7d8c0e39317e6695b561445e310066a18)
- Under this interpretation the formula
can be read as " Every natural number is smaller than its successor and the sum of
and
is a prime number."
, such that
![{\displaystyle U_{2}=\{a,f(a),g(a,a),f(g(a,a)),g(f(a),f(a)),\cdots \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea43096adff1b6438c61dad3b6538f4af1e5714e)
for ![{\displaystyle t\in U_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6005e592138284fcfcc207face573ee88287c756)
, if ![{\displaystyle t_{1},t_{2}\in U_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b6315f912b87277a0ac39ac34d77fafc5a9bb65)
![{\displaystyle A_{2}(a)=a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95133ad1d5e8917be553e6c505297d02946f4c09)
![{\displaystyle A_{2}(z)=f(f(a))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ca7abde91a932027e092b942340655d2b1310ec)
![{\displaystyle A_{2}(p)=\{p(a,a),p(f(a),f(a)),p(f(f(a)),f(f(a)))\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0402ffe577b4e4c5ca6ccb9ae68c4a66de78d9ca)
![{\displaystyle A_{2}(q)=\{g(t_{1},t_{2})\mid t_{1},t_{2}\in U_{2}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf1b22bbf65c8d5773ee9855b18260d3c2751340)
For a given interpretation
we write in the following
instead of
; the same abbreviation will be used for
the assignments for function symbols and variables.
Let
be a formula and
an interpretation for
. For terms
which can be composed with symbols from
the value
is given
by
![{\displaystyle {\mathcal {I}}(x)=x^{\mathcal {I}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba2f97dcb1002a334eba85208809f4e94f071ba)
, if
are terms and
a
-ary function symbol. (This holds for the case
as well.)
The value
of a formula
is given by
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7944c4db0559a491fbaa7020f503aa70218c6dcc)
![{\displaystyle {\mathcal {I}}(F\land G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{and}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f89dc73d45c389818c09e3a682c7f892d66153dd)
![{\displaystyle {\mathcal {I}}((F\lor G))={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=true{or}{\mathcal {I}}(G)=true\\\;\;\,false&otherwise\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7107d021a776dcca177e39eb95885c880b195627)
![{\displaystyle {\mathcal {I}}(\lnot F)={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {I}}(F)=false\\\;\;\,false&otherwise\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/629b14c42b1507fbdf249ecd06a402e926e53f6c)
![{\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)
where,
The notions of satisfiable, valid, and
are defined
according to the propositional case (Semantic (Propositional logic)).
Note that, predicate calculus is an extension of propositional
calculus: Assume only
-ary predicate symbols and a formula which
contains no variable, i.e. there can be no terms and no quantifier in
a well-formed formula.
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.
Another example for a second order formula of is the induction principle from Induction.
The interpretation
as follows:
![{\displaystyle U_{\mathcal {I}}=\mathbb {N} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/599c091717a0dfc8626f29ba70dfda24e5f15529)
![{\displaystyle p^{\mathcal {I}}={(m,n)\mid m<n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab38562553f3ded02a972e74ba3fcb85acf3e2ec)
![{\displaystyle f^{\mathcal {I}}(m,n)=m+n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2d0d466ee003dd2a69f8656523f23b8839ea1ae)
Determine the value of following terms and formulae:
![{\displaystyle {\mathcal {I}}(f(f(x,x),y))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4775ffb0d7a50e76a7fba3ebdf4a07dab60d9ef)
![{\displaystyle {\mathcal {I}}(\forall x\forall y(p(x,y)\lor p(y,x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37d77d814d0a9652f9394e6681c269822bcaa197)
![{\displaystyle {\mathcal {I}}(p(x,x)\to p(y,x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcd51a244630dc262fa3c10483d8edc70ef7e5a1)
![{\displaystyle {\mathcal {I}}(\exists xp(y,x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c0fa973740be1a2f7a3c212406689112f73c7e0)
The interpretation
as follows:
![{\displaystyle U_{\mathcal {I}}=\mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6bc9aa7a4e40a9704c156b99c3812755612e4ba)
![{\displaystyle P^{\mathcal {I}}={z\mid z\geq 0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0b93ee93dfe790a9939bdcdfdedb458e0daa678)
![{\displaystyle f^{\mathcal {I}}(z)=z^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ead08da2016b07e1010ea6fdb0dd0c3fd9a2ead)
![{\displaystyle x^{\mathcal {I}}={\sqrt {2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01981e1ed6b478972d71ed11f4abc9ced196e639)
![{\displaystyle E^{\mathcal {I}}={(x,y)\mid x=y}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3734a2e6ec7991316d8cf5162e23e6afda0dbee)
![{\displaystyle g^{\mathcal {I}}(x,y)=x+y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dd14f7eabf3029f52bea267c0395a7d0aac282a)
Determine the value of following terms and formulae:
![{\displaystyle 3.{\mathcal {I}}(\exists z\forall x\forall y\,E(g(x,y),z))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34a6c82127cdd60afa2e7ba6df6ee2b9ac203a19)
The following formula is given:
Indicate a structure
, which is a model for
and
a structure
which is no model for
!