Modellvollständigkeit und Entscheidbarkeit der additiven Struktur von ganzen Zahlen erweitert um eine Funktion für eine Beatty-Sequenz

Grundlegende Informationen

• Papier-ID: 2110.01673
• Titel: Model-completeness and decidability of the additive structure of integers expanded with a function for a Beatty sequence
• Autoren: Mohsen Khani, Ali N. Valizadeh, Afshin Zarei
• Klassifikation: math.LO (Mathematische Logik)
• Veröffentlichungsdatum: 17. April 2024 (endgültige Version)
• Papier-Link: https://arxiv.org/abs/2110.01673

Zusammenfassung

In diesem Papier wird eine modellvollständige Theorie eingeführt, die die Struktur $Z_α = ⟨Z, +, 0, 1, f⟩$ vollständig axiomatisiert, wobei $f : x ↦ ⌊αx⌋$ eine unäre Funktion ist und $α$ eine feste transzendente Zahl ist. Wenn $α$ berechenbar ist, ist die Theorie rekursiv aufzählbar und daher als Folge der Vollständigkeit entscheidbar. Dieses Ergebnis entspricht dem allgemeineren Thema, multiplikative Spuren zu ganzen Zahlen hinzuzufügen, ohne die Entscheidbarkeit zu verlieren.

Forschungshintergrund und Motivation

Problemhintergrund

1. Kernproblem: Untersuchung der Entscheidbarkeit von Erweiterungsstrukturen der additiven Gruppe der ganzen Zahlen $⟨Z, +⟩$, insbesondere der Struktureigenschaften nach Hinzufügen der Beatty-Sequenzfunktion $f(x) = ⌊αx⌋$.
2. Forschungsbedeutung:
   • Liegt an der Schnittstelle zweier aktiver Forschungsrichtungen: einerseits die Entscheidbarkeit und Klassifikation von Erweiterungen von $⟨Z, +⟩$ (stabile oder instabile Strukturen)
   • Andererseits die Untersuchung von Erweiterungen der reellen Zahlengeraden mit spezifischen diskreten additiven Untergruppen
3. Einschränkungen bestehender Arbeiten:
   • Hieronymi bewies in H16 die Entscheidbarkeit nur für quadratische Zahlen $α$
   • Für transzendente Zahlen $α$ ist die Entscheidbarkeit der allgemeineren Struktur $R_α$ noch ungeklärt
   • Es sind neue Techniken erforderlich, um die Unabhängigkeit verschiedener Potenzen von $f$ im transzendenten Fall zu behandeln
4. Forschungsmotivation:
   • Bereitstellung eines Entscheidbarkeitsnachweises für den transzendenten Fall
   • Verwendung grundlegender Werkzeuge der Modelltheorie und Zahlentheorie für einen konstruktiven Beweis
   • Grundlegung für die Lösung des allgemeineren Problems der Struktur $R_α$

Kernbeiträge

1. Etablierung einer modellvollständigen Theorie: Konstruktion der Theorie $T_α$, die die Struktur $Z_α = ⟨Z, +, 0, 1, f⟩$ vollständig axiomatisiert, wobei $f(x) = ⌊αx⌋$ und $α$ eine transzendente Zahl ist.
2. Beweis der Entscheidbarkeit: Wenn $α$ berechenbar ist, ist $T_α$ rekursiv aufzählbar, und in Kombination mit Vollständigkeit ergibt sich Entscheidbarkeit.
3. Technische Innovationen:
   • Umwandlung von Bruchteilverhältnissen in Formeln der ersten Ordnung
   • Verwendung des erweiterten Kronecker-Lemmas zur Behandlung nicht-algebraischer Formeln
   • Entwicklung von Reduktionsmethoden für algebraische Formeln
4. Theoretische Analyse: Beweis, dass die Struktur strikte Ordnungseigenschaften besitzt, und Analyse der Struktur definierbarer Mengen.

Methodische Details

Aufgabendefinition

Untersuchung der Theorie erster Ordnung der Struktur $Z_α = ⟨Z, +, 0, 1, f⟩$ in der Sprache $L = \{+, -, 0, 1, f\}$, wobei:

• $Z$ die Menge der ganzen Zahlen ist
• $+$ die Additionsoperation ist
• $f: x ↦ ⌊αx⌋$ die Beatty-Sequenzfunktion ist
• $α$ eine feste berechenbare transzendente Zahl ist

