Mathématiques discrètes - Théorie des groupes

Semi-groupe

Un ensemble fini ou infini $ 'S' $ avec une opération binaire $ '\ omicron' $ (Composition) est appelé semigroupe s'il remplit deux conditions simultanément -

  • Closure - Pour chaque paire $ (a, b) \ dans S, \ :( a \ omicron b) $ doit être présent dans l'ensemble $ S $.

  • Associative - Pour chaque élément $ a, b, c \ dans S, (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c) $ doit tenir.

Exemple

L'ensemble des entiers positifs (à l'exclusion de zéro) avec opération d'addition est un semi-groupe. Par exemple, $ S = \ lbrace 1, 2, 3, \ dots \ rbrace $

Ici, la propriété de fermeture est valable comme pour chaque paire $ (a, b) \ dans S, (a + b) $ est présente dans l'ensemble S. Par exemple, $ 1 + 2 = 3 \ in S] $

La propriété associative est également valable pour chaque élément $ a, b, c \ dans S, (a + b) + c = a + (b + c) $. Par exemple, $ (1 + 2) + 3 = 1 + (2 + 3) = 5 $

Monoïde

Un monoïde est un semi-groupe avec un élément d'identité. L'élément d'identité (noté $ e $ ou E) d'un ensemble S est un élément tel que $ (a \ omicron e) = a $, pour tout élément $ a \ dans S $. Un élément d'identité est également appeléunit element. Ainsi, un monoïde détient trois propriétés simultanément -Closure, Associative, Identity element.

Exemple

L'ensemble des entiers positifs (à l'exclusion de zéro) avec opération de multiplication est un monoïde. $ S = \ lbrace 1, 2, 3, \ points \ rbrace $

Ici, la propriété de fermeture est valable comme pour chaque paire $ (a, b) \ dans S, (a \ times b) $ est présente dans l'ensemble S. [Par exemple, $ 1 \ times 2 = 2 \ in S $ et ainsi de suite]

La propriété associative est également valable pour chaque élément $ a, b, c \ dans S, (a \ times b) \ times c = a \ times (b \ times c) $ [Par exemple, $ (1 \ times 2) \ times 3 = 1 \ fois (2 \ fois 3) = 6 $ et ainsi de suite]

La propriété d'identité est également valable pour chaque élément $ a \ dans S, (a \ times e) = a $ [Par exemple, $ (2 \ times 1) = 2, (3 \ times 1) = 3 $ et ainsi de suite]. Ici, l'élément d'identité est 1.

Groupe

Un groupe est un monoïde avec un élément inverse. L'élément inverse (noté I) d'un ensemble S est un élément tel que $ (a \ omicron I) = (I \ omicron a) = a $, pour chaque élément $ a \ dans S $. Ainsi, un groupe détient quatre propriétés simultanément - i) Clôture, ii) Associatif, iii) Élément d'identité, iv) Élément inverse. L'ordre d'un groupe G est le nombre d'éléments dans G et l'ordre d'un élément dans un groupe est l'entier le moins positif n tel que an est l'élément d'identité de ce groupe G.

Exemples

L'ensemble des matrices non singulières $ N \ fois N $ forme un groupe sous l'opération de multiplication matricielle.

Le produit de deux matrices non singulières $ N \ fois N $ est également une matrice non singulière $ N \ fois N $ qui détient la propriété de fermeture.

La multiplication matricielle elle-même est associative. Par conséquent, la propriété associative tient.

L'ensemble des matrices non singulières $ N \ fois N $ contient la matrice d'identité contenant la propriété d'élément d'identité.

Comme toutes les matrices ne sont pas singulières, elles ont toutes des éléments inverses qui sont également des matrices non singulières. Par conséquent, la propriété inverse est également valable.

Groupe Abelian

Un groupe abélien G est un groupe pour lequel la paire d'éléments $ (a, b) \ dans G $ détient toujours la loi commutative. Ainsi, un groupe possède cinq propriétés simultanément - i) Clôture, ii) Associatif, iii) Élément d'identité, iv) Élément inverse, v) Commutatif.

Exemple

L'ensemble des entiers positifs (y compris zéro) avec opération d'addition est un groupe abélien. $ G = \ lbrace 0, 1, 2, 3, \ points \ rbrace $

