Determinación de las propiedades de la relación sobre $P(\mathbb{N})$ donde $ARB \iff A \cup B \in H$

Question

Tuve dos problemas con este ejercicio:

• No conozco el universo para hacer $\overline{A}$ (Lo mostraré a continuación).
• No pude demostrar que fuera transitivo, aunque estoy bastante seguro de que lo es.

¿Puede ayudarme ahí?

---

Para $A \in P(\mathbb{N})$ decimos que $A \in H \iff \overline{A}$ es finito.

En $P(\mathbb{N})$ se define la relación $R$ :

$$ARB \iff A \cup B \in H$$

Determina sus propiedades.

En primer lugar, la afirmación inicial dice que para una parte X de $\mathbb{N}$ :

• $X \in H \implies \overline{X}$ es finito
• $\overline{X}$ es finito $\implies X \in H$

---

Pregunta : Cuando dice $\overline{A}$ necesito saber el universo en el que estamos trabajando, ¿verdad? ¿Es el universo $\mathbb{N}$ ? O $P(\mathbb{N})$ ? O $\mathbb{R}$ ?

Para este ejercicio supondré que se refiere a $\mathbb{N}$ .

---

Reflexivo

No. Tener un conjunto $A$ en $P(\mathbb{N})$ donde $A = \{1,2,3\}$ . Tenga en cuenta que $\overline{A}$ sería infinito, dado que el universo es $\mathbb{N}$ .

Desde $\overline{A}$ es infinito, $A \not \in H$ Según la premisa que se nos da.

$A \cup A = A$ y sabemos que $A \not \in H$ . Por lo tanto, la relación no es reflexiva.

---

Simétrico

Sí. Queremos demostrar que $ARB \implies BRA$ para $A,B \in P(\mathbb{N})$ .

Tenga

$$ARB$$

$$A \cup B \in H$$

Desde $\cup$ es conmutativo, es equivalente a

$$B \cup A \in H$$

Por lo tanto, la relación es simétrica.

---

Antisimétrico

No. Tener conjuntos $A,B \in P(\mathbb{N})$ , donde $A = \mathbb{N}$ y $B = \{1,2,3\}$ .

Desde $\overline{A} = \emptyset$ , $\overline{A}$ es finito. Según la premisa, esto significa que $A \in H$ . Por lo tanto:

$$A \cup B \in H$$

Así que $ARB$ . Y entonces:

$$B \cup A \in H$$

Así que $BRA$ . Sin embargo:

$$A \not = B$$

Así que la relación no es antisimétrica.

---

Transitivo

Sí. Tengan $A,B,C \in P(\mathbb{N})$ donde $ARB \land BRC$ .

$$ARB \land BRC$$

$$(A \in H \lor B \in H) \land (B \in H \lor C \in H)$$

$$(B \in H) \lor (A \in H \land C \in H)$$

$$B \in H \lor A \in H \lor C \in H$$

Si pudiera demostrar que $B \not \in H$ Yo habría terminado. ¿Pero cómo?

---

Total

No. Tener conjuntos $A,B \in P(\mathbb{N})$ donde $A = \{1,2,3\}$ y $B = \{4,5,6\}$

A partir de nuestra prueba reflexiva, sabemos que $A \not \in H$ . La misma lógica puede aplicarse a $B$ .

Dado que ninguno de los dos está en $H$ tenemos que

$$A \cup B \not \in H$$

Y por supuesto,

$$B \cup A \not \in H$$

Así,

$$A\not R B \land B \not R A$$

Así que la relación no es total.

Answer 1

Sí, los complementos se toman en $\Bbb N$ . $H$ es la colección de subconjuntos de $\Bbb N$ cuyos complementos en $\Bbb N$ son finitas; éstas se denominan cofinito subconjuntos de $\Bbb N$ .

Sus ejemplos demuestran que $R$ no es reflexivo y no es antisimétrico están bien, al igual que su prueba de que $R$ es simétrica. $R$ es no transitivo. Por ejemplo, $\varnothing\cup\Bbb N=\Bbb N$ y el complemento de $\Bbb N$ siendo vacía, es ciertamente finita, por lo que $\varnothing\mathbin{R}\Bbb N$ . Por simetría (o repitiendo el argumento) también tenemos $\Bbb N\mathbin{R}\varnothing$ . Pero $\varnothing\cup\varnothing=\varnothing$ cuyo complemento $\Bbb N\setminus\varnothing=\Bbb N$ no es ciertamente finito, por lo que $\varnothing\,\not R\,\varnothing$ y $R$ no es transitivo.

Se podría haber sospechado esta falta de transitividad por el hecho de que $R$ es simétrica pero no reflexiva. Hay relaciones simétricas no reflexivas que son transitivas, pero son casos especiales: son subconjuntos propios de la relación de identidad sobre un conjunto. Lo más frecuente es tener el tipo de situación que tenemos aquí: un elemento $a$ que no se relaciona consigo mismo, sino que es relacionado con algún otro elemento $b$ . Aquí $\varnothing$ no está relacionado consigo mismo, pero sí con $\Bbb N$ . Siempre que se tenga esa situación con una relación simétrica, se puede mostrar tal como lo hice aquí con $\varnothing$ y $\Bbb N$ que la relación no es transitiva: $a\mathbin{R}b$ y por simetría $b\mathbin{R}a$ pero -en contra de la transitividad- $a\,\not R\,b$ .

Su ejemplo muestra que $R$ no es total está bien, pero en realidad no lo necesitabas: el hecho de que $R$ no es reflexivo ya muestra que no es total, ya que (por ejemplo) $\color{blue}{\varnothing}\,\not R\,\color{brown}{\varnothing}$ y $\color{brown}{\varnothing}\,\not R\,\color{blue}{\varnothing}$ .

Answer 2

Si una relación es simétrica y no reflexiva, es difícil que sea transitiva. Tomemos cualquier $A$ tal que $\neg ARA$ . Entonces, asumiendo la transitividad se obtiene $$ \neg ARA \implies \neg (ARB\wedge BRA)\implies \neg ARB $$ para cualquier $B$ . (Así que si puedes encontrar un $A$ y cualquier $B$ tal que $ARB$ , se tiene un contraejemplo de transitividad).