Completezza di modello e decidibilità della struttura additiva degli interi espansa con una funzione per una sequenza di Beatty

Informazioni di base

• ID articolo: 2110.01673
• Titolo: Completezza di modello e decidibilità della struttura additiva degli interi espansa con una funzione per una sequenza di Beatty
• Autori: Mohsen Khani, Ali N. Valizadeh, Afshin Zarei
• Classificazione: math.LO (Logica Matematica)
• Data di pubblicazione: 17 aprile 2024 (versione finale)
• Link articolo: https://arxiv.org/abs/2110.01673

Riassunto

Questo articolo introduce una teoria modello-completa che assiomatizza completamente la struttura $Z_α = ⟨Z, +, 0, 1, f⟩$, dove $f : x ↦ ⌊αx⌋$ è una funzione unaria e $α$ è un numero trascendente fisso. Quando $α$ è calcolabile, la teoria è ricorsivamente enumerabile e, di conseguenza della completezza, è decidibile. Questo risultato si allinea con il tema più generale di aggiungere tracce di moltiplicazione agli interi senza perdere la decidibilità.

Contesto di ricerca e motivazione

Contesto del problema

1. Problema centrale: Studiare la decidibilità delle strutture espanse del gruppo additivo degli interi $⟨Z, +⟩$, in particolare le proprietà strutturali dopo l'aggiunta della funzione della sequenza di Beatty $f(x) = ⌊αx⌋$.
2. Significato della ricerca:
   • Si trova all'intersezione di due direzioni di ricerca attive: da un lato riguarda la decidibilità e la classificazione delle espansioni di $⟨Z, +⟩$ (strutture stabili o instabili)
   • Dall'altro riguarda lo studio della retta reale e delle espansioni di sottogruppi additivi discreti specifici
3. Limitazioni dei lavori esistenti:
   • Hieronymi in H16 ha provato la decidibilità solo nel caso di numeri quadratici $α$
   • Per il caso di numeri trascendenti $α$, la decidibilità della struttura più generale $R_α$ rimane irrisolta
   • Sono necessarie nuove tecniche per affrontare l'indipendenza di diverse potenze di $f$ nel caso trascendente
4. Motivazione della ricerca:
   • Fornire una prova di decidibilità nel caso trascendente
   • Fornire una prova costruttiva utilizzando strumenti fondamentali della teoria dei modelli e della teoria dei numeri
   • Gettare le basi per risolvere il problema più generale della struttura $R_α$

Contributi principali

1. Stabilimento di una teoria modello-completa: Costruzione della teoria $T_α$ che assiomatizza completamente la struttura $Z_α = ⟨Z, +, 0, 1, f⟩$, dove $f(x) = ⌊αx⌋$ e $α$ è un numero trascendente.
2. Prova della decidibilità: Quando $α$ è calcolabile, $T_α$ è ricorsivamente enumerabile; combinato con la completezza, si ottiene la decidibilità.
3. Innovazioni tecniche:
   • Trasformazione delle relazioni di parte frazionaria in formule di logica del primo ordine
   • Utilizzo del lemma di Kronecker esteso per gestire formule non algebriche
   • Sviluppo di tecniche di riduzione per gestire formule algebriche
4. Analisi teorica: Prova che la struttura possiede proprietà di ordine stretto e analisi della struttura degli insiemi definibili.

Spiegazione dettagliata dei metodi

Definizione del compito

Studio della teoria del primo ordine della struttura $Z_α = ⟨Z, +, 0, 1, f⟩$ nel linguaggio $L = \{+, -, 0, 1, f\}$, dove:

• $Z$ è l'insieme degli interi
• $+$ è l'operazione di addizione
• $f: x ↦ ⌊αx⌋$ è la funzione della sequenza di Beatty
• $α$ è un numero trascendente calcolabile fisso

Struttura tecnica centrale

1. Espressione logica della parte frazionaria

Osservazione chiave: Sebbene la parte frazionaria non sia nel linguaggio, le proprietà chiave della parte frazionaria possono essere descritte in $L$ nel seguente modo:

Per $a, b ∈ Z$ e $n ∈ N$:

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

dove $[x] = x - ⌊x⌋$ denota la parte frazionaria.

2. Strategia di classificazione delle formule

Classificazione sistematica delle formule $L$ in due categorie:

Formule non algebriche: della 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$

Formule algebriche: della forma $h_1(x_1) + \cdots + h_n(x_n) = y$, dove $h_i(x)$ sono $f$-polinomi.

3. Lemma di Kronecker esteso

Teorema 3.4 (Lemma di Kronecker esteso): Per ogni $n ∈ N$, il seguente insieme di $(n+1)$-uple è denso in $(0,1)^{n+1}$: $\{([αa], [αf(a)], [αf^2(a)], \ldots, [αf^n(a)]) : a ∈ N\}$

Questo vale perché la trascendenza di $α$ garantisce che $1, α, α^2, \ldots, α^n$ siano linearmente indipendenti su $\mathbb{Q}$.

Strategia di prova della completezza di modello

Passo 1: Gestione delle formule non algebriche

• Lemma 3.6: Per ogni insieme di formule non algebriche $Γ(x; \bar{y})$, esiste una formula senza quantificatori $χ(\bar{y})$ tale che $Z_α ⊨ ∀\bar{y}(∃xΓ(x; \bar{y}) ↔ χ(\bar{y}))$
• Utilizzo dell'algoritmo di eliminazione di Fourier-Motzkin per gestire sistemi di disuguaglianze lineari

Passo 2: Tecniche di riduzione

