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}$.


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.


Yes. We want to prove that $ARB \implies BRA$ for $A,B \in P(\mathbb{N})$.



$$A \cup B \in H$$

Since $\cup$ is commutative, it is equivalent to

$$B \cup A \in H$$

Hence, the relation is symmetric.


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.


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?


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$$


$$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.)

  • $\begingroup$ $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. $\endgroup$ – Zol Tun Kul Nov 7 '13 at 8:45
  • $\begingroup$ If it was transitive, you could deduce $ARA$ from $ARB$ and $BRA$, but as you said $ARA$ is false. $\endgroup$ – Christoph Nov 7 '13 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.