Universal introduction with a limited vocabulary

74 Views Asked by At

I understand (I think) how to apply Universal Introduction in general, but am uncertain how to use it with a specified limited vocabulary.

For example, given a language with a finite set of object constants, $\{a,b,c\}$ from the premises

$$\Pi =\{p(a),p(b),p(c)\}$$

I can use Universal Introduction to conclude things like

$$\Pi \vdash\forall x.p(a)$$

or

$$\Pi \vdash\forall c.p(c)$$

but I don't see how I can use these premises to get

$$\Pi \vdash\forall x.p(x)$$

even though it is clearly the case (I think) that

$$\Pi \models\forall x.p(x)$$

Can I use using (finite) Herbrand semantics to get this result?

1

There are 1 best solutions below

3
On BEST ANSWER

$\Pi \not\vDash \forall x. p(x)$, and hence $\Pi \not\vdash \forall x. p(x)$. The problem is that you could have objects in your domain which aren't named. Here's a model which satisfies $\Pi$, but doesn't satisfy $\forall x. p(x)$: Let the domain consist of 5 objects, and let 4 of those objects be $p$-objects (i.e. put 4 objects into the extension of $p$). Give the names $a,b,c$ to 3 of those $p$-objects. This will satisfy $\Pi$ but fail to satisfy $\forall x. p(x)$, since we have one lonely non-$p$ object in the domain, i.e. the extension of $p$ is not the entire domain.

Now, if you included in $\Pi$ the extra sentence $\forall x (x = a \vee x = b \vee x = c)$, then we would have $\Pi \vDash \forall x. p(x)$, since this extra sentence guarantees that all of the objects are named by one of the three constants. To show $\Pi + \forall x (x = a \vee x = b \vee x = c) \vdash \forall x. p(x)$, you could use identity rules from your deduction system.


If you're using (finite) Herbrand semantics, then your deduction system should have some sort of "domain closure rule" which allows you to deduce $\forall x.p(x)$ given every instance of $p(x)$, which in this case is $\Pi$. See this webpage from Stanford for more details.