Wiskundige logica

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Prof. Jan Denef

Examen juni 2012

• Vraag 1 (gesloten boek, schriftelijk, 5 pt):
  • Bewijs de onbeslisbaarheid van de predikatenlogica
  • Bewijs de definieerbaarheid van het stopprobleem
• Vraag 2 (gesloten boek, schriftelijk, 2 pt): Geef een trouwe vertaling van de volgende zin naar predikatenlogica. Je mag gebruik maken van de relatie-identifiers Triangle, Square, Pentagon, LeftOf, Smaller.
  • "Er liggen minstens twee vierkanten links van eenzelfde driehoek die kleiner is dan alle vijfhoeken."
• Vraag 3 (open boek, mondeling, 6 pt):
  • Toon aan dat er een oneindig veld K bestaat zodat voor elke zin t geldt dat t waar is in K als er slechts eindig veel priemgetallen p bestaan zodat t vals is in het veld met p elementen.
  • Toon aan dat er definieerbare relaties zijn op N die niet definieerbaar zijn door middel van een Sigma1-formule.
  • Toon aan dat er geen formule t(x) bestaat met een vrije variabele x zodat voor elk reeel getal r geldt dat t(r) waar is in het veld der reele getallen als en slechts als r een natuurlijk getal is.
• Vraag 4 (open boek, schriftelijk, 5 pt): Zij B de verzameling van berekenbare afbeeldingen van N naar N. Een operator op B is een afbeelding van B naar B.
  • Is de volgende zin waar of vals? Verklaar uw antwoord. "De verzameling van alle deelverzamelingen van B is gelijkmachtig met de verzameling van alle operatoren op B."
  • We zeggen dat twee operatoren P1 en P2 op B equivalent zijn als er een berekenbare afbeelding s van N naar Z bestaat zodat voor alle f in B en alle x in N geldt dat P2(f)(x) = P1(f)(x) + s(x). Bereken het kardinaalgetal van de verzameling der equivalentieklassen van deze equivalentierelatie op de verzameling van alle operatoren op B.

Examen juni 2011

Examen Logica juni 2011

Examen juni 2010

Examen Logica juni 2010

Examen juni 2009

Examen Logica juni 2009

Examen juni 2006

1) De bewering dat elke berekenbare afbeelding van $\mathbb{\mathbb{N}}$ naar $\mathbb{\mathbb{N}}$ sterk representeerbaar is in PA door middel van een $\Sigma_1$-formule, speelt een belangrijke rol voor de tweede onvolledigheidsstelling van G\"odel. Leg uit hoe.

2)

  a) Formuleer en bewijs de compactheidsstelling voor de predikatenlogica.
  b) Formuleer en bewijs de stelling over het bestaan van infinitesimalen.

3) Zij A het kardinaalgetal van de verzameling van alle deelverzamelingen van de verzameling $\{f|f:\mathbb{ℝ}\to \mathbb{ℝ}\}$. Geef een zo eenvoudig mogelijke uitdrukking voor $A^{{\omega }^{\omega }}$ waarin A niet voorkomt en waarin $\omega$ slechts een keer voorkomt.

4) Vul de volgende redering aan met alle verzwegen details: Er bestaan berekenbare relaties op $\mathbb{\mathbb{N}}$ die niet definieerbaar zijn door middel van een $\Delta$-formule, want anders zou er een rij relaties R_1, R_2, \dots bestaan waarin elke berekenbare relatie voorkomt en zodat de relatie $n\in R_m$ berekenbaar is.

5) In deze oefening speelt de volledigheidsstelling en/ of de compactheidsstelling een belangrijke rol.

  a) Bewijs dat er geen eindige theorie in $L_{+\cdot }$ bestaat waarvan de modellen precies de velden met karakteristiek nul zijn.
  b) Bewijs dat er geen theorie in de taal $L_{+\cdot }$ bestaat waarvan de modellen precies de eindige velden zijn.

Examen juni 2005

1) Bewijs: een $\sigma -1$-zin die waar is in N is bewijsbaar uit PA_0.

2) Vraag komt letterlijk uit cursus (ergens in laatste 11 blz van deel III): "Zij T een berekenbare theorie ... ... ... Bewijs dat de afbeelding ${\mathbb{\mathbb{N}}}^2\to \mathbb{\mathbb{N}}:(m,n)\mapsto F(m,n)$ berekenbaar is.

Hierbij moet je twee dingen zeggen: - Omdat T berekenbaar is en omdat uit m het bewijs kan afgeleid worden kan men controleren of er effectief zo'n Theta te vinden op algoritmische wijze en dus ook met behulp van een masjien (hypothese van Church) - Vervolgens kun je starten met (omdat wegens de stelling van vraag 1 als theta(n,y) waar is ze bewijsbaar is) theta(n,0) voor bepaalde duur te trachten bewijzen uit PA_0. Stop en start met theta(n,1) voor bep. duur, stop start terug met theta(n,0). Stop en start dan met theta(n,2) etc. Dit allemaal zolang er geen bewijs gevonden wordt. (een dergelijk bewijs zal eens gevonden worden wegens semi-beslisbaarheid).

3) Geef trouwe vertaling in Tarski-predtaal: Minstens 2 driehoeken bevinden zich achter al de vierhoeken die rechts van alle vijfhoeken liggen.

4) Bewijs dmv WinKE bewijs: (3) is een logisch gevolg van (1) en (2).

   *1* (A x) (U(x) => (A y) (W(y) => ~R(x,y)))
   *2* (A x) (U(x) => (A y) (S(y) => R(x,y)))
   *3* (E x) (U(x) /\ W(x)) => (E y) ~S(y)

5) Bereken |{f:R->R| (E C) zodat C deelverz van R is en C eindig is en f constant is op R\C}|

Reservevraag: zeg alles wat je weet over de formule van Goedel

Andere vraag ipv. 5: Bewijs dat de afbeelding die n -> 2^n definieerbaar is. Maakt gebruik van de beta(n,u,v) in het lemma dat gebruikt wordt bij het bewijs van de definieerbaarheid van berekenbare relaties.