Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Mit dem Kompaktheitssatz/Endlichkeitssatz beweisen

Mit dem Kompaktheitssatz/Endlichkeitssatz beweisen

Universität / Fachhochschule

Mengentheoretische Topologie

Tags: Mengentheoretische Topologie

incc1 aktiv_icon

14:24 Uhr, 21.04.2018

Hallo,ich bräuchte Hilfe mit dem Verstehen des Kompaktheitssatzes/Endlichkeitssatzes.

Seien

M = {F_{1}, F_{2}, ...}

und

N = {G_{1}, G_{2}, ...}

unendliche Mengen aussagenlogischer Formeln. Zeigen oder widerlegen Sie folgende Aussagen:

a)

Ist

R_{n} = {F_{n}, F_{n + 1}, ...}

für alle

n \in {1, 2, 3 ...}

erfüllbar, dann ist

M

erfüllbar.

b)

Ist

S_{n} = {F_{1}, F_{2}, F_{3}, ..., F_{2 n}}

für alle

n \in ℕ

erfüllbar, dann ist

M

erfüllbar.

Ich verstehe einfach nicht, wie ich dem Kompaktheitssatz ausnutzen kann, um diese Aussagen zu beweisen/widerlegen. Wie funktioniert der Kompaktheitssatz an diesen Beispielen genau. Könnte vielleicht jemand das ausführlich und verständlich erklären?
Wäre sehr dankbar.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

tobit aktiv_icon

19:58 Uhr, 21.04.2018

Hallo incc1!

Bevor ich zu den Aufgaben a) und b) komme, sollten wir uns ein wenig mit dem nötigen Verständnis des Kompaktheitssatzes bzw. des Erfüllbarkeits-Begriffes beschäftigen.

Ich weiß nicht, inwieweit du mit dem Erfüllbarkeits-Begriff vertraut bist.
Kannst du z.B. irgendwelche konkreten aussagenlogische Formeln F und G nennen, so dass die (einelementige) Menge {F} erfüllbar ist und die Menge {G} nicht erfüllbar ist?

Wenn N eine Menge erfüllbare Menge aussagenlogischer Formeln ist und M eine Teilmenge von N, ist dir dann klar, dass M (erst recht) erfüllbar ist?
Ist hingegen lediglich eine Teilmenge M von N erfüllbar, muss die Menge N selbst noch lange nicht erfüllbar sein. (Fällt dir ein Beispiel ein?)
(Diese Zusammenhänge sind für ein Verständnis des Kompaktheitssatzes und zum Lösen der Aufgabe zentral.)

Wenn N erfüllbar ist, dann sind also alle Teilmengen von N auch erfüllbar.
Insbesondere sind in diesem Fall alle endlichen Teilmengen von N erfüllbar.

Der Kompaktheitssatz besagt nun umgekehrt: Wenn wir von einer Menge N aussagenlogischer Formeln nur wissen, dass alle ihre endlichen Teilmengen erfüllbar sind, dann ist schon die ganze Menge N erfüllbar!

Nun zu den Aufgaben:

Zu a): Heißt es dort wirklich

R_{n} = {F_{n}, F_{n + 1}, \dots}

mit den drei Pünktchen (dann wäre

M = R_{1}

erfüllbar) oder soll es

R_{n} = {F_{n}, F_{n + 1}}

heißen (dann wäre die Aussage im Allgemeinen falsch und somit zu widerlegen)?

Zu b): Heißt es am Ende der Definition von

S_{n}

tatsächlich

F_{2 n}

oder

F_{2^{n}}

?
In beiden Fällen kann man aber im Wesentlichen gleich argumentieren, dass die Aussage wahr ist:
Um die Erfüllbarkeit von M zu zeigen, müssen wir nach dem Kompaktheitssatz nur die Erfüllbarkeit jeder endlichen Teilmenge

M^{ʹ}

von

M

zeigen.
Sei also

M^{ʹ}

eine beliebig vorgegebene endliche Teilmenge von

