Vollständige logische Signaturen & Abzählbarkeit?

Question

Wie überprüfe ich, ob es sich um eine vollständige logische Signatur handelt und ob eine Menge abzählbar ist?

Eine Beispiel-Lösung/Vorangehensweise an den Beispielen: {→, ¬} (für Beweis der Vollständigen logischen Signatur) und wenn A abzählbar ist, dann ist auch B ⊆ A abzählbar (für Beweis der Abzählbarkeit), wäre nett! ^^

Danke im Voraus

Comments

Hat jemand eine Idee?

Answer 1

ob es sich um eine vollständige logische Signatur handelt

Drücke jedes Element einer bekanntermaßen vollständigen logischen Signatur durch die zu prüfende logische Signatur aus.

ob eine Menge abzählbar ist

Um zu beweisen dass eine Menge \(M\) abzählbar ist, zeige dass es eine Bijektion zwischen \(M\) und der Menge der natürlichen Zahlen gibt. Dabei hilft oft ein Vorgehen analog zu Cantors erstem Diagonalargument.

Um zu beweisen dass \(M\) nicht abzählbar ist, zeige dass es eine solche Bijektion nicht gibt. Dabei hilft oft ein Vorgehen analog zu Cantors zweitem Diagonalargument.

Comments

Die Boolesche Standardsignatur heißt {¬,∧,∨}, somit muss ich beim Beispiel {→, ¬} nur "→" beweisen und versuchen "→" als ¬ oder ∧ oder ∨ auszudrücken, richtig? Welche Funktion nehme ich denn dafür? Einfach A → B == ¬A ∨ B, dann fertig? {→, ¬} ist also eine vollständige logische Signatur, denn "→" lässt sich durch ¬ und ∨ darstellen?

---

somit muss ich beim Beispiel {→, ¬} nur "→" beweisen und versuchen "→" als ¬ oder ∧ oder ∨ auszudrücken

Umgekehrt. Du musst

1. ¬ mittels → und ¬ darstellen (was trivial ist)
2. ∧ mittels → und ¬ darstellen
3. ∨ mittels → und ¬ darstellen (was wegen
            A∨B ≡ ¬(¬A ∧ ¬B)
   ebenfalls trivial ist, wenn du 1. und 2. schon hast)
   

---

Ich danke dir