Matfyz Wiki
{{TIN064 Skripta}}
Zavedení produktivních a kreativních množin
Definice
Množina B je produktivní, pokud existuje ČRF
\varphitaková, že\forall x: W_x \subseteq B \Rightarrow (\varphi(x)\downarrow \And \varphi(x) \in B \smallsetminus W_x). Funkce\varphise pak nazývá produktivní funkce (pro množinu B).Množina A je kreativní, pokud je RS a její doplněk
\overline{A}je produktivní.
Poznámky:
\varphizde neoznačuje univerzální funkci. (Tato dvojznačnost se ovšem používá i na přednášce a ve skriptech, takže je dobré na to být připraven a rozlišovat: toto\varphinemá index.)Místo
(\varphi(x)\downarrow \And \varphi(x) \in B \smallsetminus W_x)se někdy zkráceně píše\varphi(x)\downarrow \in B \smallsetminus W_x. (Ono kdyby se ten znak konvergence vynechal, tak to vyjde asi nastejno — nedefinovaná hodnota nemůže být elementem. Píše se to ale takto také proto, aby se naznačilo, že konvergence není samozřejmá. I když uvidíme za chvíli...)Nechť B je non-RSM a
W_x \subseteq B. Pak víme, že zaručeně existuje nějakéy \in B \smallsetminus W_x, protože jinak by seW_xrovnalo B. Problém je v tom, jak takovéyefektivně najít — tedy sestrojit ČRF\varphitak, aby\varphi(x)=y.Produktivní množina nemůže být RSM (kdyby byla, byla by pro nějaké x sama svou podmnožinou a produktivní funkce by musela vrátit bod nový bod mimo - spor (množinový rozdíl z definice je tady prázdná množina a v té nemůže být žádný prvek).
Proč zkoumáme takhle strašně divnou množinu? Godelova věta, ke které celou dobu směřujeme, vlastně dokazuje, že množina pravdivých výroků v matematické logice je produktivní (nějakým odvozovacím pravidlem
\varphinám z různých podmnožin pravdivých výroků vypadává vždy nějaký mimo ně) a tudíž není RSM.Jako mnemotechnickou pomůcku pro produktivní funkce množiny nabízím toto: produktivní funkce produkuje (jak se dozvíme v důkazu následující věty) nekonečně nových bodů.
Příklady
Vzpomeňme si na množinu
K=\{x|x \in W_x\}. Tato množina je kreativní. * *