Wenn Leute nicht glauben, dass Mathematik einfach ist, dann nur deshalb, weil sie nicht begreifen, wie kompliziert das Leben ist.
John von Neumann


Auf das Thema antworten  [ 7 Beiträge ] 
Übungsangaben SS10 
Autor Nachricht

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag Übungsangaben SS10
Alle Übungsangaben vom Sommersemester 2010 -- for future reference.

Gabriel.


Zuletzt geändert von gabriel am Do 18-03-2010 20:04:15, insgesamt 1-mal geändert.



Do 18-03-2010 19:53:33
Diesen Beitrag melden
Profil

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag 1. Übung
[ P ist Peano-Arithmetik, Q ist Robinson-Arithmetik ]

1. Beweisen Sie in P: Für alle y ungleich null gibt es ein z mit Sz=y.

2. Beweisen Sie in P: Wenn für alle y phi(x,y), dann für alle y phi(x+1,y),
wobei phi(x,y) die Aussage (x<y oder x=y oder y<x) ist.

3. Beweisen Sie in P den Satz vom minimalen Element, d.h. für jede Formel psi die Aussage "wenn es ein x mit psi(x) gibt, dann auch ein minimales"

4. Beweisen Sie in P die Verlaufsinduktion, d.h. die Aussage:
Wenn für alle x aus phi(<x) die Aussage phi(x) folgt, dann gilt für alle x die Aussage phi(x). (Wobei phi(<x) Abkürzung für "für alle z<x: phi(z)" ist.)

5. Sei A eine semientscheidbare Menge natürlicher Zahlen mit 0 in A. Geben Sie eine berechenbare Funktion f an, die genau Wertebereich A hat.

6. Zeigen Sie, dass alle Axiome von R in Q beweisbar sind.


Do 18-03-2010 19:54:16
Diesen Beitrag melden
Profil

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag 2. Übung
Das sind die Beispiele 3, 4, 5, 6, 7, 8, 10, 11 vom SS08.

3. Zeigen Sie, dass die folgenden Funktionen (oder zumindest einige von ihnen) primitiv rekursiv sind:
$x\dot{-}1,\; x\dot{-}y,\; \mathrm{sign}(x),\; x^y,\; \chi_<,\; \chi_\leq,\; \chi_=,\; 2^x (2y + 1) - 1$
$\chi_R$ sei hier die charakteristische Funktion der (zweistelligen) Relation R (also eine zweistellige Funktion); $x\dot-y := \max(0, x-y)$.

4. Zeigen Sie, dass ihre Lieblingsfunktion primitiv rekursiv ist.

5. Sei f eine primitiv rekursive Funktion (der Einfachkeit halber: einstellig). Dann ist der Graph von f eine primitiv rekursive (zweistellige) Relation.

6. Sei f eine Funktion von $\mathbb N$ nach $\mathbb N$, deren Graph primitiv rekursiv ist. Dann ist f primitiv rekursiv.

7. Wenn $f:\mathbb N \to \mathbb N$ primitiv rekursiv ist, dann auch $\sum f$, definiert durch $(\sum f)(n) = \sum_{i<n} f(i)$. Gilt auch die Umkehrung?

8. Zeigen Sie, dass die folgenden Funktionen primitiv rekursiv sind (oder zumindest einige von ihnen):
1. Konkatenation (Verkettung von Strings) $(x,y) \mapsto xy$
2. Spiegelbild (z.B. $abcab \mapsto bacba$)
3. car und cdr (z.B. $\mathrm{car}(abcab) = a,\; \mathrm{cdr}(abcab) = bcab$)
4. $(x,y) \mapsto |y|$-ter Buchstabe von x. ($\epsilon$ wenn $|x| < |y|$)
5. $(x,y) \mapsto$ längster gemeinsamer Anfangsabschnitt von x und y.
6. $(x,y,z) \mapsto $ der erste in x vorkommende Substring der Form y wird durch z ersetzt.
7. ...


Sa 20-03-2010 20:11:19
Diesen Beitrag melden
Profil

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag 3. Übung
Bitte bereiten Sie für den 15.4.die folgenden (oder einige der folgenden) Beispiele vor:

Erstens: 13-17, 21. (Diese Beispiel sind als Vorbereitung für die Vorlesung hilfreich)

Zweitens, wenn es Ihnen Spaß macht: 25, A1-A4. (Werden in der Vorlesung kaum oder nicht vorkommen.)