Ici, la propriété de fermeture est valable comme pour chaque paire $ (a, b) \ dans S, (a + b) $ est présente dans l'ensemble S. [Par exemple, $ 1 + 2 = 2 \ in S $ et ainsi de suite]

La propriété associative est également valable pour chaque élément $ a, b, c \ dans S, (a + b) + c = a + (b + c) $ [Par exemple, $ (1 +2) + 3 = 1 + (2 + 3) = 6 $ et ainsi de suite]

La propriété d'identité est également valable pour chaque élément $ a \ dans S, (a \ times e) = a $ [Par exemple, $ (2 \ times 1) = 2, (3 \ times 1) = 3 $ et ainsi de suite]. Ici, l'élément d'identité est 1.

La propriété commutative est également valable pour chaque élément $ a \ dans S, (a \ times b) = (b \ times a) $ [Par exemple, $ (2 \ times 3) = (3 \ times 2) = 3 $ et ainsi sur]

Groupe cyclique et sous-groupe

UNE cyclic groupest un groupe qui peut être généré par un seul élément. Chaque élément d'un groupe cyclique est une puissance d'un élément spécifique qui est appelé un générateur. Un groupe cyclique peut être généré par un générateur «g», de sorte que tout autre élément du groupe peut être écrit comme une puissance du générateur «g».

Exemple

L'ensemble des nombres complexes $ \ lbrace 1, -1, i, -i \ rbrace $ sous l'opération de multiplication est un groupe cyclique.

Il existe deux générateurs - $ i $ et $ –i $ as $ i ^ 1 = i, i ^ 2 = -1, i ^ 3 = -i, i ^ 4 = 1 $ et aussi $ (- i) ^ 1 = -i, (–i) ^ 2 = -1, (–i) ^ 3 = i, (–i) ^ 4 = 1 $ qui couvre tous les éléments du groupe. C'est donc un groupe cyclique.

Note - Un cyclic groupest toujours un groupe abélien mais tous les groupes abéliens ne sont pas un groupe cyclique. Les nombres rationnels sous addition ne sont pas cycliques mais sont abéliens.

UNE subgroup H est un sous-ensemble d'un groupe G (noté $ H ≤ G $) s'il satisfait simultanément les quatre propriétés - Closure, Associative, Identity element, et Inverse.

Un sous-groupe H d'un groupe G qui n'inclut pas le groupe entier G est appelé un sous-groupe propre (désigné par $ H <G $). Un sous-groupe d'un groupe cyclique est cyclique et un sous-groupe abélien est également abélien.

Exemple

Soit un groupe $ G = \ lbrace 1, i, -1, -i \ rbrace $

Alors certains sous-groupes sont $ H_1 = \ lbrace 1 \ rbrace, H_2 = \ lbrace 1, -1 \ rbrace $,

Ceci n'est pas un sous-groupe - $ H_3 = \ lbrace 1, i \ rbrace $ parce que $ (i) ^ {- 1} = -i $ n'est pas dans $ H_3 $

Ensemble partiellement commandé (POSET)

Un ensemble partiellement ordonné consiste en un ensemble avec une relation binaire qui est réflexive, antisymétrique et transitive. «Ensemble partiellement ordonné» est abrégé en POSET.

Exemples

  • L'ensemble des nombres réels sous opération binaire inférieur ou égal à $ (\ le) $ est un poset.

    Soit l'ensemble $ S = \ lbrace 1, 2, 3 \ rbrace $ et l'opération est $ \ le $

    Les relations seront $ \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace $

    Cette relation R est réflexive comme $ \ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ in R $

    Cette relation R est anti-symétrique, car

    $ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ et \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R $

    Cette relation R est aussi transitive comme $ \ lbrace (1,2), (2,3), (1,3) \ rbrace \ in R $.

    Par conséquent, c'est un poset.

  • L'ensemble de sommets d'un graphe acyclique dirigé sous l'opération «accessibilité» est un poset.

Diagramme de Hasse

Le diagramme de Hasse d'un poset est le graphe orienté dont les sommets sont l'élément de ce poset et les arcs recouvrent les paires (x, y) dans le poset. Si dans le poset $ x <y $, alors le point x apparaît plus bas que le point y dans le diagramme de Hasse. Si $ x <y <z $ dans le poset, alors la flèche n'est pas affichée entre x et z car elle est implicite.

