Dtjytyk

In Kleene's "Mathematical Logic" and "Introduction to Metamathematics" for a classical predicate calculus the following two rules of inference are chosen.

If $A(x) Rightarrow C$ then $(exists xA(x)) Rightarrow (C)$ and
if $C Rightarrow A(x)$ then $(C) Rightarrow (forall xA(x))$ where $C$ does not contain variable $x$ free.

I tried motivating these choices but unfortunately I could not. Because it is a classical predicate calculus I tried considering truth table semantics to somehow see why these results should be valid, but what I found (not sure if correct) is that the following results are semantically valid as well.

If $A(x) Rightarrow C$ then $(forall x(A(x)) Rightarrow (C)$ and also if $C Rightarrow A(x)$ then $(C) Rightarrow (exists x A(x))$ where $C$ again does not contain variable $x$ free.

If this is indeed true then I am confused as one sees that $exists$ and $forall$ act in inference rules in exactly the same way while intuitively I would think that these two logical symbols should act differently.

I would appreciate your advice or thoughts about this.

The additional rules you give are indeed valid (on non-empty domains). The reason for this is that the implication $forall x, A(x) Rightarrow exists x, A(x)$ is valid (on non-empty domains) - if I recall correctly, this is sometimes called "existential import".

So if $A(x) Rightarrow C$, then we have both $forall x, A(x)Rightarrow exists x, A(x)$ and $exists x, A(x)Rightarrow C$, so $forall x, A(x)Rightarrow C$.

And dually, if $CRightarrow A(x)$, then we have both $CRightarrow forall x, A(x)$ and $forall x, A(x)Rightarrow exists x, A(x)$, so $CRightarrow exists x, A(x)$.

But we don't get from this that $exists$ and $forall$ "act in exactly the same way", because the rules you've given in your question don't totally capture the meaning of $exists$ and $forall$. You need more rules.

I'm not sure what rules Kleene uses, but there are two common approaches:

1. One approach is to also give the converses of your rules: If $exists x, A(x)Rightarrow C$, then $A(x)Rightarrow C$, and if $CRightarrow forall x, A(x)$, then $CRightarrow A(x)$ (where $x$ is not free in $C$).




2. Another approach is to include the axioms $A(t)Rightarrow exists x, A(x)$ and $forall x, A(x)Rightarrow A(t)$, where $t$ is a term substitutable for $x$.

In either of these approaches, you'll notice that if you try to replace $exists$ by $forall$ or vice versa, the rules are obviously not sound.

One more comment: The classical approach to first-order logic assumes that every structure has non-empty domain. But this assumption is not universal. If our semantics for first-order logic allows empty domains, then existential import fails: If there are no $x$s, then $forall x, A(x)$ is vacuously true, while $exists x, A(x)$ is false.

And similarly, if we allow empty domains, then your versions of the rules where we swap $exists$ and $forall$ are no longer valid. Frabala's answer gives a very nice intuitive example of this.

An intuitive answer, in a world of match sticks and fire and no magic, i.e. one can not make fire out of nothing.

Consider a variable $x$ to mean a match stick. Let $A(x)$ mean "Stick $x$ smokes" and $C$ mean "There is fire".

The rule "if $A(x)Rightarrow C$ then $(exists x A(x))Rightarrow C$" states the very obvious: "if stick x smokes then there's fire" means "if there is some stick $x$ that smokes, then there's fire". This sentence holds in any universe of match sticks.

Now, consider your rule "if $A(x)Rightarrow C$ then $(forall x A(x))Rightarrow C$". It states the following: "if stick x smokes, then there's fire" means also that "if all sticks $x$ are smoking, then there's fire". This derivation is valid only in models that contain at least one object. Because in an empty universe that has no match sticks, all match sticks (which are actually none) are smoking. However, there can be no fire without match sticks!