3
$\begingroup$

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents.

Definition. If $\phi_1,\dots, \phi_n,\phi$ are formulas, then $\phi_1\dots\phi_n\vdash\phi$, often abbreviated by $\Gamma\vdash\phi$, is called a sequent.

Can somebody please explain to me the following two inference rules?

  1. Introduction of the universal quantifier.

$$ \begin{array}{c} \Gamma\vdash\phi\\ \hline \Gamma\vdash\forall x(\phi) \end{array}\text{, where $x$ does not occur as a free variable in $\Gamma$.} $$

  1. Elimination of the existential quantifier.

$$ \begin{array}{c} \Gamma\vdash\exists x(A)\qquad \Gamma, A\vdash B\\ \hline \Gamma\vdash B \end{array} \text{, where $x$ does neither occur as a free variable in $\Gamma$ nor as a free variable in $B$.} $$

I am especially interested in what the restriction that $x$ is not allowed to occur as a free variable in $\Gamma$ (and also not in $B$) is all about. I have heard the following explanation for the necessity of this restriction:

Otherwise we could derive $\exists x (A(x))\rightarrow \forall x (A(x))$. But this is not a logically valid formula; and we want to have a correct calculus.

Although I can reconstruct this argument, I do not really understand the two rules given above. I have no intuition why $x$ should not be a free variable in $B$ or in $\Gamma$, for example. Could you please explain the intuition behind these inference rules?

EDIT: Another question, but a related question: Can you give an example of a proof which uses the rule of existential quantifier eliminination where there is some free variable occuring in $B$?

$\endgroup$
4
$\begingroup$

My intuition is that propositions without free variables are fully general, while a proposition with a free variable $x$ is a statement about a specific thing named $x$. For example, $\forall x : \text{IsRed}(x)$ means "everything is red", but $\text{IsRed(x)}$ means "the thing called $x$ is red".

So suppose we already derived $\text{IsRound}(x) \vdash \text{IsRed}(x)$. This means that we know that if the thing called $x$ is round, it has to be red. Now, if we disregarded the restriction, we could wrongly conclude $\text{IsRound}(x) \vdash \forall x : \text{IsRed}(x)$. This means that if the thing called $x$ is round, then everything is red. Note that even though the two $x$s are the same letter, they represent different things: The first one refers to the object named $x$, the gets all its meaning from the quantifier where it was bound.

Now, if the $\forall$-introduction rule is used correctly, it captures the intuition that if I say "Paul has a nose" without assuming (/observing) anything about Paul, then I know that everything has a nose.


Now, let's look at the rule for $\exists$-elimination. To extend my methaphor, it says that if I know that something has a nose, and if I also know that if Paul (some "generic" person in the sense that we don't assume anything else about him) has a nose, then grass must be green, then we also know that grass is green.

Now, let's see what could go wrong if we violate the two restrictions:

  • Let's say we already derived that $\text{isRed}(x) \vdash \exists y : \text{isRound}(y)$, and we also derived $\text{isRed}(x), \text{isRound}(x) \vdash 1 = 0$. Then, we might incorrectly conclude that $\text{isRed}(x) \vdash 1 = 0$ if we ignore the restriction that $x$ can't be free in $\Gamma$.

    To abuse my metaphor a bit, in this case Paul (or $x$) stopped being a "generic" person because we assumed some properties about him that might make him contribute to grass being green.

  • Suppose we already derived that $\vdash \exists y : \text{isRound}(y)$ and also that $\text{isRound}(x) \vdash \text{isRed}(x)$. Then, we might incorrectly conclude that $\vdash \text{isRed}(x)$, if we ignore the rule that $x$ can't be free in $B$.

    To torture my metaphor a little bit more, in this case instead of concluding something general like "grass is green", we concluded some statement about Paul. This is incorrect since we intended to use Paul as some kind of stand-in for the thing that has a nose (which we know exists), so we can't conclude any statements about the actual Paul!

