Why $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology?

83 Views Asked by At

Let $c$ be a new constant symbol in the language. Then $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology.

This means the expression is always $\textbf{true}$ regardless of the truth assignment of all the prime formulas, which assume the form of $\forall y \beta,$ occuring in it.

Every wff in the expression is built from formulas of the form: $\forall z \beta,$ via the operations $\rightarrow$ and $\neg.$ So how do I build $\neg\alpha^{x}_{c}$ from $\forall y \beta \ ?$ And how do I assign a truth value on it?

Kindly advise. Thank you.

1

There are 1 best solutions below

0
On

The formula :

$(∀x¬α → ¬α^x_c) \rightarrow (α^x_c → ∃xα)$

is a valid formula of first-order logic.

Usually, the use of tautology is restricted to propositional logic.

But we have also another prossibility : we can say that a formula of f-o logic is an instance of a tautology, in which case it is obviously valid.

To show this, we must assume that $\exists$ is an abbreviation for : $\lnot \forall \lnot$.

Start then from the tautology :

$(\varphi \rightarrow \lnot \psi) \rightarrow (\psi \rightarrow \lnot \varphi)$

and instantiate it with $∀x \lnot \alpha$ in place of $\varphi$ and $\alpha^x_c$ in place of $\psi$.

We have :

$(∀x¬α → ¬α^x_c) \rightarrow (α^x_c → ¬∀x¬α)$.

With the above abbreviation, we conclude with :

$(∀x¬α → ¬α^x_c) \rightarrow (α^x_c → ∃xα)$.

Thus, we have proved that the formula is valid, exactly because it is an instance of a tautology.


Comment

If you want to use a "semantical" argument, based on truth assignment, again you have to start form :

$(∀x¬α → ¬α^x_c) \rightarrow (α^x_c → ¬∀x¬α)$.

Assume an assignment $v$ such that $v(\alpha^x_c)=F$; then the consequent of the "main" conditional is true and the formula evaluates to true.

Assume now an assignment $v$ such that $v(\alpha^x_c)=T$.

We have two possibilities :

  • if $v(∀x¬α)=F$, then $v(¬∀x¬α)=v(∃xα)=T$, and the consequent of the conditional is true; then, the formula is true.

  • if $v(∀x¬α)=T$, then $v(¬∀x¬α)=v(∃xα)=F$, and the consequent of the conditional is false; but then, $v(\alpha^x_c)=T$ means that $v(¬\alpha^x_c)=F$, which implies that also the antecedent of the conditional is false. Thus, the formula is again evaluated to true.