Skip to main content
added 77 characters in body
Source Link
chi
  • 14.7k
  • 1
  • 31
  • 40

Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be $$ {\sf eats}({\sf cat}, {\sf head}({\sf tuna})) $$ Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows: $$ \mbox{World $w$: }\qquad\qquad \begin{array}{l} [\![ {\sf cat} ]\!]^c = 5 \\ [\![ {\sf tuna} ]\!]^c = 4 \\ [\![ {\sf squirrel} ]\!]^c = 2 \\ \ldots \\ [\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\ \ldots \\ [\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \} \end{array} $$ (A structure can define more symbols than those used in the formula, hence the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$. Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$. Predicate symbols are interpreted as subsets of $D$$D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $[\![-]\!]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have $$ [\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c)) $$ which is $$ < (5, g(4)) $$ i.e. $$ 5 < \pi \cdot 4 $$ which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.

Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be $$ {\sf eats}({\sf cat}, {\sf head}({\sf tuna})) $$ Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows: $$ \mbox{World $w$: }\qquad\qquad \begin{array}{l} [\![ {\sf cat} ]\!]^c = 5 \\ [\![ {\sf tuna} ]\!]^c = 4 \\ [\![ {\sf squirrel} ]\!]^c = 2 \\ \ldots \\ [\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\ \ldots \\ [\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \} \end{array} $$ (A structure can define more symbols than those used in the formula, hence the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$. Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$. Predicate symbols are interpreted as subsets of $D$ by the interpretation $[\![-]\!]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have $$ [\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c)) $$ which is $$ < (5, g(4)) $$ i.e. $$ 5 < \pi \cdot 4 $$ which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.

Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be $$ {\sf eats}({\sf cat}, {\sf head}({\sf tuna})) $$ Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows: $$ \mbox{World $w$: }\qquad\qquad \begin{array}{l} [\![ {\sf cat} ]\!]^c = 5 \\ [\![ {\sf tuna} ]\!]^c = 4 \\ [\![ {\sf squirrel} ]\!]^c = 2 \\ \ldots \\ [\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\ \ldots \\ [\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \} \end{array} $$ (A structure can define more symbols than those used in the formula, hence the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$. Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$. Predicate symbols are interpreted as subsets of $D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $[\![-]\!]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have $$ [\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c)) $$ which is $$ < (5, g(4)) $$ i.e. $$ 5 < \pi \cdot 4 $$ which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.

Source Link
chi
  • 14.7k
  • 1
  • 31
  • 40

Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be $$ {\sf eats}({\sf cat}, {\sf head}({\sf tuna})) $$ Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows: $$ \mbox{World $w$: }\qquad\qquad \begin{array}{l} [\![ {\sf cat} ]\!]^c = 5 \\ [\![ {\sf tuna} ]\!]^c = 4 \\ [\![ {\sf squirrel} ]\!]^c = 2 \\ \ldots \\ [\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\ \ldots \\ [\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \} \end{array} $$ (A structure can define more symbols than those used in the formula, hence the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$. Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$. Predicate symbols are interpreted as subsets of $D$ by the interpretation $[\![-]\!]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have $$ [\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c)) $$ which is $$ < (5, g(4)) $$ i.e. $$ 5 < \pi \cdot 4 $$ which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.