$\endgroup$
  • $\begingroup$ I am gonna try explaining the $\exists$-elimination in an hour or so. $\endgroup$ – dankness Jun 9 '16 at 19:12
  • $\begingroup$ Thanks. Your answer helped me so far. $\endgroup$ – ooooooo Jun 9 '16 at 19:29
  • $\begingroup$ @ooooooo: Done! $\endgroup$ – dankness Jun 9 '16 at 21:03
  • $\begingroup$ Thanks so much, dude! You helped me very much!!!!!! :-) $\endgroup$ – ooooooo Jun 10 '16 at 15:31
6
$\begingroup$

Example

Let $\Gamma$ the set of first-order Peano axioms: no variables free.

1) $\Gamma \vdash \exists x (x = 0)$ --- easily provable

2) $\Gamma, x=0 \vdash x=0$ --- obvious

3) $\Gamma \vdash x=0$ --- from 1) and 2) by $\exists$-elim : wrong !

4) $\Gamma \vdash \forall x (x=0)$ --- from 3) by $\forall$-intro,


1) $\Gamma, x=0 \vdash x = 0$

2) $\Gamma, x=0 \vdash \forall x (x=0)$ --- by $\forall$-intro: wrong !

3) $\Gamma \vdash x=0 \to \forall x (x=0)$ --- from 2) by $\to$-intro

4) $\Gamma \vdash \forall x [x=0 \to \forall x (x=0)]$ --- from 3) by $\forall$-intro

5) $\Gamma \vdash 0=0 \to \forall x (x=0)$ --- from 4) by $\forall$-elim.



The ground for the restriction on $\forall$-intro are linked to the "generalization principle":

what holds for any, holds for all.

Thus, in order to formalize this principle with a rule of inference, we read it as:

if something holds for an "arbitrary object", then it holds for all objects.

We have to capture the informal concept of “arbitrary object” by way of a syntactic criterion.

Consider now a variable $x$ in the context of a derivation: we shall call $x$ arbitrary if nothing has been assumed concerning $x$. In other words, $x$ is arbitrary at its particular occurrence in a derivation if the part of the derivation above it contains no hypotheses containing $x$ free.

$\endgroup$
1
$\begingroup$

$$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma, A \vdash B}{\Gamma \vdash B}$$

This axiom is basically modus ponens, a little prenexing, and universal elimination combined into 1 statement. Suppose I gave you:

$$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma \vdash (\exists x ~ A) \implies B}{\Gamma \vdash B}$$

That is just a trivial application of modus ponens. Suppose you are also familiar with the prenex derivation:

$$(\exists x ~ A) \implies B$$ $$\lnot (\exists x ~ A) \lor B$$ $$(\forall x ~ \lnot A) \lor B$$ $$\forall x ~ (\lnot A \lor B)$$ $$\forall x ~ (A \implies B)$$

$(\exists x ~ A) \implies B ~~\vdash^\equiv~~ \forall x ~ (A \implies B)$ provides a way of converting a $\exists$ to $\forall$ by pulling it out of the condition of an implication. But it does require that $x \not \in {\rm FV}(B)$.

And suppose you accept universal elimination, that is:

$$\frac{\Gamma \vdash \forall x~A}{\Gamma \vdash A} \quad \text{for } x \not \in {\rm FV}(\Gamma)$$

Then you can put those together to get the existential elimination axiom:

$$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma \vdash (\exists x ~ A) \implies B}{\Gamma \vdash B}$$

$$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma \vdash \forall x ~ (A \implies B)}{\Gamma \vdash B}$$

$$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma \vdash (A \implies B)}{\Gamma \vdash B}$$

$$\frac{\Gamma \vdash \exists x ~ A \quad \Gamma,~A \vdash B}{\Gamma \vdash B}$$

To correctly apply the $\exists$ conversion, you need $x \not \in {\rm FV}(B)$. To correct apply the $\forall$ elimination you need $x \not \in {\rm FV}(\Gamma)$. That doesn't establish that those conditions are necessary, but hopefully can offer some confidence about the correctness of the axiom.

