2.6: Ejercicios

EJERCICIO 2.1. ¿Cuál de las propiedades de reflexividad, simetría, antisimetría y transitividad se aplica a las relaciones dadas en los Ejemplos 2.1-2.4?

EJERCICIO 2.2. Demostrar que la relación en Ejemplo\(2.6\) es un ordenamiento parcial.

EJERCICIO 2.3. Enumere cada par en la relación dada en el Ejemplo 2.10.

EJERCICIO 2.4. Demostrar que la relación en Ejemplo\(2.17\) es una equivalencia.

EJERCICIO 2.5. Demostrar que la congruencia\(\bmod n\) es una relación de equivalencia sobre\(\mathbb{Z}\).

EJERCICIO 2.6. Demostrar que dos enteros están en la misma clase de congruencia\(\bmod n\) si y solo si tienen el mismo resto cuando se dividen por\(n\).

EJERCICIO 2.7. Supongamos que\(R\) es una relación sobre\(X\). ¿Qué significa si\(R\) es tanto un orden parcial como una equivalencia?

EJERCICIO 2.8. Considerar las relaciones sobre las personas “es hermano de”, “es hermano de”, “es padre de”, “está casado con”, “es descendiente de”. ¿Cuál de las propiedades de reflexividad, simetría, antisimetría y transitividad tiene cada una de estas relaciones? EJERCICIO 2.9. Vamos\(X=\{k \in \mathbb{N}: k \geq 2\}\). Considere las siguientes relaciones sobre\(X\):

(i)\(j R_{1} k\) si y sólo si\(\operatorname{gcd}(j, k)>1(\operatorname{gcd}\) representa el mayor divisor común).

ii)\(j R_{2} k\) si y sólo si\(j\) y\(k\) son coprimos (es decir\(\operatorname{gcd}(j, k)=1\)).

iii)\(j R_{3} k\) si y sólo si\(j \mid k\).

(iv)\(j R_{4} k\) si y sólo si\[\{p: p \text { is prime and } p \mid j\}=\{q: q \text { is prime and } q \mid k\} .\] Para cada relación, decir cuál de las propiedades de Reflexivity, Simetría, Antisimetría, Transitividad tiene.

EJERCICIO 2.10. Para\(j, k\) en\(\mathbb{N}^{+}\), definir dos relaciones\(R_{1}\) y\(R_{2}\) por\(j R_{1} k\) si\(j\) y\(k\) tener un dígito en común (pero no necesariamente en el mismo lugar) y\(j R_{2} k\) si \(j\)y\(k\) tener un dígito común en el mismo lugar (así, por ejemplo,\(108 R_{1} 82\), pero\((108,82) \notin R_{2}\)).

(i) Si\(j=\sum_{m=0}^{M} a_{m} 10^{m}\) y\(k=\sum_{n=0}^{N} b_{n} 10^{n}\), con\(a_{M} \neq 0\) y\(b_{N} \neq 0\), ¿cómo se puede definir matemáticamente\(R_{1}\) y\(R_{2}\) en términos de los coeficientes\(a_{m}\) y\(b_{n}\)?

(ii) ¿Cuál de las cuatro propiedades de reflexividad, simetría, antisimetría y transitividad tienen\(R_{1}\) y\(R_{2}\) tienen?

EJERCICIO 2.11. Vamos\(X=\{a, b\}\). Enumere todas las relaciones posibles sobre\(X\), y diga cuáles son reflexivas, cuáles son simétricas, cuáles son antisimétricas y cuáles son transitivas.

EJERCICIO 2.12. ¿Cuántas relaciones hay en un set con 3 elementos? ¿Cuántos de estos son reflexivos? ¿Cuántos son simétricos? ¿Cuántos son antisimétricos?

EJERCICIO 2.13. Repita Ejercicio\(2.12\) para un conjunto con\(N\) elementos.

