Completitud de modelo y decidibilidad de la estructura aditiva de enteros expandida con una función para una secuencia de Beatty

Información Básica

• ID del Artículo: 2110.01673
• Título: Completitud de modelo y decidibilidad de la estructura aditiva de enteros expandida con una función para una secuencia de Beatty
• Autores: Mohsen Khani, Ali N. Valizadeh, Afshin Zarei
• Clasificación: math.LO (Lógica Matemática)
• Fecha de Publicación: 17 de abril de 2024 (versión final)
• Enlace del Artículo: https://arxiv.org/abs/2110.01673

Resumen

En este artículo se introduce una teoría modelo-completa que axiomatiza completamente la estructura $Z_α = ⟨Z, +, 0, 1, f⟩$, donde $f : x ↦ ⌊αx⌋$ es una función unaria y $α$ es un número trascendental fijo. Cuando $α$ es computable, la teoría es recursivamente enumerable y, por lo tanto, decidible como consecuencia de la completitud. Este resultado se alinea con el tema más general de añadir trazas multiplicativas a los enteros sin perder decidibilidad.

Contexto de Investigación y Motivación

Antecedentes del Problema

1. Problema Central: Investigar la decidibilidad de estructuras expandidas del grupo aditivo de enteros $⟨Z, +⟩$, particularmente la estructura después de añadir la función de secuencia de Beatty $f(x) = ⌊αx⌋$.
2. Significado de la Investigación:
   • Pertenece a la intersección de dos direcciones de investigación activas: por un lado, la decidibilidad de expansiones de $⟨Z, +⟩$ y su clasificación (estructuras estables o inestables)
   • Por otro lado, la investigación de expansiones de la recta real con subgrupos aditivos discretos específicos
3. Limitaciones del Trabajo Existente:
   • Hieronymi en H16 solo probó decidibilidad para el caso de números cuadráticos $α$
   • Para números trascendentales $α$, la decidibilidad de la estructura más general $R_α$ aún no se ha resuelto
   • Se requieren nuevas técnicas para manejar la independencia de diferentes potencias de $f$ en el caso trascendental
4. Motivación de la Investigación:
   • Proporcionar una prueba de decidibilidad para el caso trascendental
   • Utilizar herramientas fundamentales de teoría de modelos y teoría de números para dar una prueba constructiva
   • Sentar las bases para resolver el problema más general de la estructura $R_α$

Contribuciones Principales

1. Establecimiento de Teoría Modelo-Completa: Se construye la teoría $T_α$ que axiomatiza completamente la estructura $Z_α = ⟨Z, +, 0, 1, f⟩$, donde $f(x) = ⌊αx⌋$ y $α$ es un número trascendental.
2. Prueba de Decidibilidad: Cuando $α$ es computable, $T_α$ es recursivamente enumerable, y combinado con la completitud se obtiene decidibilidad.
3. Innovación Técnica:
   • Transformación de relaciones de parte fraccionaria en fórmulas de lógica de primer orden
   • Uso del Lema de Kronecker extendido para manejar fórmulas no algebraicas
   • Desarrollo de técnicas de reducción para manejar fórmulas algebraicas
4. Análisis Teórico: Se prueba que esta estructura posee propiedades de orden estricto y se analiza la estructura de conjuntos definibles.

Explicación Detallada de Métodos

Definición de la Tarea

Se estudia la teoría de primer orden de la estructura $Z_α = ⟨Z, +, 0, 1, f⟩$ en el lenguaje $L = \{+, -, 0, 1, f\}$, donde:

• $Z$ es el conjunto de enteros
• $+$ es la operación de adición
• $f: x ↦ ⌊αx⌋$ es la función de secuencia de Beatty
• $α$ es un número trascendental computable fijo

Marco Técnico Central

1. Expresión Lógica de la Parte Fraccionaria

Observación Clave: Aunque la parte fraccionaria no está en el lenguaje, se pueden describir sus propiedades clave en $L$ de la siguiente manera:

Para $a, b ∈ Z$ y $n ∈ N$:

