Some facts regarding equational systems

[martdowd at aol.com]

FOM,

In preparation for a new paper on the specialized Cook conjecture
I have written a paper
 "Some Facts Regarding Equational Systems"
 https://www.researchgate.net/publication/346448465
The main content is a correction to the consistency proof of $\{cal L}$A
given in an earlier paper.  Various other facts of interest about
${\cal L}$A and related systems ("small Grzegorczyk classes") are given.

The list of sections is as follows.
  Introduction
  Definitions
  C-terms in ${\cal L}_0$A and ${\cal E}_0$A
  Basic facts about ${\cal E}_1$A
  The O function of ${\cal L}_0$A
  Equality in ${\cal L}_1$A
  Recursion on $m$-adic notation in ${\cal L}_1$A
  Two variable recursion in ${\cal L}_1$A
  Godel pairing function in ${\cal L}_1$A
  Adding propositional connectives to ${\cal L}_1$A
  Equality in ${\cal E}_1$A
  Adding propositional connectives to ${\cal E}_1$A
  Further facts about ${\cal E}_1$A
  Adding $\leq$ to ${\cal E}_1$A
  Further facts about ${\cal L}_1$A
  Godel pairing function in ${\cal E}_2$A
  ${\cal E}_{i+1}$A simulates ${\cal L}_i$A, $i=0,1$
  Review of $\LA$ valuation function
  $\LA$ consistency proof

In section 13 it is shown that $(x-y)+y=(y-x)+x$, where $-$ is limited
subtraction, is provable in ${\cal E}_1$-arithmetic.  This is proved
in Goodstein's recursive number theory book by two-variable induction.
It is assumed as an axiom of ${\cal L}^2$-arithmetic in Rose's book on
subrecursion.  If anyone knows of a proof please send me an email.

Also, please send me an email if you have any comments on the consistency
proof.

I noticed that many facts which are well-known for ${\cal L}$A in fact
hold for ${\cal L}_1$A, which is ${\cal L}$A with iterated concatenation
omitted.  The functions definable in ${\cal L}_1$A are those computable in
polynomial time and linear space by a (single tape) Turing machine.
(This is shown in my PhD thesis.)

Clearly this class includes a great majority of functions encountered in
meta-mathematics.  A question of interest is, what are some mathematically
interesting functions which are in ${\cal L}$, but not in ${\cal L}_1$?

Martin Dowd

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20201128/924d93ef/attachment.html>