M

.
Zeigen müssen wir die Erfüllbarkeit von

M^{ʹ}

.
Wir setzen bereits voraus, dass die

S_{n}

erfüllbar sind.
Wenn wir ein

n \in ℕ

finden, so dass

M^{ʹ} \subseteq S_{n}

ist, können wir aus der Erfüllbarkeit von

S_{n}

die von

M^{ʹ}

folgern und haben gewonnen... ;-)

Ich habe bis morgen Abend Zeit, dir weiterzuhelfen. Am besten schreibst du dazu, was dir klar ist und was nicht.

Viele Grüße
Tobias

incc1 aktiv_icon

20:37 Uhr, 21.04.2018

Hallo Tobias,
danke für deine Antwort.

Mit dem Erfüllbarkeits-Begriff bin ich vertaut.

{F}

mit

F = a \lor \neg a

wäre erfüllbar und

{G}

mit

G = a \land \neg a

wäre unerfüllbar.

"Wenn

N

eine Menge erfüllbare Menge aussagenlogischer Formeln ist und

M

eine Teilmenge von

N,

ist dir dann klar, dass

M

(erst recht) erfüllbar ist?"
Ja, das ist mir klar.

"Ist hingegen lediglich eine Teilmenge

M

von

N

erfüllbar, muss die Menge

N

selbst noch lange nicht erfüllbar sein. (Fällt dir ein Beispiel ein?)"
Wäre ein Beispiel hier die nicht einfach die Vereinigung von

{F}

und

{G}

aus dem Beispiel oben? Wäre diese Menge dann also nicht erfüllbar?

"Der Kompaktheitssatz besagt nun umgekehrt: Wenn wir von einer Menge

N

aussagenlogischer Formeln nur wissen, dass alle ihre endlichen Teilmengen erfüllbar sind, dann ist schon die ganze Menge

N

erfüllbar!"
Genau das fällt mir schwer zu verstehen und insbesondere diesen Satz anzuwenden. Ich muss also beweisen, dass ALLE endliche Teilmengen einer Menge

N

aussagenlogischer Formeln erfüllbar ist? Aber wie mache ich das? Was bedeutet "alle Teilmengen von N..."?

Zu

a) :

Es soll tatsächlich

R_{n} = {F_{n}, F_{n + 1}}

heißen.
Zu

b) : F_{2^{n}}

"Sei also M′ eine beliebig vorgegebene endliche Teilmenge von M."
Was meinst du mit "beliebig vorgegebene endliche Teilmenge"? Meinst du damit jeweils die

R_{n}

und

S_{n}

?

"Wenn wir ein n∈ℕ finden, so dass M′⊆Sn ist, können wir aus der Erfüllbarkeit von Sn die von M′ folgern und haben gewonnen... ;-)"
Verstehe ich nicht

: (

tobit aktiv_icon

21:17 Uhr, 21.04.2018

" {F} mit F=a∨¬a wäre erfüllbar und {G} mit G=a∧¬a wäre unerfüllbar. "

Genau. Auch z.B. für

F = a

wäre {F} erfüllbar.

"Ist hingegen lediglich eine Teilmenge M von N erfüllbar, muss die Menge N selbst noch lange nicht erfüllbar sein. (Fällt dir ein Beispiel ein?)"
Wäre ein Beispiel hier die nicht einfach die Vereinigung von {F} und {G} aus dem Beispiel oben? Wäre diese Menge dann also nicht erfüllbar?

Ja, da schon {G} nicht erfüllbar ist, ist die Menge {F,G} erst recht nicht erfüllbar (denn wäre {F,G} erfüllbar, dann wäre auch {G} als Teilmenge von {F,G} erfüllbar).
Somit wäre z.B. M={F} und N={F,G} ein Beispiel der von mir gesuchten Art.

Anderes Beispiel: Betrachten wir mal

F = a

und

G = \neg a

. Dann sind {F} und {G} beide erfüllbar, jedoch ist {F,G} nicht erfüllbar.

" "Der Kompaktheitssatz besagt nun umgekehrt: Wenn wir von einer Menge N aussagenlogischer Formeln nur wissen, dass alle ihre endlichen Teilmengen erfüllbar sind, dann ist schon die ganze Menge N erfüllbar!"
Genau das fällt mir schwer zu verstehen und insbesondere diesen Satz anzuwenden. "

Geht es nur um die Anwendung dieses Satzes oder ist dir an der Aussage des Satzes an sich etwas unklar?

" Ich muss also beweisen, dass ALLE endliche Teilmengen einer Menge N aussagenlogischer Formeln erfüllbar ist? "

Musst du nicht... ;-) Aber wenn du beweisen möchtest, dass eine Menge N erfüllbar ist, genügt es zu zeigen, dass die endlichen Teilmengen von N erfüllbar sind.

