Programacion

´ CONJUNTOS Y NUMEROS. HOJA 4

(1) Hemos definido una relaci´n R en un conjunto A a partir de un subconjunto SR ⊂ A × A. Dado el conjunto o A = {a, b, c}, definir un subconjunto SR ⊂ A × A cuya relaci´n asociada R cumpla simultaneamente las o siguientes condiciones: i) R es una relacion de orden. ii) R no define un orden total. iii) R no es la relaci´n identidad. o (2) Sea A un conjunto. Definimosen P (A) la relaci´n X R Y ⇔ X ⊂ Y . Demostrar que R es una relaci´n de o o orden en P (A). (3) Sea A = {a, b, c} y sea X el subconjunto de P (A) cuyos elementos son los subconjuntos propios de A (un subconjunto de A es propio si es distinto de A). Consideramos en X la relaci´n inducida por la inclusi´n en o o P (A) (v´ase el ejercicio 2). Hallar los elementos maximales y minimales de X. e (4) Sea(A, ≤) un conjunto ordenado, B ⊂ A un subconjunto. Para cada una de las afirmaciones siguientes demostrar que es cierta o dar un contraejemplo: i) Si A tiene un m´ximo, entonces A tiene un unico elemento a ´ maximal; ii) Si A tiene un unico elemento maximal, entonces A tiene un m´ximo; iii) Si B tiene un ´ ´ a ınfimo en A, entonces B tiene un unico elemento minimal y iv) Si B tiene un unicoelemento minimal, entonces B tiene ´ ´ un ´ ınfimo en A. (5) Dada la relaci´n de orden en N, nRm⇐⇒n divide a m, hallar los elementos maximales, minimales, m´ximos o a y m´ ınimos (si existen) del conjunto A = {2, 3, 5, 6, 15, 10, 30}. ¿Es R una relaci´n de orden total en A?. o (6) Sea X un conjunto no vac´ (N, ≤) el conjunto ordenado de los n´meros naturales y f : X −→ N una ıo, u aplicaci´n. Se define enX la siguiente relaci´n: xRy ⇔ f (x) ≤ f (y). Demostrar que: o o a) La relaci´n R no es en general una relaci´n de orden. o o b) La relaci´n R es una relaci´n de orden si y s´lo si f es una aplicaci´n inyectiva. o o o o (7) Diremos que una relaci´n R en un conjunto A (que supondremos = ∅) es una relaci´n de orden estricto si o o satisface las dos propiedades siguientes: i) No existen x, y ∈ Atales que xRy e yRx (se podr´ llamar a esta propiedad “antisim´trica estricta”). ıa e ii) Si xRy e yRz, entonces xRz (propiedad transitiva). a) Demostrar que una relaci´n de orden no es una relaci´n de orden estricto, y que una relaci´n de orden o o o estricto no es una relaci´n de orden. o b) A pesar de la anterior, demostrar que dar una relaci´n de orden estricto en un conjunto A es equivalente o adar una relaci´n de orden en A. (Sugerencia: ¿qu´ hay que a˜adir a una relaci´n de orden estricto para o e n o convertirla en una relaci´n de orden?) o (8) Sea X = {A ∈ P (Z) : A es finito}. Dado A finito, Card(A), el cardinal de A, es el n´mero de elementos de A. u a) Definimos en X la relaci´n ARB⇐⇒Card(A) ≤ Card(B). Demostrar que R NO es una relaci´n de o o orden. b) Definimos ahora en X larelaci´n AR B⇐⇒Card(A) < Card(B). Demostrar que R es una relaci´n de o o orden estricto (v´ase el ejercicio 7). e c) Describe la relaci´n de orden definida por R de acuerdo con el procedimiento del apartado b) del o problema 7. (9) Dados α = (a, b, c) y α = (a , b , c ) en N3 , se define: α ≤ α ⇐⇒(a < a ) ∨ (a = a ∧b < b ) ∨ (a = a ∧b = b ∧c ≤ c ). Discutir qu´ tipo de relaci´n de orden es. Esta relaci´n deorden se llama orden lexicogr´fico, por e o o a el modo en que ordenamos las palabras en el diccionario. Explicar por qu´ merece este nombre. e (10) a) Generalizar la relaci´n del ejercicio anterior para, dado k, ordenar k-uplas (a1 , a2 , . . . , ak ) de enteros posio tivos. b) Generalizar el apartado anterior definiendo un orden lexicogr´fico en Ak := {(a1 , . . . , ak ) | ai ∈ A}, donde a (A, ≤)es un conjunto ordenado cualquiera. (11) Demuestra que si X e Y son conjuntos totalmente ordenados, entonces X × Y con orden lexicogr´fico es un a conjunto totalmente ordenado. (12) Consideramos a N×N con orden lexicogr´fico. En este conjunto totalmente ordenado definimos el subconjunto a S = {(0, a) | a ∈ N }. Demuestra que S es un subconjunto acotado superiormente, pero no tiene m´ximo. a ¿Tiene...