Die Ackermannfunktion ist durch A(0,0)=1, A(x+1,0)=A(x,1) und A(x+1,y+1)=A(x,A(x+1,y)) definiert. Die Funktion A_i ist durch A_i(y)=A(i,y) definiert. Die Funktion DA ist durch DA(x)=A(x,x) definiert.

A1. Für alle i gilt: A_i ist (wohldefiniert und) primitiv rekursiv.
Berechnen Sie A_i(y) für i=0,1,2,3.

A2. A(x,y) ist streng monoton in beiden Argumenten. A(x,y+1) <= A(x+1,y).
Für alle i,j gibt es k (=max(i,j), vielleicht max(i,j)+1) mit: Für alle x: A(i,A(j,x)) < A(k,x).

A3. Für alle primitiv rekursiven f gibt es ein i, sodass für alle x(1), ..., x(k) gilt: f(x(1), ..., x(k)) < A(i, max(x(1), ..., x(k)).

A4. Die Funktion DA ist nicht primitiv rekursiv. Ihr Graph ist aber primitiv rekursiv, und DA ist rekursiv.

Wenn Ihnen diese Beispiele keinen Spaß machen, schauen Sie sich die Beispiele 27-38 an.


So 11-04-2010 01:46:12
Diesen Beitrag melden
Profil

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag 4. Übung
Hier kamen die übriggebliebenen Beispiele von der 3. Übung (Beispiele 27-38).


Do 29-04-2010 20:39:30
Diesen Beitrag melden
Profil

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag 5. Übung ("ein paar schwierige Aufgaben")
Wir betrachten die Sprache L der Peano-Arithmetik (mit Exponentiation)
und definieren die Formel IN(x,y) als Abkürzung von
das x-te Bit von y ist 1,
also genauer:
Es gibt a,b<y mit y=a*2^(x+1) + 2^x + b, und b<2^x.

Zeigen Sie für möglichst viele ZFC-Axiome, dass sie in den natürlichen
Zahlen N gelten, wenn man sie als Formeln der Sprache L interpretiert,
das Element-Symbol also durch die Formel IN(.,.) ersetzt.

(Dies bedeutet, dass man Mengen als Zahlen auffassen kann. ZB
entspricht 0 der leeren Menge, 1=2^0 dem Singleton {0}.
Allgemeiner, wenn n der Menge x entspricht, k der Menge y, dann
entspricht 2^n+2^k der Menge {x,y}.)

Insbesondere für das Extensionalitätsaxiom, das Nullmengenaxiom, das Paarmengenaxiom, das Potenzmengenaxiom und das Vereinigungsmengenaxiom.
(Für eines der ZFC-Axiome ist dies nicht möglich --- für welches?)

Zeigen Sie weiters, dass diese ZFC-Axiome sogar aus PA folgen. (Hier
sind keine formalen Beweise gefragt, aber Sie sollten sich
überlegen, welche Induktionsaxiome Sie verwenden und wo, wenn
überhaupt, infinitäre Überlegungen einfließen.)

Und schließlich noch etwas Schwieriges:

Formulieren Sie das (finitäre) Schubfachprinzip als Satz der Mengenlehre.
Beweisen Sie, dass es (d.h., seine Übersetzung, wenn "x in y" durch
IN(x,y) übersetzt wird) in den natürlichen Zahlen gilt.
Skizzieren Sie einen Beweis aus den PA-Axiomen.


Do 29-04-2010 20:40:45
Diesen Beitrag melden
Profil

Registriert: 04/2008
Beiträge: 25 + 22
Mit Zitat antworten
Beitrag 5. Übung ("einige etwas leichtere Übungen")
Zeigen Sie, dass die folgenden Mengen (bzw die Menge der entsprechenden Gödelzahlen) rekursiv aufzählbar sind:

a. die logischen Axiome (das ist mühsam) [sogar entscheidbar]
b. die Axiome von Q (das ist trivial) [sogar entscheidbar]
c. die Menge aller Q-Beweise (ein Beweis ist eine Folge von Formeln, diese kann in eine Folge von Zahlen übersetzt werden, diese in eine einzige Zahl)
d. die in Q beweisbaren Sätze

e. Schließen Sie, dass jede repräsentierbare Funktion berechenbar ist.


Fr 30-04-2010 00:17:24
Diesen Beitrag melden
Profil
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 7 Beiträge ] 


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst neue Themen in diesem Forum erstellen.
Du darfst Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB © phpBB Group.  |  Designed by STSoftware for PTF  |  © Czechnology 2007 - 2021  |  Deutsche Übersetzung durch phpBB.de