How to solve system of set-theoretic equations? Consider the next setup:
$S = \{a,b,c,d,e\}, A_1,A_2,B_1,B_2,X_1,X_2 ⊂ S$
$(A_1\setminus X_1) \cup X_2 = B_1$
$(A_2\setminus X_1) \cup X_2 = B_2$
\ is relative complement. $\{a,b\} \setminus \{a\} = \{b\} $
How to find all possible solutions for $X_1, X_2$? What is the right mathematical name for such equations?
Example:
$(\{a,b,c\}\setminus X_1) \cup X_2 = \{b,c\}$
$(\{a,b,c\} \setminus \{a\}) \cup \{c\} = \{b,c\}$
$(\{a,d,e\} \setminus \{a\}) \cup \{c\} = \{d,e,c\}$
My idea was to use equation 1 to express $X_2$ in terms $X_1$ and substitute $X_2$ in equation 2.
But I am stuck with what to do next.
$X_2 = B_1 \setminus (A_1 \setminus X_1)$
$X_1 = A_2 \setminus (B_2 \setminus (B_1 \setminus (A_1 \setminus X_1)))$
 A: Given that your universe, i.e. the number of primal elements is finite, you can recast any set operation as a boolean logical operation.
That way, you can transform any set formula over the universe into a propositional formula.
In your case $S=\{1,..,5\}$ is the universe.
Define for every set $X\subseteq X$ the binary variables $X^1$,...,$X^5$.
The idea behind these variables is that $X^i = 1\Leftrightarrow 1\in X$.
Now we create variables $\varphi_i$ with binary variables $\varphi_i^k$, k=1,...,5 for every partial formula and connect them to our original variables:
$\varphi_1 := A_1\setminus x_1$
$\varphi_1^k \Leftrightarrow A_1^k \land \lnot x_1^k$
$\varphi_2:=\varphi_1\cup x_2$
$ \varphi_2^k \Leftrightarrow \varphi_1^k\lor x_2^k$
$\varphi_3:=\varphi_2=B$
$\varphi_3^k \Leftrightarrow (\varphi_2^k\Leftrightarrow B_1^k)$
We now simplify $\varphi_3^k$ by applying the substituions $... \Leftrightarrow ...$:
$\varphi_3^k
\equiv \varphi_2^k\Leftrightarrow B_1^k 
\equiv (\varphi_1^k\lor x_2k)\Leftrightarrow B_1^k 
\equiv ((A_1^k \land \lnot x_1^k)\lor x_2^k)\Leftrightarrow B_1^k 
$
You then do the same for the other equation for another variable $\psi$.
Having done this, you'll now need to solve the propositional formula
$$
\left(\bigwedge_{k=1}^5 \varphi_3^k\right) \land \left(\bigwedge_{k=1}^5 \psi_3^k\right)  
$$
. More precisely, you're looking for a substitution of $x_1^k, x_2^k$ k=1,...,5  which makes the formula true.
You can further simplify the formula by realizing that  $\left(\bigwedge_{k=1}^5 \varphi_3^k\right) \land \left(\bigwedge_{k=1}^5 \psi_3^k\right) $ can be decomposed into 5 independent formulas $\varphi_3^k\land \psi_3^k$ for $k=1,...,5$:
(This should always be the case, no matter the formula, so as partial general result we obtain, that the size of our universe $S$ doesn't matter)
$$
\varphi_3^k\land \psi_3^k \equiv (((A_1^k \land \lnot x_1^k)\lor x_2^k)\Leftrightarrow B_1^k) \land (((A_2^k \land \lnot x_1^k)\lor x_2^k)\Leftrightarrow B_2^k ) 
$$
(From now on, I'll drop the exponent $k$, to save me some writing)
Rewriting this into DNF gives you the full solution, however it does so as case function. The DNF is:
$$
\begin{aligned}
&(¬ x_2 ∧ ¬ x_1 ∧ ¬ A_1 ∧ A_2 ∧ ¬ B_1 ∧ B_2) 
\\ &∨(¬ x_2 ∧ ¬ x_1 ∧ A_1 ∧ ¬ A_2 ∧ B_1 ∧ ¬ B_2) 
\\&∨ (¬ x_2 ∧ ¬ A_1 ∧ ¬ A_2 ∧ ¬ B_1 ∧ ¬ B_2) 
\\&∨ (¬ x_2 ∧ x_1 ∧ ¬ A_1 ∧ ¬ B_1 ∧ ¬ B_2)
\\ &∨ (¬ x_2 ∧ x_1 ∧ ¬ B_1 ∧ ¬ B_2)
\\ &∨ (x_2 ∧ ¬ x_1 ∧ A_1 ∧ B_1 ∧ B_2)
\\ &∨ (x_2 ∧ B_1 ∧ B_2)
\\ &∨ (¬ x_1 ∧ A_1 ∧ A_2 ∧ B_1 ∧ B_2)
\end{aligned}$$
For example the disjunction $¬ x_2 ∧ ¬ x_1 ∧ ¬ A_1 ∧ A_2 ∧ ¬ B_1 ∧ B_2$ gives you the case, that when $A_1=0, A_2=1, B_=0, B_2=1$ we have $x_1=0, x_2=0$.
We can "unclausify" this as follows:

*

*Fix $i\in\{1,2\}$.

*Delete all clauses without $x_i$.

*Delete $x_1,x_2, \lnot x_1, \lnot x_2$ from all clauses.

The resulting formula now describes $x_i$, and replacing the logical operators by the corresponding set operators gives you the set formula for $x_i$ that is maximally true, i.e. it only doesn't hold, if for the partial evaluation of $A_1,A_2,B_1,B_2$ no possible assignments of $X_1,X_2$ makes the formula true.
Finally, you should test whether the formula is a tautology (by checking if the negated formula is satisfiable).
The only problem with this solution is that in general, the solution size is exponential in the number of variables.
In return however, you can always find a solution using this method.

For example, with the DNF given above, we obtain
$x_2=( A_1 ∧ B_1 ∧ B_2) ∨ ( B_1 ∧ B_2) = B_1 ∧ B_2$
$x_1=(¬ A_1 ∧ ¬ B_1 ∧ ¬ B_2) ∨ (¬ B_1 ∧ ¬ B_2) = ¬ B_1 ∧ ¬ B_2 $
Substituting $x_1,x_2$ in the formula $(((A_1 \land \lnot x_1)\lor x_2)\Leftrightarrow B_1) \land (((A_2 \land \lnot x_1)\lor x_2)\Leftrightarrow B_2 ) $, and testing whether
$$ \lnot \bigg((((A_1 \land \lnot x_1)\lor x_2)\Leftrightarrow B_1) \land (((A_2 \land \lnot x_1)\lor x_2)\Leftrightarrow B_2 ) \bigg)$$
is satisfiable, gives us that e.g. $B_2=A_1=0 \land B_1=1$ satisfies above formula.
From this we can construct a counter example for our original set equation:
Let $S = \{a\}, A_1,A_2,B_1,B_2,X_1,X_2 ⊂ S$
and
$B_2=A_1=\emptyset$, $B_1=\{a\}$.
Then we have
$(\emptyset\setminus X_1) \cup X_2 = B_1 \rightarrow X_2=B_1 \rightarrow X_2=\{a\}$
$(A_2\setminus X_1) \cup X_2 = \emptyset\rightarrow X_2=\emptyset$
