0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JDH Jul 4 '11 at 10:31
  • $\begingroup$ Yes, you were right. joriki figured in his answer out what I meant. Sorry. $\endgroup$ – temo Jul 6 '11 at 10:37
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I meant that. thanks. $\endgroup$ – temo Jul 6 '11 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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