Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Completeness
Hey,
mir ist beim Bearbeiten des aktuellen Aufgabenblatts aufgefallen, dass ich completeness nicht ganz verstanden hab. Und zwar sagt mir https://en.wikipedia.org/wiki/Completeness_(logic), dass es sowohl semantic als auch strong completeness gibt. Fuer die completeness Beweise in der Aufgabenstellung sollen wir hier aber nur semantic completeness zeigen, oder? Zumindest wuerde ich das aus dem Beispielbeweis aus den Folien so folgern. Koennte es auch sein, dass semantic und strong completeness fuer propositional logic aequivalent sind?
Nicht nur für propositional sondern für alle reasonable logics sind die äquivalent. Dass semantic aus strong folgt ist denke ich klar; die Rückrichtung folgt aus dem Deduktionssatz und Kompaktheit (daher brauchen wir reasonable).
…davon abgesehen dass kompaktheit deutlich über reasonable hinaus geht… ähm, ja. Auf jeden fall gilt es für propositional und first-order logic 
Was ist eine reasonable Logic? Ich dachte reasonable war eine Eigenschaft von Kalkülen und nicht Logiken?
Was genau muss kompakt sein? Das ist doch auch wieder nur eine Eigenschaft von Mengen. Also müssen alle Formelmengen kompakt sein oder was?
“Kompaktheit” ist eine Eigenschaft von logiken (eine formelmenge hat ein modell genau dann wenn jede endliche teilmenge ein modell hat. Das ist rein semantisch).
@reasonable - ha, ich hatte die definition falsch im kopf. Nevermind 
Was ich meinte ist auf jeden fall den deduktionssatz und somit die existenz einer Implikation, die sich “vernünftig” verhält; dann kann ich jede logische folgerung auf eine tautologische Implikation reduzieren:
A |= Phi genau dann, wenn für eine endliche teilmenge A’={A1,A2,…,An} gilt: |= (A1 & A2 & … & An) → Phi
Dafür brauch ich natürlich kompaktheit um die endliche Teilmenge zu erhalten und den Deduktionssatz, um Ak |= Phi umzuformen in |= (Ak → Phi)
Point is: Das gilt auf jeden Fall für Aussagenlogik und Prädikatenlogik und ich würde hoffen/vermuten/behaupten für die meisten “normalen” Logiken genauso…