In what way is the existential and universal quantifiers treated differently by the rules of $\forall$-introduction and $\exists$-introduction?

211 Views Asked by At

In Natural Deduction in what way is the existential and universal quantifiers treated differently by the rules of $\forall$-introduction and $\exists$-introduction?

They look really similar in their definitions?:

$\forall$-introduction: $\frac{\frac{}{A(c)}}{\forall x A(x)}$ Provided that c is a new constant symbol

$\exists$-introduction: $\frac{A(t)}{\exists x A(x)}$

2

There are 2 best solutions below

2
On BEST ANSWER

Well, say $c$ is a constant symbol. Then the rule tells you that you can conclude $\exists{x}A(x)$, but you certainly can't conclude $\forall{x}A(x)$.

For an example: Suppose you are working with real numbers and $A(0)$ is stating that $\forall{y}$ $0.y=0$ (i.e. multiply any number by $0$ and you get back $0$). So it is correct to conclude $\exists{x}\forall{y}$ $x.y=x$ (i.e. there is some number s.t. if you multiply any number with that number you get the initial number back). It is certainly not correct to conclude $\forall{x}\forall{y}$ $x.y=x$ (i.e. the product of any two numbers is equal to the first number.)

Edit 1: I'm not really clear on what you mean by "new", but I think the point that is being attempted is the following (suppose that the only constant symbols you have are $0,1$): Suppose that you assume $c$ is some arbitrary element and you manage to prove some thing about $c$, then you can conclude for all $x$. For example, suppose $c$ is non-zero number. Then you can prove $\exists{y}$ s.t. $c.y=1$. So you can conclude for all $x$, if $x$ is non-zero, then there is some $y$ s.t. $x.y=1$. However you have $1.1=1$. You can't conclude for all $x$, $x.x=x$. But you can conclude there is some $x$ for which $x.x=x$

0
On

The $\exists Intro$ has no restrictions, because as soon as something ($t$) has property $A$, then of course there is something that has property $A$. So, from $A(t)$ you can infer $\exists x A(x)$, no matter what $t$ is, or how $t$ came about.

The $\forall Intro$ works quite differently. You want to show that $\forall x A(x)$. How can you show that? Because $A(t)$ for some $t$? Clearly that is not enough ... You need to know that $A(t)$ is true for all $t$'s! OK, so how do we show that? Well, if we assume that $c$ is some completely arbitrary object from our domain (and we do this by introducing a new symbol $c$, so we can ensure that we don't know anything about $c$ other than that it is some object from our domain), and we can show that $c$ has property $A$, then we can conclude that all objects have property $A$.

In short, if any object $c$ has property $A$ (i.e. If $A(c)$ for a newly introduced $c$), then all objects have property $A$ (I.e. then $\forall x A(x)$)