====== AP3, IN3 Uspořádání ======
(relace uspořádání, uspořádané množiny a svazy, číselné obory)

===== Vypracovanie =====

==== Relace usporiadania ====

<box 95% round blue|Usporiadanie a predusporiadanie>Relace <math>R \subseteq M \times M</math> je **usporiadanie** práve vtedy, keď **//R//** je reflexívna, antisymetrická a tranzitívna.
Relace <math>R \subseteq M \times M</math> je **predusporiadanie** (kvaziusporiadanie, polousporiadanie) práve vtedy, keď **//R//** je reflexívna a tranzitívna (a neplatí antisymetrie).
</box>

==== Usporiadané množiny ====

<box 95% round blue|Usporiadaná množina>(Pred)usporiadaná množina je dvojica <math>(M,\sqsubseteq)</math> , kde **//M//** je množina a <math>\sqsubseteq</math> je (pred)usporiadanie na **//M//**.
Usporiadaná množina <math>(M,\sqsubseteq)</math> sa nazýva //lineárne usporiadaná (reťazec)//, ak <math>\forall a, b \in M:\ a \sqsubseteq b\  \vee \ b \sqsubseteq a</math> (každé dva prvky sú zrovnateľné).
</box>

Príkladom lineárne usporiadaných množín sú **//N//**, **//Z//**, **//Q//**, **//R//** vzhľadom k usporiadaniu podľa veľkosti. Príkladom predusporiadanej množiny, ktorá nie je usporiadaná je **//(Z*,|)//**, kde **//Z*//** je množina všetkých nenulových celých čísel a **//|//** je relace deliteľnosti (množina **//(N,|)//** usporiadaná je) ((Základy matematiky skriptá, str. 13)).

Na usporiadaných množinách môžeme definovať ďalšie relace usporiadania:
  * **usporiadanie po bodoch**
Nech **//M//** je množina a <math>(A,\leq)</math> usporiadaná množina. Nech <math>F = \{f|f:\ M \rightarrow A\}</math>. Definujeme binárnu relaci                             <math>\sqsubseteq</math> na **//F//** predpisom:
<math>f\ \sqsubseteq \ g \ \Leftrightarrow \ \forall x \in M:\ f(x) \leq g(x)</math>
Potom <math>(F,\sqsubseteq)</math> je usporiadaná množina a usporiadanie <math>\sqsubseteq</math> sa nazýva **"po bodoch"**.
  * **usporiadanie po zložkách**
Nech <math>(A,\leq)</math> a <math>(B,\preceq)</math> sú usporiadané množiny. Definujeme binárnu relaci                             <math>\sqsubseteq</math> na <math>A \times B</math> predpisom:
<math>(a,b)\ \sqsubseteq \ (a',b')\ \Leftrightarrow \ a \leq a'\ \wedge \ b \preceq b'</math>
Potom <math>(A \times B,\sqsubseteq)</math> je usporiadaná množina a usporiadanie <math>\sqsubseteq</math> sa nazýva **"po zložkách"**. 
  * **usporiadanie lexikografické**
Nech <math>(A,\leq)</math> a <math>(B,\preceq)</math> sú usporiadané množiny. Definujeme binárnu relaci                             <math>\sqsubseteq</math> na <math>A \times B</math> predpisom:
<math>(a,b)\ \sqsubseteq \ (a',b')\ \Leftrightarrow \ (a \leq a'\ \wedge\ a \neq a')\ \vee \ (a = a'\ \wedge \ b \preceq b')</math>
Potom <math>(A \times B,\sqsubseteq)</math> je usporiadaná množina a usporiadanie <math>\sqsubseteq</math> sa nazýva **"lexikografické"**. Ak sú usporiadania <math>\leq</math> a <math>\preceq</math> lineárne, je aj usporiadanie <math>\sqsubseteq</math> lineárne.

