I have begun self-studying Logic (I am a numerical physicist), and I am stuck at the very beginning. I have a problem with the proof of the Unique Readability Theorem for Terms in First Order Logic (but the same issue applies to formulas). The proof is done using Induction on the Length (or Rank) of Terms. However to do that one need first to prove that the recursive definition for the Length (or Rank) of a Term, is indeed a function (i.e. each term has a unique Length). To prove this, one needs to assume that terms can only be written in one way. If I assume that a term can be written in two different ways, there is nothing in the recursive definition of length that prevents it from having two different values for length. This to me look circular!
I can prove that Unique Readability is equivalent to Uniqueness of Length, but I cannot prove both. I am under the impression that, either one assumes order in the set of Terms, taking uniqueness of recursive definition as a axiom, and prove induction, or assumes induction as an axiom and prove uniqueness of recursive definition (order).
Is there a way to prove both Unique Readability and Uniqueness of Length? And if not, why this is not stated clearly? I have read dozens of first order logic book, but none seems to consider this issue. I apologize if this is a stupid question. It is the first time I am using StackExchange, but I am really stuck.
Thank you in advance.
I will try to articulate:
I am not using a specific book, but browsing a lot of them and trying to re-organize their content in a way that can convince myself, because I want to see if I can recover those results. There is something similar for strings in Cori & Lascaux.
Unique readability for terms begin by showing that no term can be a proper initial segment of another. This is done via induction.
To use induction you need order (you need to be able to tell that a term is shorter that another). You start by assuming that your induction hypothesis holds for all terms of length n and then prove it holds for terms of length n+1, by reduction ab absurdum (you assume that on a term of length n+1 it is violated and derive that is should be violated also for terms of length n contradicting the induction hypothesis).
You can see that you are making a lot of untold assumptions here (all term have a length, the length of a term is unique, all length can be compared, all length are positive integers .....). Either you assume all of them (and this to me amount to elevating uniqueness of length to an axiom), or you need to provide a definition of length that ensures all of these assumptions. You cannot say that they hold just because you can write down terms that satisfy them. The set of term is infinite, so the fact that a property holds for any finite subset is not enough.
The definition is done via recursion: if a term is a variable or constant its length is 1. if a term $t= f t_1 ....t_n$ (and $f$ is an $n-$ary function symbol) and the length of each term $t_i$ is $l_i$ then the length of $t$ is $1+\sum l_i$
Obviously if the term $t$ can be written in two ways (say $ft_1t_2t_3$ and $ft_4t_5t_6$), this recursive definition does not ensure that its length is unique, unless $l_1=l_4,l_2=l_5,l_3=l_6$, but why should this be? How can I prove it? For example van Dalen Thm 2.1.6 makes it clear that defining a relation by recursion is not enough to prove that it is a function (i.e. uniqueness).
Unique readability is not required for unique length. An expression like $P \lor Q \land R$ has no unique reading, but it does have a unique length.
This one counterexample shows that Uniqueness of Length does not imply Uniqueness of Readability, let alone that these two are equivalent.
I also want to note that you talk about terms being written in two different ways, but there is no such thing: a term is a string of symbols … any other string of symbols is a different term … or not a term at all. Note that we are talking about Uniqueness of Readability, not Uniqueness of Writability.