Teorie polomnožin

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Teorie polomnožin je matematická teorie zobecňující teorii množin, která byla vyvinuta v 70. a 80. letech 20. století Petrem Vopěnkou a Petrem Hájkem. Její axiomatizace je podobná Von Neumann-Gödel-Bernaysově teorie množin, ale liší se tím, že umožňuje existenci vlastních tříd, které jsou částí nějaké množiny. Tato vlastnost umožňuje polomnožinám sloužit jako základ Vopěnkovy alternativní teorie množin.

Axiomatizace teorie polomnožin[editovat | editovat zdroj]

Základní definice[editovat | editovat zdroj]

Některé definice v tomto odstavci využívají objekty, jejichž existenci a vlastnosti lze dokázat pouze použitím některých axiomů. Proto při výstavbě teorie polomnožin je nutné postupovat po krocích (zavést axiomy, jejich užitím definovat nějaké objekty, ty využít k formulaci dalších axiomů, pomocí nich definovat další objekty, atd …). Pro přehlednost jsou však uvedeny axiomy a definice zvlášť a v pořadí, které neodpovídá jejich postupnému zavádění, ale jejich významu.

  • Uspořádanou dvojici <x,y> definujeme jako \,\{x,\{x,y\}\} (existence takové množiny plyne z axiomu dvojice pro množiny - viz dále).
  • Řekneme, že třída R je relace, značíme Rel(R), jsou-li všechny prvky R tvaru <u,v> pro nějaké množiny u,v. Je-li <u,v>\in R, píšeme také někdy uRv. Definiční obor relace R, D(R), je množina všech v, pro které existuje u, že <u,v>\in R. Obor hodnot relace R, W(R), je množina všech u, pro které existuje v, že <u,v>\in R.
  • Extenze prvku x\in D(R) v relaci R, \, Ext_R(x), je \{y;<y,x>\in R\}.
  • Třída X je polomnožina, Pm(X), existuje-li množina y, že X\subseteq y.
  • Relace R je regulární, Reg(R), je-li \, Ext_R(x) polomnožinou pro všechna x\in D(R).
  • Relace R je prostá, Pr(R), je-li pro x\neq y z D(R) nutně Ext_R(x)\neq Ext_R(y).
  • Třída X je exaktní funktor, Exct(X), je-li Rel(X) \and Reg(X) \and Pr(X).

Axiomy[editovat | editovat zdroj]

Axiomatizace teorie polomnožin se obvykle vyslovuje v logice obsahující dva druhy proměnných - proměnné pro množiny a proměnné pro třídy. V následující axiomatizaci budeme označovat proměnné pro množiny malými písmeny x,y,z,… a proměnné pro třídy velkými písmeny X,Y,Z,…

Axiomy definující množinové proměnné[editovat | editovat zdroj]

  • (MP1) (\exists x)(x=X) \leftrightarrow (\exists Y)(X \in Y) (Axiom definice množinové proměnné) Třída X je množina, právě když je prvkem nějaké třídy.
  • (MP2) (\forall x)(\exists X)(x=X) (Axiom inkluze množinových a třídových proměnných) Každá množina je zároveň třída.

Axiomy o třídách a množinách[editovat | editovat zdroj]

  • (TM1) (\exist X)(\exists Y)(X\in Y) (Axiom existence množiny) Existuje nějaká množina.
  • (TM2) (\forall Z)(Z \in X \leftrightarrow Z \in Y)\leftrightarrow(X=Y) (Axiom extenzionality pro třídy) Třídy jsou si rovny právě když mají stejné prvky.
  • (TM3) (\forall x,y)(\exists z)(\forall u)(u \in z \leftrightarrow (u=x \vee u=y)) (Axiom dvojice pro množiny) Pro každé dvě množiny existuje množina, která je neuspořádanou dvojicí těchto množin.
  • (TM4) (\exists x)(\emptyset \in x \and (\forall y)(y\in x \rightarrow \{y\}\in x)) (Axiom nekonečna) Existuje nekonečná množina.

