IB107 úkol 2, příklad 1 Odevzdání: 3. 12. 2020 23:59
Jméno: Adalbert Kolínský UČO: 1234567
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [2,5 bodu] V následujícím zadání označme 2N množinu všech sudých přirozených čísel (včetně 0).
Uvažme množinu
A = {i | 2N ⊆ range(ϕi)}.
1. Rozhodněte a dokažte, zda je množina A rekurzivní.
2. Rozhodněte a dokažte, zda je množina A rekurzivně spočetná.
Ukážeme, že A není rekurzivně spočetná. Tím pádem nemůže být ani rekurzivní, tedy odpověď na
obě otázky je NE.
Použijeme 3. Riceovu větu. Nejprve ověřme, že A respektuje funkce. Nechť i, j ∈ N jsou indexy
takové, že ϕi = ϕj a i ∈ A. Pak 2N ⊆ range(ϕi) = range(ϕj), tedy rovněž j ∈ A. Množina A tedy
vskutku respektuje funkce.
Nyní uvažme funkci θ, která je identitou na přirozených číslech, tj. θ(x) = x pro všechna x ∈ N.
Zřejmě θ je vyčíslitelná (počítá ji např. program begin x1 := x1 end) a navíc
range(θ) = N ⊇ 2N.
Tedy {i | ϕi = θ} ⊆ A. Nechť nyní f je libovolné konečné zúžení funkce θ, tj. f ≤ θ a dom(f) je
konečná množina. Protože dom(f) je konečná množina, je i range(f) konečná množina.1 Zejména
tedy 2N, která je nekonečná, nemůže být podmnožinou range(f). Proto
{i | ϕi ≤ θ a dom(ϕi) je konečná množina} ⊆ A.
Z 3. Riceovy věty plyne, že A není rekurzivně spočetná.
1
Pozn. autora: obecně vztah |range(f)| ≤ |dom(f)| platí pro libovolnou funkci typu N → N, a za využití axiomu
výběru platí pro funkce nad libovolnými množinami.
Oblast strojově snímaných informací, nezasahujte. Zde jsou losi.