# Equality of Sets

I have three sets say A,B,C and a procedure only to check if a set S is nonempty ( I cannot negate the answer of the procedure to say that the set S is empty). Now using this procedure, how can I check if the three sets are equal i.e. I want a formula which will denote a nonempty-set exactly when the three sets are equal.

• If you want to show that all of those sets are equal, then you need to have an element in all of these sets. First, pick an element from, say, set $A$. Then, show that it also belongs to set $B$ and $C$. You will need to probably break up into cases. Otherwise, don't bother with this. – NasuSama May 28 '13 at 18:03
• I am avoiding the task of enumerating the elements. Or in other words, I am trying to stick to only boolean operators, avoiding the forall quantifier. – Shambo May 28 '13 at 18:06
• I think you have a problem if $A, B, C$ are empty - are you allowed to create the set {A} - how else will you create your non-empty set? – Mark Bennet May 28 '13 at 18:36
• What is the source of this problem? – Asaf Karagila May 28 '13 at 19:05
• I want to use a SAT/SMT solver to come-up with three variables x1, x2, x3, st formula1(x1,y) iff formula2(x2,y) iff formula3(x3,y). – Shambo May 28 '13 at 19:09

Incomplete: $$X=(A\setminus B)\cup (B\setminus A)\cup (A\setminus C)\cup (C\setminus A)\cup (B\setminus C)\cup (C\setminus B)$$
This is empty if $A=B=C$, and nonempty otherwise. Unfortunately, you want the opposite.
After a bit of thought, I'm no closer to an answer. I think the $A,B,C$ is somewhat misleading in this question. The real problem is this:
Given set $X\subseteq U$, for some universe $U$, and some function $S:\mathcal{P}(U)\rightarrow \{0,1\}$ where $S(X)=\begin{cases} 1 & X=\emptyset\\ 0 & \textrm{ otherwise}\end{cases}$, how can we find set $Y\subseteq U$ such that $S(Y)=1-S(X)$, using only certain specified binary set theoretic operations like $\cup, \cap$.