0

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)

Community
  • 1
temo
  • 5,237
  • 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 04 '11 at 10:31
  • Yes, you were right. joriki figured in his answer out what I meant. Sorry. – temo Jul 06 '11 at 10:37

1 Answers1

1

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.

joriki
  • 238,052