{{TIN064 Skripta}}

Zavedení produktivních a kreativních množin

Definice

• Množina B je produktivní, pokud existuje ČRF $\varphi$ taková, že $\forall x: W_x \subseteq B \Rightarrow (\varphi(x)\downarrow \And \varphi(x) \in B \smallsetminus W_x)$. Funkce $\varphi$ se 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:

• $\varphi$ zde 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 $\varphi$ nemá 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 se $W_x$ rovnalo B. Problém je v tom, jak takové $y$ efektivně najít — tedy sestrojit ČRF $\varphi$ tak, 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 $\varphi$ ná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í. * *

Produktivní obsahuje nekonečnou RSM

Důsledek

Věta o produktivní ORF

Jak se nedokazuje

Jak se dokazuje

Dodatek

Věta o produktivní ORF bijekci

Konstrukce surjektivní funkce g

Konstrukce prosté funkce h

Věta o ekvivalenci pojmů

Důkaz: 1. implikuje 2.

Důkaz: 2. implikuje 3.

Důkaz: 3. implikuje 1.

Jiná věta o ekvivalenci pojmů

Důkaz: 1. implikuje 2.

Důkaz: 2. implikuje 3.

Důkaz: 3. implikuje 1.

Úplně produktivní množiny

Definice

Produktivní jsou úplně produktivní

Tot je produktivní