Exemple

L'ensemble des sous-ensembles de $ \ lbrace 1, 2, 3 \ rbrace = \ lbrace \ emptyset, \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace, \ lbrace 1, 2 \ rbrace, \ lbrace 1 , 3 \ rbrace, \ lbrace 2, 3 \ rbrace, \ lbrace 1, 2, 3 \ rbrace \ rbrace $ est illustré par le diagramme de Hasse suivant -

Ensemble ordonné linéairement

Un ensemble ordonné linéairement ou un ensemble ordonné total est un ensemble d'ordre partiel dans lequel chaque paire d'éléments est comparable. On dit que les éléments $ a, b \ dans S $ sont comparables si $ a \ le b $ ou $ b \ le a $ tient. La loi de la trichotomie définit cet ensemble ordonné total. Un ensemble totalement ordonné peut être défini comme un réseau distributif ayant la propriété $ \ lbrace a \ lor b, a \ land b \ rbrace = \ lbrace a, b \ rbrace $ pour toutes les valeurs de a et b de l'ensemble S.

Exemple

L'ensemble de puissance de $ \ lbrace a, b \ rbrace $ ordonné par \ subseteq est un ensemble totalement ordonné comme tous les éléments de l'ensemble de puissance $ P = \ lbrace \ emptyset, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace a, b \ rbrace \ rbrace $ sont comparables.

Exemple de jeu de commandes non total

Un ensemble $ S = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ sous l'opération x divise y n'est pas un ensemble ordonné total.

Ici, pour tout $ (x, y) \ in S, x | y $ doit tenir mais il n'est pas vrai que 2 | 3, car 2 ne divise pas 3 ou 3 ne divise pas 2. Ce n'est donc pas un ensemble ordonné total.

Treillis

Un treillis est un poset $ (L, \ le) $ pour lequel chaque paire $ \ lbrace a, b \ rbrace \ in L $ a une borne inférieure (notée $ a \ lor b $) et une borne inférieure ( notée $ a \ land b $). LUB $ (\ lbrace a, b \ rbrace) $ est appelée la jointure de a et b. GLB $ (\ lbrace a, b \ rbrace) $ est appelée la rencontre de a et b.

Exemple

Cette figure ci-dessus est un treillis car pour chaque paire $ \ lbrace a, b \ rbrace \ dans L $, il existe un GLB et un LUB.

Cette figure ci-dessus n'est pas un treillis car $ GLB (a, b) $ et $ LUB (e, f) $ n'existe pas.

Quelques autres réseaux sont discutés ci-dessous -

Treillis délimité

Un treillis L devient un treillis borné s'il a un plus grand élément 1 et un plus petit élément 0.

Treillis complété

Un réseau L devient un réseau complété s'il s'agit d'un réseau borné et si chaque élément du réseau a un complément. Un élément x a un complément x 'si $ \ existe x (x \ land x' = 0 et x \ lor x '= 1) $

Treillis distributif

Si un treillis satisfait les deux propriétés de distribution suivantes, il est appelé treillis distributif.

  • $ a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c) $

  • $ a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c) $

Treillis modulaire

Si un treillis satisfait la propriété suivante, il est appelé treillis modulaire.

$ a \ land (b \ lor (a \ land d)) = (a \ land b) \ lor (a \ land d) $

Propriétés des treillis

Propriétés idempotentes

  • $ a \ lor a = a $

  • $ a \ land a = a $

Propriétés d'absorption

  • $ a \ lor (a \ land b) = a $

  • $ a \ land (a \ lor b) = a $

Propriétés commutatives

  • $ a \ lor b = b \ lor a $

  • $ a \ land b = b \ land a $

Propriétés associatives

  • $ a \ lor (b \ lor c) = (a \ lor b) \ lor c $

  • $ a \ land (b \ land c) = (a \ land b) \ land c $

Double d'un treillis

Le dual d'un treillis est obtenu en interchangeant les opérations '$ \ lor $' et '$ \ land $'.

Exemple

Le dual de $ \ lbrack a \ lor (b \ land c) \ rbrack \ est \ \ lbrack a \ land (b \ lor c) \ rbrack $