FO Axiomatisierbarkeit < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Welche der folgenden Klassen sind FO-axiomatisierbar, welche endlich axiomatisierbar? Begründen Sie Ihre Antwort und geben Sie gegebenenfalls ein Axiomensystem an.
a) Die Klasse der endlich verzweigten ungerichteten Graphen
b) Die Klasse der Graphen, die einen zu [mm](Potenzmenge \mathcal{P}(\mathbb{N}),\subset)[/mm] isomorphen Teilgraphen enthalten (wobei die Teilmengenrelation als Kantenrelation aufzufassen ist. |
zu a) Könnte man hierbei endlich axiomatisieren, dass kein Knoten y Nachfolger von Knoten x ist und x endlich viele Nachfolger hat?
zu b) Ich denke, dass dies nicht axiomatisierbar ist, weiss aber nicht wie ich es zeigen soll.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=74244
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:02 Di 24.04.2007 | | Autor: | komduck |
Meiner Ansicht nach ist beides nicht FO axiomatisierbar:
Wenn a FO axiomatisierbar wäre könnte ich noch Axiome für Äquivalenzrelation
und ein Axiom das es nur eine Äquivalenzklasse gibt hinzunehmen.
Dann hätte ich eine Axiomatisierung der Endlichkeit.
Die Endlichkeit ist aber nicht FO axiomatisierbar, weil ich die
Axiome "Es gibt mindestens n Elemente" hinzunehmen könnte.
Nun hätte jede endliche Teilmenge dieser Axiome ein Model, nach dem
Endlichkeitssatz hätte die gesamte Formelmenge ein Model.
Wenn b FO axiomatisierbar wäre dann müßte das Model überabzählbar viel
Elemente haben. Da aber jede FO Axiomatisierung ein abzählbares
Model besitzt ist dies ein Widerspruch.
mfg komduck
|
|
|
|
