Matemática Discreta 1

Videos indicados: Relaciones de equivalencia y Relaciones de orden.

Temario (basado en las secciones 7.3 y 7.4 del Grimaldi)

• Relaciones de equivalencia y su relación con particiones, clases de equivalencias y conjunto cociente.
• Conjuntos parcialmente ordenados, ordenes totales y parciales, diagrama de Hasse, cadenas y anticadenas.
• Retículos (látices), cotas superiores e inferiores, supremo e ínfimo, elementos maximales y minimales, máximo y mínimo.

Definiciones y convenciones:  Consideremos una relación de orden parcial $\leq$ en un conjunto A.

• Llamamos cadena a un subconjunto $C=\{c_1,c_2,\ldots, c_m\}\subseteq A$ tal que para todo $i,j$ tenemos $c_i\leq c_j$ o $c_j\leq c_i$. También llamamos cadena a una secuencia $(c_1,c_2,\ldots,c_m)$ tal que $c_1\leq c_2 \leq \ldots \leq c_m$ (decimos que esta cadena comienza en $c_1$ y termina en $c_m$).
• El cardinal o tamaño de una cadena $(c_1,c_2,\ldots,c_m)$ es $m$ y su largo es $m-1$.
• La altura de un elemento $a\in A$ es el largo de la mayor cadena que termina en $a$ (los minimales tendrán altura $0$).
• Por convención, cuando dibujemos el diagrama de Hasse, elementos con la misma altura estarán en un mismo nivel.