Wiskundige logica

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. Sinds 2024-2025 wordt dit vak gegeven door Nicolas Daans.

Examenvragen

Examen Januari 2023

1. Zij $\kappa >{\mathrm{\aleph }}_0$ een reguliere kardinaal ($\mathrm{c}\mathrm{o}\mathrm{f}(\kappa )=\kappa$). Een deelverzameling $C\subseteq \kappa$ is een club als elke deelverzameling $A\subseteq C$ gesloten is, i.e. dat $\mathrm{s}\mathrm{u}\mathrm{p}(A)\in C\cap \{\kappa \}$ en $C$ cofinaal is in $\kappa$, i.e. voor elke $x\in \kappa$ bestaat er een $y\in C$ zodat $x<y$.
   1. Bewijs dat, als $C_1$ en $C_2$ een club zijn, dan is $C_1\cap C_2$ ook een club.
      Hint: beschouw voor $\alpha \in \kappa$ rijen $({\beta }_n{)}_n$ in $C_1$ en $({\gamma }_n{)}_n$ in $C_2$ zodat $\alpha <{\beta }_0<{\gamma }_0<{\beta }_1<{\gamma }_1<\cdots$.
   2. Waarom is de voorwaarde dat $\mathrm{c}\mathrm{o}\mathrm{f}(\kappa )>{\mathrm{\aleph }}_0$ nodig? Geef een voorbeeld van twee gesloten ongebegrense deelverzamelingen van ${\mathrm{\aleph }}_0$ met lege doorsnede.
2. Beschouw een taal ${ℒ}$ met een enkel functiesymbool $+$ met ariteit 2. Beschouw ${ℒ}$-structuren $\mathfrak{𝔑}=\mathbb{\mathbb{Z}}$ en $\mathfrak{𝔐}=\mathbb{\mathbb{Q}}$ waarin $+$ de gebruikelijke optelling is. Zijn $\mathfrak{𝔑}$ en $\mathfrak{𝔐}$ elementair equivalent, m.a.w. zijn dezelfde ${ℒ}$-zinnen waar in $\mathfrak{𝔑}$ en $\mathfrak{𝔐}$? Geef argumenten.
3. Beschouw de theorie $T$ in de taal ${{ℒ}}_{\text{ring}}$ van de ringen die bestaat uit alle zinnen die waar zijn in elk eindig veld.
   1. Bewijs dat $T$ consistent is.
   2. Bewijs dat $T$ modellen heeft van alle oneindige kardinaliteiten.
   3. Bewijs dat $T$ niet compleet.
   4. Geef een voorbeeld van een theorie $T\subseteq T^{\prime }$ die wel compleet is.
4. Er is een zin die de consistentie van de rekenkunde van Peano $PA$ uitdrukt (zie 5.7.7). Toch heeft de theorie die bestaat uit de negatie van deze zin toegevoegd aan $PA$ een model. Verklaar.

Examen Januari 2021

• Volledig open boek

1. Hfdst 1 oefening 1: een ordinaal $\alpha$ is een limietordinaal als en slechts als er een ordinaal $\beta$ bestaat zodat $\alpha =\omega \beta$. Hint: kijk naar Euclidische deling.
2. Neem L de taal met een 2-ary functiesymbool. Neem modellen $\mathbb{\mathbb{Z}}$ met de standaardoptelling en $\mathbb{\mathbb{Z}}\oplus \mathbb{\mathbb{Z}}$ met optelling $(a,b)+(c,d)=(a+c,b+d)$. Bewijs dat deze modellen niet elementair equivalent zijn. Hint: even getallen
3. Bewijs dat als T een beslisbare theorie en $\varphi$ een L-zin dat $T\cup \{\varphi \}$ beslisbaar is. (Dit is ook oefening 5.2.6 in het boek).
4. Als $f,g:M\to M$ definieerbare functies zijn, bewijs $g\circ f$ definieerbaar is.
5. Stel dat T modellen heeft van willekeurige eindige grootte, dus voor alle n bestaat een eindig model met meer dan n elementen, bewijs dat T een oneindig model heeft.
6. Bewijs dat voor elke formule $\varphi (x)$ er een formule $\psi (x)=Q_1{y}_1{Q}_2{y}_2\dots Q_l{y}_l({\psi }_0(x,y_1,y_2,\dots ,y_l))$ bestaat met elke $Q_i$ een kwantor en ${\psi }_0$ kwantorvrij zodat $\models \mathrm{\forall }x(\varphi (x)\leftrightarrow \varphi (x))$.

Examen augustus 2019

• Deel gesloten boek