EJERCICIO 2.14. La suma de dos enteros pares es par, la suma de un entero par y otro impar es impar, y la suma de dos enteros impares es par. ¿Cuál es la generalización de esta afirmación a las clases de residuos\(\bmod 3\)? EJERCICIO 2.15. ¿Cuál es el último dígito de\(3^{5^{7}}\)? \(7^{5^{3}}\)¿De? \(11^{10^{6}}\)¿De? \(8^{5^{4}}\)¿De?

EJERCICIO 2.16. ¿Qué es\(2^{1000000} \bmod 17\)? ¿Qué es\(17^{77} \bmod 14\)?

EJERCICIO 2.17. Mostrar que el residuo de un número\(\bmod 3\) es el mismo que la suma de sus dígitos.

EJERCICIO 2.18. Demostrar que la afirmación de Ejercicio no\(2.17\) es cierta\(\bmod n\) para ningún valor de\(n\) excepto 3 y 9.

EJERCICIO 2.19. Demostrar que hay un número infinito de números naturales que no se pueden escribir como la suma de tres cuadrados. (Pista: Mira los posibles residuos mod 8).

EJERCICIO 2.20. Dejar\(f: X \rightarrow Y\) y\(g: Y \rightarrow Z\). ¿Qué se puede decir de la relación entre\(X / f\) y\(X /(g \circ f)\)?

EJERCICIO 2.21. \(R\)Sea la relación sobre\(X=\mathbb{Z} \times \mathbb{N}^{+}\) definida en el Ejemplo 2.17. Definir una operación\(\star\) de la\(X / R\) siguiente manera: para\(x=(a, b)\) y\(y=(c, d)\),\[[x] \star[y]=[(a d+b c, c d)] .\] ¿Está\(\star\) bien definida?

EJERCICIO 2.22. Dejar\(X\) ser el conjunto de funciones de subconjuntos finitos de\(\mathbb{N}\) a\(\ulcorner 2\urcorner\) (es decir\(f \in X\), si hay un conjunto finito\(D \subseteq \mathbb{N}\) tal que\(f: D \rightarrow\ulcorner 2\urcorner\)). Defina una relación\(R\) de la\(X\) siguiente manera: si\(f, g \in X, f R g\) iff\(\operatorname{Dom}(g) \subseteq \operatorname{Dom}(f)\) y\(g=\left.f\right|_{\operatorname{Dom}(g)}\). ¿Es\(R\) un pedido parcial? ¿Es\(R\) una relación de equivalencia?

EJERCICIO\(2.23\). Dejar\(X\) ser el conjunto de todas las secuencias binarias infinitas. Definir una relación\(R\) de la\(X\) siguiente manera: Para cualquier\(f, g \in X, f R g\) iff\(f^{-1}(1) \subseteq\)\(g^{-1}(1)\). ¿Es\(R\) un pedido parcial? ¿Es\(R\) una relación de equivalencia?

EJERCICIO 2.24. Vamos\(X=\{\ulcorner n\urcorner \mid n \in \mathbb{N}\}\). Dejar\(R\) ser una relación sobre\(X\) definida por\(x, y \in R\) iff\(x \subseteq y\). Demostrar que\(R\) es un ordenamiento lineal. EJERCICIO 2.25. Vamos\(X=\{f: \mathbb{R} \rightarrow \mathbb{R} \mid f\) es una sobrejección\(\}\). Definir una relación\(R\) sobre\(X\) por\(f R g\) iff\(f(0)=g(0)\). Demostrar que\(R\) es una relación de equivalencia. Dejar\(F: X \rightarrow \mathbb{R}\) ser definido por\(F(f)=f(0)\). Mostrar que los conjuntos de niveles de\(F\) son las clases de equivalencia de\(X / R\). Eso es demostrar que\[X / R=X / F .\] EJERCICIO 2.26. Vamos\(f: X \rightarrow Y\). Mostrar que\(X / f\) se compone de singletons (conjuntos con exactamente un elemento) iff\(f\) es una inyección.