$\endgroup$
  • $\begingroup$ Thank you. Could you please recommend me a book about this topic? The ones I have are rather old and the notation looks strange. $\endgroup$ – Cure Jun 28 '16 at 0:33
  • 3
    $\begingroup$ @Cure I have never seen a decent presentation of any logic. Everyone seems to want to start in the middle with obscure not-self-evident axioms then make handwaving informal but complex proofs about them. If I ever find a decent presentation of a logic I'll try to remember to let you know. $\endgroup$ – DanielV Jun 28 '16 at 1:03
1
$\begingroup$

If you do the foundations of logic so that variant statements are identified (in my terminology I say they are the same as formulas because they in some sense have the same form), then all the generalization rules you need are those guaranteeing that $\forall x A$ is the infimum of the set of formulas $[t/x]A$, where $t$ ranges over the set of terms. I.e., thinking of $\vdash$ as a (non-strict) smaller than relation, you need

  1. $\forall x A \vdash [t/x]A$ for all terms $t$.
  2. If $C \vdash [t/x] A$ for all terms $t$, then $C \vdash \forall xA$.

This seems a more natural way of looking at things, in my opinion. It takes me about a page or two of (pretty) proof to show that one gets the same inferences if (2) above is replaced with the standard rule

2*. If $C\vdash A$ where $x$ is not free in $C$, then $C \vdash \forall x A$.

Thus, we can still define proofs by (2*) rather than (2) (and not need to check infinitely many things to prove things).

Similarly, the standard instantiation rules can be replaced by the rules directly guaranteeing that $\exists x A$ is the supremum of the set of formulas $[t/x]A$.

In my terminology, for a statement $R$, $[t/x]R$ I take to be the formula obtained by replacing $x$ in the formula corresponding to $R$ with $t$. So by just looking at what I call formulas one can also avoid in the deepest foundation the bother of having to worry about substitutability.

I know it's not as standard, but I think it strange that anyone would want to think of $\vdash$ as anything other than a preorder on the set of formulas (fortunately one of my undergraduate professors at UNC-CH, Johann Sonner, taught me the preorder approach). It seems to me that allowing on the fundamental-definition level sets of formulas (or more than one formula) to the left of $\vdash$ introduces a high degree of awkwardness not worth whatever higher generality such might be seen as giving. Part of the problem is that $\vdash$ is pointy on the wrong side, the right-hand side, akin to most symbols suggesting a larger than relation, obscuring that it should represent a smaller than relation.

