1
$\begingroup$

Exact problem in words:

Let $M$ be an interpretation, and let $M′$ be an extension of $M$. Prove that, for any sentence $A$, if $M$$\models$$A$, then M′ $\models$ $A$.

I'm having trouble here because can't the extension of M' be true while M is false?

For example, taking the sentence $A$: $\exists$$x$(P($x$) $\cap$ R($a$))

So, I make an interpretation $M$ for $A$ where:

$|M|$ = {$1, 2$}

$M^P$ = {$2$}

$M^R$ = {$1$}

$M(a) = 2$

And construct an extension of $M$, $M'$, with the same domain and predicate extensions of $M$, but assigning $a$ a different object from the domain, namely

$M'(a) = 1$

Then, I see that $M$ $\models$$A$. But wouldn't the extension $M'$ be false, because $2$ $\notin$ $M^R$ $?$ Would this not provide proof that the original statement is indeed false? I'm asked to prove this statement for an assignment, so it must be true, so I must not be understanding how extensions of interpretations work, or my definition of $\models$ is wonky. Any insight into what i'm not getting would be greatly appreciated. Thanks in advance!

$\endgroup$
1
$\begingroup$

In the situation you've described, $M'$ is not an extension of $M$: to be an extension, $M'$ must agree with $M$ on all the symbols in the language of $M$ (in particular here, it can't send $a$ to somewhere other than where $M$ sends $a$).

The idea is that $M'$ adds structure to the existing structure of $M$. For example, the structure $A=(\mathbb{Z}; +,\times)$ is an extension of the structure $B=(\mathbb{Z};+)$: they have the same domain and each interpret the "$+$" symbol in the same way, but $A$ has an additional bit of structure, namely multiplication.


Of course, above I'm being a bit fast and loose with the distinction between a symbol and a function (or relation, or constant). Really it would be more precise to say:

"Let $\oplus,\otimes$ be binary function symbols, let $\Sigma=\{\oplus\}$, and let $\Pi=\{\oplus,\otimes\}$. Let $A$ be the $\Sigma$-structure with domain $\mathbb{Z}$ and which interprets $\oplus$ as $+$, and let $B$ be the $\Pi$-structure with domain $\mathbb{Z}$ which interprets $\oplus$ as $+$ and $\otimes$ as $\times$. Then $A$ and $B$ have the same domain, the language of $A$ is contained in the language of $B$, and $A$ and $B$ agree on the interpretations of everything in their shared language (namely, just $\oplus$ in this case); so $B$ is an extension of $A$."

But that's a bit long, and I think the way I wrote it above is more intuitive.


Incidentally, if you're familiar with abstract algebra, there's a very general kind of extension you've seen before: a ring is an extension of its underlying group. If you're not familiar with abstract algebra, ignore this bit, but if you are this might help make the notion of extension seem more natural.

$\endgroup$
  • $\begingroup$ So if i say for $M'$ that it sends $a$ to the set {$1,2$}, then $M'$ would be considered a valid extension? $\endgroup$ – MattyS11 Feb 12 at 5:26
  • $\begingroup$ @MattyS11 A structure can't send a constant symbol to a set, it has to send it to a single element. Again, $M'$ is an extension of $M$ iff the interpretation in $M'$ of each of the symbols in the language of $M$ is exactly the same as the interpretation of that symbol in $M$. $M'$ needs to be identical to $M$ except as far as any new symbols (= symbols in the language of $M'$ but not in the language of $M$) are concerned. $\endgroup$ – Noah Schweber Feb 12 at 13:58
  • $\begingroup$ right right sorry im dumb lol. So M'(a) would HAVE to map to 2 in this case, but could also send any other constant symbol x to any element of the domain. $\endgroup$ – MattyS11 Feb 13 at 23:35
  • $\begingroup$ @MattyS11 Yes - as long as such an other constant symbol wasn't in the language of $M$ already. $\endgroup$ – Noah Schweber Feb 13 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.