I had two problems with this exercise:
- I don't know the universe for doing $\overline{A}$ (I'll show below).
- I couldn't show that it was transitive, although I'm fairly sure it is.
Can you assist me there?
For $A \in P(\mathbb{N})$, we say that $A \in H \iff \overline{A}$ is finite.
Over $P(\mathbb{N})$ is defined the relation $R$:
$$ARB \iff A \cup B \in H$$
Determine its properties.
First of all, the beginning statement says that for a part X of $\mathbb{N}$:
- $X \in H \implies \overline{X}$ is finite
- $\overline{X}$ is finite $\implies X \in H$
Question: When it says $\overline{A}$, I need to know the universe we're working on, right? Is the universe $\mathbb{N}$? Or $P(\mathbb{N})$? Or $\mathbb{R}$?
For this exercise I will assume that it refers to $\mathbb{N}$.
Reflexive
No. Have a set $A$ in $P(\mathbb{N})$ where $A = \{1,2,3\}$. Note that $\overline{A}$ would be infinite, given that the universe is $\mathbb{N}$.
Since $\overline{A}$ is infinite, $A \not \in H$, according to the premise we're given.
$A \cup A = A$, and we know that $A \not \in H$. Therefore the relation is not reflexive.
Symmetric
Yes. We want to prove that $ARB \implies BRA$ for $A,B \in P(\mathbb{N})$.
Have
$$ARB$$
$$A \cup B \in H$$
Since $\cup$ is commutative, it is equivalent to
$$B \cup A \in H$$
Hence, the relation is symmetric.
Antisymmetric
No. Have sets $A,B \in P(\mathbb{N})$, where $A = \mathbb{N}$ and $B = \{1,2,3\}$.
Since $\overline{A} = \emptyset$, $\overline{A}$ is finite. According to the premise, this means that $A \in H$. Therefore:
$$A \cup B \in H$$
So $ARB$. And then:
$$B \cup A \in H$$
So $BRA$. However:
$$A \not = B$$
So the relation isn't antisymmetric.
Transitive
Yes. Have $A,B,C \in P(\mathbb{N})$ where $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$$
If I could show that $B \not \in H$ I would be done. But how?
Total
No. Have sets $A,B \in P(\mathbb{N})$ where $A = \{1,2,3\}$ and $B = \{4,5,6\}$
From our reflexive proof, we know that $A \not \in H$. The same logic can be applied to $B$.
Since neither are in $H$, we have that
$$A \cup B \not \in H$$
And of course,
$$B \cup A \not \in H$$
Thus,
$$A\not R B \land B \not R A$$
So the relation isn't total.
Yes, the complements are taken in $\Bbb N$. $H$ is the collection of subsets of $\Bbb N$ whose complements in $\Bbb N$ are finite; these are called the cofinite subsets of $\Bbb N$.
Your examples showing that $R$ is not reflexive and not antisymmetric are fine, as is your proof that $R$ is symmetric. $R$ is not transitive. For example, $\varnothing\cup\Bbb N=\Bbb N$, and the complement of $\Bbb N$, being empty, is certainly finite, so $\varnothing\mathbin{R}\Bbb N$. By symmetry (or by repeating the argument) we also have $\Bbb N\mathbin{R}\varnothing$. But $\varnothing\cup\varnothing=\varnothing$, whose complement $\Bbb N\setminus\varnothing=\Bbb N$ is certainly not finite, so $\varnothing\,\not R\,\varnothing$, and $R$ is not transitive.
You could have suspected this lack of transitivity from the fact that $R$ is symmetric but not reflexive. There are symmetric, non-reflexive relations that are transitive, but they’re special cases: they’re proper subsets of the identity relation on a set. More often you have the kind of situation that we have here: an element $a$ that is not related to itself but is related to some other element $b$. Here $\varnothing$ is not related to itself but is related to $\Bbb N$. Whenever you have that situation with a symmetric relation, you can show just I did here with $\varnothing$ and $\Bbb N$ that the relation is not transitive: $a\mathbin{R}b$, and by symmetry $b\mathbin{R}a$, but — contrary to transitivity — $a\,\not R\,b$.
Your example showing that $R$ is not total is fine, but you didn’t actually need it: the fact that $R$ is not reflexive already shows that it’s not total, since (for instance) $\color{blue}{\varnothing}\,\not R\,\color{brown}{\varnothing}$ and $\color{brown}{\varnothing}\,\not R\,\color{blue}{\varnothing}$.