Relaciones de orden
Páginas: 10 (2298 palabras)
Publicado: 10 de marzo de 2012
Apuntes de Matem´tica Discreta a 7. Relaciones de Orden
Francisco Jos´ Gonz´lez Guti´rrez e a e
C´diz, Octubre de 2004 a
Universidad de C´diz a
Departamento de Matem´ticas a
ii
Lecci´n 7 o
Relaciones de Orden
Contenido
7.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7.1.1 7.1.2 7.1.3 7.1.4 7.2 7.2.1 7.2.2 7.2.3 7.3 7.3.1 7.3.27.4 7.5 7.6 7.4.1 Relaci´n de Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 o Relaci´n de Orden Estricto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 o Proposici´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 o Proposici´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 o ElementosComparables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Orden Parcial y Total . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Conjuntos Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Orden del Producto . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 164 Orden Lexicogr´fico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 a Diagrama de Hasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Conjuntos Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Producto
Representaci´n Gr´fica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .171 o a Ordenaci´n Topol´gica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 o o Elementos Caracter´ ısticos de un Conjunto Ordenado . . . . . . . . . . . . . 177 7.6.1 7.6.2 7.6.3 7.6.4 7.6.5 7.6.6 7.6.7 7.6.8 7.6.9 Elemento Maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 Elemento Minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 178 Existencia del Maximal y Minimal . . . . . . . . . . . . . . . . . . . . . . . . . 178 Algoritmo para la Ordenaci´n Topol´gica . . . . . . . . . . . . . . . . . . . . . 178 o o Elemento M´ximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 a Elemento M´ ınimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Unicidad del M´ximo y el M´ aınimo . . . . . . . . . . . . . . . . . . . . . . . . . 183 Cota Superior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Cota Inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.6.10 Conjunto Acotado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.6.11 Supremo . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 185 7.6.12 ´ Infimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.6.13 Unicidad del ´ Infimo y el Supremo . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Estudiamos en esta lecci´n una de las relaciones binarias m´s importantes que pueden definirse en un o a conjunto, las relaciones de orden. 153
Universidadde C´diz a
Departamento de Matem´ticas a
7.1
Generalidades
Una relaci´n de orden es una relaci´n definida en un conjunto que verifica las propiedades reflexiva, o o antisim´trica y transitiva. e Cuando en un conjunto hayamos definido una relaci´n de orden, diremos que el conjunto est´ ordenado o a con respecto a dicha relaci´n. o Los ret´ ıculos y las ´lgebras de Boole son conjuntosordenados con caracter´ a ısticas especiales. Estas estructuras algebraicas juegan un importante papel en la teor´ de conjuntos, as´ como en problemas ıa ı de ordenaci´n y b´squeda (problemas ´stos de especial inter´s en la inform´tica), y en particular las o u e e a a ´lgebras de Boole son importantes para la representaci´n de circuitos l´gicos. o o Antes de comenzar fijaremos ideas con un par...
Francisco Jos´ Gonz´lez Guti´rrez e a e
C´diz, Octubre de 2004 a
Universidad de C´diz a
Departamento de Matem´ticas a
ii
Lecci´n 7 o
Relaciones de Orden
Contenido
7.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7.1.1 7.1.2 7.1.3 7.1.4 7.2 7.2.1 7.2.2 7.2.3 7.3 7.3.1 7.3.27.4 7.5 7.6 7.4.1 Relaci´n de Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 o Relaci´n de Orden Estricto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 o Proposici´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 o Proposici´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 o ElementosComparables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Orden Parcial y Total . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Conjuntos Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Orden del Producto . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 164 Orden Lexicogr´fico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 a Diagrama de Hasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Conjuntos Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Producto
Representaci´n Gr´fica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .171 o a Ordenaci´n Topol´gica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 o o Elementos Caracter´ ısticos de un Conjunto Ordenado . . . . . . . . . . . . . 177 7.6.1 7.6.2 7.6.3 7.6.4 7.6.5 7.6.6 7.6.7 7.6.8 7.6.9 Elemento Maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 Elemento Minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 178 Existencia del Maximal y Minimal . . . . . . . . . . . . . . . . . . . . . . . . . 178 Algoritmo para la Ordenaci´n Topol´gica . . . . . . . . . . . . . . . . . . . . . 178 o o Elemento M´ximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 a Elemento M´ ınimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Unicidad del M´ximo y el M´ aınimo . . . . . . . . . . . . . . . . . . . . . . . . . 183 Cota Superior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Cota Inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.6.10 Conjunto Acotado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.6.11 Supremo . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 185 7.6.12 ´ Infimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.6.13 Unicidad del ´ Infimo y el Supremo . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Estudiamos en esta lecci´n una de las relaciones binarias m´s importantes que pueden definirse en un o a conjunto, las relaciones de orden. 153
Universidadde C´diz a
Departamento de Matem´ticas a
7.1
Generalidades
Una relaci´n de orden es una relaci´n definida en un conjunto que verifica las propiedades reflexiva, o o antisim´trica y transitiva. e Cuando en un conjunto hayamos definido una relaci´n de orden, diremos que el conjunto est´ ordenado o a con respecto a dicha relaci´n. o Los ret´ ıculos y las ´lgebras de Boole son conjuntosordenados con caracter´ a ısticas especiales. Estas estructuras algebraicas juegan un importante papel en la teor´ de conjuntos, as´ como en problemas ıa ı de ordenaci´n y b´squeda (problemas ´stos de especial inter´s en la inform´tica), y en particular las o u e e a a ´lgebras de Boole son importantes para la representaci´n de circuitos l´gicos. o o Antes de comenzar fijaremos ideas con un par...
Leer documento completo
Regístrate para leer el documento completo.