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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am asked to prove that

$$K \vdash (a \rightarrow \exists x \beta ) \implies K\vdash \alpha \rightarrow \beta[t/x]$$ is true using deduction.

I've failed to prove this and suspect there is an error here and this is false.

share|cite|improve this question
I think it is wrong. In the left term, $x$ is a bound variable (i.e. it is binded, you can't give it any value you want), while in the right term, $x$ is a free variable, so the truth value of the expression depends on the value of $x$. – Zachi Evenor Jun 9 '12 at 12:12
up vote 2 down vote accepted

It is not true. Let $K$ be the empty theory in a language with one predicate letter $p$, no constant letters and no function letters; then let $\alpha$ be $\exists x.p(x)$ and $\beta$ be $p(x)$. Then the precedent $$\varnothing \vdash (\exists x.p(x)) \to (\exists x.p(x))$$ is easily provable, but the only possible $t$s in the languages are variables, and if we choose such a $t$, then the conclusion $$\varnothing \vdash (\exists x.p(x)) \to p(y)$$ is clearly not valid -- it is easy to find an interpretation where it isn't true.

On the other hand, you should be able to prove $$ K\vdash \alpha \to \forall x.\beta ~\Longrightarrow~ K \vdash \alpha \to \beta[t/x]$$

share|cite|improve this answer
I hate this course :( – Nahum Litvin Jun 9 '12 at 16:09

Your Answer


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.