18 PL druheho radu

• predikátové (např. znaky M, N, O, R, S)
• - jejich hodnotami jsou nějaké množiny, jmenovitě podmnožiny univerza nebo podmnožiny kartézského součinu univerza (tj. relace).
• - Navíc tyto predikátové proměnné mohou být kvantifikovány

- kvantifikace predikátové proměnné v PL2

• ∀x∀y (x=y) ↔ ∀P (P(x)↔P(y)),
• = pro všechna individua x a y platí, že x a y jsou identická právě tehdy, když mají všechny vlastnosti stejné (P je zde proměnná pro vlastnosti).

binárních relací (tj. množiny prvků)

• Jak už bylo naznačeno, v našich zápisech jsou znaky M, N, O, R, S proměnné pro množiny/třídy či relace. (Jsou to objektové proměnné, nikoli metajazykové proměnné zastupující predikátové symboly.)
• V našich definicích se proměnné jako např. M (či R) vyskytují ve formulích po obou stranách definičního znaku „=_df“ volně; předpokládá se přitom, že celá definice je z objektového hlediska formulí tvaru ekvivalence (kdy „=_df“ zastupuje „↔“), jež je uzavřena příslušným obecným kvantifikátorem  ∀M (či ∀R).

• ^{Kromě logiky druhého řádu se někdy hovoří o logice vyšších řádů (než 2), někdy se tím míní všech řádů včetně řádu 2.}
• Pod logikou vyššího řádů je tedy myšlena logika umožňující kvantifikaci přes třídy tříd (množiny množin), resp. logika umožňující kvantifikovat přes entity jakéhokoli řádu.
• Obory proměnných jsou přitom omezovány na entity určitého druhu, na tzv. sorty (sorta individuí, sorta tříd individuí, sorta tříd tříd individuí, atd.)

Vzhledová podobnost operátorů daných dvou jazyků bude vyšší, když si připomeneme, že „M^C“ bývá mnohdy značeno např. „–M“, a dále že „→“ a „↔“ bývají značeny i „⊃“ a „☰“.

• V logice se, zčásti z historických důvodů, množinám říká třídy (angl. „classes“).
• Problematika ukazovaná v této sekci pak bývá někdy nazývána logika tříd. V jistém smyslu se nejedná o nic jiného než o překlad jazyka teorie množin, a v ní uváděných poznatků, do jazyka PL.
• Například si ukážeme, že „M∩N“ lze prostředky PL vyjádřit s pomocí „(M(x)∧N(x))“. Z jiného úhlu pohledu, operátor ∩ se dá definovat (proto níže „=_df“) s  pomocí „(M(x)∧N(x))“.
• Všimněme si, že „M∩N“ je infixním zápisem, prefi xní „∩(M,N)“ se neužívá. Připomeňme si ještě, že M, N, O jsou libovolné podmnožiny U.

• (M∩N)je nějaká množina O a my proto vlastně zapisujeme, že x patří do O.
• (Při užití lambda-notace se těmto komplikacím můžeme vyhnout díky λ-operátoru, protože můžeme psát jednoduše např. ∅ =_df λx (M(x)∧¬M(x)); v  PL se naproti tomu vždy musí po  stranách „=_df“ vyskytovat formule, např. „∅(x) =_df
• (M(x)∧¬M(x))“.)

• ^{operace se třídami (= je proto rovnost mezi třídami), čemuž se někdy říká algebra tříd, v logice pak obvykle kalkul tříd.}
• 

• zákon reflexivity
• zákon (slabé) antisymetrie
• zákon tranzitivity

(M^C)^C = M

• M ∩ N = N ∩ M
• M ∪ N = N ∪ M

• (M ∩ N) ∩ O = M ∩ (N ∩ O)
• (M ∪ N) ∪ O = M ∪ (N ∪ O)

• M ∩ (N ∪ O) = (M ∩ N) ∪ (M ∩ O)
• M ∪ (N ∩ O) = (M ∪ N) ∩ (M ∪ O)

• M ∩ M = M
• M ∪ M = M

• M ∩ N = (M^C ∪ N^C)^C
• M ∪ N = (M^C ∩ N^C)^C

• M ∩ ∅ = ∅
• M ∪ ∅ = M
• M ∩ U = M
• M ∪ U = U

∀M(M ⊆ M)

∀M∀N((M ⊂ N) ∧ (N ⊂ M) → (M = N))

∀M∀N∀O((M ⊂ N) ∧ (N ⊂ O)) → (M ⊂ O)

tranzitivity S ⊆ M ⊆ P

n-ární relace nad univerzem U jsou podmnožinami kartézského součinu Uⁿ. Protože jsou relace množiny, většina principů jejich stavby je shodná s principy stavby obyčejných množin.

• V  našem zápisu relací neužíváme mnohdy používanou infixní notaci (např. „xRy“), používáme notaci výše zavedenou v gramatice PL1 pro binární predikátové symboly. Přidáváme druhořádové proměnné pro binární relace, „R“ a  „S“. Z  daných kontextů jako např. „∅(x,y)“, je zřejmé, že „∅“ označuje prázdnou množinou dvojic.
• V principech stavby se relace liší od obyčejných množin jen tím, že navíc existují inverzní relace a dále kompozice (skládání) relací.

R^C2(x, y) =df ¬R(x, y)

R⁻¹(x, y) =df R(y, x)

• Inverzní relace je někdy zvána konverzní relace.
• Příkladem k sobě inverzních relací je ‚být potomkem (někoho)‘ –‚být předkem (někoho)‘ nebo ‚být rodič (někoho)‘–‚být dítě (někoho)‘.

