Nakopírovat to, za co mně ogg pochválil. Dopsat do článku Fundované jádro o mohutnosti definované pomocí ranku. Jazyk (matematická logika) Důkaz (výroková a predikátová logika)

Predikátová logika prvního řádu (často jen predikátová logika, nehrozí-li nedorozumění). je obor matematické logiky, který exaktně formalizuje pojem "dokazatelnost formule" podobně jako výroková logika, ale pro mnohem širší okruh přípustných formulí, neboť povoluje i značky (tzv. kvantifikátory) znamenající "pro každé" a "existuje". Povoluje je jen pro objekty, zatímco logika vyššího řádu i pro množiny objektů či množiny množin objektů atd. Přesto tyto prostředky stačí na vyjádření tak širokého množství matematických tvrzení, že je predikátová logika prvního řádu zdaleka nejšířeji používaným systémem, jak formalizovat pojem důkaz tak, aby odpovídal jeho m

Základními pojmy jsou jazyk, formule, teorie (tj. predikátová teorie prvního řádku) a důkaz. Toto vše jsou pojmy syntaktické, tj. pouhé symboly a pravidla, jak s nimi manipulovat. Zároveň predikátová

Kam. V logice prvního řádu tedy není možné formulovat v Peanově aritmetice matematickou indukci jako jediný výrok „Pro každou množinu x platí “

Relativizace formule

Relativizace formule a absolutnost vlastnosti je pojem z matematické logiky, který se uplatňuje při studiu axiomatických teorií množin jako je ZFC. Vlastnost $\phi$ je absolutní v modelu $\mathbb {M}$ , pokud v rámci modelu (tj. relativizovaně) platí právě tehdy, platí-li absolutně (tj. „objektivně“).

Buď například $\mathbb {M} =\langle M,R\rangle$ model Zermelovy–Fraenkelovy teorie množin (ZF), což znamená, že

$M$ je množina (většina úvah ovšem platí, když $M$ je třída),
$R$ je binární relace na $M$ ,
A jsou splněny Zermelovy–Fraenkelovy axiomy.

ZF je teorie (konkrétně predikátová teorie prvního řádu) se symbolem „náležení“. Model $\mathbb {M} =(M,R)$ tento symbol realizuje relací $R$ na nosné množině $M$ ; ta může být naprosto odlišná od absolutního náležení.

Relativizace

Pojmy „relativizace“ a „absolutnosti“ by neměly smysl pro většinu teorií, například

pro aritmetiku – s výjimkou modelů, jejich nosná množina obsahuje jen přirozená čísla, nebo alespoň objekty, na nichž je v „absolutním“ světě zaveden nějaký druh sčítání.
Euklidovskou geometrii – s výjimkou modelů, na jejichž nosné množině (která reprezentuje body a přímky) je absolutně zavedena nějaká obdoba pojmů rovnoběžnost a bod leží na úsečce.
Obecně: neexistuje-li odpovídající absolutní pojem, nemají tyto pojmy smysl, protože relativní pojem v modelu není s čím srovnávat.

Axiomatická teorie množin má však výsadní postavení, neboť se hodí k popisu „matematické pravdy“ a reprezentuje každý objekt jako množinu (například dvojku jako $\{\emptyset ,\{\emptyset \}\}$ ). Je tedy možné srovnávat relaci $R$ s absolutním náležením. Tato relace může být zcela odlišná od absolutního náležení, ale je-li totožná, říkáme, že model má absolutní náležení.

Dále lze zkoumat absolutnost pojmů, které jsou definovány pomocí náležení. Například $c=\{a,b\}$ (čteno „ $a$ je (neuspořádaná) dvojice prvků $a$ a $b$ “) je zkratkou pro: Pro každé $d$ platí, že $d\in c$ , právě když $d$ je rovno $a$ nebo $b$ .

Relativizace této formule do $M$ je vytvořena

a) Nahrazením každého absolutního náležení

p\in q

relativním náležením

(p,q)\in R

; aby vynikla podobnost (

R

i absolutní náležení jsou binární relace), píše se místo

(p,q)\in R

někdy

pRq\in

.

b)Úpravou každého kvantifikátoru „existuje

p

takové, že“ formulací „existuje

p\in M

takové, že“.

c) Úpravou každého výrazu „Pro každé

p

platí“ formulací „Pro každé

p

, které náleží do

M

, platí“.

Poznámka: Predikátová logika přesně vymezuje, co je to „formule“ (nikoli věta přirozeného jazyka, ale posloupnost symbolů), ovšem zde použití slovního popisu nepředstavuje újmu na přesnosti.

Relativizace formule $c=\{a,b\}$ do modelu $\mathbb {M} =(M,R)$ tedy zní: Pro každé $d\in M$ platí, že $dRc$ , právě když $d$ je rovno $a$ nebo $b$ a označuje se $c=\{a,b\}^{M}$ . Tato formule tedy vyžadovala po jedné úpravě typu a) a typu c). Úprava typu b) nebyla zapotřebí, protože existenční kvantifikátor se ve formuli nevyskytoval.

Absolutnost

Formule $c=\{a,b\}$ se nazývá absolutní v modelu $\mathbb {M}$ , pokud pro každé $a,b,c\in M$ platí $c=\{a,b\}$ právě když $c=\{a,b\}^{M}$ .

Ani v modelu s absolutním náležením nemusí pojem neuspořádané dvojice (tj. $c=\{a,b\}$ ) být absolutní. Pro libovolné, navzájem různé matematické objekty $u,v,w$ takové, že do $M$ náleží $u,v$ a rovněž $\{u,v\}$ , ovšem nikoli $w$ , je formule Nelze pochopit (neznámá funkce „\b“): {\displaystyle c=\{a,\b}} při přiřazení $a\rightarrow u,b\rightarrow v,c\rightarrow \{u,v,w\}$ splněna relativně v $\mathbb {M}$ , ovšem samozřejmě ne absolutně. Platí Nelze pochopit (syntaktická chyba): {\displaystyle \{u, v\}^M = \{u, v, w\} \not = {u, v\}} .

Tranzitivní model

Ani v teorii s absolutním náležením nemusí tedy být absolutní mnohé elementární pojmy; dokonce ani natolik zásadní, jako $c=\{a,b\}$ . To je však absolutní v tranzitivních modelech, tj. v modelech s absolutním náležením, v němž $M$ je tranzitivní množina (případně třída).

Tranzitivní modely jsou intenzívně studovány pro svoji přehlednost, protože v nich je mnoho pojmů absolutních. Příkladem takového modelu je třída všech Goedelových konstruovatelných množin, pomocí nichž se dokazuje, (relativní) bezespornost AC a GCH.

Skolemův paradox

Skolemův paradox je zdánlivý rozpor pramenící z následujících faktů:

Je-li ZFC bezesporná (jak všichni věří), dle Gödelovy věty o úplnosti má nějaký model.
Dle

Mostowského kolaps

Model $\mathbb {M} =(M,R)$ teorie ZF splňuje předpoklady Mostowského věty o kolapsu, právě když je na něm relace $R$ (realizující náležení) fundovaná. To je silnější předpoklad, než že model splňuje axiom fundovanosti, který je v podstatě relativizací formule „ $R$ je fundovaná“ do modelu $\mathbb {M}$ .

xx