Fusable Numbers Paper

[Harvey Friedman]

I hadn't known about this Fusable development Avron posted about till now.
I have some questions about this obviously interesting and important
development.

First of all I flirted briefly with some natural numerical representations
of serious proof theoretic ordinals decades ago, but moved on never having
found anything this interesting. This makes me want to take a hard look at
this general topic again, even while I am finishing up #110 on my
downloadables dealing with HUGE and beyond.

I view this paper as some evidence of my longstanding belief that there is
no real limit to how basic and rudimentary and interesting and fundamental
a statement can be with strong metamathematical properties.

CONJECTURE: There are Pi01 statements even more rudimentary and interesting
and fundamental than current Fusable stuff that are independent of the HUGE
cardinal hierarchy - even Pi01 - although I won't live long enough to see
them.

So here are some very first impression questions, some of which may be
easily answered from the paper already.

1. What is the computational complexity of the set of fusable numbers?

2. What is the complexity of the gsp function g as defined in the abstract?

3. What is the logical complexity of the statement mentioned at the end of
the abstract? Prima facie Pi03 but presumably Pi02 by basic considerations?


4. The definition of fusable numbers is as the least set of rationals
containing a given finite set of rationals and closed under a rational
piecewise linear function from Q^2 into Q^2. It has order type epsilon_0.
What can we say about such rationally piecewise linearly generated sets of
rationals,especially in low dimension? Come to think of it, I think I
showed a long time ago even in low dimension that you can simulate the
behavior of Turing machines here. But this fusable operation is obviously
extremely simple compared to arbitrary ones, and it would be interesting to
put one's finger on the right way of saying how simple it is, abstractly.
So there should be a good notion of "rudimentary piecewise linear function"
here. How hard is it to tell whether they generate a well ordered set? What
length well orderings can you get this way?

Harvey Friedman

On Mon, Jun 15, 2020 at 12:29 AM Arnon Avron <aa at tauex.tau.ac.il> wrote:

> Recently I came across a rather new paper: "Fusible numbers and Peano
> Arithmetic", by
> Erickson, Nivasch, and Xu (https://arxiv.org/abs/2003.14342).
> One of the results of this paper is the following:
>
> Consider the algorithm "M(x): if x < 0 return -x, else return M(x -M(x -
> 1))/2." Then
> M terminates on real inputs, although PA cannot prove the statement "M
> terminates on all
> natural inputs."
>
> Now a theorem about the termination of an algorithm, especially one that
> was
> introduced while investigating a mathematical subject that had been
> inspired by a mathematical riddle involving fuses (see in the paper),
> seems to me as `natural' as one might wish.
>
> I would like to know whether other people in this list agree or disagree
> with that.
>
> Arnon Avron
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200615/f31ee3fc/attachment-0001.html>