Grundlegendes technisches Rahmenwerk

1. Logische Ausdrückbarkeit von Bruchteilen

Schlüsselbeobachtung: Obwohl Bruchteile nicht in der Sprache vorhanden sind, können ihre wesentlichen Eigenschaften in $L$ wie folgt beschrieben werden:

Für $a, b ∈ Z$ und $n ∈ N$:

• $f(na) = nf(a) + i$ genau dann, wenn $\frac{i}{n} < [αa] < \frac{i+1}{n}$
• $[αa] + [αb] < 1$ genau dann, wenn $f(a+b) = f(a) + f(b)$
• $[αa] < [αb]$ genau dann, wenn $f(b-a) = f(b) - f(a)$

wobei $[x] = x - ⌊x⌋$ den Bruchteil bezeichnet.

2. Formelklassifikationsstrategie

Systematische Aufteilung von $L$-Formeln in zwei Klassen:

Nicht-algebraische Formeln: der Form $\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$

Algebraische Formeln: der Form $h_1(x_1) + \cdots + h_n(x_n) = y$, wobei $h_i(x)$ ein $f$-Polynom ist.

3. Erweitertes Kronecker-Lemma

Satz 3.4 (Erweitertes Kronecker-Lemma): Für jedes $n ∈ N$ ist die folgende $(n+1)$-elementige Menge in $(0,1)^{n+1}$ dicht: $\{([αa], [αf(a)], [αf^2(a)], \ldots, [αf^n(a)]) : a ∈ N\}$

Dies ist der Fall, weil die Transzendenz von $α$ garantiert, dass $1, α, α^2, \ldots, α^n$ linear unabhängig über $\mathbb{Q}$ sind.

Beweismethode für Modellvollständigkeit

Schritt 1: Behandlung nicht-algebraischer Formeln

• Lemma 3.6: Für die Menge nicht-algebraischer Formeln $Γ(x; \bar{y})$ existiert eine quantorenfreie Formel $χ(\bar{y})$ derart, dass $Z_α ⊨ ∀\bar{y}(∃xΓ(x; \bar{y}) ↔ χ(\bar{y}))$
• Verwendung des Fourier-Motzkin-Eliminationsalgorithmus zur Behandlung linearer Ungleichungssysteme

Schritt 2: Reduktionsmethoden

• Lemma 4.12 (Technischer Trick): Reduktion von gemischten Systemen mit algebraischen Formeln auf Systeme mit weniger Variablen, die nicht-algebraisch sind
• Schlüsselidee: Durch Einführung von Hilfsvariablen $w$ und Term $h(x)$ wird eine multivariate algebraische Gleichung in den univariaten Fall umgewandelt

Schritt 3: Algebraische Abgeschlossenheit

• Lemma 4.13: Wenn $M_1 ⊆ M_2$ Modelle von $T_α$ sind, $b ∈ M_1$, $a ∈ M_2$ und $h(a) = b$, dann $a ∈ M_1$
• Gewährleistet die Abgeschlossenheit von Unterstrukturen unter Umkehroperationen verschiedener Potenzen von $f$

Axiomatisches System

Axiomenschema 1 (Berechnung von $f(n)$)

Für $n ∈ N$ und $0 ≤ i < n$ mit $\frac{f(n)}{n} ≡ i$: $f(\underbrace{1 + \cdots + 1}_{n \text{-mal}}) = \underbrace{f(1) + \cdots + f(1)}_{n \text{-mal}} + \underbrace{1 + \cdots + 1}_{i \text{-mal}}$

Axiom 2 (Grundlegende Eigenschaften)

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. Die Relation $[αx] < [αy]$ ist eine dichte lineare Ordnung

Axiomenschema 3 (Dichtheit)

Für $m, n ∈ N$: Wenn $\bigwedge_{i=1}^n [αz_i] < [αy_i]$, dann existieren mindestens $m$ verschiedene $x$ derart, dass $\bigwedge_{i=1}^n [αy_i] < [αf^i(x)] < [αz_i]$.

Experimentelle Ergebnisse und theoretische Analyse

Hauptergebnisse

Hauptsatz: Sei $α$ eine transzendente reelle Zahl, dann gilt:

1. $T_α$ ist eine vollständige und modellvollständige Axiomatisierung der Struktur $Z_α$
2. $Z_α$ besitzt strikte Ordnungseigenschaften
3. Wenn $α$ berechenbar ist, ist $T_α$ entscheidbar