" Aber wie mache ich das? "

Das hängt davon ab, wie die Menge N aussieht bzw. was du über sie weißt.
Unabhängig davon ist aber die typische Strategie zum Nachweis einer "für alle"-Aussage anwendbar:
Nimm dir eine beliebig vorgegebene endliche Teilmenge

N^{ʹ}

von

N

("Sei

N^{ʹ}

eine endliche Teilmenge von N.") und zeige, dass diese Teilmenge

N^{ʹ}

erfüllbar ist.
Da die endliche Teilmenge

N^{ʹ}

von

N

beliebig vorgegeben war, sind somit ALLE Teilmengen

N^{ʹ}

von

N

erfüllbar.

" Was bedeutet "alle Teilmengen von N..."? " "

Die Aussage "Alle Teilmengen von N sind erfüllbar" bedeutet, dass jede Teilmenge

N^{ʹ}

von

N

erfüllbar ist.
(Möglicherweise habe ich aber deine Frage noch nicht wirklich verstanden.)

" "Sei also M′ eine beliebig vorgegebene endliche Teilmenge von M."
Was meinst du mit "beliebig vorgegebene endliche Teilmenge"? Meinst du damit jeweils die Rn und Sn? "

Nein. Wir wollen etwas über ALLE endlichen Teilmengen von M zeigen. Sei dazu

M^{ʹ}

EINE ("feste, aber beliebige") endliche Teilmenge von M. Wir zeigen die Erfüllbarkeit von

M^{ʹ}

. Da die Argumentation für jede beliebige endliche Teilmenge

M^{ʹ}

gilt, haben wir dann die Erfüllbarkeit von

M^{ʹ}

für JEDE endliche Teilmenge

M^{ʹ}

von M gezeigt.

" "Wenn wir ein n∈ℕ finden, so dass M′⊆Sn ist, können wir aus der Erfüllbarkeit von Sn die von M′ folgern und haben gewonnen... ;-)"
Verstehe ich nicht :( "

Wir sind gerade an der Stelle, an der wir die Erfüllbarkeit von

M^{ʹ}

zeigen möchten (Wenn uns dies gelingt, dann haben wir gewonnen, d.h. unseren Beweis erbracht).
Wir setzen voraus, dass jede Menge

S_{n}

erfüllbar ist.
Teilmengen erfüllbarer Mengen sind (erst recht) wieder erfüllbar.
Wenn wir also

M^{ʹ} \subseteq S_{n}

(für irgendein

n \in ℕ

) zeigen können, muss

M^{ʹ}

erst recht erfüllbar sein.

incc1 aktiv_icon

21:37 Uhr, 21.04.2018

"Geht es nur um die Anwendung dieses Satzes oder ist dir an der Aussage des Satzes an sich etwas unklar?"

Ich glaube, dass ich einfach einen ausführlichen Beispiel sehen muss. Kannst du das vielleicht an

a)

zeigen und ich probiere mich dann an

b); D

tobit aktiv_icon

21:50 Uhr, 21.04.2018