NEW: I am adding proof that my quantification rules give standard inferences. (Don't know how original this is.) I use $<$ to denote $\vdash$. My quantification rules are

IA (Infer any): $\mathbf{\underset x \wedge A < [t/x]A}$ for all terms $\mathbf{t}$.

GEN (Generalization): If $\mathbf{B < [t/x]A}$ for all terms $t$, then $\mathbf{B < \underset x \wedge A}$.

IE (Infer existence): $\mathbf{[t/x]A < \underset x \vee A}$ for all terms $\mathbf{t}$.

INS (Instantiation): If $\mathbf{[t/x]A < B}$ for all terms $\mathbf{t}$, then $\mathbf{\underset x \vee A < B}$.

I say (making up the definition) that a variable $\mathbf{x}$ is abstract in an inference system if given any $\mathbf{A < B}$ valid in the inference system and any variable $\mathbf{y}$ not in $\mathbf{A < B}$, $\mathbf{[y/x]A < [y/x]B}$ is valid in the inference system. I say an inference system is abstract if it possesses infinitely many abstract variables.

Next, I wish to demonstrate the substitution law, namely that for formulas $\mathbf{A}$ and $\mathbf{B}$, if $\mathbf{A} < \mathbf{B}$, then $[\mathbf{t}/\mathbf{y}] \mathbf{A }< [\mathbf{t}/\mathbf{y}] \mathbf{B}$ (with no restrictions on $\mathbf{t}$ other than that it be a term). If we prove this for $\mathbf{t}$ not containing $\mathbf{y}$, we shall prove it in general, for from $\mathbf{A} < \mathbf{B}$ we will have $[\mathbf{w}/\mathbf{y}] \mathbf{A }< [\mathbf{w}/\mathbf{y}] \mathbf{B}$ for $\mathbf{w}$ not in $\mathbf{t}$ or free in $\mathbf{A}$ or $\mathbf{B}$, and then the result follows from $[\mathbf{t}/\mathbf{w}] [\mathbf{w}/\mathbf{y}] \mathbf{A} < [\mathbf{t}/\mathbf{w}] [\mathbf{w}/\mathbf{y}] \mathbf{B}$. Therefore, we assume $\mathbf{t}$ does not contain $\mathbf{y}$.

Define the relation "$<_{\mathbf{t},\mathbf{y}}$"such that $\mathbf{A} <_{\mathbf{t},\mathbf{y}} \mathbf{B}$ if and only if $[\mathbf{t}/\mathbf{y}] \mathbf{A }< [\mathbf{t}/\mathbf{y}] \mathbf{B}$. We need to show that "$<_{\mathbf{t},\mathbf{y}}$" is a larger relation than "$<$", i.e., that it satisfies the inference rules. In fact, I prove a stronger result, namely that in any abstract inference system containing one of the official rules we have given, the rule obtained by replacing in an official rule the relation "$<$" with "$<_{\mathbf{t},\mathbf{y}}$" holds merely as a result of the official rule holding and that the inference system is abstract. Again, the only difficulties are with those inference rules involving generalization and instantiation. I shall deal here only with generalization, leaving the entirely analogous proof in the case of instantiation to you.

As for IA, we need to show that for any formula $\mathbf{A}$ that $[\mathbf{t}/\mathbf{y}] \underset{\mathbf{x}} \wedge \mathbf{A} < [\mathbf{t}/\mathbf{y}] [\mathbf{s}/\mathbf{x}] \mathbf{A}$ for all terms $\mathbf{s}$. The result is easy if $\mathbf{x}$ is the same variable as $\mathbf{y}$, so we assume they are different. Letting $\mathbf{z}$ be a variable distinct from $\mathbf{y}$ and not occurring in $\mathbf{t}$ or free in $\mathbf{A}$, it is clear from the dummy variable rule that our desired inference is identical to $[\mathbf{t}/\mathbf{y}] \underset{\mathbf{z}}\wedge [\mathbf{z}/\mathbf{x}] \mathbf{A} < [\mathbf{t}/\mathbf{y}] [\mathbf{s}/\mathbf{z}] [\mathbf{z}/\mathbf{x}] \mathbf{A}\,.$ In other words, without loss of generality we may assume also that $\mathbf{x}$ does not occur in $\mathbf{t}$. Making this assumption, $[\mathbf{t}/\mathbf{y}] \underset{\mathbf{x}}\wedge \mathbf{A}$ is the same formula as $\underset{\mathbf{x}} \wedge [\mathbf{t}/\mathbf{y}] \mathbf{A}$, and $[\mathbf{t}/\mathbf{y}] [\mathbf{s}/\mathbf{x}] \mathbf{A}$ is the same formula as $[[\mathbf{t}/\mathbf{y}] \mathbf{s}/\mathbf{x}] [\mathbf{t}/\mathbf{y}] \mathbf{A}$, and we make use of IA holding for "$<$".

The situation for GEN is more complex than that for the other cases (except for the entirely analogous INS). Apparently, one needs there not just that the inference rule holds, but also that the inference rules as a whole form an inference system which is abstract.

As for GEN, suppose that $[\mathbf{t}/\mathbf{y}] \mathbf{B} < [\mathbf{t}/\mathbf{y}] [\mathbf{s}/\mathbf{x}] \mathbf{A}$ for all terms $\mathbf{s}$. Choose $\mathbf{z}$ such that $\mathbf{z}$ is distinct from $\mathbf{y}$, and such that $\mathbf{z}$ is not free in $\mathbf{A}$,$\mathbf{B}$ or $\mathbf{t}$. Let $\mathbf{D}$ be $[\mathbf{z}/\mathbf{x}] \mathbf{A}$. Then $[\mathbf{t}/\mathbf{y}] \mathbf{B} < [\mathbf{t}/\mathbf{y}] [\mathbf{s}/\mathbf{z}] \mathbf{D}$ for all terms $\mathbf{s}$. Fix $\mathbf{s}$ and let $\mathbf{w}$ be an abstract variable distinct from both $\mathbf{y}$ and $\mathbf{z}$ and not occurring in $\mathbf{B}$, $\mathbf{t}$, $\mathbf{D}$, or $\mathbf{s}$. Then in particular, $[\mathbf{t}/\mathbf{y}] \mathbf{B} < [\mathbf{t}/\mathbf{y}] \left[\left[\mathbf{w}/\mathbf{y}\right]\mathbf{s}/\mathbf{z}\right] \mathbf{D}$. By a substitution lemma, this is the same inference as $\tag*{$(\dagger)$}\label{eq:sub}[\mathbf{t/y}] \mathbf{B} < [[\mathbf{w}/\mathbf{y}]\mathbf{s}/\mathbf{z}][\mathbf{t}/\mathbf{y}] \mathbf{D}.$ Since $\mathbf{w}$ (like all variables in the inference system under consideration) is an abstract variable, the above inference, which does not contain $\mathbf{y}$, remains valid when $\mathbf{w}$ is replaced by $\mathbf{y}$. We have \begin{align*}[\mathbf{t}/\mathbf{y}] \mathbf{B} = [\mathbf{y}/\mathbf{w}][\mathbf{t}/\mathbf{y}]\mathbf{B} < [\mathbf{y}/\mathbf{w}][[\mathbf{w}/\mathbf{y}]\mathbf{s}/\mathbf{z}][\mathbf{t}/\mathbf{y}] \mathbf{D} &= [[\mathbf{y}/\mathbf{w}][\mathbf{w}/\mathbf{y}]\mathbf{s}/\mathbf{z}][\mathbf{t}/\mathbf{y}] \mathbf{D}\\ &= [\mathbf{s}/\mathbf{z}][\mathbf{t}/\mathbf{y}]\mathbf{D}. \end{align*} Since $\mathbf{s}$ was arbitrary, $[\mathbf{t/y}] \mathbf{B} < [\mathbf{s}/\mathbf{z}][\mathbf{t}/\mathbf{y}] \mathbf{D}$ for all terms $\mathbf{s}$. From GEN applied to "$<$" it follows that $[\mathbf{t/y}] \mathbf{B} < \underset{\mathbf{z}}\wedge [\mathbf{t}/\mathbf{y}] \mathbf{D}$, i.e., $[\mathbf{t/y}] \mathbf{B} < \underset{\mathbf{z}}\wedge [\mathbf{t}/\mathbf{y}] [\mathbf{z}/\mathbf{x}] \mathbf{A}$. Thus it suffices to show that $\underset{\mathbf{z}}\wedge [\mathbf{t}/\mathbf{y}] [\mathbf{z}/\mathbf{x}] \mathbf{A}$ is verily equivalent to $[\mathbf{t}/\mathbf{y}] \underset{\mathbf{x}}\wedge \mathbf{A}$. In fact, they are the same formulas. Indeed, by the dummy variable rule, $[\mathbf{t}/\mathbf{y}] \underset{\mathbf{x}}\wedge \mathbf{A}$ is the same formula as $[\mathbf{t}/\mathbf{y}] \underset{\mathbf{z}}\wedge [\mathbf{z}/\mathbf{x}] \mathbf{A}$, which is the same formula as $\underset{\mathbf{z}}\wedge [\mathbf{t}/\mathbf{y}] [\mathbf{z}/\mathbf{x}] \mathbf{A}$ since $\mathbf{z}$ does not occur in $\mathbf{t}$ and is distinct from $\mathbf{y}$.

To reiterate, we have shown the following.

The Substitution Law. For all formulas $\mathbf{A}$ and $\mathbf{B}$, terms $\mathbf{t}$ and variables $\mathbf{x}$, if $\mathbf{A} < \mathbf{B}$ then $[\mathbf{t}/\mathbf{x}] \mathbf{A} < [\mathbf{t}/\mathbf{x}] \mathbf{B}$.

Note that the substitution law immediately implies

GEN*. If $\mathbf{B} < \mathbf{A}$ and $\mathbf{x}$ is not free in $\mathbf{B}$, then $\mathbf{B} < \underset{\mathbf{x}}\wedge \mathbf{A}$.

INS*. If $\mathbf{A} < \mathbf{B}$ and $\mathbf{x}$ is not free in $\mathbf{B}$, then $\underset{\mathbf{x}} \vee \mathbf{A} < \mathbf{B}$.

Moreover, if we drop GEN and INS from our list of rules of inference, and replace them by GEN* and INS*, then GEN and INS will follow, and so replacing GEN and INS by their starred counterparts gives an equivalent inference relation "$<<$" identical to "$<$". Indeed, looking at generalization (instantiation is similar), suppose $\mathbf{B} << \mathbf{A}[\mathbf{t}/\mathbf{x}]$ for all terms $\mathbf{t}$. Then $\mathbf{B} << \mathbf{A}[\mathbf{z}/\mathbf{x}]$, where $\mathbf{z}$ is a variable not free in $\mathbf{A}$ or $\mathbf{B}$. Hence, $\mathbf{B} << \underset{\mathbf{z}}\wedge \mathbf{A}[\mathbf{z}/\mathbf{x}]$, and so $\mathbf{B} << \underset{\mathbf{x}}\wedge \mathbf{A}$ by the dummy variable rule. This alternative set of inference rules is interesting because it is easy to show using them that the set of valid inferences are just those inferences that can be obtained by (finite) proofs, i.e., lists of inferences of the form $\mathbf{A} < \mathbf{B}$ in which each entry of the list can be obtained from prior entries using an inference rule (with GEN and INS replaced by their starred counterparts). Thus, although at first glance our original inference rules may appear to (undesirably) involve infinite methods (e.g., checking whether a formula $\mathbf{B}$ is such that $\mathbf{B} < \mathbf{A}[\mathbf{t}/\mathbf{x}]$ holds for all terms $\mathbf{t}$), which could make the notion of proof obscure and not finitary, they really do not in any unavoidable way.

$\endgroup$
  • $\begingroup$ Does this style of reasoning provide insight on the existential elimination axiom? It reminds me of the "weakest precondition/strongest postcondition" type of reasoning used in Hoare logic. $\endgroup$ – DanielV Jun 27 '16 at 22:19
  • $\begingroup$ Thinking of $\vdash$ as giving preorder, that $A \vdash B$ implies $\exists x A \vdash B$ if $x$ is not free in $B$ is the obvious useful replacement for the existential elimination axioms. Replacing this and the introduction of universal quantifier axioms with axioms more geared to showing that instantiation and generalization are supremums and infimums, respectively, has not seemed useful, but it brings out analogy with disjunction and conjunction, making things less mysterious--and the axioms feel less disturbing as it takes work to show standard axioms aren't strictly stronger. $\endgroup$ – Stephen A. Meigs Jun 29 '16 at 17:05
  • $\begingroup$ Stating the axioms in a way that makes the infimum/supremum interpretation clear seems to me like it couldn't be useless. By "analogy with disjunction and conjunction" I assume you mean the idea that $\forall$ is generalized $\land$ and $\exists$ is generalized $\lor$. I am not sure what you mean by "brings out" though. Could explicitly list the axiom you are talking about, or offer a reference? $\endgroup$ – DanielV Jun 30 '16 at 2:43
  • $\begingroup$ I meant "useless" in sense of not useful for proving proofs. It is useful if foundations are natural looking, even if making them more so doesn't make the foundations more directly useful for applications. To make clear what I was saying about bringing out analogies, perhaps I will try to add to my answer above a proof of what I was claiming in my answer (way too long for a comment) and list all the quantification inference rules I'm talking about. $\endgroup$ – Stephen A. Meigs Jun 30 '16 at 19:24

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.