• Lemma 4.12 (Tecnica tecnica): Riduzione di sistemi misti contenenti formule algebriche a sistemi non algebrici con meno variabili
• Idea chiave: Attraverso l'introduzione di variabili ausiliarie $w$ e termini $h(x)$, trasformazione di equazioni algebriche multivariabili al caso univariato

Passo 3: Chiusura algebrica

• Lemma 4.13: Se $M_1 ⊆ M_2$ sono modelli di $T_α$, $b ∈ M_1$, $a ∈ M_2$ e $h(a) = b$, allora $a ∈ M_1$
• Garantisce la chiusura della sottostruttura rispetto alle operazioni inverse di $f$ in diverse potenze

Sistema assiomatico

Schema di assiomi 1 (Calcolo di $f(n)$)

Per $n ∈ N$ e $0 ≤ i < n$ con $\frac{f(n)}{n} ≡ i$: $f(\underbrace{1 + \cdots + 1}_{n \text{ volte}}) = \underbrace{f(1) + \cdots + f(1)}_{n \text{ volte}} + \underbrace{1 + \cdots + 1}_{i \text{ volte}}$

Assioma 2 (Proprietà fondamentali)

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 relazione $[αx] < [αy]$ è un ordine lineare denso

Schema di assiomi 3 (Densità)

Per $m, n ∈ N$: Se $\bigwedge_{i=1}^n [αz_i] < [αy_i]$, allora esistono almeno $m$ diversi $x$ tali che $\bigwedge_{i=1}^n [αy_i] < [αf^i(x)] < [αz_i]$.

Risultati sperimentali e analisi teorica

Risultati principali

Teorema principale: Sia $α$ un numero reale trascendente, allora:

1. $T_α$ è un'assiomatizzazione completa e modello-completa della struttura $Z_α$
2. $Z_α$ possiede proprietà di ordine stretto
3. Quando $α$ è calcolabile, $T_α$ è decidibile

Proprietà degli insiemi definibili

1. Insiemi strutturati: Le formule che non contengono potenze di $f$ definiscono classi di congruenza (progressioni aritmetiche infinite)
2. Insiemi casuali: Gli insiemi definiti da formule contenenti potenze di $f$ non contengono progressioni aritmetiche infinite
3. Proprietà miste: Il codominio di qualsiasi $f$-polinomio contiene progressioni aritmetiche finite di lunghezza arbitraria

Proposizione 5.1: Per $h(x) = \sum_{i=0}^k m_i f^i(x)$, per ogni $n ∈ N$, il codominio di $h$ contiene una progressione aritmetica di lunghezza $n$.

Lavori correlati

1. Hieronymi H16: Prova della decidibilità di $R_α$ nel caso di $α$ quadratico
2. Conant & Pillay CP18: Studio della classificazione della stabilità delle espansioni di $⟨Z, +⟩$
3. Günaydin & Özsahakyan GO22: Ricerca indipendente, trattamento della sequenza di Beatty come predicato piuttosto che come funzione
4. Khani & Zarei KZ22: Prova semplificata nel caso della sezione aurea

Conclusioni e discussione

Conclusioni principali

1. Generalizzazione con successo del risultato di Hieronymi dai numeri quadratici ai numeri trascendenti
2. Fornitura di una prova costruttiva della completezza di modello
3. Stabilimento di un nuovo quadro tecnico per affrontare il caso trascendente

Limitazioni

1. Necessità della calcolabilità di $α$ per garantire l'enumerabilità ricorsiva
2. Il problema più generale della struttura $R_α$ rimane irrisolto
3. L'eliminazione dei quantificatori nel caso trascendente sembra non fattibile

Direzioni future

1. Problema aperto: Decidibilità e completezza di modello della struttura $⟨Z, <, +, -, 0, 1, f⟩$ (con aggiunta dell'ordine degli interi)
2. Generalizzazione ad altri tipi di numeri trascendenti
3. Studio di combinazioni più complesse di sequenze di Beatty

Punti di innovazione tecnica

1. Completezza di modello effettiva: Il processo di prova è costruttivo e consente l'eliminazione effettiva dei quantificatori
2. Connessione o-minimale: Connessione tra la parte non algebrica $T_{nalg}$ e le teorie o-minimali
3. Quadro unificato: Metodo unificato per gestire formule algebriche e non algebriche

Valutazione approfondita

Punti di forza

1. Contributo teorico: Generalizzazione significativa dei risultati noti, il passaggio dai numeri quadratici ai numeri trascendenti rappresenta un progresso importante
2. Innovazione tecnica: L'applicazione del lemma di Kronecker esteso e la progettazione delle tecniche di riduzione sono molto creative
3. Generalità del metodo: Le tecniche possono essere applicate al caso di numeri algebrici
4. Prova costruttiva: Fornisce un risultato effettivo di completezza di modello

Insufficienze

1. Complessità computazionale: Sebbene teoricamente decidibile, la complessità pratica potrebbe essere molto elevata
2. Limitazioni di espressività: Impossibilità di gestire alcune strutture correlate naturali
3. Complessità tecnica: La prova coinvolge diversi lemmi tecnici complessi

Impatto

1. Valore accademico: Fornisce nuove tecniche e risultati al campo della logica matematica e della teoria dei modelli
2. Prospettive di applicazione: Getta le basi per lo studio di strutture aritmetiche più complesse
3. Contributo metodologico: Dimostra come affrontare sistematicamente questo tipo di strutture miste algebriche-analitiche

Scenari applicabili

1. Ricerca sulla teoria della decidibilità nella logica matematica
2. Problemi diofantini nella geometria aritmetica
3. Dimostrazione automatica di teoremi nell'informatica
4. Studio delle proprietà distributive nella teoria dei numeri

Bibliografia

• 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