Prueba de la fórmula recursiva para los "números de fusibles"

Question

El conjunto de los fusibles de los números es un fantástico conjunto de los números racionales se define por una simple regla. La historia está bien contada aquí, pero lo voy a repetir las definiciones. Es la fórmula de la diapositiva 17 que estoy tratando de entender.

Definir $\displaystyle \oplus b = \frac{a+b+1}{2}$. Un número es el fusible si es $0$ o si puede ser escrito como $a \oplus b$ donde $a, b$ son fusible e $|a-b|<1$. Deje que $F$ el conjunto de los fusibles de los números. Más formalmente, $F$ es la intersección de todos los conjuntos de números reales que están cerrados por debajo de los $\oplus$ aplicado a los argumentos, a una distancia máxima de 1.

El conjunto $F$ es un conjunto ordenado de la no-números racionales negativos. La prueba de que es bien ordenado no está incluido en el archivo PDF que he ligado, pero no es difícil mostrar esto. (No sería cierto si no hubiésemos insistido en la condición $|a-b|<1$, por cierto.)

Sorprendentemente, el tipo de orden de $F$ es $\varepsilon_0$. También es cierto que $F$ es cerrado bajo ordinaria, además; no es difícil de probar, pero no sé si se juega una parte en lo que sigue.

Debido a que $F$ es bien ordenado, podemos definir $f(x)$ para ser el fusible número mayor que $x$, para cualquier valor de $x$. Además, el conjunto $m(x) = f(x)-x$. Obviamente hemos de $m(x) = -x$ para $x<0$, mientras que para $x \geq 0$, es el postulado de que $$m(x) = \frac{1}{2}m(x-m(x-1))$$ La pregunta es: ¿por qué es esta última fórmula verdad?

Soy capaz de mostrar una de las necesarias desigualdades, es decir, que $\displaystyle m(x) \leq \frac{1}{2}m(x-m(x-1))$:
Dado que $x$, se observa que la $$(x-1+t) \oplus (x-t+u) = x + u/2$$ Tomar $t = m(x-1)$, lo que garantiza que ($x-1+t$) es de hecho fusible. Ahora $u = m(x-t)$ lo que hace ($x-t+u$) fusible así, y la distancia entre los dos fusibles de los números no puede ser mayor que $1$. De ello se sigue que ($x+u/2$) es fusible, y por lo que $m(x)$ es en la mayoría de la $u/2$ para $u$, lo cual es de $m(x-m(x-1))$.

La pregunta, entonces, es:

¿Cómo podemos demostrar que no hay otra opción de $t$ rendimientos aún más el valor de $m(x)$?

No es difícil mostrar que no hay pérdida de generalidad en centrarse en $x-1+t$ y $x-t+m(x-t)$, pero con avidez minimizar $t$ $t=m(x-1)$ no es de ninguna manera obvia garantizado para producir el valor mínimo de $m(x)$, por lo que puedo ver.

Lo que me estoy perdiendo?

Answer 1

Esa fórmula es el mal-ver aquí (ligada a partir de aquí). Que tenga en cuenta también contiene otras interesantes reflexiones acerca de los fusibles de los números, incluyendo una nueva conjetura que también implica que el tipo de orden de $F$ es $\epsilon_0$.

Aquí un poco de código Java me escribió para explorar estos números. Usted puede colocar una línea roja en algún lugar por mayús-clic en no y, a continuación, haciendo clic o arrastrando (sin Cambio) puede mover un par de líneas verdes tales que $a\oplus b = c$, donde $a$ y $b$ son los números correspondientes a las líneas de color verde y $c$ es el número correspondiente a la línea roja. He utilizado este encontrar, por ejemplo, que 101/64 pueden ser generados en tres formas diferentes: $101/64=3/4\oplus45/32=15/16\oplus39/32=31/32\oplus19/16$.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionAdapter;
import java.awt.event.MouseMotionListener;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class FusibleNumbers {
    static class BinaryNumber {
        long mantissa;
        int exponent;

        public BinaryNumber (long mantissa,int exponent) {
            this.mantissa = mantissa;
            this.exponent = exponent;

            normalize ();
        }

        public void normalize () {
            if (mantissa == 0)
                exponent = 0;
            else
                while ((mantissa & 1) == 0) {
                    mantissa >>= 1;
                    exponent--;
                }
        }

        public double toDouble () {
            return mantissa / (double) (1L << exponent);
        }

        public String toString () {
            return mantissa + "/2^" + exponent;
        }
    }

    static BinaryNumber getMargin (BinaryNumber x) {
        if (x.mantissa < 0)
            return new BinaryNumber (-x.mantissa,x.exponent);
        BinaryNumber m = getMargin (new BinaryNumber (x.mantissa - (1L << x.exponent),x.exponent));
        int newExponent = Math.max (x.exponent,m.exponent);
        m = getMargin (new BinaryNumber ((x.mantissa << (newExponent - x.exponent)) - (m.mantissa << (newExponent - m.exponent)),newExponent));
        m.exponent++;
        m.normalize ();
        if (m.exponent > 50)
            throw new Error ("exponent overflow");
        return m;
    }

    static int xmin;
    static int xother;

    public static void main (String [] args) {
        JFrame frame = new JFrame ();

        final JPanel panel = new JPanel () {
            public void paintComponent (Graphics g) {
                super.paintComponent (g);
                int exponent = 9;
                int scale = 1 << exponent;
                Dimension size = getSize ();
                for (int i = 0;i < size.width;i++) {
                    BinaryNumber b = new BinaryNumber (i,exponent);
                    BinaryNumber m = getMargin (b);
                    double d = b.toDouble () + m.toDouble ();
                    int x = (int) (d * scale + .5);
                    g.drawLine (x,0,x,size.height);
                }
                drawLine (g,size,xmin,Color.RED);
                drawLine (g,size,xother,Color.GREEN);
                drawLine (g,size,2*xmin - scale - xother,Color.GREEN);
            }

            private void drawLine (Graphics g,Dimension size,int x,Color color) {
                g.setColor (color);
                g.drawLine (x,0,x,size.height);
            }
        };

        panel.addMouseListener (new MouseAdapter () {
            boolean ctrl;

            MouseMotionListener motionListener = new MouseMotionAdapter () {
                public void mouseDragged (MouseEvent me) {
                    update (me);
                }
            };

            public void mouseReleased (MouseEvent me) {
                update (me);
                panel.removeMouseMotionListener (motionListener);
            }

            public void mousePressed (MouseEvent me) {
                ctrl = (me.getModifiers () & MouseEvent.SHIFT_MASK) != 0;
                panel.addMouseMotionListener (motionListener);
                update (me);
            }

            void update (MouseEvent me) {
                if (ctrl)
                    xmin = me.getX ();
                else
                    xother = me.getX ();
                panel.repaint ();
            }
        });

        frame.getContentPane ().add (panel);
        frame.setBounds (0,0,1200,200);
        frame.setVisible (true);
    }
}

Answer 2

He ampliado mi nota en un papel, disponible aquí. Un Mathematica biblioteca de funciones útiles para la exploración de los fusibles de los números está disponible aquí, pero yo no he escrito una documentación. Espero que usted puede averiguar lo que las funciones de hacer. Divertirse!

Sólo mencionar brevemente un hecho: $-\log_2\ m(3)$ es en realidad más grande que $2\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow16$, después de Knuth de la flecha hacia arriba en la notación.

De hecho, lo anterior debería ser un comentario, pero no tengo suficiente reputación aquí.