Wiskundige logica: verschil tussen versies

Ga naar: navigatie, zoeken
Regel 51: Regel 51:
 
   a) Bewijs dat er geen eindige theorie in <math>L_{+\cdot}</math> 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 <math>L_{+\cdot}</math> 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.
 +
 +
== Examen juni 2011 ==
 +
[[Media:Examen.pdf|Examen Logica juni 2011]]
 +
  
 
[[Categorie: mw]]
 
[[Categorie: mw]]
 
[[Categorie: mi]]
 
[[Categorie: mi]]

Versie van 27 jun 2011 om 22:21

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.

Examen juni 2011

Examen Logica juni 2011