Matemáticas discretas - Teoría de grupos
Semigroup
Un conjunto finito o infinito $ 'S' $ con una operación binaria $ '\ omicron' $ (Composición) se llama semigrupo si cumple las siguientes dos condiciones simultáneamente:
Closure - Para cada par $ (a, b) \ en S, \ :( a \ omicron b) $ tiene que estar presente en el conjunto $ S $.
Associative - Para cada elemento $ a, b, c \ en S, (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c) $ debe ser válido.
Ejemplo
El conjunto de enteros positivos (excluyendo el cero) con operación de suma es un semigrupo. Por ejemplo, $ S = \ lbrace 1, 2, 3, \ dots \ rbrace $
Aquí la propiedad de cierre es válida para cada par $ (a, b) \ en S, (a + b) $ está presente en el conjunto S. Por ejemplo, $ 1 + 2 = 3 \ en S] $
La propiedad asociativa también es válida para cada elemento $ a, b, c \ en S, (a + b) + c = a + (b + c) $. Por ejemplo, $ (1 + 2) + 3 = 1 + (2 + 3) = 5 $
Monoide
Un monoide es un semigrupo con un elemento de identidad. El elemento de identidad (denotado por $ e $ o E) de un conjunto S es un elemento tal que $ (a \ omicron e) = a $, para cada elemento $ a \ en S $. Un elemento de identidad también se llamaunit element. Entonces, un monoide tiene tres propiedades simultáneamente:Closure, Associative, Identity element.
Ejemplo
El conjunto de enteros positivos (excluyendo el cero) con operación de multiplicación es un monoide. $ S = \ lbrace 1, 2, 3, \ dots \ rbrace $
Aquí la propiedad de cierre es válida para cada par $ (a, b) \ en S, (a \ times b) $ está presente en el conjunto S. [Por ejemplo, $ 1 \ times 2 = 2 \ en S $ y así sucesivamente]
La propiedad asociativa también es válida para cada elemento $ a, b, c \ en S, (a \ times b) \ times c = a \ times (b \ times c) $ [Por ejemplo, $ (1 \ times 2) \ times 3 = 1 \ times (2 \ times 3) = 6 $ y así sucesivamente]
La propiedad de identidad también es válida para cada elemento $ a \ en S, (a \ times e) = a $ [Por ejemplo, $ (2 \ times 1) = 2, (3 \ times 1) = 3 $ y así sucesivamente]. Aquí el elemento de identidad es 1.
Grupo
Un grupo es un monoide con un elemento inverso. El elemento inverso (denotado por I) de un conjunto S es un elemento tal que $ (a \ omicron I) = (I \ omicron a) = a $, para cada elemento $ a \ en S $. Entonces, un grupo tiene cuatro propiedades simultáneamente: i) Cierre, ii) Asociativo, iii) Elemento de identidad, iv) Elemento inverso. El orden de un grupo G es el número de elementos en G y el orden de un elemento en un grupo es el número entero menos positivo n tal que an es el elemento de identidad de ese grupo G.
Ejemplos
El conjunto de $ N \ veces N $ matrices no singulares forman un grupo bajo la operación de multiplicación de matrices.
El producto de dos matrices no singulares $ N \ veces N $ es también una matriz no singular $ N \ veces N $ que tiene la propiedad de cierre.
La multiplicación de matrices en sí es asociativa. Por tanto, la propiedad asociativa se mantiene.
El conjunto de $ N \ veces N $ matrices no singulares contiene la matriz identidad que contiene la propiedad del elemento identidad.
Como todas las matrices son no singulares, todas tienen elementos inversos que también son matrices no singulares. Por tanto, la propiedad inversa también es válida.
Grupo Abeliano
Un grupo abeliano G es un grupo para el cual el par de elementos $ (a, b) \ en G $ siempre tiene una ley conmutativa. Entonces, un grupo tiene cinco propiedades simultáneamente: i) Cierre, ii) Asociativo, iii) Elemento de identidad, iv) Elemento inverso, v) Conmutativo.
Ejemplo
El conjunto de enteros positivos (incluido el cero) con operación de suma es un grupo abeliano. $ G = \ lbrace 0, 1, 2, 3, \ dots \ rbrace $
Aquí la propiedad de cierre es válida para cada par $ (a, b) \ en S, (a + b) $ está presente en el conjunto S. [Por ejemplo, $ 1 + 2 = 2 \ en S $ y así sucesivamente]
La propiedad asociativa también es válida para cada elemento $ a, b, c \ en S, (a + b) + c = a + (b + c) $ [Por ejemplo, $ (1 +2) + 3 = 1 + (2 + 3) = 6 $ y así sucesivamente]
La propiedad de identidad también es válida para cada elemento $ a \ en S, (a \ times e) = a $ [Por ejemplo, $ (2 \ times 1) = 2, (3 \ times 1) = 3 $ y así sucesivamente]. Aquí, el elemento de identidad es 1.
La propiedad conmutativa también es válida para cada elemento $ a \ en S, (a \ times b) = (b \ times a) $ [Por ejemplo, $ (2 \ times 3) = (3 \ times 2) = 3 $ y así en]
Grupo cíclico y subgrupo
UNA cyclic groupes un grupo que puede ser generado por un solo elemento. Cada elemento de un grupo cíclico es una potencia de algún elemento específico que se llama generador. Un grupo cíclico puede ser generado por un generador 'g', de modo que todos los demás elementos del grupo pueden escribirse como una potencia del generador 'g'.
Ejemplo
El conjunto de números complejos $ \ lbrace 1, -1, i, -i \ rbrace $ bajo operación de multiplicación es un grupo cíclico.
Hay dos generadores: $ i $ y $ –i $ como $ i ^ 1 = i, i ^ 2 = -1, i ^ 3 = -i, i ^ 4 = 1 $ y también $ (- i) ^ 1 = -i, (–i) ^ 2 = -1, (–i) ^ 3 = i, (–i) ^ 4 = 1 $ que cubre todos los elementos del grupo. Por tanto, es un grupo cíclico.
Note - A cyclic groupes siempre un grupo abeliano, pero no todos los grupos abelianos son cíclicos. Los números racionales bajo la suma no son cíclicos sino abelianos.
UNA subgroup H es un subconjunto de un grupo G (denotado por $ H ≤ G $) si satisface las cuatro propiedades simultáneamente - Closure, Associative, Identity elementy Inverse.
Un subgrupo H de un grupo G que no incluye a todo el grupo G se denomina subgrupo propio (indicado por $ H <G $). Un subgrupo de un grupo cíclico es cíclico y un subgrupo abeliano también es abeliano.
Ejemplo
Sea un grupo $ G = \ lbrace 1, i, -1, -i \ rbrace $
Entonces, algunos subgrupos son $ H_1 = \ lbrace 1 \ rbrace, H_2 = \ lbrace 1, -1 \ rbrace $,
Este no es un subgrupo - $ H_3 = \ lbrace 1, i \ rbrace $ porque ese $ (i) ^ {- 1} = -i $ no está en $ H_3 $
Conjunto parcialmente ordenado (POSET)
Un conjunto parcialmente ordenado consiste en un conjunto con una relación binaria que es reflexiva, antisimétrica y transitiva. "Conjunto parcialmente ordenado" se abrevia como POSET.
Ejemplos
El conjunto de números reales bajo operación binaria menor o igual que $ (\ le) $ es un poset.
Sea el conjunto $ S = \ lbrace 1, 2, 3 \ rbrace $ y la operación es $ \ le $
Las relaciones serán $ \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace $
Esta relación R es reflexiva como $ \ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ in R $
Esta relación R es antisimétrica, ya que
$ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ y \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R $
Esta relación R también es transitiva como $ \ lbrace (1,2), (2,3), (1,3) \ rbrace \ en R $.
Por tanto, es un poset.
El conjunto de vértices de un gráfico acíclico dirigido bajo la operación 'alcanzabilidad' es un poset.
Diagrama de Hasse
El diagrama de Hasse de un poset es el gráfico dirigido cuyos vértices son el elemento de ese poset y los arcos cubren los pares (x, y) en el poset. Si en el poset $ x <y $, entonces el punto x aparece más bajo que el punto y en el diagrama de Hasse. Si $ x <y <z $ en el poset, entonces la flecha no se muestra entre xyz ya que está implícita.
Ejemplo
El conjunto de subconjuntos 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 $ se muestra en el siguiente diagrama de Hasse:
Conjunto ordenado linealmente
Un conjunto ordenado linealmente o un conjunto ordenado total es un conjunto de orden parcial en el que cada par de elementos es comparable. Se dice que los elementos $ a, b \ en S $ son comparables si se cumple $ a \ le b $ o $ b \ le a $. La ley de tricotomía define este conjunto ordenado total. Un conjunto totalmente ordenado se puede definir como una red distributiva que tiene la propiedad $ \ lbrace a \ lor b, a \ land b \ rbrace = \ lbrace a, b \ rbrace $ para todos los valores de ayb en el conjunto S.
Ejemplo
El conjunto de potencias de $ \ lbrace a, b \ rbrace $ ordenado por \ subseteq es un conjunto totalmente ordenado como todos los elementos del conjunto de potencias $ P = \ lbrace \ emptyset, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace a, b \ rbrace \ rbrace $ son comparables.
Ejemplo de conjunto de pedidos no totales
Un conjunto $ S = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ bajo la operación x divide y no es un conjunto ordenado total.
Aquí, para todo $ (x, y) \ en S, x | y $ tienen que mantenerse, pero no es cierto que 2 | 3, como 2 no divide a 3 o 3 no divide a 2. Por tanto, no es un conjunto ordenado total.
Enrejado
Una celosía es un poset $ (L, \ le) $ para el cual cada par $ \ lbrace a, b \ rbrace \ en L $ tiene un límite superior mínimo (denotado por $ a \ lor b $) y un límite inferior mayor ( denotado por $ a \ land b $). LUB $ (\ lbrace a, b \ rbrace) $ se llama la unión de ay b. GLB $ (\ lbrace a, b \ rbrace) $ se llama el encuentro de ay b.
Ejemplo
Esta figura anterior es una celosía porque para cada par $ \ lbrace a, b \ rbrace \ en L $, existe un GLB y un LUB.
Esta figura anterior no es un enrejado porque $ GLB (a, b) $ y $ LUB (e, f) $ no existen.
Algunas otras celosías se analizan a continuación:
Celosía acotada
Una celosía L se convierte en una celosía acotada si tiene un elemento mayor 1 y un elemento mínimo 0.
Celosía complementada
Una celosía L se convierte en una celosía complementada si es una celosía acotada y si cada elemento de la celosía tiene un complemento. Un elemento x tiene un complemento x 'si $ \ existe x (x \ land x' = 0 y x \ lor x '= 1) $
Celosía distributiva
Si una celosía satisface las siguientes dos propiedades de distribución, se denomina celosía distributiva.
$ a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c) $
$ a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c) $
Celosía modular
Si una celosía satisface la siguiente propiedad, se denomina celosía modular.
$ a \ land (b \ lor (a \ land d)) = (a \ land b) \ lor (a \ land d) $
Propiedades de las celosías
Propiedades idempotentes
$ a \ lor a = a $
$ a \ land a = a $
Propiedades de absorción
$ a \ lor (a \ land b) = a $
$ a \ land (a \ lor b) = a $
Propiedades conmutativas
$ a \ lor b = b \ lor a $
$ a \ tierra b = b \ tierra a $
Propiedades asociativas
$ a \ lor (b \ lor c) = (a \ lor b) \ lor c $
$ a \ tierra (b \ tierra c) = (a \ tierra b) \ tierra c $
Doble de una celosía
El dual de una celosía se obtiene intercambiando las operaciones '$ \ lor $' y '$ \ land $'.
Ejemplo
El dual de $ \ lbrack a \ lor (b \ land c) \ rbrack \ es \ \ lbrack a \ land (b \ lor c) \ rbrack $