a) und b) sind leider sehr unterschiedlich.
Bei a) ist ein konkretes Gegenbeispiel gesucht (das hat nichts mit dem Kompaktheitssatz zu tun).
Bei b) lässt sich die Aussage unter Zuhilfenahme des Kompaktheitssatzes beweisen.
Gibt es auch noch weitere Aufgabenteile, in denen die Menge N vorkommt?

Ich schreibe gleich in einem separaten Beitrag einen Lösungsvorschlag für b) im Zusammenhang.

Bei a) untersuche z.B. mal

F_{1} = a

F_{2} = b

F_{3} = \neg a

F_{4} = c

F_{5} = d

F_{6} = e

F_{7} = f

, ... .

tobit aktiv_icon

22:06 Uhr, 21.04.2018

Zu b):

Wir beweisen die Aussage aus b).

Sei dazu

S_{n}

für alle

n \in ℕ

erfüllbar.
Zu zeigen ist die Erfüllbarkeit von M.

Nach dem Kompaktheitssatz genügt es, die Erfüllbarkeit von

M^{ʹ}

für jede endliche Teilmenge

M^{ʹ}

von M zu zeigen.

Sei also eine endliche Teilmenge

M^{ʹ}

von M beliebig vorgegeben.
Zu zeigen ist die Erfüllbarkeit von

M^{ʹ}

.

Hilfsbehauptung: Es existiert ein

n \in ℕ

mit

M^{ʹ} \subseteq S_{n}

.

Wenn die Hilfsbehauptung bewiesen ist, ist

M^{ʹ}

als Teilmenge der erfüllbaren Menge

S_{n}

erst recht erfüllbar, was zu zeigen war.

Fehlt nur noch der Beweis der Hilfsbehauptung:
Da

M^{ʹ}

eine endliche Teilmenge von

M = {F_{1}, F_{2}, \dots}

ist, hat

M^{ʹ}

die Gestalt

M^{ʹ} = {F_{i_{1}}, F_{i_{2}}, \dots, F_{i_{k}}}

für gewisse

i_{1}, i_{2}, \dots, i_{k}

für ein

k \in ℕ

. Sei

n := max (i_{1}, i_{2}, \dots, i_{k})

. Dann ist

i_{1}, i_{2}, \dots, i_{k} \leq n \leq 2^{n}

und damit

F_{i_{1}}, F_{i_{2}}, \dots, F_{i_{k}} \in S_{n}

, also wie gewünscht

M^{ʹ} = {F_{i_{1}}, F_{i_{2}}, \dots, F_{i_{k}}} \subseteq S_{n}

incc1 aktiv_icon

00:34 Uhr, 22.04.2018

hmm, warum kann ich bei der

b)

nicht genau wie bei der

a)

irgendwelche Formeln aussuchen, also

Bei

b)

F_{1} = a, F_{2} = b,

F_3=¬a,

F_{4} = c, F_{5} = d, F_{6} = e, F_{7} = f, . .

.

(sry für die blöden fragen^^)

tobit aktiv_icon

07:51 Uhr, 22.04.2018

Du darfst und sollst hier gerne auch "blöde" Fragen stellen. :-)
Nur wenn du sie stellst, kann ich darauf eingehen.

Die Aussage aus a) ist im Allgemeinen falsch (d.h. nicht immer richtig). Um das einzusehen, genügt EIN Gegenbeispiel.

Die Aussage aus b) ist immer richtig. Um das einzusehen, genügt die Betrachtung eines Beispiels nicht. Denn wenn die Aussage in diesem Beispiel stimmt, wissen wir noch lange nicht, ob sie immer stimmt.

Dennoch kann die Betrachtung von Beispielen dem Verständnis und damit der Lösungsfindung helfen.
Schauen wir uns mal das Beispiel
F1=a,F2=b, F3=¬a,
F4=c,F5=d,F6=e,F7=f,...
bei b) an.
Dann ist z.B.

S_{2} = {F_{1}, F_{2}, F_{3}, F_{4}}

nicht erfüllbar.
Also sind nicht alle

S_{n}

