Campo chiuso reale - Real closed field
In matematica , un campo reale chiuso è un campo F che ha le stesse proprietà del primo ordine del campo dei numeri reali . Alcuni esempi sono il campo dei numeri reali, il campo dei numeri algebrici reali e il campo dei numeri iperreali .
Definizioni
Un campo chiuso reale è un campo F in cui è vera una delle seguenti condizioni equivalenti:
- F è elementaremente equivalente ai numeri reali. In altre parole, ha le stesse proprietà del primo ordine dei reali: qualsiasi frase nel linguaggio dei campi del primo ordine è vera in F se e solo se è vera nei reali.
- C'è un ordine totale su F che lo rende un campo ordinato tale che, in questo ordinamento, ogni elemento positivo di F ha radice quadrata in F e ogni polinomio di grado dispari con coefficienti in F ha almeno una radice in F .
- F è un campo formalmente reale tale che ogni polinomio di grado dispari con coefficienti in F ha almeno una radice in F , e per ogni elemento a di F esiste b in F tale che a = b 2 oppure a = − b 2 .
- F non è algebricamente chiuso , ma la sua chiusura algebrica è un'estensione finita .
- F non è algebricamente chiuso ma l' estensione del campo è algebricamente chiusa.
- C'è un ordinamento su F che non si estende a un ordinamento su alcuna estensione algebrica propria di F .
- F è un campo formalmente reale tale che nessuna estensione algebrica propria di F è formalmente reale. (In altre parole, il campo è massimale in una chiusura algebrica rispetto alla proprietà di essere formalmente reale.)
- C'è un ordinamento su F che lo rende un campo ordinato tale che, in questo ordinamento, il teorema del valore intermedio vale per tutti i polinomi su F con grado ≥ 0.
- F è un campo ordinato debolmente o-minimo .
Se F è un campo ordinato, il teorema di Artin-Schreier afferma che F ha un'estensione algebrica, chiamata chiusura reale K di F , tale che K è un campo chiuso reale il cui ordinamento è un'estensione dell'ordinamento dato su F , ed è unico fino ad un unico isomorfismo di campi identici su F (si noti che ogni omomorfismo ad anello tra campi chiusi reali conserva automaticamente l' ordine , perché x ≤ y se e solo se ∃ z y = x + z 2 ). Ad esempio, la vera chiusura del campo ordinato dei numeri razionali è il campo dei numeri algebrici reali . Il teorema prende il nome da Emil Artin e Otto Schreier , che lo dimostrarono nel 1926.
Se ( F , P ) è un campo ordinato, ed E è un'estensione di Galois di F , allora per il Lemma di Zorn esiste una massima estensione ordinata del campo ( M , Q ) con M un sottocampo di E contenente F e l'ordine su M che si estende p . Questo M , insieme al suo ordinamento Q , è chiamato chiusura reale relativa di ( F , P ) in E . Chiamiamo ( F , P ) reale chiuso rispetto a E se M è solo F . Quando E è la chiusura algebrica di F la chiusura reale relativa di F in E è in realtà la chiusura reale di F descritta in precedenza.
Se F è un campo (non si assume un ordinamento compatibile con le operazioni sul campo, né si assume che F sia ordinabile) allora F ha ancora una vera chiusura, che potrebbe non essere più un campo, ma solo un vero e proprio anello chiuso . Ad esempio, la vera chiusura del campo è l'anello (le due copie corrispondono ai due ordinamenti di ). Se invece viene considerato come un sottocampo ordinato di , la sua vera chiusura è ancora il campo .
Decidibilità ed eliminazione del quantificatore
Il linguaggio di campi chiusi reali include simboli per le operazioni di somma e moltiplicazione, le costanti 0 e 1, e la relazione d'ordine ≤ (così come uguaglianza, se questo non è considerato un simbolo logico). In questo linguaggio, la teoria (del primo ordine) dei campi chiusi reali, , consiste in quanto segue:
- gli assiomi dei campi ordinati ;
- l'assioma che afferma che ogni numero positivo ha una radice quadrata;
- per ogni numero dispari , l'assioma che afferma che tutti i polinomi di grado hanno almeno una radice.
Tutti gli assiomi di cui sopra possono essere espressi in logica del primo ordine (cioè intervalli di quantificazione solo su elementi del campo).
Tarski dimostrò ( c. 1931 ) che è completo , il che significa che per ogni frase può essere dimostrata vera o falsa dagli assiomi di cui sopra. Inoltre, è decidibile , nel senso che esiste un algoritmo per decidere la verità o la falsità di tale frase.
Il teorema di Tarski-Seidenberg estende questo risultato all'eliminazione del quantificatore decidibile . Cioè, esiste un algoritmo che, data una qualsiasi -formula, che può contenere variabili libere, produce una formula equivalente senza quantificatori nelle stesse variabili libere, dove equivalente significa che le due formule sono vere esattamente per gli stessi valori delle variabili . Il teorema di Tarski-Seidenberg è un'estensione del teorema di decidibilità, in quanto può essere facilmente verificato se una formula senza quantificatori senza variabili libere è vera o falsa .
Questo teorema può essere ulteriormente esteso al seguente teorema di proiezione . Se R è un campo chiuso reale, una formula con n variabili libere definisce un sottoinsieme di R n , l'insieme dei punti che soddisfano la formula. Tale sottoinsieme è detto insieme semialgebrico . Dato un sottoinsieme di k variabili, la proiezione da R n a R k è la funzione che mappa ogni n -tupla alla k -tupla delle componenti corrispondenti al sottoinsieme di variabili. Il teorema della proiezione afferma che una proiezione di un insieme semialgebrico è un insieme semialgebrico e che esiste un algoritmo che, data una formula senza quantificatori che definisce un insieme semialgebrico, produce una formula senza quantificatori per la sua proiezione.
Infatti, il teorema della proiezione equivale all'eliminazione del quantificatore, in quanto la proiezione di un insieme semialgebrico definito dalla formula p ( x , y ) è definita da
dove x e y rappresentano rispettivamente l'insieme delle variabili eliminate e l'insieme delle variabili mantenute.
La decidibilità di una teoria del primo ordine dei numeri reali dipende drammaticamente dalle operazioni e dalle funzioni primitive che vengono considerate (qui addizione e moltiplicazione). L'aggiunta di altri simboli di funzioni, ad esempio il seno o la funzione esponenziale , può fornire teorie indecidibili; vedi Teorema di Richardson e Decidibilità delle teorie del primo ordine dei numeri reali .
Complessità nel decidere
L'algoritmo originale di Tarski per l' eliminazione dei quantificatori ha una complessità computazionale non elementare , il che significa che nessuna torre
può limitare il tempo di esecuzione dell'algoritmo se n è la dimensione della formula di input. La decomposizione algebrica cilindrica , introdotta da George E. Collins , fornisce un algoritmo di complessità molto più praticabile
dove n è il numero totale di variabili (libere e vincolate), d è il prodotto dei gradi dei polinomi presenti nella formula e O ( n ) è la notazione O grande .
Davenport e Heintz (1988) hanno dimostrato che questa complessità nel caso peggiore è quasi ottimale per l'eliminazione dei quantificatori producendo una famiglia Φ n di formule di lunghezza O ( n ) , con n quantificatori, e coinvolgendo polinomi di grado costante, in modo tale che qualsiasi quantificatore- libera formula equivalente a Φ n deve coinvolgere polinomi di grado e lunghezza , dove è il grande notazione Ω . Ciò mostra che sia la complessità temporale che la complessità spaziale dell'eliminazione del quantificatore sono intrinsecamente doppiamente esponenziali .
Per il problema della decisione, Ben-Or, Kozen e Reif (1986) affermarono di aver dimostrato che la teoria dei campi chiusi reali è decidibile in spazio esponenziale , e quindi in doppio tempo esponenziale, ma il loro argomento (nel caso di più di una variabile) è generalmente ritenuto difettoso; vedere Renegar (1992) per una discussione.
Per formule puramente esistenziali, cioè per formule della forma
- ∃ x 1 , ..., ∃ x k P 1 ( x 1 , ..., x k ) ⋈ 0 ∧ ... ∧ P s ( x 1 , ..., x k ) ⋈ 0,
dove ⋈ sta per <, > o = , la complessità è minore. Basu e Roy (1996) hanno fornito un buon algoritmo per decidere la verità di una tale formula esistenziale con complessità di s k +1 d O ( k ) operazioni aritmetiche e spazio polinomiale .
Proprietà dell'ordine
Una proprietà di cruciale importanza dei numeri reali è che si tratta di un campo di Archimede , il che significa che ha la proprietà di Archimede che per ogni numero reale esiste un numero intero più grande di esso in valore assoluto . Un'affermazione equivalente è che per ogni numero reale ci sono interi sia più grandi che più piccoli. Tali campi chiusi reali che non sono Archimede, sono campi ordinati non Archimede . Ad esempio, qualsiasi campo di numeri iperreali è reale chiuso e non archimedeo.
La proprietà di Archimede è legata al concetto di cofinalità . Un insieme X contenuto in un insieme ordinato F è cofinale in F se per ogni y in F esiste una x in X tale che y < x . In altre parole, X è una successione illimitata in F . La cofinalità di F è la dimensione del più piccolo insieme cofinale, vale a dire, la dimensione della cardinalità più piccola che dà una sequenza illimitata. Ad esempio, i numeri naturali sono cofinali nei reali, e la cofinalità dei reali è quindi .
Abbiamo quindi i seguenti invarianti che definiscono la natura di un campo chiuso reale F :
- La cardinalità di F .
- La cofinalità di F .
A questo possiamo aggiungere
- Il peso di F , che è la dimensione minima di un sottoinsieme denso di F .
Questi tre numeri cardinali ci dicono molto sulle proprietà d'ordine di qualsiasi campo chiuso reale, sebbene possa essere difficile scoprire quali siano, specialmente se non siamo disposti a invocare l' ipotesi del continuo generalizzato . Ci sono anche proprietà particolari che possono contenere o meno:
- Un campo F è completo se non esiste un campo ordinato K contenente correttamente F tale che F è denso in K . Se la cofinalità di F è κ , questo equivale a dire sequenze Cauchy indicizzati da κ sono convergenti in F .
- Un campo ordinato F ha la proprietà eta insieme η α , per il numero ordinale α , se per due sottoinsiemi L e U di F di cardinalità minore di tale che ogni elemento di L è minore di ogni elemento di U , esiste un elemento x in F con x maggiore di ogni elemento di L e minore di ogni elemento di U . Questo è strettamente correlato alla proprietà teorica del modello di essere un modello saturo ; due campi chiusi reali sono η α se e solo se sono -saturi, e inoltre due campi chiusi η α reali entrambi di cardinalità sono isomorfi di ordine.
L'ipotesi del continuo generalizzato
Le caratteristiche dei campi chiusi reali diventano molto più semplici se si vuole assumere l' ipotesi del continuo generalizzato . Se vale l'ipotesi del continuo, tutti i campi chiusi reali con cardinalità il continuum e aventi la proprietà η 1 sono isomorfi all'ordine. Questo campo unico Ϝ può essere definita mediante un ultrapotenza , come , dove M è un massimo ideale non conduce a un campo fine-isomorfa . Questo è il più comunemente usato campo numero iperreale in analisi non standard , e la sua unicità è equivalente all'ipotesi continuo. (Anche senza l'ipotesi del continuo abbiamo che se la cardinalità del continuo è allora abbiamo un unico campo η β di dimensione η β .)
Inoltre, non abbiamo bisogno di ultrapotenze per costruire Ϝ , possiamo farlo in modo molto più costruttivo come il sottocampo di serie con un numero numerabile di termini diversi da zero del campo delle serie di potenze formali su un gruppo abeliano divisibile totalmente ordinato G che è un η 1 gruppo di cardinalità ( Alling 1962 ).
Ϝ tuttavia non è un campo completo; se prendiamo il suo completamento, si finisce con un campo Κ di cardinalità più grande. Ϝ ha la cardinalità del continuo, che per ipotesi è , Κ ha cardinalità , e contiene Ϝ come sottocampo denso. Non è un ultrapotere ma è un campo iperreale, e quindi un campo adatto per gli usi dell'analisi non standard. Può essere visto come l'analogo di dimensioni superiori dei numeri reali; con cardinalità invece di , cofinalità invece di , e peso invece di , e con la proprietà η 1 al posto della proprietà η 0 (che significa semplicemente che tra due numeri reali qualsiasi ne possiamo trovare un altro).
Esempi di campi chiusi reali
- i veri numeri algebrici
- i numeri calcolabili
- i numeri definibili
- i numeri reali
- numeri superreali
- numeri iperreali
- la serie di Puiseux con coefficienti reali
- i numeri surreali
Appunti
Riferimenti
- Alling, Norman L. (1962), "Sull'esistenza di campi reali chiusi che sono η α -insiemi di potenza power α .", Trans. Ame. Matematica. Soc. , 103 : 341–352, doi : 10.1090/S0002-9947-1962-0146089-X , MR 0146089
- Basu, Saugata, Richard Pollack e Marie-Françoise Roy (2003) "Algoritmi nella geometria algebrica reale" in Algoritmi e calcolo in matematica . Springer. ISBN 3-540-33098-4 ( versione online )
- Michael Ben-Or, Dexter Kozen e John Reif, La complessità dell'algebra elementare e della geometria , Journal of Computer and Systems Sciences 32 (1986), n. 2, pp. 251-264.
- Caviness, BF, e Jeremy R. Johnson, eds. (1998) Eliminazione del quantificatore e decomposizione algebrica cilindrica . Springer. ISBN 3-211-82794-3
- Chen Chung Chang e Howard Jerome Keisler (1989) Teoria dei modelli . Olanda Settentrionale.
- Dales, HG e W. Hugh Woodin (1996) Campi super-reali . Università di Oxford Stampa.
- Davenport, James H. ; Heintz, Joos (1988). "L'eliminazione del quantificatore reale è doppiamente esponenziale" . J. Simb. Calcola . 5 (1–2): 29–35. doi : 10.1016/s0747-7171(88)80004-x . Zbl 0663.03015 .
- Efrat, Ido (2006). Le valutazioni, ordinamenti, e Milnor K -teoria . Indagini matematiche e monografie. 124 . Providence, RI: Società matematica americana . ISBN 0-8218-4041-X. Zbl 1103.12002 .
- Macpherson, D., Marker, D. e Steinhorn, C., Strutture debolmente o-minimali e campi chiusi reali , Trans. della matematica americana. Soc., vol. 352, n. 12, 1998.
- Mishra, Bhubaneswar (1997) " Geometria algebrica reale computazionale ", in Manuale di geometria discreta e computazionale . CRC Press. edizione 2004, pag. 743. ISBN 1-58488-301-4
- Rajwade, AR (1993). Piazze . Serie di appunti della conferenza della London Mathematical Society. 171 . Cambridge University Press . ISBN 0-521-42668-5. Zbl 0785.11022 .
- Renegar, James (1992). "Sulla complessità computazionale e sulla geometria della teoria del primo ordine dei reali. Parte I: Introduzione. Preliminari. La geometria degli insiemi semialgebrici. Il problema decisionale per la teoria esistenziale dei reali" . Giornale di calcolo simbolico . 13 (3): 255-299. doi : 10.1016/S0747-7171(10)80003-3 .
- Passmore, Grant (2011). Procedure di decisione combinate per aritmetica non lineare, reale e complessa (PDF) (PhD). Università di Edimburgo .
- Alfred Tarski (1951) Un metodo decisionale per l'algebra elementare e la geometria . Univ. della California Press.
- Erdos, P.; Gillman, L.; Henriksen, M. (1955), "Un teorema di isomorfismo per campi reali chiusi" , Ann. di matematica. , 2, 61 (3): 542–554, doi : 10.2307/1969812 , JSTOR 1969812 , MR 0069161