{{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](#Produktivní%20obsahuje%20nekonečnou%20RSM)) 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ů ##

1. 
1. 
1. 

### Důkaz: 1. implikuje 2. ###

### Důkaz: 2. implikuje 3. ###

### Důkaz: 3. implikuje 1. ###

## Jiná věta o ekvivalenci pojmů ##

1. 
1. 
1. 

### 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í ##