• $f(na) = nf(a) + i$ si y solo si $\frac{i}{n} < [αa] < \frac{i+1}{n}$
• $[αa] + [αb] < 1$ si y solo si $f(a+b) = f(a) + f(b)$
• $[αa] < [αb]$ si y solo si $f(b-a) = f(b) - f(a)$

donde $[x] = x - ⌊x⌋$ denota la parte fraccionaria.

2. Estrategia de Clasificación de Fórmulas

Se clasifican sistemáticamente las fórmulas $L$ en dos categorías:

Fórmulas No Algebraicas: De la forma $\sum_{i=0}^{\ell_1} n_{1i}[αf^i(x_1)] + \cdots + \sum_{i=0}^{\ell_k} n_{ki}[αf^i(x_k)] \triangleleft \sum_{i=0}^{k'} m_i[αy_i] + [αq] + \ell$

Fórmulas Algebraicas: De la forma $h_1(x_1) + \cdots + h_n(x_n) = y$, donde $h_i(x)$ son $f$-polinomios.

3. Lema de Kronecker Extendido

Teorema 3.4 (Lema de Kronecker Extendido): Para cada $n ∈ N$, el siguiente conjunto de $(n+1)$-tuplas es denso en $(0,1)^{n+1}$: $\{([αa], [αf(a)], [αf^2(a)], \ldots, [αf^n(a)]) : a ∈ N\}$

Esto es cierto porque la trascendencia de $α$ garantiza que $1, α, α^2, \ldots, α^n$ son linealmente independientes sobre $\mathbb{Q}$.

Estrategia de Prueba de Completitud de Modelo

Paso 1: Tratamiento de Fórmulas No Algebraicas

• Lema 3.6: Para cada conjunto de fórmulas no algebraicas $Γ(x; \bar{y})$, existe una fórmula sin cuantificadores $χ(\bar{y})$ tal que $Z_α ⊨ ∀\bar{y}(∃xΓ(x; \bar{y}) ↔ χ(\bar{y}))$
• Se utiliza el algoritmo de eliminación de Fourier-Motzkin para manejar sistemas de desigualdades lineales

Paso 2: Técnicas de Reducción

• Lema 4.12 (Truco Técnico): Se reduce un sistema mixto que contiene fórmulas algebraicas a un sistema no algebraico con menos variables
• Idea clave: Mediante la introducción de variables auxiliares $w$ y términos $h(x)$, se transforman ecuaciones algebraicas multivariables al caso univariable

Paso 3: Clausura Algebraica

• Lema 4.13: Si $M_1 ⊆ M_2$ son modelos de $T_α$, $b ∈ M_1$, $a ∈ M_2$ y $h(a) = b$, entonces $a ∈ M_1$
• Garantiza que las subestructuras sean cerradas bajo operaciones inversas de diferentes potencias de $f$

Sistema de Axiomatización

Esquema de Axiomas 1 (Cálculo de $f(n)$)

Para $n ∈ N$ y $0 ≤ i < n$ tal que $\frac{f(n)}{n} ≡ i$: $f(\underbrace{1 + \cdots + 1}_{n \text{ veces}}) = \underbrace{f(1) + \cdots + f(1)}_{n \text{ veces}} + \underbrace{1 + \cdots + 1}_{i \text{ veces}}$

Axioma 2 (Propiedades Fundamentales)

1. $∀x∀y(f(x+y) = f(x) + f(y) ∨ f(x+y) = f(x) + f(y) + 1)$
2. $∀x(f(-x) = -f(x) - 1)$
3. $∀y∃x(\bigvee_{i=0}^{f(1)} y + i = f(x))$
4. La relación $[αx] < [αy]$ es un orden lineal denso

Esquema de Axiomas 3 (Densidad)

Para $m, n ∈ N$: Si $\bigwedge_{i=1}^n [αz_i] < [αy_i]$, entonces existe al menos $m$ valores distintos de $x$ tales que $\bigwedge_{i=1}^n [αy_i] < [αf^i(x)] < [αz_i]$.

Resultados Experimentales y Análisis Teórico

Resultados Principales

Teorema Principal: Sea $α$ un número real trascendental, entonces:

1. $T_α$ es una axiomatización completa y modelo-completa de la estructura $Z_α$
2. $Z_α$ posee propiedades de orden estricto
3. Cuando $α$ es computable, $T_α$ es decidible

Propiedades de Conjuntos Definibles

1. Conjuntos Estructurados: Las fórmulas sin potencias de $f$ definen clases de congruencia (progresiones aritméticas infinitas)
2. Conjuntos Aleatorios: Los conjuntos definidos por fórmulas con potencias de $f$ no contienen progresiones aritméticas infinitas
3. Propiedades Mixtas: El rango de cualquier $f$-polinomio contiene progresiones aritméticas finitas de longitud arbitraria

Proposición 5.1: Para $h(x) = \sum_{i=0}^k m_i f^i(x)$, para cada $n ∈ N$, existe una progresión aritmética de longitud $n$ en el rango de $h$.

Trabajo Relacionado

1. Hieronymi H16: Probó decidibilidad de $R_α$ para el caso cuadrático
2. Conant & Pillay CP18: Investigaron la clasificación de estabilidad de expansiones de $⟨Z, +⟩$
3. Günaydin & Özsahakyan GO22: Investigación independiente, tratando secuencias de Beatty como predicados en lugar de funciones
4. Khani & Zarei KZ22: Prueba simplificada para el caso de la razón áurea

Conclusiones y Discusión

Conclusiones Principales

1. Se generalizó exitosamente el resultado de Hieronymi de números cuadráticos a números trascendentales
2. Se proporcionó una prueba constructiva de completitud de modelo
3. Se estableció un nuevo marco técnico para manejar el caso trascendental

Limitaciones

1. Se requiere computabilidad de $α$ para garantizar enumerabilidad recursiva
2. El problema más general de la estructura $R_α$ aún no se ha resuelto
3. La eliminación de cuantificadores en el caso trascendental parece no ser viable

Direcciones Futuras

1. Problema Abierto: Decidibilidad y completitud de modelo de la estructura $⟨Z, <, +, -, 0, 1, f⟩$ (con orden de enteros añadido)
2. Generalización a otros tipos de números trascendentales
3. Investigación de combinaciones más complejas de secuencias de Beatty

Puntos de Innovación Técnica

1. Completitud de Modelo Efectiva: El proceso de prueba es constructivo, permitiendo eliminación de cuantificadores efectiva
2. Conexión o-minimal: La conexión entre la parte no algebraica $T_{nalg}$ y teorías o-minimales
3. Marco Unificado: Método unificado para manejar fórmulas algebraicas y no algebraicas

Evaluación Profunda

Ventajas

1. Contribución Teórica: Generalización significativa de resultados conocidos, el paso de números cuadráticos a trascendentales es un avance importante
2. Innovación Técnica: La aplicación del Lema de Kronecker extendido y el diseño de técnicas de reducción son muy creativos
3. Universalidad de Métodos: Las técnicas pueden aplicarse al caso de números algebraicos
4. Prueba Constructiva: Se proporciona un resultado de completitud de modelo efectivo

Deficiencias

1. Complejidad Computacional: Aunque teóricamente decidible, la complejidad práctica puede ser muy alta
2. Limitaciones de Expresividad: No puede manejar ciertas estructuras relacionadas naturales
3. Complejidad Técnica: La prueba involucra múltiples lemas técnicos complejos

Impacto

1. Valor Académico: Proporciona nuevas técnicas y resultados para el campo de lógica matemática y teoría de modelos
2. Perspectivas de Aplicación: Sienta las bases para investigar estructuras aritméticas más complejas
3. Contribución Metodológica: Demuestra cómo manejar sistemáticamente este tipo de estructuras mixtas algebraico-analíticas

Escenarios Aplicables

1. Investigación de teoría de decidibilidad en lógica matemática
2. Problemas diofánticos en geometría aritmética
3. Demostración automática de teoremas en ciencias de la computación
4. Investigación de propiedades de distribución en teoría de números

Referencias

• H16 P. Hieronymi, Expansions of the ordered additive group of real numbers by two discrete subgroups
• KZ22 M. Khani and A. Zarei, The additive structure of integers with the lower Wythoff sequence
• HM+21 P. Hieronymi et al., Decidability for Sturmian words
• C60 I. G. Connell, Some properties of Beatty sequences II