erfüllbar.
Somit ist die Aussage aus b) in unserem Beispiel wahr.

Hast du schon das Beispiel bei a) untersucht?
Sind die

R_{n}

erfüllbar? (Also ist

R_{1}

erfüllbar? Ist

R_{2}

erfüllbar? Ist

R_{3}

erfüllbar? ...)
Ist

M

erfüllbar?

incc1 aktiv_icon

10:24 Uhr, 22.04.2018

Also dieses Beispiel sowohl für

a)

als auch für

b) :

F_{1} = a, F_{2} = b, F_{3} = \neg a, F_{4} = c, F_{5} = d, F_{6} = e, F_{7} = f, . .

.

"Sind die

R_{n}

erfüllbar? (Also ist

R_{1}

erfüllbar? Ist

R_{2}

erfüllbar? Ist

R_{3}

erfüllbar?

...)

Ist

M

erfüllbar?"
Ich würde sagen, dass alle drei

(R_{1}, R_{2}, R_{3})

jeweils selber erfüllbar sind, aber die Vereinigung aus zum Beispiel

R_{1}

und

R_{2}

sind nicht erfüllbar. Und da schon eine endliche Teilmenge von

R_{n}

unerfüllbar ist, ist auch

R_{n}

unerfüllbar und somit M?

Und das selbe könnte ich doch dann für

b)

behaupten, oder?

"Dann ist

z . B

S 2 = {F 1, F 2, F 3, F 4}

nicht erfüllbar.
Also sind nicht alle Sn erfüllbar.
Somit ist die Aussage aus

b)

in unserem Beispiel wahr."

Das verstehe ich leider nicht... Nach dem Kompaktheitssatz, wenn schon eine endliche Teilmenge von

S_{n}

also

S_{2}

nicht erfüllbar ist, dann ist doch

S_{n}

unerfüllbar... (genau wie bei der

a))

tobit aktiv_icon

12:22 Uhr, 22.04.2018

" Ich würde sagen, dass alle drei (R1,R2,R3) jeweils selber erfüllbar sind,"

Genau. Die Mengen

R_{4}, R_{5}, R_{6}, \dots

sind ebenfalls jeweils erfüllbar. Somit sind alle

R_{n}

erfüllbar.

" aber die Vereinigung aus zum Beispiel R1 und R2 sind nicht erfüllbar. "

Ja. (Es gilt

R_{1} = {F_{1}, F_{2}}

R_{2} = {F_{2}, F_{3}}

und damit

R_{1} \cup R_{2} = {F_{1}, F_{2}, F_{3}}

.)
Wegen

R_{1} \cup R_{2} \subseteq M

ist

M

erst recht nicht erfüllbar.

" Und da schon eine endliche Teilmenge von Rn unerfüllbar ist, ist auch Rn unerfüllbar "

Nein, im Beispiel sind alle

R_{n} = {F_{n}, F_{n + 1}}

jeweils erfüllbar. Für die Fälle

n = 1, 2, 3

hast du das ja selbst oben festgestellt.
(Wenn du tatsächlich eine unerfüllbare Teilmenge von irgendeinem

R_{n}

finden würdest, wäre in der Tat auch

R_{n}

unerfüllbar. Aber das ist nicht möglich.)

Zusammengefasst: Im Beispiel sind alle

R_{n}

erfüllbar,

M

ist jedoch nicht erfüllbar.
Also ist die Aussage aus a) für dieses Beispiel falsch.

" Und das selbe könnte ich doch dann für b) behaupten, oder? "

Was M angeht, ja. Die

R_{n}

tauchen hingegen bei b) ja gar nicht auf. Und die

S_{n}

sind im Gegensatz zu den

R_{n}

im Beispiel ja nicht alle erfüllbar.

" Nach dem Kompaktheitssatz, wenn schon eine endliche Teilmenge von Sn also S2 nicht erfüllbar ist, dann ist doch Sn unerfüllbar... (genau wie bei der a)) "

Im Beispiel ist

