1
$\begingroup$

I'm trying to follow a proof in a logic text and it seems like the author used universal instantiation twice to reach the needed result. I was under the impression that you could only use UI one time in a proof.

$\endgroup$
  • 3
    $\begingroup$ Where did you get that impression? $\endgroup$ – Andreas Blass Jul 24 '14 at 4:26
  • $\begingroup$ This may not be particularly interesting to say, but it is indeed that case that, for all real numbers $a$ there exists a real number $c$ such that, for all positive numbers $e$, $e>a+c$. $\endgroup$ – Micah Jul 24 '14 at 4:27
  • $\begingroup$ I've only ever seen it used once in the proofs I've seen. Intuitively it seems like I should be able to use UI as many times as I want since the statement is true for all objects in the universe. Is this a correct assumption? $\endgroup$ – user166057 Jul 24 '14 at 4:28
  • $\begingroup$ If technique X can only be used once in a proof, and I use it to prove A implies B, and use it to prove B implies C, then I wouldn't be able to combine these proofs to show A implies C as that would require two uses, and mathematics would pretty well come to a halt. $\endgroup$ – Dan Piponi Jul 24 '14 at 4:39
1
$\begingroup$

Nothing prevents us to use universal instantiation (UI) more than once in a proof.

Consider the formula in the language of formal arithmetics :

$\forall x \exists y (y = S(x))$

where $S(x)$ is the "successor" function.

We can clearly instantiate it with $0$, to get :

$\exists y (y = S(0))$

which is true when $y$ get the value $1$; and again with :

$\exists y (y = S(S(0)))$

which is true when $y$ get the value $2$.


Added

You can see Peter Smith's answer to this post.

In order to prove :

$\forall x \forall yR(x,y) \vdash \forall xR(x,x)$

we have to proceed this way :

(i) $\forall x \forall yR(x,y)$ --- assumed

(ii) $\forall yR(x,y)$ --- by Universal Instantiation

(iii) $R(x,x)$ --- by UI

(iv) $\forall x R(x,x)$ --- by Universal Generalization, $x$ is not free in $\Gamma$, where $\Gamma = \{ \forall x \forall yR(x,y) \}$.

$\endgroup$

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.