Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 22

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

Zeige, dass für die beiden Repräsentierungskonzepte zusammenfallen.


Aufgabe *

Es sei

die Menge der geraden natürlichen Zahlen. Es sei die Ausdrucksmenge, die besagt, dass eine assoziative, kommutative Verknüpfung mit als neutralem Element ist. Es sei

Zeige, dass durch in schwach repräsentiert wird, aber nicht stark.


Aufgabe

Es sei

die Menge der geraden natürlichen Zahlen. Es sei die Ausdrucksmenge, die besagt, dass eine assoziative, kommutative Verknüpfung mit als neutralem Element ist. Es sei

und

Es sei

Zeige, dass durch in repräsentiert wird.


Aufgabe

Zeige, dass eine widersprüchliche Ausdrucksmenge Repräsentierungen erlaubt.


Aufgabe

Es sei eine Ausdrucksmenge, die Repräsentierungen erlaube. Zeige, dass jede größere Ausdrucksmenge ebenfalls Repräsentierungen erlaubt.


Aufgabe

Zeige, dass die Gleichheit von natürlichen Zahlen (also die Diagonalrelation in ) durch den Ausdruck in der erststufigen Peano-Arithmetik repräsentierbar ist.


Aufgabe

Es sei das Axiomensystem eines kommutativen Halbringes. Zeige, dass die Gleichheit von natürlichen Zahlen (also die Diagonalrelation in ) durch den Ausdruck in nicht repräsentiert wird.


Aufgabe

Es sei das Axiomensystem eines kommutativen Halbringes. Zeige, dass keine Repräsentierungen erlaubt.

Insbesondere erlauben die erststufigen Peano-Axiome ohne das Induktionsschema keine Repräsentierungen.

Aufgabe

Sei und sei

wobei -mal der Summand vorkommt. Zeige, dass , also die Menge der Vielfachen von , in der erststufigen Peano-Arithmetik durch repräsentiert wird.


Aufgabe

Zeige, dass die Menge der Quadratzahlen in der erststufigen Peano-Arithmetik repräsentiert werden kann.


Aufgabe

Es sei eine widerspruchsfreie und -entscheidbare Ausdrucksmenge.

a) Zeige, dass jede in repräsentierbare Relation -entscheidbar ist.

b) Zeige, dass jede in repräsentierbare Abbildung

-berechenbar ist.


Aufgabe *

Es sei eine arithmetische Ausdrucksmenge ohne freie Variablen und eine Relation. Es seien Ausdrücke in einer freien Variablen . Zeige, dass aus

folgt, dass in die Relation genau dann repräsentiert, wenn in die Relation repräsentiert.


Aufgabe *

Es sei eine arithmetische Ausdrucksmenge und eine Relation. Es seien Ausdrücke in einer freien Variablen . Zeige, dass aus

nicht folgt, dass in die Relation genau dann repräsentiert, wenn in die Relation repräsentiert.


Aufgabe

Es sei eine Aufzählung einer abzählbar-unendlichen Symbolmengen. Berechne die zu Wörtern über diesem Alphabet zugehörige Zahl im Sinne der Primzahlkodierung und umgekehrt.

  1. ,
  2. ,
  3. ,
  4. ,
  5. ,
  6. ,
  7. .


Aufgabe

Es sei eine fixierte natürliche Zahl und

wobei durch die -fache Summe der mit sich selbst realisiert werde. Zeige direkt, dass es Sätze mit

und mit

gibt.




Aufgaben zum Abgeben

Aufgabe (4 Punkte)

Zeige, dass die Menge der Primzahlen in der erststufigen Peano-Arithmetik repräsentiert werden kann.


Aufgabe (4 Punkte)

Es sei eine Aufzählung einer abzählbar-unendlichen Symbolmengen. Berechne die zu Wörtern über diesem Alphabet zugehörige Zahl im Sinne der Primzahlkodierung und umgekehrt.

  1. ,
  2. ,
  3. ,
  4. .


Aufgabe (4 Punkte)

Zeige, dass in der erststufigen Peano-Arithmetik die Addition von natürlichen Zahlen repräsentierbar ist.


Aufgabe (6 Punkte)

Es sei

eine Polynomfunktion mit mit Koeffizienten . Zeige, dass durch den Ausdruck in der erststufigen Peano-Arithmetik repräsentiert wird.



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2018) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)