0
$\begingroup$

I'm having trouble following this proof about the syntax of first-order logic. When $A$ and $B$ are expressions, we say that $B$ is an initial segment of $A$ if and only if $A$ can be obtained by concatenating some (possibly no) symbols to the (right-hand) end of $B$. For example:

$$\neg$$

is an initial segment of $$ \neg \neg A$$

Now the inductive hypothesis is that for some arbitrary $A$ every sentence shorter than $A$ has this property. Then we reason by cases. The atomic case is straightforward, but the proof lost me on the case for negation. It says:

Say that $A$ is $\neg B$ for some sentence $B$. Let $A^*$ be any sentence which is an initial segment of $A$. So $A^*$ is $\neg B^*$, for some sentence $B^*$. Evidently, $B^*$ is an initial segment of $B$. But $B$ and $B^*$ are both sentences that are shorter than $A$; so by the induction hypothesis, $B^*$ must just be $B$ itself. Hence $A^*$ is $A$ itself, and so $A$ has the induction property.

This proof-segment is quite quick and compressed, and I'm not seeing the moves that it presents as obvious.

First of all:

Why is $B^*$ 'evidently' an initial segment of $B$? After all, $B$ and $B^*$ could be anything, string of conjunctions, conditionals, whatever? The author treats this as an obvious step, but I don't see it.

Second:

How could $B^*$ not be $B$ when we have said that $A$ is $\neg B$ and $ \neg B^*$ is an initial segment of $A$?

Any help would be much appreciated.

$\endgroup$
3
  • $\begingroup$ We have that $A$ is $(\lnot B)$ and we assume that we can find $A^*$ that is an initial segment of $A$; this means that $A$ must be $(\lnot \text { something})$ and we call that something $B^*$. Obviously $B^*$ must be an initial segment of $B$: try with an example: $A$ is $\lnot (C \land D)$ and thus $B$ is $(C \land D)$ and thus $B^*$ must be this way: $(C \ldots$. $\endgroup$
    – Mauro ALLEGRANZA
    Nov 1, 2022 at 19:20
  • $\begingroup$ If $B^*$ is an initial segment of $B$ we apply the induction hypotheses that holds because $B$ is shorter than $A$ and thus $B^*$ is equal to $B$ itself by assumption. $\endgroup$
    – Mauro ALLEGRANZA
    Nov 1, 2022 at 19:24
  • $\begingroup$ sadly I don't think I follow with the first one $\endgroup$
    – Dan Öz
    Nov 1, 2022 at 21:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .