I'm reading Peter G. Hinman-Fundamentals of Mathematical Logic, I'm new with stuff like proofs, and as newbie I'm not used to proving anything, so I'm jammed in the exercises of the book of the section 1.1, I really want to solve the exercise of proving that an initial proper segment of a sentence can't be a sentence, I think this can involve induction, but I really can't tackle the problem.

Any hint is appreciated. Thanks in advance!

I posted a link to the book, but it was erased, please see the caveman comment below for see the problem.

  • 2
    $\begingroup$ You shouldn't expect people to download the book. It would be better to link the image that you posted in chat which explains the question. The answer by MyWhy does not address the question so I am confused as to why you accepted it. $\endgroup$ – user58512 Mar 14 '13 at 11:51
  • $\begingroup$ Because he uses infix notation and your book uses prefix notation $\endgroup$ – user58512 Mar 14 '13 at 23:00
  • $\begingroup$ @caveman , does prefix notation is the same " polish notation " ? $\endgroup$ – Fawzy Hegab Mar 24 '13 at 19:49
  • $\begingroup$ yes ${}{}{}{}{}$ $\endgroup$ – user58512 Mar 24 '13 at 19:52

Hint ,

1- an expresion is an wff iff has equal number of left and right paretheses

so show that the intial segment doesn't have the equality so it's not a wff .

and you can do this as follows

let $ A , B$ are wffs $Q = ( A $^$ B ) $ the intial segments for this Wff are


(intial segment of A



(A^intial segment of B


show that in every case that the number of left paretheses is NOT EQUAl to # of right paretheses .

and maked the same thing with negation and conjuction and so on

" first prove the same things with A , B as propositional ( sentence ) symbols ( variables ) to make the induction complete .

  • $\begingroup$ Hi. This is an old answer so I don't know if it's normal to comment on this at this time. I noticed that "an expresion is an wff iff has equal number of left and right paretheses" is not true, take the expression $()$, which is not a formula. $\endgroup$ – Jihoon Kang Jan 23 '18 at 10:49

In your book the expression $$(x \lor (\lnot y)) \land (\lor z w)$$ is written in prefix notation like this $$\land \lor x \lnot y \lor z w.$$

To show that no proper initial segment of a prefix sentence is a prefix sentence we can annotate sentences with a counter that tells you how many things you are to read from it: Since we're reading one sentence we start with 1: $$^1 \land ^2 \lor ^3 x ^2 \lnot ^2 y ^1 \lor ^2 z ^1 w ^0$$ then $\land$ need 2 parameters so we add 1 to the counter, then $\lor$ needs 2 parameters so we add 1 to the counter again, reading an $x$ gives the first parameter of the $\lor$ so we subtract one, seeing a $\lnot$ means we still need to read another so the counter stays the same, and we continue on until we get to the end.. at that point we need nothing more, So:

Lemma When you annotate a valid sentence you have 0 at the end and never before.
proof: Induction on the structure of sentences:

  • (variable case) $^1 x ^0$
  • (logical not case) $^1 \lnot ^1 X ^0$ where $X$ is a valid sentence.
  • (binary connective case) $^1 \land ^2 \bar X ^1 Y ^0$ where $X$ and $Y$ are valid sentences, and $\bar X$ denotes we take the annotation of $X$ and add 1 to everything.

Corollary No initial segment of a sentence is a valid sentence.
proof: Annotate the initial segment and notice it doesn't end in 0.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.