1
$\begingroup$

If $\mathcal{L}$ is any first-order language then I want to prove that no wff have $\neg$ and $)$ next to each other (in any order) in the string of symbols that make up the wff. As a hint it has been given that I should start by proving that no wff ends with the symbol $\neg$.

Intuitively, this makes sense as I think $\neg$ should be placed in front of something in order to negate it. However, I struggle to do this more formally.

My idea is the following:

By Enderton (p.74) I have that "The set of well-formed formulas (wffs, or just formulas) is the set of expressions that can be built up from the atomic formulas by applying (zero or more times) the operations $E_{\neg}$, $E_\to$,and $Q_i$ (i=1,2,...)" where

$E_{\neg}(\gamma)=(\neg \gamma)$

$E_\to(\gamma,\delta)=(\gamma \to \delta)$

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

I think it is rather clear that I cannot form $\gamma \neg$ from either $E_{\neg}$, $E_\to$ or $Q_i$ if $\gamma$ is an atomic formula. But I think there should be something else to the solution. My questions are therefore:

1) Is there another way to get started with this problem as my current approach only provides me with a more intuitive feeling?

2) $\neg$ is a unary operation according to Enderton but does this means that $\neg$ "needs" some terms on the right side of it in order to be an atomic formula?

I am quite new to mathematical logic hence the probably basic questions.

$\endgroup$
1
  • $\begingroup$ The most common way of proving this type of problem is by induction on formulas, most mathematical logic textbooks include a section on the topic. $\endgroup$
    – Sam
    Apr 22, 2020 at 11:17

1 Answer 1

0
$\begingroup$

From the substitution rules, we see that in any wff

  • $\neg$ can only be preceded by $($ and be followed by the start of a wff
  • the start of a wff is either an atom or $($

This immediately shows that $\neg$ can never appear beside $)$ in a wff.

$\neg$ is not an atomic formula because $\neg$ is a logical connective that just happens to connect to only one argument. It does not constitute a predicate.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .