$\equiv$ is congruence relation in the structure. Prove that $\mathcal{F}=[X]_\equiv$ if $|\mathcal{A}/\equiv|>1$

Question

$\mathcal{A}$ is field of subsets of $X$

Prove that if $\equiv$ is congruence relation in the structure $<\mathcal{A},\emptyset,X,\cup,\cap,->$ and $|\mathcal{A}/\equiv|>1$, then $\mathcal{F}=[X]_\equiv$ is a filter in $\mathcal{A}$.

I am not sure if I understand everything correctly. If $|\mathcal{A}/\equiv|=1$, then for every $A,B\in\mathcal{A}$ we have $A\equiv B$.

So we can start by assuming that $\equiv$ is congruent relation and $\mathcal{F}$ is not a filter. Let's pick $A\in\mathcal{F}$. So for example, there exist $B\in \mathcal{A}$ such that $A\subset B$ and $B\notin\mathcal{F}$. That means that either $B\equiv A$ or $B\equiv B'\in\mathcal{F}$.
But I believe this is not going right way to the solution, so any hint would be helpful.

Answer 1

• Let $A, B \in \mathcal{F}$. Then $A \equiv X$ and $B \equiv X$, but since $\equiv$ is a congruence, we have $A \cap B \equiv X \cap X = X$, hence $A \cap B \in \mathcal{F}$.
• Let $A \subseteq B$ and $A \in \mathcal{F}$. Then $A \equiv X$ and $B \equiv B$, so $B = A \cup B \equiv X \cup B = X$, i.e. $B \in \mathcal{F}$.
• By the second property, if $\varnothing \in \mathcal{F}$, then $\mathcal{F} = \mathcal{A}$, so there would be just one equivalence relation, which is assumed to be false.

Answer 2

When you approach a new proof there are essentially two ways to go about things. The first is to assume by contradiction, and try to find where you get stuck; and the second is to try and be positive and see if you get stuck.

My general recommendation is always to start with the second approach, because it will reveal to you how you might be able to come up with a counterexample: simply analyze where you got stuck with the proof.

So, the positive proof in this case would be the simply verify the definition of a filter holds for $[X]_\equiv$.

For this you need to use the fact that $\equiv$ respects all the Boolean operations; and as you noted, if $|\cal A/{\equiv}|>1$, this means that there are two sets which are not congruent, and you can use this to deduce that $\varnothing\notin[X]_\equiv$.