Wiskundige logica

Ga naar: navigatie, zoeken

Samenvattingen

Klik hier om de samenvattingen te bekijken

Informatie over het examen

Sinds 2012-2013 is dit vak tweejaarlijks en wordt het gegeven door Raf Cluckers (daarvoor door Jan Denef). De inhoud is daarmee ook veranderd.

Examenvragen

Examen januari 2019

Er was eerst een stuk gesloten boek (ongeveer 30 minuten) dat je mondeling moest gaan uitleggen. Daarna waren er twee oefeningen open boek.

  • Deel gesloten boek
  1. Wat is een definieerbare verzameling? Wat is een definieerbare functie? Geef een voorbeeldje.
  2. Geef de volledigheidsstelling van Gödel.
  • Deel open boek
  1. Zij L de taal met één functiesymbool van ariteit 2 en geen andere symbolen. Beschouw de structuren M= en N= waarbij we dit functiesymbool als + interpreten in beide structuren. Zijn M en N elementair equivalent? Bijvraag: is N elementair equivalent met de structuur ?
  2. Zij L de taal van de ringen. We beschouwen de theorie T waarbij een zin phi tot T behoort als en slechts als phi waar is in elk eindig veld. Toon aan dat T consistent is. Bewijs dat T modellen heeft van elke oneindige kardinaliteit. Toon aan dat T niet volledig is. Geef een concrete theorie die T bevat en volledig is.

Examen 29 januari 2013

Voor de delen die gesloten en open boek waren, moest je 1 uur, respectievelijk 3 uur rekenen. Dit bleek evenwel niet strikt te zijn. Er werd bij aanvang gezegd dat het niet de bedoeling was om alle vragen volledig op te lossen. Ideeën waren dus al veel waard en bovendien mocht je veel hulp verwachten.

  • Deel gesloten boek
  1. Zij een taal en een theorie over . Voor elk priemgetal bestaat er een model van met elementen. Toon aan dat een model met oneindige kardinaliteit heeft.
  2. [Deel van Exercise 2.5.12 uit Marker] Met een universele formule bedoelen we een formule van de vorm waarbij geen kwantoren bevat. Beschouw een taal en een theorie over . Bewijs dat voor een -formule hieronder (ii) volgt uit (i). (i) Er bestaat een universele formule zo dat . (ii) Als en modellen van zijn, (dit zijn de respectievelijke universums) en voor geldt dat , dan geldt ook dat .
  • Deel open boek
  1. [Deel van Exercise 2.5.12 uit Marker] Toon aan dat hierboven (i) volgt uit (ii). [Het werd aangeraden te wachten met deze opgave tot de volgende hulp gegeven was: baseer je op het bewijs van Theorem 2.3.9 op p. 47 in Marker. Een andere optie was om over dat bewijs enkele vragen te beantwoorden.]
  2. [Exercise 2.5.11 uit Marker] We hebben een taal , -structuren , en en elementaire inbeddingen en . Geef een -structuur en elementaire inbeddingen en zo dat . [Na een tijdje kon je ook vergemakkelijken tot de lege taal = en als universum van , en .]
  3. [Exercise 3.4.27 a) uit Marker] We noemen een functie algebraïsch als er een veelterm bestaat die niet identiek nul is en voldoet aan voor alle . Gebruik kwantoreneliminatie om te bewijzen dat een semialgebraïsche functie algebraïsch is. [Later toegevoegde hint: de kwantoreneliminatie zit al verborgen in de manier waarop je de grafiek van kan schrijven met behulp van een booleaanse combinatie met veeltermen en . Het is essentieel dat we met een grafiek te maken hebben om in te zien dat dit herleid kan worden tot een booleaanse combinatie met veeltermen en . De negatie kan alvast weggewerkt worden.]
  4. [Exercise 4.5.3 uit Marker] Zij een -structuur, het universum van en . We zeggen dat definieerbaar is over als er een -formule bestaat zo dat . De verzameling van zulke noteren we met . Bewijs dat als en , dan .


Oudere examens

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 naar 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 . Geef een zo eenvoudig mogelijke uitdrukking voor waarin A niet voorkomt en waarin slechts een keer voorkomt.

4) Vul de volgende redering aan met alle verzwegen details: Er bestaan berekenbare relaties op 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 berekenbaar is.

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

  a) Bewijs dat er geen eindige theorie in  bestaat waarvan de modellen precies de velden met karakteristiek nul zijn.
  b) Bewijs dat er geen theorie in de taal  bestaat waarvan de modellen precies de eindige velden zijn.

Examen juni 2005

1) Bewijs: een -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 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.