Gödelovské axiomy pro třídy[editovat | editovat zdroj]

  • (GT1) (\exists Y)(\forall x)(x \in Y) (Existence univerzální třídy) Existuje třída všech množin.
  • (GT2) (\forall X)(\exists Y)(\forall x)(x\in Y \leftrightarrow (\exists u,v)(x\in X \and x=<u,v> \and u\in v)) (Existence reprezentace \in) Na každé třídě existuje třídová reprezentace relace \in.
  • (GT3) (\forall X,Y)(\exists Z)(\forall x)(x \in Z \leftrightarrow (x\in X \and x \not \in Y)) (Axiom doplňku) Pro každé dvě třídy existuje doplněk jedné do druhé.
  • (GT4) (\forall X)(\exists Y)(\forall x)(x\in Y \leftrightarrow (\exists y)(<y,x>\in X)) (Axiom projekce) Pro každou třídu je její definiční obor rovněž třídou.
  • (GT5) (\forall X,Y)(\exists Z)(\forall x)(x\in Z \leftrightarrow (\exists u,v)(x\in X \and x=<u,v> \and v\in Y)) (Axiom zúžení) Pro každé dvě třídy existuje zúžení jedné na druhou.
  • (GT6) (\forall X)(\exists Y)(\forall x)(x\in Y \leftrightarrow (\exists u,v)(x=<u,v> \and <v,u>\in X)) (Axiom binární inverze) Pro každou třídu (binární relaci) existuje třída k ní inverzní.
  • (GT7) (\forall X)(\exists Y)(\forall x)(x\in Y \leftrightarrow (\exists u,v,w)(x=<u,v,w> \and <v,w,u>\in X)) (Axiom ternární inverze) Pro každou třídu (ternární relaci) existuje třída, jež je její „cyklickou záměnou“.

Gödelovské axiomy pro množiny[editovat | editovat zdroj]

  • (GM2) (\forall x)(\exists y)(\forall u)(u\in y \leftrightarrow (\exists v,w)(u\in x \and u=<v,w> \and v\in w)) (Existence reprezentace \in) Na každé množině existuje množinová reprezentace relace \in.
  • (GM3) (\forall x,y)(\exists z)(\forall u)(u \in z \leftrightarrow (u\in x \and u \not \in y)) (Axiom doplňku) Pro každé dvě množiny existuje doplněk jedné do druhé.
  • (GM4) (\forall x)(\exists y)(\forall u)(u\in y \leftrightarrow (\exists v)(<v,u>\in x)) (Axiom projekce) Pro každou množinu je její definiční obor rovněž množinou.
  • (GM5) (\forall x,y)(\exists z)(\forall u)(u\in z \leftrightarrow (\exists v,w)(u\in x \and u=<v,w> \and w\in y)) (Axiom zúžení) Pro každé dvě množiny existuje zúžení jedné na druhou.
  • (GM6) (\forall x)(\exists y)(\forall u)(u\in y \leftrightarrow (\exists v,w)(u=<v,w> \and <w,v>\in x)) (Axiom binární inverze) Pro každou množinu (binární relaci) existuje množina k ní inverzní.
  • (GM7) (\forall x)(\exists y)(\forall u)(u\in y \leftrightarrow (\exists v,w,r)(u=<v,w,r> \and <w,r,v>\in x)) (Axiom ternární inverze) Pro každou třídu (ternární relaci) existuje třída, jež je její „cyklickou záměnou“.

Axiom exaktního funktoru[editovat | editovat zdroj]

  • (EF) Extc(X)\rightarrow (Pm(D(X))\leftrightarrow Pm(W(X))) (Axiom exaktního funktoru) Exaktní funktor má polomnožinový definiční obor, právě když má polomnožinový obraz.

Polomnožina[editovat | editovat zdroj]

Polomnožinou nazýváme takovou vlastní třídu X, pro kterou existuje množina y, že X\subseteq y.

Související články[editovat | editovat zdroj]