Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On page 99, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed),

Show that if $x$ does not occur free in $α$, then $α \vDash ∀ x α$.

Added:This could be seen as a follow-up problem of this one. Frankly speaking, I'm totally confused between this problem and the answer to that problem.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

"$\vDash$" means that RHS is true in every model of LHS. If $x$ does not occur free in $\alpha$, a model of $\alpha$ need not assign a value to $x$ - that is, in a model of $\alpha$, $\alpha$ is true for all assignments of $x$, so $\alpha \vDash \forall x \alpha$.

I'm not really sure if this is how formally you are expected to answer something like this (assuming this is attached to some kind of course in logic), but this is the reason it's true.

share|improve this answer
add comment

According to Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)), page 88 :

Definition. Let $\Gamma$ be a set of wffs, $\varphi$ a wff. Then $\Gamma$ logically implies $\varphi$, written $\Gamma \vDash \varphi$, iff for every structure $\mathcal A$ for the language and every function $s : Var \mapsto |\mathcal A|$ such that $\mathcal A$ satisfies every member of $\Gamma$ with $s$, $\mathcal A$ also satisfies $\varphi$ with $s$.

And [page 84] :

$\mathcal A \vDash \forall x \varphi[s]$ iff for every $d \in |\mathcal A|$, we have $\mathcal A \vDash \varphi[s(x|d)]$.

We want to show that :

if $x$ does not occur free in $\alpha$, then $\alpha \vDash \forall x \alpha$.

Consider a structure $\mathcal A$ and a function $s$ and apply the above definition with $\Gamma = \{ \alpha \}$.

If $\mathcal A$ satisfies $\alpha$ with $s$, i.e.

$\mathcal A \vDash \alpha[s]$,

then also an assignment $s(x|d)$ will satisfy $\alpha$, because the variable $x$ is not free in it and thus it does not matter what is the "denotation" that $s$ assign to it.

But $d \in |\mathcal A|$ is whatever; thus :

for every $d \in |\mathcal A|$, we have that : $\mathcal A \vDash \alpha[s(x|d)]$, and this is the condition for :

$\mathcal A \vDash \forall x \alpha[s]$.

Conclusion

We have showed that, if $x$ does not occur free in $\alpha$, for every structure $\mathcal A$ and every function $s$ such that $\mathcal A$ satisfies $\alpha$ with $s$, $\mathcal A$ also satisfies $\forall x \alpha$ with $s$, and this amounts to :

$\alpha \vDash \forall x \alpha$.


Comment

You say that you are confused with this example and the previous post.

There we have showed that :

$\vDash ∃x(Qx \rightarrow ∀xQx)$

proving it by way of the logical theorem [see Enderton (Q3A), page 130] :

$\vdash (∀xβ \rightarrow α) \leftrightarrow ∃x(β \rightarrow α)$, if $x$ does not occur free in $\alpha$.

Here we can note that : $\alpha \vDash \forall x \alpha$ iff $\vDash \alpha \rightarrow \forall x \alpha$.

We can use now a second logical theorem [see Enderton (Q2A), page 121] :

$\vdash (α \rightarrow ∀xβ) \leftrightarrow ∀x(α \rightarrow β)$, if $x$ does not occur free in $\alpha$.

If we apply it to : $\alpha \rightarrow \forall x \alpha$, because $x$ does not occur free in $\alpha$, we get :

$\vDash ∀x(α \rightarrow α)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.