Wiskundige logica: verschil tussen versies

Ga naar: navigatie, zoeken
Regel 9: Regel 9:
 
== Examen juni 2005 ==
 
== Examen juni 2005 ==
  
1) Bewijs: een sigma-1-zin die waar is in N is bewijsbaar uit PA_0.
+
1) Bewijs: een <math>\sigma-1</math>-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):
 
2) Vraag komt letterlijk uit cursus (ergens in laatste 11 blz van deel III):
"Zij T een berekenbare theorie ... ... ... Bewijs dat de afbeelding N^2 -> N:
+
"Zij T een berekenbare theorie ... ... ... Bewijs dat de afbeelding <math>\mathbb{N}^2 \rightarrow \mathbb{N}:
(m,n) ->F(m,n) berekenbaar is.
+
(m,n) \mapsto F(m,n)</math> berekenbaar is.
  
 
Hierbij moet je twee dingen zeggen:
 
Hierbij moet je twee dingen zeggen:
Regel 37: Regel 37:
 
== Examen juni 2006 ==
 
== Examen juni 2006 ==
  
1) De bewering dat elke berekenbare afbeelding van \N naar \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.
+
1) De bewering dat elke berekenbare afbeelding van <math>\mathbb{N}</math> naar <math>\mathbb{N}</math> 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)  
 
2)  
Regel 43: Regel 43:
 
   b) Formuleer en bewijs de stelling over het bestaan van infinitesimalen.
 
   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: \R \to \R\}$. Geef een zo eenvoudig mogelijke uitdrukking voor $$A^{\omega^\omega}$$ waarin A niet voorkomt en waarin $\omega$ slechts een keer voorkomt.
+
3) Zij A het kardinaalgetal van de verzameling van alle deelverzamelingen van de verzameling <math>\{f | f: \mathbb{R} \to \mathbb{R}\}</math>. Geef een zo eenvoudig mogelijke uitdrukking voor <math>A^{\omega^\omega}</math> waarin A niet voorkomt en waarin <math>\omega</math> slechts een keer voorkomt.
  
 
4) Vul de volgende redering aan met alle verzwegen details:  
 
4) Vul de volgende redering aan met alle verzwegen details:  
Er bestaan berekenbare relaties op $\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.
+
Er bestaan berekenbare relaties op <math>\mathbb{N}</math> 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 <math>n \in R_m</math> berekenbaar is.
  
 
5) In deze oefening speelt de volledigheidsstelling en/ of de compactheidsstelling een belangrijke rol.
 
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.
+
   a) Bewijs dat er geen eindige theorie in <math>L_{+\cdot}</math> 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.
+
   b) Bewijs dat er geen theorie in de taal <math>L_{+\cdot}</math> bestaat waarvan de modellen precies de eindige velden zijn.
  
 
[[Categorie: mw]]
 
[[Categorie: mw]]
 
[[Categorie: mi]]
 
[[Categorie: mi]]

Versie van 18 dec 2009 om 14:14

Prof. Jan Denef

Inleiding

Ter verduidelijking: het gaat hier niet om Wiskundige logica en structuren uit eerste bachelor.

Jan Denef geeft in de licenties namelijk een gevorderd vak Wiskundige Logica.

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.


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.