0

$\equiv$ is an equivalence relation on $P(\mathbb{N})$ ($P(A)$ denotes the power set of the set $A$) defined as $$A\equiv B \iff A,B\subseteq \mathbb{N} \land (\forall X\subseteq\mathbb{N})[A\cup X=\mathbb{N}\iff B\cup X=\mathbb{N}]$$ Is $P(\mathbb{N})/\equiv$ a finite set (the quotient set of $P(\mathbb{N})$ by $\equiv$; so the set of all equivalence classes in $P(\mathbb{N})$ with respect to the relation $\equiv$)?

Note: I have a feeling that the definition of the relation could be simplified but I don't see how. I am not sure what exactly $(\forall X\subseteq\mathbb{N})[A\cup X=\mathbb{N}\iff B\cup X=\mathbb{N}]$ means for $A$ and $B$.

First I am trying to see why the given relation is actually an equivalence relation.

I think it's obvious that $A\equiv A \text{ } \forall A\in P(\mathbb{N})$ as $$A\cup X=\mathbb{N}$$ and $$(A=)B\cup X=\mathbb{N}$$ are the same thing, so of course they are equivalent.

If $A\equiv B,$ then $B\equiv A$ as $A$ and $B$ participate symetrically in the given equivalence. So we would just swap them and get $B\cup X=\mathbb{N} \iff A\cup X=\mathbb{N}$ which gives exactly $B\equiv A$. Note that we started by assuming that $A$ and $B$ are in $\equiv$.

I am not so sure how to check if the relation is transitive though. And I also have no idea how to find the classes of equivalence. Thanks!

SAQ
  • 367
  • 3
    Is this $\equiv$ not very simply the same thing as $=$? Suppose that $A\neq B$... then there is some element contained in one that is not in the other. Without loss of generality suppose that element is called $x$ and that $x\not\in A$ while $x\in B$. Then by letting $X=\Bbb N\setminus B$ you have $B\cup X = \Bbb N$ while $A\cup X\neq \Bbb N$ as it is missing the element $x$... Therefore $A\neq B\implies A\not\equiv B$ – JMoravitz Feb 07 '24 at 17:42
  • 1
    The fact that $=$ is an equivalence relation is obvious, per the definition. – JMoravitz Feb 07 '24 at 17:43
  • @JMoravitz, a nice observation again! Thank you!!!! It is really clever, but I don't think I would ever be able to arrive at such conclusions myself. – SAQ Feb 07 '24 at 17:49
  • @JMoravitz, may I also ask you why did you say $A\cup X\ne \mathbb{N}$ as it is missing the element $x$? Okay, that's right, but it is also missing every element $b\in B$, so $x$ is just one of them, right? – SAQ Feb 07 '24 at 17:51
  • And actually the set of all classes of equivalence is not finite, right? – SAQ Feb 07 '24 at 17:54
  • There could be many elements missing in $A\cup X$ from $\Bbb N$, but there could also have only been the one element missing as well. Having not specified anything further about the relationship between $A$ and $B$ beyond that they are not equal, the only element I could directly mention was the $x$ I brought up earlier, but that was enough to prove the point. – JMoravitz Feb 07 '24 at 18:07
  • As for "the set of all classes of equivalence is not finite, right?" I don't understand that sentence. The set of all equivalence classes here for this specific equivalence relation is infinite, and each equivalence class for this specific equivalence relation happens to contain only a single element. For different equivalence relations, these might not be the case... There are equivalence relations where there are finitely many classes, as well as relations where each class has infinitely many, etc... for instance the equivalence relation "Are both finite or are both infinite" – JMoravitz Feb 07 '24 at 18:09

0 Answers0