Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Can someone give me a hint, how to prove that the $\Sigma$-formula

$$ \neg (\psi_{x \rightarrow t} \ \& \ \exists x \psi)$$

where $\psi$ is an arbitrary $\Sigma$-formula, $t$ is a $\Sigma$-term whose variable don't appear in $\psi$ and $x$ is any variable, holds in every nonempty structure ?

(What "$\psi_{x \rightarrow t}$" means and for other technical details, over which alphabet the $\Sigma$-terms etc. were defined see a different post of mine)

share|cite|improve this question
Is there a typo in the question? The assertion you are asking us to prove is false. If $\psi$ is a tautology, for example, with no free variables, then $\psi$ and $\exists x\ \psi$ hold in every structure. – JDH Jul 4 '11 at 10:31
Yes, you were right. joriki figured in his answer out what I meant. Sorry. – temo Jul 6 '11 at 10:37
up vote 1 down vote accepted

As JDH pointed out, this is false. I'll assume that you meant

$$\neg (\psi_{x \rightarrow t} \ \& \ \neg\exists x \psi)$$

(with a negation added).

If $x$ does not occur in $\psi$, then the formula holds in every nonempty structure since in this case the replacement and the existential quantifier are irrelevant (since there exists at least one $x$ in the nonempty structure), so the formula holds iff $\neg(\psi\&\neg\psi)$ holds.

If $x$ does occur in $\psi$, then for the first conjunct to be true $t$ has to evaluate to an $x$ that makes $\psi$ true, and hence $\exists x\psi$, so in this case the second conjunct is false.

share|cite|improve this answer
Yes, I meant that. thanks. – temo Jul 6 '11 at 10:38

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.