Grundlegende Begriffe

Häufig findet man in mathematischen Sätzen variablenabhängige Aussagen. A(x) sei also eine Aussage, die von der Variablen x abhängt, z.B. A(x) := {“x ist Primzahl"} oder A(s,p) := {“Student s versteht Professor p"}. Gebräuchlich sind sogenannte “Quantoren”, um den Geltungsbereich derartiger Aussagen in knapper Form zu beschreiben. Die Symbole “∀”, “∃”, und “∃!” finden Verwendung und werden folgendermaßen definiert:

  • ∀: "für alle"
  • ∃: "es exestiert ein"
  • ∃!: "es exestiert genau ein"

Hier mit Beispielen:

  • ∀s A(s,p) ”Für alle Studenten s gilt: s versteht den Professor p.“
  • ∃s A(s,p) ”Es gibt einen Studenten s, sodass gilt: s versteht den Professor p.“ Achtung: Dies ist eine Existenzaussage, d.h. es gibt mindestens einen Studenten s, für den die Aussage A(s,p) richtig ist.
  • ∃!s A(s,p) ”Es gibt genau einen Studenten s, der p versteht“(d.h. alle anderen verstehen ihn nicht.)

Entsprechend lassen sich Quantoren kombinieren

  • ∃s ∀p A(s,p): ”Es gibt einen Studenten s, sodass für alle Professoren p gilt: s versteht p.“
  • ∀s ∀p A(s,p): ”Für alle Studenten s gilt: s versteht alle Professoren p.“

Sehr wichtig sind die folgenden Regeln zur Negation von Quantorenaussagen:

  • ¬(∀x A(x)) ⇔∃x (¬A(x)), • ¬(∃x A(x)) ⇔∀x (¬A(x)),

entsprechend gilt:

¬(∃s ∀p A(s,p)) = ¬(∃s (∀p A(s,p)))

= ∀s ¬(∀p A(s,p))

= ∀s ∃p ¬A(s,p).