Eigenschaften definierbarer Mengen

1. Strukturierte Mengen: Formeln ohne Potenzen von $f$ definieren Kongruenzklassen (unendliche arithmetische Progressionen)
2. Zufällige Mengen: Von Formeln mit Potenzen von $f$ definierte Mengen enthalten keine unendlichen arithmetischen Progressionen
3. Gemischte Eigenschaften: Der Wertebereich jedes $f$-Polynoms enthält arithmetische Progressionen beliebiger endlicher Länge

Proposition 5.1: Für $h(x) = \sum_{i=0}^k m_i f^i(x)$ existiert für jedes $n ∈ N$ eine arithmetische Progression der Länge $n$ im Wertebereich von $h$.

Verwandte Arbeiten

1. Hieronymi H16: Beweis der Entscheidbarkeit von $R_α$ für quadratisches $α$
2. Conant & Pillay CP18: Untersuchung der Stabilitätsklassifikation von Erweiterungen von $⟨Z, +⟩$
3. Günaydin & Özsahakyan GO22: Unabhängige Forschung, behandelt Beatty-Sequenzen als Prädikate statt als Funktionen
4. Khani & Zarei KZ22: Vereinfachter Beweis für den Fall des goldenen Schnitts

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Erfolgreiche Verallgemeinerung von Hieronymis Ergebnis von quadratischen Zahlen auf transzendente Zahlen
2. Bereitstellung eines konstruktiven Modellvollständigkeitsbeweises
3. Etablierung eines neuen technischen Rahmens zur Behandlung transzendenter Zahlen

Einschränkungen

1. Berechenbarkeit von $α$ ist erforderlich, um rekursive Aufzählbarkeit zu gewährleisten
2. Das allgemeinere Strukturproblem $R_α$ bleibt ungelöst
3. Quantoreneliminierung scheint im transzendenten Fall nicht möglich zu sein

Zukünftige Richtungen

1. Offene Fragen: Entscheidbarkeit und Modellvollständigkeit der Struktur $⟨Z, <, +, -, 0, 1, f⟩$ (mit Hinzufügen der Ordnung auf ganzen Zahlen)
2. Verallgemeinerung auf andere Arten transzendenter Zahlen
3. Untersuchung komplexerer Beatty-Sequenzkombinationen

Technische Innovationspunkte

1. Effektive Modellvollständigkeit: Der Beweisprozess ist konstruktiv und ermöglicht effektive Quantoreneliminierung
2. o-minimale Verbindung: Verbindung zwischen dem nicht-algebraischen Teil $T_{nalg}$ und o-minimalen Theorien
3. Einheitlicher Rahmen: Einheitliche Methode zur Behandlung algebraischer und nicht-algebraischer Formeln

Tiefgreifende Bewertung

Stärken

1. Theoretischer Beitrag: Signifikante Verallgemeinerung bekannter Ergebnisse, ein wichtiger Fortschritt von quadratischen Zahlen zu transzendenten Zahlen
2. Technische Innovation: Die Anwendung des erweiterten Kronecker-Lemmas und die Gestaltung der Reduktionsmethoden sind kreativ
3. Methodische Universalität: Die Techniken sind auf algebraische Zahlen anwendbar
4. Konstruktiver Beweis: Bereitstellung eines effektiven Modellvollständigkeitsergebnisses

Mängel

1. Rechenkomplexität: Obwohl theoretisch entscheidbar, kann die praktische Komplexität sehr hoch sein
2. Ausdrucksbeschränkungen: Unfähigkeit, bestimmte natürliche verwandte Strukturen zu behandeln
3. Technische Komplexität: Der Beweis beinhaltet mehrere komplexe technische Lemmata

Einflussfaktor

1. Akademischer Wert: Bietet neue Techniken und Ergebnisse für die Bereiche mathematische Logik und Modelltheorie
2. Anwendungsperspektiven: Grundlegung für die Untersuchung komplexerer arithmetischer Strukturen
3. Methodologischer Beitrag: Zeigt, wie man systematisch solche gemischten algebraisch-analytischen Strukturen behandelt

Anwendungsszenarien

1. Forschung zur Entscheidbarkeitstheorie in der mathematischen Logik
2. Diophantische Probleme in der arithmetischen Geometrie
3. Automatisierte Theorembeweise in der Informatik
4. Untersuchung von Verteilungseigenschaften in der Zahlentheorie

Literaturverzeichnis

• 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