Uspořádané množiny
• (A, <) je uspořádaná množina, jestliže < je relace uspořádání na množině A.
• Uspořádaná množina (A, <) se nažývá lineárně uspořádaná (nebo řetězec), jestliže pro libovolná a, b G A platí bud' a < b nebo b < a.
• V uspořádane množine (A, <) symbolem a < b rožumíme a < b, a = b. Příklady:
1. N, Z, Q, R jsou lineárne uspořádane množiny (vhledem k uspořadaní dle velikosti).
2. Pro libovolnou množinu A je = uspořadaní na A. Vžnikla uspořadana množina se nažáva přotiřetěžec.
3. Uspořádanou množinu (A, <) žnažorníme graficky - prvky jsou body a áseCkou se spojí sousední prvky: a, b G A tak, že a < b kdy neexistuje c G A tak, že a < c < b, píseme a -< b. Body a, b G A takove, že a -< b kreslíme tak, že a je níže než b. Tyto obražky se nažávají Hásseovy diágřámy.
1. Rožhodnete, žda jsou následující relace uspořádání, resp. lineární uspořádání na N. V případe kladne odpovedi nažnacte Hasseuv diagram uspořádane množiny (N, ^).
(a) x r< y ^ x = y;
(b) x ^ y ^ x < y;
(c) x r< y ^ x < y;
(d) x ^ y ^ y = 4 V y = x;
(e) x r< y ^ pocet cifer císla x je mensí nebo roven poctu cifer císla y;
(f) x r< y ^ x ^ y (mod 5);
(g) x ^ y ^ (x = y) V (2 \ x A 2|y) V (2|x + y A x < y).
2. Necht A je libovolna množina. Dokažte, že (P(A), C) je uspořadana množina. Sestrojte Hasseovy diagramy v případe:
(a) A = 0;
(b) A = {a};
(c) A = {a, b};
(d) A = {a, b, c}.
• nejmensí prvek usporadane množiny A je prvek a takovy, že pro libovolne x G A platí
a < x;
• minimálni prvek uspořádane množiny A je taková prvek a, že neexistuje prvek x G A tak, že x < a.
• nejmensí prvek, pokud existuje, je jediny a je žaroveň minimalní. Minimalních prvku muže byt více.
• analogicky definujeme nejvetsí a máximální prvek.
• A je uspořádaná množina a X C A; prvek a G A je horní žávorá podmnožiny X, jestliže x < a pro libovolne x G X;
• prvek a je supremum podmnožiny X, jestliže je horní žávorou X a pro libovolnou horní žíavoru b mn. X platí a < b;
• analogicky - infimum podmnožiny X je nejvetsí dolní žavora.
1
3. Popište maximální a minimální prvky, resp. největší a nejmenší prvek množiny M s uspořádáním p:
(a) M = (a, b, c}, p = {(a, a), (6,6), (c, c)}
(b) M = (a, 6, c}, p = {(a, a), (6,6), (c, c), (a, 6), (6, c), (a, c)}
(c) M = (a, 6, c, d}, p = {(a, a), (6,6), (c, c), (d, d), (a, 6), (a, c)}
(d) M = P ({a, 6}), p = C
4. Popište maximální a minimální prvky, resp. nejvetší a nejmenší prvek, který mají tyto hasse-ovske diagramy:
5. Na množine M = {1, 2, 3,4, 5,6, 7} definujeme relaci R tak, že
(x, y) G R ^ (3 n G N)(y = n • x).
Dokažte, že R je usporádání a sestrojte hasseovský diagram množiny (M, R). Uvažujte relaci R definovanou tímto vžtahem na množine N a schematicky nažnaCte hasseovský diagram (N, R). Popište maximální, minimální, nejvetší a nejmenší prvky techto množin.
6. V predchožích príkladech diskutujte existenci superem a infim.
2