Logika dla informatyków/Ćwiczenia 12

Ćwiczenie 1

Napisać zdanie logiki drugiego rzędu aksjomatyzujące pojęcie porządku ciągłego i wywnioskować stąd, że dla tej logiki nie zachodzi także dolne twierdzenie Skolema-Löwenheima.

Ćwiczenie 2

Pokazać, że odpowiednik twierdzenia o zwartości nie zachodzi dla logiki drugiego rzędu.

Ćwiczenie 3

Napisać zdanie MSO, którego wszystkie skończone modele to dokładnie te grafy, które są 3-kolorowalne.

Ćwiczenie 4

Napisać zdanie ${\mathrm{\Sigma }}_1^1$, którego wszystkimi modelami są dokładnie struktury skończone.

Ćwiczenie 5

Napisać zdanie MSO, które definiuje język regularny składający się z tych wszystkich słów nad $A_1=\{0,1\}$, w których liczba jedynek jest parzysta.