{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Cvičení 5 (23. 10. 2023)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 1\n", "\n", "Nechť $A=\\lbrace 1, 2\\rbrace$. Napište operační tabulku (Cayleyho tabulku) grupoidu $(A^A,\\circ)$ a určete jeho vlastnosti.\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "\n", "Nejprve je třeba si všimnout, že operace $\\circ$ je definovaná na $A^A$, což je systém všech zobrazení $A \\to A$. Prvky grupoidu tedy budou tvořit funkce, ne čísla $1$ a $2$, která leží v množině $A$. Operace $\\circ$ pak značí skládání funkcí.\n", "\n", "Musíme tedy najít všechny funkce $f$ pro které platí $f: A \\to A$. Hledáme tedy takové funkce $f(x)$, které jsou definované pro $x=1$ a $x=2$ a pro které platí, že $f(x)=1$ nebo $f(x)=2$.\n", "\n", "Jednotlivé funkce si vypíšeme\n", "- $f_1(x)=x$, tj. $f_1(1)=1$ a $f_1(2) = 2$ - tato funkce zachovává původní vstup (identita),\n", "\n", "- $f_2(x)=3-x$, tj. $f_2(1)=2$ a $f_2(2)=1$ - tato funkce vrací vždy druhý prvek z množiny $A$,\n", "\n", "- $f_3(x)=1$, tj. $f_3(1)=1$ a $f_3(2)=1$ - tato funkce vrácí vždy prvek $1$,\n", "\n", "- $f_4(x)=2$, tj. $f_4(1)=2$ a $f_4(2)=2$ - tato funkce vrácí vždy prvek $2$.\n", "\n", "Vypsali jsme všechny možné funkce z $A$ do $A$ a můžeme tedy sestrojit Cayleyho tabulku. Prvky tabulky budeme zjišťovat postupně pomocí operace $\\circ$. Uvedeme si několik příkladů:\n", "\n", "- $(f_1 \\circ f_1) (x) = $ $f_1 (f_1 (x)) = $ $f_1 (x)$,\n", "\n", "- $(f_1 \\circ f_2) (x) = $ $f_1 (f_2 (x)) = $ $f_1 (3-x)=$ $3-x=$ $f_2 (x)$,\n", "\n", "- $(f_2 \\circ f_2) (x) = $ $f_2 (f_2 (x)) = $ $f_2 (3-x)=$ $3-(3-x)=$ $3-3+x=$ $x=$ $f_1 (x)$,\n", "\n", "- $(f_1 \\circ f_3) (x) = $ $f_1 (f_3(x)) = $ $f_1 (1)=$ $1 =$ $f_3(x)$,\n", "\n", "- $(f_3 \\circ f_4) (x) = $ $f_3 (f_4(x)) = $ $f_3 (2)=$ $1 =$ $f_3(x)$,\n", "\n", "- $(f_4 \\circ f_3) (x) = $ $f_4 (f_3(x)) = $ $f_4 (1)=$ $2 =$ $f_4(x)$.\n", "\n", "Výsledná Cayleyho tabulka prvků:\n", "\n", "| $\\circ$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ |\n", "|:-------:|:-------:|:-------:|:-------:|:-------:|\n", "| $f_1$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ |\n", "| $f_2$ | $f_2$ | $f_1$ | $f_4$ | $f_3$ |\n", "| $f_3$ | $f_3$ | $f_3$ | $f_3$ | $f_3$ |\n", "| $f_4$ | $f_4$ | $f_4$ | $f_4$ | $f_4$ |\n", "\n", "\n", "Nyní je třeba vyšetřit jednotlivé vlastnosti grupoidu:\n", "\n", "* **Komutativita** \n", "\n", "Grupoid je komutativní, pokud je Cayleyho tabulka symetrická podle hlavní diagonály. Naše tabulka symetrická není (např. $f_3 \\circ f_2 \\neq f_2 \\circ f_3$) a tedy grupoid není *komutativní*.\n", "\n", "\n", "* **Asociativita**\n", "\n", "Asociativitu nelze přímo ověřit z Cayleyho tabulky. Obecně ale víme, že skládání funkcí je asociativní a tedy náš grupoid je *asociativní*.\n", "\n", "Důkaz:\n", "$\\forall f, g, h\\in A^A, \\forall x\\in A:$\n", "\n", "$((f\\circ g)\\circ h)(x)=$ $(f\\circ g)(h(x))=f(g(h(x)))$,\n", "\n", "a\n", "\n", "$(f\\circ (g\\circ h))(x)=$ $f ((g\\circ h)(x))=f(g(h(x)))$,\n", "\n", "a tedy\n", "\n", "$((f\\circ g)\\circ h)(x)=(f\\circ (g\\circ h))(x)$.\n", "\n", "\n", "* **Neutrální prvek**\n", "\n", "Hledáme takový prvek, jehož řádek je shodný s prvním řádkem tabulky a zároveň jehož sloupec je shodný s prvním sloupcem tabulky. Toto splňuje prvek $f_1$ a je tedy prvkem neutrálním.\n", "\n", "\n", "* **Symetrický prvek**\n", "\n", "Vzájemně symetrické prvky mají v místě průsečíku neutrální prvek. Protože se neutrální prvek nenachází v každém řádku i sloupci, je zřejmé že k některým prvkům neexistují neutrální prvky (konkrétně k prvkům $f_3$ a $f_4$).\n", "\n", "\n", "* Prověřili jsme všechny vlastnosti a můžeme říct, že $(A^A , \\circ)$ je *monoid*.\n", "\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 2\n", "\n", "Napište operační tabulku (Cayleyho tabulku) grupoidu $(\\overline{\\mathbb{Z}}_{5},\\oplus)$ a určete jeho vlastnosti. \n", "\n", " \n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "\n", "Nejprve si rozebereme náš grupoid. Množina $\\overline{\\mathbb{Z}}_{5}$ je množina zbytkových tříd modulo $5$, tj. $\\overline{\\mathbb{Z}}_{5}=\\lbrace \\overline 0, \\overline 1, \\overline 2, \\overline 3 , \\overline 4\\rbrace$, kde \n", "- $\\lbrace \\overline 0\\rbrace = \\lbrace \\ldots -15, -10, -5, 0, 5, 10, 15, \\ldots\\rbrace$,\n", "\n", "- $\\lbrace \\overline 1\\rbrace = \\lbrace \\ldots -14, -9, -4, 1, 6, 11, 16, \\ldots\\rbrace$,\n", "\n", "- $\\lbrace \\overline 2\\rbrace = \\lbrace \\ldots -13, -8, -3, 2, 7, 12, 17, \\ldots\\rbrace$,\n", "\n", "- $\\lbrace \\overline 3\\rbrace = \\lbrace \\ldots -12, -7, -2, 3, 8, 13, 18, \\ldots\\rbrace$,\n", "\n", "- $\\lbrace \\overline 4\\rbrace = \\lbrace \\ldots -11, -6, -1, 4, 9, 14, 19, \\ldots\\rbrace$.\n", "\n", "Tj. množina $\\overline{\\mathbb{Z}}_{5}$ obsahuje celkem $5$ množin, kde každá z těchto množin představuje množinu celých čísel, které jsou spolu kongruentní modulo $5$ (mají stejný zbytek po dělení $5$). Například množina $\\lbrace \\overline 2 \\rbrace$ je množinou celých čísel, které mají po dělení $5$ zbytek $2$. \n", "\n", "Neměli bychom ani zapomínat, že vzhledem ke konkruenci můžeme množinu $\\overline 0$ stejně tak označit pomocí $\\overline {5}$, $\\overline {-5}$, $\\overline {10},\\cdots$\n", "\n", "Operace $\\oplus$ je na $\\overline{\\mathbb{Z}}_{5}$ definovaná následovně: $\\overline a \\oplus \\overline b = \\overline {a+b}$.\n", "\n", "Nyní můžeme sestrojit Cayleyho tabulku:\n", "\n", "| $\\oplus$ | $\\overline 0$ | $\\overline 1$ | $\\overline 2$ | $\\overline 3$ | $\\overline 4$ |\n", "|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|\n", "| $\\overline 0$ | $\\overline 0$ | $\\overline 1$ | $\\overline 2$ | $\\overline 3$ | $\\overline 4$ |\n", "| $\\overline 1$ | $\\overline 1$ | $\\overline 2$ | $\\overline 3$ | $\\overline 4$ | $\\overline 0$ |\n", "| $\\overline 2$ | $\\overline 2$ | $\\overline 3$ | $\\overline 4$ | $\\overline 0$ | $\\overline 1$ |\n", "| $\\overline 3$ | $\\overline 3$ | $\\overline 4$ | $\\overline 0$ | $\\overline 1$ | $\\overline 2$ |\n", "| $\\overline 4$ | $\\overline 4$ | $\\overline 0$ | $\\overline 1$ | $\\overline 2$ | $\\overline 3$ |\n", "\n", "Nyní je třeba vyšetřit jednotlivé vlastnosti grupoidu:\n", "\n", "* **Komutativita** \n", "\n", "Grupoid je komutativní, pokud je Cayleyho tabulka symetrická podle hlavní diagonály. Naše tabulka symetrická je a tedy grupoid je *komutativní*.\n", "\n", "\n", "* **Asociativita**\n", "\n", "Asociativitu nelze přímo ověřit z Cayleyho tabulky. Je tedy třeba dokázat, že operace $\\oplus$ je asociativní.\n", "\n", "Důkaz:\n", "$\\forall a, b, c\\in \\overline{\\mathbb{Z}}_{5}:$\n", "\n", "$(\\overline a \\oplus \\overline b)\\oplus \\overline c =$ $\\overline {a+b}\\oplus \\overline c =$ $\\overline {(a+b)+c}=$ $\\overline {a+(b+c)}=$ $\\overline a \\oplus \\overline {b+c}=$ $\\overline a \\oplus (\\overline b \\oplus \\overline c)$.\n", "\n", "Grupoid tedy je asociativní.\n", "\n", "\n", "* **Neutrální prvek**\n", "\n", "Hledáme takový prvek, jehož řádek je shodný s prvním řádkem tabulky a zároveň jehož sloupec je shodný s prvním sloupcem tabulky. Toto splňuje prvek $\\overline 0$ a je tedy prvkem neutrálním.\n", "\n", "\n", "* **Symetrický prvek**\n", "\n", "Vzájemně symetrické prvky mají v místě průsečíku neutrální prvek. Protože se neutrální prvek nachází v každém řádku i sloupci, je zřejmé že ke každému prvku existuje symetrický prvek (např. k prvku $\\overline 2$ je symetrický prvek $\\overline 3$).\n", "\n", "\n", "* Prověřili jsme všechny vlastnosti a můžeme říct, že $(\\overline{\\mathbb{Z}}_{5},\\oplus)$ je *Abelovská grupa*.\n", "\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Příklad 3\n", "\n", "Na množině $\\mathbb{R}\\setminus \\lbrace 0,1\\rbrace$ definujeme následující funkce:\n", "\n", "- $f_1(x) = x$,\n", "\n", "- $f_2(x) = \\frac{1}{x}$,\n", "\n", "- $f_3(x) = 1-x$,\n", "\n", "- $f_4(x) = \\frac{x}{x-1}$,\n", "\n", "- $f_5(x) = \\frac{x-1}{x}$,\n", "\n", "- $f_6(x) = \\frac{1}{1-x}$.\n", "\n", "Ukažte, že $(G, \\circ)$ je grupa, pokud $G=\\lbrace f_1, f_2, f_3, f_4, f_5, f_6 \\rbrace$.\n", "\n", "\n", "```{admonition} Zobrazit řešení\n", ":class: dropdown warning\n", "\n", "Nejprve si sestrojíme Cayleyho tabulku:\n", "\n", "| $\\circ$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | \n", "|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|\n", "| $f_1$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | \n", "| $f_2$ | $f_2$ | $f_1$ | $f_6$ | $f_5$ | $f_4$ | $f_3$ | \n", "| $f_3$ | $f_3$ | $f_5$ | $f_1$ | $f_6$ | $f_2$ | $f_4$ | \n", "| $f_4$ | $f_4$ | $f_6$ | $f_5$ | $f_1$ | $f_3$ | $f_2$ | \n", "| $f_5$ | $f_5$ | $f_3$ | $f_4$ | $f_2$ | $f_6$ | $f_1$ | \n", "| $f_6$ | $f_6$ | $f_4$ | $f_2$ | $f_3$ | $f_1$ | $f_5$ | \n", "\n", "\n", "* **Komutativita** \n", "\n", "Grupoid je komutativní, pokud je Cayleyho tabulka symetrická podle hlavní diagonály. Naše tabulka symetrická není (např. $f_4 \\circ f_6 \\neq f_6 \\circ f_4$) a tedy grupoid *není komutativní*.\n", "\n", "\n", "* **Asociativita**\n", "\n", "Z Cayleyho tabulky nelze asociativita přímo potvrdit. V prvním přkladu tohoto cvičení jsme ale dokázali, že skládání funkcí je vždy asociativní, takže náš grupoid je *asociativní*.\n", "\n", "\n", "* **Neutrální prvek**\n", "\n", "Hledáme takový prvek, jehož řádek je shodný s prvním řádkem tabulky a zároveň jehož sloupec je shodný s prvním řádkem tabulky. Toto splňuje prvek $f_1$ a je tedy prvkem neutrálním.\n", "\n", "* **Symetrický prvek**\n", "\n", "Vzájemně symetrické prvky mají v místě průsečíku neutrální prvek. Neutrální prvek se nachází v každém řádku i sloupci, takže by ke každému prvku měl existovat symetrický prvek. \n", "\n", "Protože náš grupoid ale není komutativní, musíme ověřit, že je-li $f_j$ symetrickým prvkem k $f_i$, tj. $f_i \\circ f_j = f_1$, pak musí být zároveň $f_i$ symetrickým prvkem k $f_j$, tj. $f_j \\circ f_i = f_1$. Toto je v našem případě snadno ověřitelné, protože $f_1, f_2, f_3$ a $f_4$ jsou sami sobě symetrickými prvky, takže výše ověřené musí automaticky platit. Zbývají nám funkce $f_5$ a $f_6$, pro které je z Cayleyho tabulky snadno vidět, že jsou vzájemně k sobě inverzní.\n", "\n", "Ukázali jsme tedy, že ke každému prvku z $G$ najdeme v $G$ symetrický prvek.\n", "\n", "* Prověřili jsme všechny vlastnosti a můžeme říct, že $(G,\\circ)$ je *grupa*.\n", "```" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.6" } }, "nbformat": 4, "nbformat_minor": 4 }