1. Geef de neerwaartse en opwaartse stellingen van Löwenheim-Skolem. Schets de bewijzen met de hoofdideeën.
2. Waartoe kan kwantoreneliminatie dienen?

• Deel open boek

1. Zij $X$ een oneindige verzameling. Bewijs dat er een bijectie $f:X\to X$ bestaat zodat $f^{(n)}(x)=f\circ f\circ ...\circ f(x)\ne x$ voor alle $x\in X$ en voor alle $n\in {\mathbb{\mathbb{N}}}_{>0}$.
2. Pas Propositie 2.6.13 en het bewijs zo aan dat $C$ 'minimaal' is, namelijk: als $T^{+}⊢c=d$ voor $c,d\in C$, dan is $c=d$. Bewijs verder dat voor elke ${{ℒ}}^{+}$-formule $\varphi (x_1,...,x_n)$ (met $n>0$) er een element $(c_1,...c_n)\in C^n$ bestaat zodat $T^{+}⊢\mathrm{\exists }{x}_1\mathrm{\exists }{x}_2...\mathrm{\exists }{x}_n\varphi (x_1,...,x_n)\to {\varphi }_{c_1/x_1,...,c_n/x_n}$.

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=$\mathbb{\mathbb{Z}}$ en N=$\mathbb{\mathbb{Q}}$ waarbij we dit functiesymbool als + interpreten in beide structuren. Zijn M en N elementair equivalent? Bijvraag: is N elementair equivalent met de structuur $\mathbb{ℝ},+$?
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 $p$ bestaat er een model ${{ℳ}}_p$ van ${𝒯}$ met $p$ 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 $\mathrm{\forall }{v}_{i_1}\cdots \mathrm{\forall }{v}_{i_s}(\theta (v))$ waarbij $\theta (v)$ geen kwantoren bevat. Beschouw een taal ${ℒ}$ en een theorie ${𝒯}$ over ${ℒ}$. Bewijs dat voor een ${ℒ}$-formule $\phi (v)$ hieronder (ii) volgt uit (i). (i) Er bestaat een universele formule $\psi (v)$ zo dat ${𝒯}\models \mathrm{\forall }v(\phi (v)\leftrightarrow \psi (v))$. (ii) Als ${ℳ}$ en ${𝒩}$ modellen van ${𝒯}$ zijn, $M\subset N$ (dit zijn de respectievelijke universums) en voor $a\in M^n$ geldt dat ${𝒩}\models \phi (a)$, dan geldt ook dat ${ℳ}\models \phi (a)$.

• 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 ${{ℳ}}_0$, ${ℳ}$ en ${𝒩}$ en elementaire inbeddingen $i:{{ℳ}}_0\to {ℳ}$ en $j:{{ℳ}}_0\to {𝒩}$. Geef een ${ℒ}$-structuur ${𝒦}$ en elementaire inbeddingen $f:{ℳ}\to {𝒦}$ en $g:{𝒩}\to {𝒦}$ zo dat $f\circ i=g\circ j$. [Na een tijdje kon je ook vergemakkelijken tot de lege taal ${ℒ}$=${{ℒ}}_{=}$ en $\mathbb{\mathbb{N}}$ als universum van ${{ℳ}}_0$, ${ℳ}$ en ${𝒩}$.]
3. [Exercise 3.4.27 a) uit Marker] We noemen een functie $f:{\mathbb{ℝ}}^n\to \mathbb{ℝ}$ algebraïsch als er een veelterm $p$ bestaat die niet identiek nul is en voldoet aan $p(a,f(a))=0$ voor alle $a\in {\mathbb{ℝ}}^n$. 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 $f$ kan schrijven met behulp van een booleaanse combinatie met veeltermen en $>0$. 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 $=0$. De negatie kan alvast weggewerkt worden.]
4. [Exercise 4.5.3 uit Marker] Zij ${ℳ}$ een ${ℒ}$-structuur, $M$ het universum van ${ℳ}$ en $A\subset M$. We zeggen dat $c\in M$ definieerbaar is over $A$ als er een ${ℒ}$-formule $\phi (x)$ bestaat zo dat $\{c\}=\{x\in M\mid {ℳ}\models \phi (x)\}$. De verzameling van zulke $c$ noteren we met $dcl(A)$. Bewijs dat als $a,b\in M^n$ en $t{p}^{{ℳ}}(a/A)=t{p}^{{ℳ}}(b/A)$, dan $t{p}^{{ℳ}}(a/dcl(A))=t{p}^{{ℳ}}(b/dcl(A))$.

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 $\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.