Any formula is logically equivalent to a formula with all terms of height ≤ 1.

57 Views Asked by At

i read the book of title "A First Journey Through Logic" written by Martin Hils at page 73.

the problem is i don't understand given the proof's procedures how this process shows that any formula is logical equivalent with formula having therm height equal or less than 1?

I find it challenging to understand how this proof unfolds and, at the same time, I struggle to comprehend how comparing the lengths of formulas demonstrates their logical equivalence.

the height's def in this book may be a number of connective operations, so atomic formula's height is zero.

enter image description here

1

There are 1 best solutions below

5
On

Long comment

The "height's def in this book may be a number of connective operations"; this is the height of a formula. Terms have no connectives.

For a term, the height (or depth) means in a nutshell the number of function symbols: thus $h=0$ for variable and constants, and so on.

The proof consider the atomic formula $Rt_1 \ldots t_n$ and apply induction.

The machinery is to consider terms from right to left (lexicograpich order) and reduce the height one-by-one. Assuming that we have already worked on terms $t_{m+1}, \ldots, t_n$ we have to "reduce" the previous ones.

Consider $t_i=f_i(s_{i,1} \ldots s_{i, k_{i}})$: the terms $s$'s have height one less that that of $t_i$.

Thus we use new variables $y_{i,j}$ and we "equate" them to the $s$'s terms using the formula: $y_{i,j}=s_{i,j}$ whose terms have height less than that of $t_i$.

The equivalence is simply:

$\varphi(t) \leftrightarrow (\varphi [y/t] \land y=t)$.