S_{n}

erfüllbar für

n = 1

und nicht erfüllbar für

n \geq 2

.
Wie auch immer: Jedenfalls sind nicht alle

S_{n}

erfüllbar (im Gegensatz zu den

R_{n}

aus a), die allesamt erfüllbar waren).
Damit taugt unser Beispiel nicht als Gegenbeispiel bei b).
(Und wir werden auch gar kein Gegenbeispiel finden, denn die Aussage b) ist stets wahr.)

incc1 aktiv_icon

19:42 Uhr, 22.04.2018

"(Wenn du tatsächlich eine unerfüllbare Teilmenge von irgendeinem Rn finden würdest, wäre in der Tat auch Rn unerfüllbar. Aber das ist nicht möglich.)"

Aber was würde passieren wenn wir beispielsweise diese Formeln nehmen würden:
F1=a,F2=¬a,F3=b,F4=c,F5=d,F6=e,F7=f,...

Dann ist doch

R_{n}

nicht für alle

n

erfüllbar und somit muss

a)

wahr sein?

Und zuletzt: Könntest du mir vielleicht noch deinen formalen Beweis für

b)

oben erklären bzw. die Hilfsbehauptung?
Also:
Wie kommst du auf die Gestalt

M'

bzw. wie kann ich die indexe

i

mit den Zahlen daneben verstehen? Und was macht die Funktion

n := max (. .

. ) genau?

Danke schonmal für deine Hilfe.

tobit aktiv_icon

03:09 Uhr, 23.04.2018

" Aber was würde passieren wenn wir beispielsweise diese Formeln nehmen würden:
F1=a,F2=¬a,F3=b,F4=c,F5=d,F6=e,F7=f,...

Dann ist doch Rn nicht für alle n erfüllbar und somit muss a) wahr sein? "

Ja genau, für dieses Beispiel trifft die Aussage aus a) zu.
Sie trifft für manche Beispiele zu, für andere nicht.
Damit ist sie im Allgemeinen falsch.

" Und zuletzt: Könntest du mir vielleicht noch deinen formalen Beweis für b) oben erklären bzw. die Hilfsbehauptung? "

Die Hilfsbehauptung ist übrigens anschaulich ziemlich naheliegend und wird möglicherweise auch ohne Beweis akzeptiert:
Wenn

M^{ʹ}

eine endliche Teilmenge von

M

ist, ist

M^{ʹ}

eine Teilmenge von

S_{n}

, wenn man nur n "genügend groß" wählt.
Mein Beweis führt im Einzelnen aus, wie man ein solches "genügend großes" n finden kann.

" Wie kommst du auf die Gestalt M′ "

Da

M^{ʹ}

endlich ist, hat

M^{ʹ}

nur endlich viele Elemente

H_{1}, \dots, H_{k}

für ein

k \in ℕ

.
Da

M^{ʹ}

eine Teilmenge von

M

ist, gilt z.B. (im Falle

k \geq 1

)

H_{1} \in M

.
Wegen

M = {F_{1}, F_{2}, \dots}

gibt es somit ein

i_{1} \in ℕ

mit

H_{1} = F_{i_{1}}

.
Analog gibt es (im Falle

k \geq 2

) ein

i_{2} \in ℕ

mit

H_{2} = F_{i_{2}}

.
Usw.
Auf diese Weise erhält man eine Darstellung der Form

M^{ʹ} = {F_{i_{1}}, F_{i_{2}}, \dots, F_{i_{k}}}

.

" bzw. wie kann ich die indexe i mit den Zahlen daneben verstehen? "

Die Indizes

i_{1}, \dots, i_{k}

sind natürliche Zahlen.

" Und was macht die Funktion n:=max(... ) genau? "

Gemeint ist das Maximum der natürlichen Zahlen

i_{1}, \dots, i_{k}

, also die größte unter diesen (endlich vielen) natürlichen Zahlen.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1423485

1423185

	Status: nicht eingeloggt	Noch nicht registriert?