Nech <math>(A,\leq)</math> je usporiadaná množina.
<color blue>Najmenší prvok</color> je prvok <math>x \in A</math> taký, že <math>\forall y \in A:\ x \leq y</math>.
<color blue>Minimálny prvok</color> je prvok <math>x \in A</math> taký, že  <math>\forall y \in A:\ y \leq x \Rightarrow x \leq y</math> (**//x//** je minimálny práve vtedy, keď neexistuje žiadny prvok menší ako **//x//**).
<color blue>Najväčší prvok</color> je prvok <math>x \in A</math> taký, že <math>\forall y \in A:\ y \leq x</math>.
<color blue>Maximálny prvok</color> je prvok <math>x \in A</math> taký, že  <math>\forall y \in A:\ x \leq y \Rightarrow y \leq x</math> (**//x//** je maximálny práve vtedy, keď neexistuje žiadny prvok väčší ako **//x//**).


**Najmenší (najväčší)** prvok, ak existuje, je **jediný** a zároveň **minimálny (maximálny)**. Minimálnych (maximálnych) prvkov môže byť viac, potom ale neexistuje najmenší (najväčší) prvek.

Usporiadané množiny môžeme prehľadne zobraziť pomocou tzv. //Hasseovských diagramov//. Nech sú usporiadané množiny zadané nasledovne ((riešené príklady od Mgr. Jana Holečka, 6. sada)):
{{:home:inf:has1.png?170|Hasseovské diagramy}}
Prvok **//a<sub>1</sub>//** je minimálny a najmenší, prvky **//a<sub>3</sub>//**, **//a<sub>4</sub>//**  sú maximálne. Prvok **//b<sub>1</sub>//** je minimálny a najmenší, prvok **//b<sub>2</sub>//** maximálny a najväčší.
Pomocou Hasseovských diagramov môžeme znázorniť usporiadané množiny <math>(B \times A, \leq)</math>, kde <math>\leq</math> je usporiadanie po zložkách a <math>(B \times A, \preceq)</math>, kde <math>\preceq</math> je lexikografické usporiadanie:
{{:home:inf:has2-zlozky.png?270 |Usporiadanie po zložkách}}{{:home:inf:has2-lex.png?125|Lexikografické usporiadanie}}

==== Svazy ====
<box 95% round blue|Svaz>Svaz je uspořádaná množina <math>(X,\preceq)</math>, ve které existuje supremum i infimum pro libovolnou dvojici prvků. Ve svazu můžeme na supremum a infimum pohlížet jako na binární operace (protože je zaručeno, že jejich hodnoty jsou definovány pro každou dvojici). Supremum prvků x, y zde značíme <math>x \vee y</math>, infimum jako <math>x \wedge y</math>. 
Definice svazu ze skript:((www.cam.zcu.cz/~ryjacek/students/DMA/skripta/3.pdf)).
</box>


Nech <math>(M,\leq)</math> je usporiadaná množina.
Prvok <math>x \in M</math> je <color blue>horná závora</color> množiny <math>A \subseteq M \Leftrightarrow \forall y\in A:\ y \leq x</math>.
Prvok <math>x \in M</math> je <color blue>suprémum</color> množiny <math>A \subseteq M</math> (sup//A//) <math>\Leftrightarrow</math> **//x//** je najmenšia horná závora množiny **//A//** (t.j. pre ľubovoľnú hornú závoru **//y//** množiny **//A//** platí <math>x \leq y</math>).
Prvok <math>x \in M</math> je <color blue>dolná závora</color> množiny <math>A \subseteq M \Leftrightarrow \forall y\in A:\ x \leq y</math>.
Prvok <math>x \in M</math> je <color blue>infimum</color> množiny <math>A \subseteq M</math>(inf//A//) <math>\Leftrightarrow</math> **//x//** je najväčšia dolná závora množiny **//A//** (t.j. pre ľubovoľnú dolnú závoru **//y//** množiny **//A//** platí <math>y \leq x</math>).
Špeciálne prípady:((Základy matematiky skriptá, str. 14)).
Přehledné vysvětlení i s příklady:((http://user.mendelu.cz/marik/in-mat-web/in-mat-webse18.html)).
<math>sup\emptyset</math> je najmenší prvok usporiadanej množiny **//M//** a <math>inf\emptyset</math> je najväčší prvok **//M//** (ak existujú).
V usporiadanej množine <math>(P(M),\subseteq)</math>, kde **//P(M)//** je potenčná množina množiny **//M//** a **//X//** je neprázdna podmnožina  **//P(M)//** platí:
<math>supX = \bigcup X</math>
<math>infX = \bigcap X</math>

<box 95% round green|Veta 1 (Faktická správnost věty 1 je zpochybněna, viz diskusi)>Nech **//A//** je usporiadaná množina, potom nasledujúce výroky sú ekvivalentné.
  - ľuboboľná podmnožina množiny **//A//** má infimum
  - ľuboboľná podmnožina množiny **//A//** má suprémum
</box>
Dôkaz predchádzajúcej vety môžete nájsť v skriptách ((skriptá RNDr. Pavla Horáka)).
<box 95% round blue|Svaz a úplný svaz>
  - Usporiadaná množina **//A//** sa nazýva **svaz**, ak jej ľubovoľná dvojprvková podmnožina má suprémum a infimum.
  - Nechť (A,∧,∨) je svaz a B je neprázdná podmnožina A. Pak B se nazývá **podsvazem** svazu A, platí-li, že B je uzavřená vzhledem ke svazovým operacím „∧“ a „∨“, tedy pro všechny a,b z B: a ∧ b náleží B, a ∨ b náleží B.
  - Usporiadaná množina **//A//** sa nazýva **úplný svaz**, ak jej ľubovoľná podmnožina má suprémum a infimum.  
</box>
Z predchádzajúcich definícií vyplývajú nasledovné dôsledky:
  * Ak je <math>(A,\leq)</math> svaz, potom tiež každá neprázdna konečná podmnožina v **//A//** má suprémum a infimum. Ak **//A//** je konečná (a neprázdna), pojmy svaz a úplný svaz splývajú.
  * Každý úplný svaz je tiež svaz.
  * Každý úplný svaz <math>(A,\leq)</math> má najmenší a najväčší prvok, ktorým je <math>infA</math> a <math>supA</math>.
Príklady svazov a úplných svazov:
  * Každá lineárne usporiadaná množina je svaz, teda aj <math>(N,\leq)</math>, <math>(Z,\leq)</math>, <math>(Q,\leq)</math>, <math>(R,\leq)</math> sú svazy (žiaden z nich nie je úplný svaz (neexistuje sup//N//, sup//Z//), pokud se na uspořádání na daných množinách díváme tak, jak je obvyklé, ovšem tyto množiny lze přeuspořádat tak, aby již byly úplným svazem).
  * Usporiadaná množina <math>(N,|)</math> je svaz -- každá dvojprvková množina <math>\{a,b\}</math> má suprémum (najmenší spoločný násobok a,b) a infimum (najväčší spoločný deliteľ a,b). 

<note>
Uspořádaná množina <math>(N_{0},|)</math> je úplný svaz. (Záleží tedy i na tom, jak si zadefinujeme relaci |. Například nechť <math>a,b \in N_{0}</math>, <math>a | b \Leftrightarrow \exists x \in Z^{*}.\ a \cdot x = b\</math>.)
</note>

  * Usporiadaná množina <math>(P(A),\subseteq)</math> je úplný svaz, nájdenie supréma a infima ľubovoľnej podmnožiny je popísané vyššie.

**Krásně nakreslený příklad svazu + suprema a infima pro jeho podmnožiny**
{{:home:inf:svaz_hasseuv_diagram.jpg|}}  {{:home:inf:svaz_infsupminmax.jpg|}} zdroj((Algebra v obrázcích - http://algebra.matfyz.info/))

==== Číselné obory ====

== Prirodzené čísla ==
Medzi prirodzené čísla **//N//** patria čísla 1, 2, 3, 4, 5,..., do **//N//**<sub>0</sub> patrí aj 0. Prirodzené čísla konštruujeme pomocou množín:
<math>0 = \emptyset</math>
<math>1 = \{\emptyset\}</math>
<math>2 = \{\emptyset, \{\emptyset\} \}</math>
<math>3 = \{ \emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}</math>
...
Vždy platí, že číslo **//n//** vyjadríme ako  <math>n = \{0, 1,..., n-1\}</math>.

== Celé čísla ==
Celé čísla <math>Z = \{...,-3,-2,-1,0,1,2,3,...\}</math> konštruujeme nasledovným spôsobom:
Definujeme na množine <math>N_{\small 0}\ \times \ N_{\small 0}</math> relaci <math>\sim</math> vzťahom:
<math>(a,b)\ \sim \ (c,d) \Leftrightarrow a + d = c + b</math>
Jedná sa o relaci ekvivalence, ak položíme <math>Z = N_{\small 0}\ \times \ N_{\small 0} / \sim </math>, dostaneme rozklad množiny. Triedu ekvivalence <math>\sim</math> určenú prvkom <math>(a,b)</math> označíme  <math>\overline{(a,b)}</math> (reprezentuje rozdiel a-b). Definujeme operácie:

<math>\overline{(a,b)} + \overline{(c,d)} = \overline{(a+c,b+d)}</math>

<math>\overline{(a,b)} \cdot \overline{(c,d)} = \overline{(ac+bd,ad+bc)}</math>

<math>- \overline{(a,b)} = \overline{(b,a)}</math>

(tip: operácie sa ľahko pamätajú, ak si pod <math>\overline{(a,b)}</math> predstavíte <math>a-b</math>)
Uvedené definície nezávisia na voľbe reprezentantov ((Základy matematiky skriptá, str. 12)). Prirodzenému číslu **//n//** odpovedá celé číslo <math>\overline{(n,0)}</math>

== Racionálne čísla ==
Na množine <math>Z\ \times \ Z^{*}</math>(<math>Z^{*}</math> značí množinu nenulových celých čísel) definujeme relaci <math>\sim</math> vzťahom:
<math>(a,b)\ \sim \ (c,d) \Leftrightarrow ad = cb</math>
Jedná sa o relaci ekvivalence, ak položíme <math>Q = (Z\ \times \ Z^{*}) / \sim </math>, dostaneme rozklad množiny. Triedu ekvivalence <math>\sim</math> určenú prvkom <math>(a,b)</math> označíme  <math>\overline{(a,b)}</math> (reprezentuje zlomok <math>\frac{a}{b}</math>). Definujeme operácie:

<math>\overline{(a,b)} + \overline{(c,d)} = \overline{(ad+bc,bd)}</math>

<math>\overline{(a,b)} \cdot \overline{(c,d)} = \overline{(ac,bd)}</math>

(tip: operácie sa ľahko pamätajú, ak si pod <math> \overline{(a,b)} </math> predstavíte <math>\frac{a}{b}</math>) 
Pre <math>a,b \neq 0</math> platí <math>\overline{(a,b)}^{-1} = \overline{(b,a)}</math>. Celému číslu **//a//** odpovedá racionálne číslo <math>\overline{(a,1)}</math>.

== Reálne čísla ==
Konštrukcia reálnych čísiel je trochu zložitejšia, preto tu nebudem uvázdať celý postup. Je nutné definovať usporiadanie na množinách **//Z//** a **//Q//** a následne definovať operácie pomocou rezov množiny **//Q//**. **//R//** definujeme ako množinu všetkých rezov, ktoré sú buď mezery (iracionálne čísla) alebo dedekindovské rezy 1.druhu (racionálne čísla). Viac informácií nájdete v skriptách ((Základy matematiky skriptá, str.17)).

== Komplexné čísla ==
Množinu komplexných čísel //C// chápeme ako množinu všetkých dvojíc reálnych čísel, teda <math>C = R \times R</math>. Pre ľubovoľné <math>(a,b),\ (c,d)\in C</math> definujeme operácie sčítania a násobenia:

<math>(a,b)+(c,d) = (a+c,b+d)</math> 

<math>(a,b)\cdot (c,d) = (ac-bd,ad+bc)</math>

Ak komplexné číslo //(0,1)// označíme //i// a //(t,0)// //t//, môžeme každé komplexné číslo <math>z= (a,b)</math>  písať v tvare:
<math>z= a+bi</math> (algebraický tvar, //a// - reálna časť, //b// -imaginárna časť)
Pre imaginárnu jednotku platí <math>i^2 = -1</math>, to nám dovoľuje riešiť aj také rovnice (napr. <math>x^2 + 1= 0</math>), ktoré v obore reálnych čísel nemajú riešenie.  
Z algebraického tvaru a ze vztahu <math>i^2 = -1</math> pak můžeme zpětně rekonstruovat násobení komplexních čísel: <math>(a,b)\cdot(c,d) = (a+bi)\cdot(c+di) = ac-bd + adi+bci = (ac-bd, ad+bc)</math>

===== Co byste ještě měli znát? =====

  * Měli byste chápat a být schopni vysvětlit rozdíl mezi minimálním a nejmenším prvkem.
  * Měli byste být schopni sami uvést příklady svazu, úplného svazu nebo nelineárního uspořádání.
  * Ale také byste měli být schopni určovat supréma, infima pro množiny zadané komisí a měli byste umět určit, zda je daná množina svaz, úplný svaz apod.


===== Predmety =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3082;kod=MB005|FI:MB005]] Základy matematiky (podzim 2005), Mgr. Ondřej Klíma, Ph.D.
  * [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3082;kod=IB000|FI:IB000]] Úvod do informatiky (podzim 2005), prof. RNDr. Antonín Kučera, Ph.D.

===== Použitá literatúra =====
  * skriptá Úvod do informatiky, prof. RNDr. Antonín Kučera, Ph.D. (odkaz som nenašiel)
  * Mgr. Jan Holeček [[https://is.muni.cz/auth/el/1433/podzim2005/IB000/za/cviceni/reseni2005-6.pdf?fakulta=1433;obdobi=3082;kod=IB000|riešené príklady 6.sada]] (dostupné pouze z domény muni.cz)
  * [[http://www.math.muni.cz/~klima/ZakladyM/zakladym-fi-07.html|Učebné materiály k MB005]]
  * [[http://www.fi.muni.cz/~hlineny/Vyuka/UINF/UInf-lect--5.pdf| Uspořádání]], skripta pro ÚdoI, doc. RNDr. Petr Hliněný, Ph.D.

===== Vypracoval =====
Dušan Katona, ICQ: 426 081 873, snad do 27.5
hotovo: <99%>
môžete kluďne niečo doplniť alebo opraviť

Otázku si přečetl pan RNDr. Jan Bouda a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen **rámcová**, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

~~DISCUSSION~~