Banachs Fixpunktsatz besagt, dass, wenn wir einen nicht leeren vollständigen metrischen Raum , jede gleichmäßig kontrahierende Funktion einen eindeutigen Fixpunkt . Der Beweis dieses Theorems erfordert jedoch das Axiom der Wahl - wir müssen ein beliebiges Element wählen , um mit der Iteration von zu beginnen und die Cauchy-Folge .
- Wie werden Fixpunktsätze in der konstruktiven Analyse formuliert?
- Gibt es auch prägnante Verweise auf konstruktive metrische Räume?
Der Grund, den ich frage, ist, dass ich ein Modell von System F konstruieren möchte, in dem die Typen (unter anderem) zusätzlich eine metrische Struktur aufweisen. Es ist ziemlich nützlich, dass wir in der konstruktiven Mengenlehre eine Familie von Mengen , so dass U unter Produkten, Exponentialen und U- indizierten Familien geschlossen ist, was es einfach macht, ein Modell von System F zu geben.
Es wäre sehr schön, wenn ich eine ähnliche Familie konstruktiver ultrametrischer Räume zusammenstellen könnte. Aber da die konstruktive Mengenlehre durch das Hinzufügen von Wahlmöglichkeiten klassischer wird, muss ich natürlich vorsichtiger mit Fixpunkt-Theoremen umgehen, und wahrscheinlich auch mit anderen Dingen.
quelle
Antworten:
Das Axiom der Wahl wird verwendet, wenn es eine Sammlung von "Dingen" gibt und Sie für jedes "Ding" ein Element auswählen. Wenn es nur eine Sache in der Sammlung gibt, ist das nicht das Axiom der Wahl. In unserem Fall haben wir nur einen metrischen Raum und "wählen" einen Punkt darin. So dass nicht das Axiom der Wahl ist , aber Beseitigung der Existenzquantoren, das heißt, wir haben eine Hypothese und wir sagen "lass x ∈ A so sein, dass ϕ ( x ) ". Leider sagen die Leute oft "∃x∈A.ϕ(x) x∈A ϕ(x) x∈A ", was dann aussieht wie die Anwendung des Axioms der Wahl.ϕ(x)
Als Referenz ist hier ein konstruktiver Beweis für Banachs Fixpunktsatz.
Satz: Eine Kontraktion auf einen bewohnten vollständigen metrischen Raum hat einen eindeutigen Fixpunkt.
Beweis. Angenommen ist ein bewohnter vollständiger metrischer Raum und f : M → M ist eine Kontraktion. Da f eine Kontraktion gibt es existiert α , so dass 0 < α < 1 und D ( f ( x ) , f ( y ) ) ≤ α ⋅ d ( x , y ) für alle x , y ∈ M(M,d) f:M→M f α 0<α<1 d(f(x),f(y))≤α⋅d(x,y) x,y∈M .
Angenommen, und v sind ein fester Punkt von f . Dann gilt d ( u , v ) = d ( f ( u ) , f ( v ) ) ≤ α d ( u , v ), woraus folgt, dass 0 ≤ d ( u , v ) ≤ ( α - 1 ) d (u v f
Es bleibt zu beweisen, dass es einen festen Punkt gibt. Da bewohnt existiert x 0 ∈ M . Definieren Sie die Folge ( x i ) rekursiv durch x i + 1 = f ( x i ) . Wir können durch Induktion beweisen, dass d ( x i , x i + 1 ) ≤ α i ⋅ d ( x 0 , ( x i )M x0∈ M ( xich)
Bemerkungen:
Ich habe darauf geachtet, nicht "wähle " und "wähle x 0 " zu sagen . Es ist üblich, solche Dinge zu sagen, und sie tragen nur zu der Verwirrung bei, die normale Mathematiker daran hindert, zu erkennen, was das Axiom der Wahl ist und was nicht.α x0
Schließlich haben die folgenden Fixpunktsätze konstruktive Versionen:
Das sind eher mehr Informationen, als Sie verlangt haben.
quelle