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)

  • 0
    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.2011-07-04
  • 0
    Yes, you were right. joriki figured in his answer out what I meant. Sorry.2011-07-06

1 Answers 1

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.

  • 0
    Yes, I meant that. thanks.2011-07-06