5
$\begingroup$

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.

Thanks in advance !!

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – NasuSama May 28 '13 at 18:03
  • $\begingroup$ 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. $\endgroup$ – Shambo May 28 '13 at 18:06
  • 1
    $\begingroup$ 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? $\endgroup$ – Mark Bennet May 28 '13 at 18:36
  • $\begingroup$ What is the source of this problem? $\endgroup$ – Asaf Karagila♦ May 28 '13 at 19:05
  • $\begingroup$ 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). $\endgroup$ – Shambo May 28 '13 at 19:09
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ As far as I understood, you are trying to construct a Y st Y will be nonempty exactly when X is empty ? Right ? Well, you can restate the problem like this also. $\endgroup$ – Shambo May 28 '13 at 19:04
  • $\begingroup$ @Shambo, that is exactly what I believe the difficulty is. $\endgroup$ – vadim123 May 28 '13 at 19:33
  • $\begingroup$ I dont think this can be done, but can you disprove it. That is, there does not exists a formula st, if A!=B then the set corresponding to the formula is empty, if A=B then it is non-empty. $\endgroup$ – Shambo May 28 '13 at 20:55

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.