Autor Tema: Una aritmética con un solo operador

0 Usuarios y 1 Visitante están viendo este tema.

16 Agosto, 2016, 04:58 pm
Leído 9882 veces

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Aquí estoy de nuevo. Esta vez espero no desaparecer  :)

Lo que sigue es un mero ejercicio que puede verse como una curiosidad: una aritmética con una sola operación.

Como sabemos, la aritmética de peano (AP) se construye con un operador monádico S, interpretado como "el siguiente de" y dos operadores diádicos + y \( \cdot{} \) interpretados como la suma y el producto usuales.
Construiremos una teoría C con un único functor \( f \) de orden 3 y mostraremos que es equivalente a la aritmética de Peano (con un functor monádico S y dos functores diádicos + y \( \cdot  \) que definiremos a partir de \( f \)). Esto es, probaremos que \( C\vdash AP\wedge AP\vdash C \)

Consideremos el lenguaje de C

\( L=\{x_i, 0, f, =, \forall, \rightarrow, \neg, |\} \)

con el que definimos los siguientes axiomas

  • C1. \( \exists !y\;\forall x\;f(x,y,0)=x \)

lo que permite asignar un nombre al designador

  \( y|\forall x\;f(x,y,0)=x\equiv 1 \)

Abreviamos además:

  \( x'\equiv f(x,1,1) \)

Y a continuación escribimos el resto de los axiomas.

  • C2. \( \forall x\;x'\neq 0 \)
  • C3. \( \forall xy\;x'=y'\rightarrow x=y \)
  • C4. \( \forall xy\;f(y,0,x)=x \)
  • C5. \( \forall xyz\;f(x,y,z')=f(x,y,z)' \)
  • C6. \( \forall xy\;f(x,y',0)=f(x,y,x) \)
  • C7. Para cada fórmula \( \phi \) con al menos una variable libre \( x \); es un axioma:
    \( \phi (0)\;\wedge\;\forall x\;(\phi (x)\rightarrow \phi (x'))\rightarrow \forall x\;\phi(x) \)

Intuitivamente, \( f(x,y,z)=xy+z \). Con esta interpretación puede verse que los axiomas son verdaderos para el modelo estándar.  El 1 se interpreta como el único natural tal que para todo natural \( n \) se cumple que \( n\cdot 1+0=n \). El siguiente de \( n \) es \( n\cdot 1+1 \) y enseguida probaremos que el siguiente de 0 es 1.

Teoremas:

Vamos a probar que C es una teoría aritmética con el operador monadico S y los operadores diadicos + y \( \cdot{} \) definidos así:

  • \( Sx\equiv f(x,1,1) \) (\( \equiv{x'} \))
  • \( x+y\equiv f(x,1,y) \)
  • \( x\cdot y\equiv f(x,y,0) \)
   
T1. \( \forall x\;f(x,1,0)=x \)

  por C1 y definición de 1.

T2. \( 1=0' \)

  \( \forall x\;f(x,0',0)\overset{C6}{=}f(x,0,x)\overset{C4}{=}x \)

  Pero por C1 y definición de 1, 1 es el único que tiene esa propiedad. Luego, \( 0'=1 \)

T3. \( \forall x\;x+0=x \)

  \( x+0\overset{def +}{=}f(x,1,0)\overset{T2}{=}f(x,0',0)\overset{C6}{=}f(x,0,x)\overset{C4}{=}x \)

T4. \( \forall xy\;x+y'=(x+y)' \)

  \( x+y'\overset{def+}{=}f(x,1,y')\overset{C5}{=}f(x,1,y)'\overset{def+}{=}(x+y)' \)

T5. \( \forall x\:x\cdot 0=0 \)

  \( x\cdot 0\overset{def\cdot}{=}f(x,0,0)\overset{C4}{=}0 \)

T6. (caracterización de f) \( \forall xyz\;f(x,y,z)=x\cdot y+z \)

  por inducción sobre \( z \) en la fórmula \( \phi(z)\equiv{\forall{xy}\;f(x,y,z)=x\cdot y+z} \)
  si vale para \( z=0 \), \( f(x,y,0)\overset{def\cdot}{=}x\cdot y\overset{T3}{=}x\cdot y+0 \), esto es, \( \phi(0) \)
  si vale para \( z \), esto es, si \( \phi(z)\equiv{f(x,y,z)=x\cdot y+z} \) (HI), entonces
  \( f(x,y,z')\overset{C5}{=}f(x,y,z)'\overset{HI}{=}(x\cdot y+z)'\overset{T4}{=}x\cdot y+z' \), esto es, \( \phi(z') \)
  Entonces, por C7 aplicado a \( \phi(z)\equiv{\forall{xy}\;f(x,y,z)=x\cdot y+z} \), se tiene la tesis.

T7. \( \forall xy\;x\cdot y'=x\cdot y+x \)

\( x\cdot y'\overset{def\cdot}{=}f(x,y',0)\overset{C6}{=}f(x,y,x)\overset{T6}{=}x\cdot y+x \)

T8. C es equivalente a AP (\( C\vdash AP\wedge AP\vdash C \))

Sean S, + y \( \cdot{} \) los operadores ya definidos en C, entonces, efectivamente:

  • \( \forall x\;x'\neq 0 \) (por C2)
  • \( \forall xy\;x'=y'\rightarrow x=y \) (por C3)
  • \( \forall x\;x+0=x \) (por T3)
  • \( \forall xy\;x+y'=(x+y)' \) (por T4)
  • \( \forall x\:x\cdot 0=0 \) (por T5)
  • \( \forall xy\;x\cdot y'=x\cdot y+x \) (por T7)
  • Para cada fórmula \( \phi \) con al menos una variable libre \( x \); es un axioma:
       \( \phi (0)\;\wedge\;\forall x\;(\phi (x)\rightarrow \phi (x'))\rightarrow \forall x\;\phi(x) \)

Que son los axiomas de AP. Por lo tanto C es una teoría aritmética, esto es \( C\vdash AP \)

La prueba de que \( AP\vdash C \) es inmediata a partir de la caracterización \( f(x,y,z)=x\cdot y+z \) y las propiedades aritméticas usuales.

Saludos.
Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

17 Agosto, 2016, 02:54 am
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Muy lindo. ?Necesitás un comentario más académico? :)

Me resulta interesante notar que en ciertas librerías de programación,  aunque no para enteros sino para reales, se define un operador ternario para xy+z.
Si el procesador tiene esta operación predefinida, puede ejecutarse como una única instrucción en bloque.



17 Agosto, 2016, 04:04 am
Respuesta #2

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
¿Un ordenador procesando reales...?

¡Gusto en saludarte argentinator! :D
Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

17 Agosto, 2016, 04:25 am
Respuesta #3

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
No. Sòlo reales con cierta cantidad fija de dìgitos.

17 Agosto, 2016, 03:22 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola. Lo he mirado sin pararme en los detalles, porque estoy bastante liado con la informática doméstica, así que no he podido pensar lo que voy a plantear, pero, ¿no se podría poner un axioma que dijera

\( \exists ! x\forall yz\, f(x,y,z)=z \)

y definir 0 como ese único x?

17 Agosto, 2016, 05:48 pm
Respuesta #5

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
¿no se podría poner un axioma que dijera

\( \exists ! x\forall yz\, f(x,y,z)=z \)

y definir 0 como ese único x?

¡Sí! Y si lo anotamos conmutando las dos primeras componentes de la terna nos ahorramos el axioma C4

Sería así:

\( L=\{x_i, f, =, \forall, \rightarrow, \neg, |\} \)

El axioma que propones:

  • C0. \( \exists ! x\forall yz\, f(y,x,z)=z \)

donde abreviamos el designador implicado

   \( 0\equiv{x|\forall yz\, f(y,x,z)=z} \)

y tenemos inmediatamente como teorema el antiguo axioma C4

   \( \forall xy\;f(y,0,x)=x \)


Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

17 Agosto, 2016, 06:01 pm
Respuesta #6

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Paso en limpio. Se presenta una teoría equivalente a la aritmética de Peano cuyo lenguaje tiene como único signo eventual un functor \( f \) de orden 3

Sea el lenguaje

\( L=\{x_i, f, =, \forall, \rightarrow, \neg, |\} \)

Definimos:
  • C0. \( \exists ! x\forall yz\, f(y,x,z)=z \)

abreviamos

   \( 0\equiv{x|\forall yz\, f(y,x,z)=z} \)

Suigiente teorema:

  • C1. \( \exists !y\;\forall x\;f(x,y,0)=x \)

abreviamos

  \( y|\forall x\;f(x,y,0)=x\equiv 1 \)

abreviamos además:

  \( x'\equiv f(x,1,1) \)

Y a continuación escribimos el resto de los axiomas.

  • C2. \( \forall x\;x'\neq 0 \)
  • C3. \( \forall xy\;x'=y'\rightarrow x=y \)
  • C5. \( \forall xyz\;f(x,y,z')=f(x,y,z)' \)
  • C6. \( \forall xy\;f(x,y',0)=f(x,y,x) \)
  • C7. Para cada fórmula \( \phi \) con al menos una variable libre \( x \); es un axioma:
    \( \phi (0)\;\wedge\;\forall x\;(\phi (x)\rightarrow \phi (x'))\rightarrow \forall x\;\phi(x) \)

Dejé la misma numeración de los axiomas para que se puedan seguir las pruebas del primer post, agregando C0 y eliminando C4 que sigue inmediatamente de C0.

Saludos.
Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

17 Agosto, 2016, 09:01 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Estaba pensando si sería posible enunciar todos los axiomas sin signos definidos. Obviamente, en teoría es posible, la cuestión es si se puede hacer de forma más elegante que la obvia, pero no he obtenido nada interesante.

17 Agosto, 2016, 09:11 pm
Respuesta #8

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
¿Quieres decir, sin signos eventuales, sin functores ni constantes?
Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

17 Agosto, 2016, 09:33 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Quieres decir, sin signos eventuales, sin functores ni constantes?

Quiero decir usando sólo \( f \), sin necesidad de que en los axiomas aparezcan los signos definidos 0 y \( x' \). Obviamente puede hacerse sustituyéndolos por sus definiciones, pero así queda un mero monstruo ilegible. Me preguntaba si sería posible dar unos axiomas para \( f \) que resulten naturales (en el mismo sentido en que tus axiomas lo son) antes de definir 0, 1, siguiente, suma y producto.

Pero bueno, era pensar por pensar.