In some simple cases it seems possible to solve for X a set equation.

For example, if I am given : X Inter U = U , and knowing the law according to which S Inter U = S for any set S, I can find that X = U.

But more generally,do the properties of the algebra of sets/ propositions allow us to solve equations? and to solve them in a mechanical way?

Is it possible to give an example of equation solving where one applies a rule equivalent to " do the same thing on both sides" in ordinary basic algebra.

Remark: by solving a propositional logic equation, I would mean : finding the unknown truth value of a proposition X involved in a given equivalence.


You can always do the same thing to both sides of an equation (it was discussed e.g. here) to simplify some equations.

In the case of algebras of sets or boolean algebras however you often can't get "exact" solutions because the operations $\cap, \cup$ are far from being as well-behaved as $\times$ in a group for instance : you can very easily have $a\cap b = a\cap c$ without having $b=c$. Therefore when you do the same thing to both sides of an equation, very often you'll only have "original equation implies modified equation", but not the converse (in a group, if you multiply by $y$ on both sides, then you get an equivalent equation, which may be easier to solve)

Let's look at your example : $X\cap U =U$, without the hypothesis on the $S$ you're considering. Then this implies $U\subset X$, and conversely, if $U\subset X$ then indeed $X\cap U = U$. This actually works in any boolean algebra : $x\land u = u\iff u\leq x$ : so we have an equation, and the "domain of solutions" is an upward directed set.

In your case, since $S\cap U = S$ for all $S$, this means $S\subset U$ for all $S$, i.e. you're only considering subsets of $U$, so clearly if $U\subset X$ you'll have $U=X$ and that's why in this case you can solve to get an "exact" solution, instead of an interval of solutions.

Boolean algebras are also very nice in that the language of boolean algebras can be translated to the language of certain rings, and so any boolean algebra equation can be equally well viewed as a polynomial equation in these rings; but these equations can have a whole load of solutions, especially in Boolean rings, which are very far from being integral domains. I don't know if there is a lot of algebraic geometry of boolean rings, though.


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.