∅(x, y) =df R(x, y) ∧ ¬R(x, y)

Příkladem prázdné relace je ‚nebýt identický se sebou‘ (pro žádné x totiž neplatí x≠x).

U²(x, y) =df R(x, y) ∨ ¬R(x, y)

Příkladem univerzální relace je ‚být v nějakém vztahu k (něčemu)‘ (každá entita je alespoň v nějakém vztahu k něčemu).

R⊆S(x, y) =df R(x, y) → S(x, y)

Příkladem relace v inkluzi je ‚být bratr (někoho)‘ vzhledem k ‚být příbuzný (někoho)‘.

R=S(x, y) =df R(x, y) ↔ S(x, y)

R∩S(x, y) =df R(x, y) ∧ S(x, y)

R∪S(x, y) =df R(x, y) ∨ S(x, y)

R◦S(x, y) =df ∃z(R(x, z) ∧ S(z, y))

Kompozici relací si nepleťme s relačním součinem a relačním součtem, což jsou starší názvy pro průnik a sjednocení relací (když ale někteří autoři hovoří jen o součinu relací, mohou uvažovat kompozici relací

Relace ‚být strýc‘ je definovatelná jako kompozice relací ‚být rodič‘ a ‚být bratr‘; relace ‚být prarodič‘ je definovatelná jako kompozice relací ‚být rodič‘ a ‚být rodič‘.

• Dané vlastnosti vymezují druhy relací, například vlastnost reflexivity vymezuje druh reflexivních relací.
• Tranzitivitu lze alternativně definovat např. pomocí ∀x∀y∀z ((R(x,y)→(R(y,z)→R(x,z))) kvůli zákonu exportace (VL).
• Konexnost lze alternativně definovat např. pomocí ∀x∀y ((x=y)∨R(x,y)∨R(y,x)) (na základě tautologie VL).
• ^{Některé relace autoři nazývají jinak. Například totální relace bývá zvána lineární relace. Ba co víc, například ∀x R(x,x) je někdy považována za definici úplné reflexivity, přičemž za vlastní definici reflexivity je považována až ∀x∀y (R(x,y)→R(x,x)).}
• Všimněme si, že dané druhy relací nejsou navzájem disjunktní. Například každá asymetrická relace je též antisymetrická (asymetrie navíc zahrnuje ireflexitivitu). Polosymetrie je konjunkcí negace symetrie a negace asymetrie. Pod sériové relace zas spadají reflexivní relace. Atd.

• příklady relací:
• - reflexivní: ‚být identický (se sebou)‘, ‚narcistně se obdivovat‘
• – poloreflexivní: ‚milovat (někoho)‘ (někdo nemiluje sám sebe, někdo ano)
• – ireflexivní: ‚být ženatý (s někým)‘, ‚být potomkem (někoho)‘
• – symetrický: ‚mít se rád navzájem s (někým)‘, ‚být sourozenec (někoho)‘
• – polosymetrický: ‚znát (někoho)‘, ‚mít rád (někoho)‘
• – antisymetrický: ‚být dělitelný‘ (v oboru přirozených čísel)
• – asymetrický: ‚platonicky milovat (někoho)‘, ‚být otcem (někoho)‘
• – tranzitivní: ‚být potomkem (někoho)‘, ‚být vyšší než (něco)‘, ‚být podmnožinou‘, ≤
• – polotranzitivní: ‚být kořist‘ (v  potravním řetězci někteří predátoři nejsou kořist)
• – antitranzitivní: ‚porazit (někoho) v turnaji‘ (když x porazil y a y porazil z, x neporazil z)
• – intranzitivní: ‚být otcem (někoho)‘
• – euklidovská: ‚věci y a z, které se rovnají stejnému x, jsou si rovny‘
• – sériová: ‚mít předka

• Reflexivita Refl (R) =df ∀x R(x,x)
• Symetrie Sym(R) =df ∀x∀y (R(x,y)→R(y,x))
• Tranzitivita Trans(R) =df ∀x∀y∀z ((R(x,y)∧R(y,z))→R(x,z))

• Relace typu ekvivalence (R) =df Refl (R) ∧ Sym(R) ∧ Trans(R)
• Částečné parciální uspořádání (R) =df Refl (R) ∧ Antisym(R) ∧ Trans(R)
• Ostré uspořádání (R) =df Total(R) ∧ Antisym (R) ∧ Trans(R)

• Částečné parciální uspořádání (angl. „weak partial order“) je někdy nazýváno kvazi uspořádání. Příkladem takové relace je relace ≤ na množině přirozených čísel, anebo relace dělení přirozených čísel m a n beze zbytku. (Relace < se od ≤ liší tím, že < je ireflexivní, v důsledku čehož je < ostrým uspořádáním.)
• ^{Druhů uspořádání je v literatuře definováno více, zde jsme se dále omezili už jen na jednu definici ostrého uspořádání.}

• Relace R je zobrazena množinou šipek, z nichž každá šipka ukazuje první a druhý člen nějaké dvojice obsažené v R.
• Pokud nějaká šipka propojuje nějakou dvojici individuí, ale je přeškrtnuta, daná dvojice nepatří do dané relace.
• Pokud nějaká šipka nějakou dvojici individuí nepropojuje, daná dvojice v relaci může být, ale nemusí.
• Šipka propojující tři individua jako např. α, β, γ reprezentuje dvě dvojice 〈α,β〉, 〈β,γ〉. ^{Někdy se používá obousměrná šipka, jež nahrazuje dvě jednosměrné šipky vedoucí opačnými směry.}