Determining the properties for the relation over $P(\mathbb{N})$ where $ARB \iff A \cup B \in H$

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}$.
If a relation is symmetric and non-reflexive, it's hard for it to be transitive. Take any $A$ such that $\neg ARA$. Then assuming transitivity gives $$\neg ARA \implies \neg (ARB\wedge BRA)\implies \neg ARB$$ for any $B$. (So if you can find a non-reflexive $A$ and any $B$ such that $ARB$, you have a counterexample to transitivity.)
• $A = \{1,2,3\}$ and $B = \mathbb{N}$, $A$ is not reflexive, $ARB$ holds since $\overline{B}$ is finite - but I still don't see how does that serve as a counterexample for transitivity. – Zol Tun Kul Nov 7 '13 at 8:45
• If it was transitive, you could deduce $ARA$ from $ARB$ and $BRA$, but as you said $ARA$ is false. – Christoph Nov 7 '13 at 11:00