Prove that in no formula(wff）does the two symbols $\neg$ and $)$ next to each other.

Question

$\mathcal{L}$ be any first-order language. Prove in no formula are the symbols $\neg$ and $)$ next to each other in any order. Hint: First prove that no formula ends with the symbol $\neg.$

I am very new and lost to the logic course. What I think first is simply say $\neg$ symbol can only be place at the start of a wff(e.g., such as before an atomic and besides a open bracket). What else can I say to have a conclusion that no formula ends with the symbol $\neg$?

Then I try to prove no $\neg$ before close bracket $)$ such as $\neg )$. By Enderton's book the well-formed formulas(wffs) are those expressions that can be built up from the atomic formulas by use(zero or more times) of the connective symbols and

$\varepsilon_{\neg}(\gamma) = (\neg \gamma),$

$\varepsilon_{\rightarrow}(\gamma,\delta)=(\gamma\rightarrow\delta),$

$Q_i(\gamma)= \forall v_i \gamma$

then I could say no expression $\gamma \neg $exists due to the above expressions when $\gamma$ is an atomic. But I don't know what to do if $\gamma$ is not a atomic but something else?

The second part $)\neg$ I try to say $\neg$ is not a connection symbol therefore it cannot has the form $\neg$ behind the close bracket.

I would be very appreciated if someone can help. Thanks

Answer 1

For the purposes of contradiction, assume that $\mathcal L$ has a wff that ends in $\neg$. We will choose $A$ to be such a wff of minimal length.

• $A$ cannot be atomic, since $\neg$ cannot be a symbol anywhere in an atomic formula, much less the end.
• $A$ cannot be of the form $(\neg B)$ or $(B\to C)$, since those forms end in $)$.
• If $A$ were of the form $\forall x B$ where $x$ is some term and $B$ is a wff, then $B$ is also a wff that ends in $\neg$. However, this violates our assumption that $A$ was of minimal length.

This violates the assumption that $A$ is well-formed. Therefore, by contradiction, it follows that no wff can end in $\neg$.

---

Honestly, though, I think any proof that would come after this lemma would be unnecessarily messy. It would be simpler to show that every instance of $\neg$ in a wff must be preceded by $($ and also that no wff can begin with $)$. With those two lemmas, all you need to do is show that no instance of $\neg$ in a wff can be preceded or followed by $)$.