# How can I define operators that implement the algebra of sets?

I need to define some operators with properties like idempotence and distribution over union and intersection so that Mathematica can symbolically simplify expressions. How do I define such operators?

For example, I want to define $⋃$ and $⋂$ such that

$\qquad (A ⋂ B) ⋃ B = B$

for all $A$ and $B$ and, whenever $A ⊂ B$, then

$\qquad A ⋂ B = A {\rm \ and\ } A⋃ B = B$

• Doesn't Mathematica automatically simplify logic expressions? In this case Union[Intersection[a,b],b] should be automatically be simplified to b if a, b are sets. By the way, = is the assignment operator, Set; Equal is ==. Commented Dec 11, 2015 at 15:25
• @DavidCarraher Mathematica does not handle Union and Intersection symbolically. Commented Dec 11, 2015 at 19:26
• I think the question is pretty clear, how does one implement Union/Intersection etc capability for symbolic sets. I have an idea on how to do this, and would like to provide an answer to the question. Commented Mar 17, 2019 at 19:38

Here is one idea. Convert the set expression into an equivalent boolean expression, use BooleanMinimize to simplify the boolean expression, and then convert back to a set expression.

Set expression

Rather than using Union and Intersection, I will use the built-in symbols SquareUnion and SquareIntersection so that I don't have to modify Union and Intersection to work with atomic symbols. So, here are the symbols I will be allowing for set expressions:

I added the symbols EmptySet and UniversalSet, similar to how Reals, Integers, etc. are handled. I also need to add formatting for these symbols:

MakeBoxes[EmptySet, StandardForm] ^= TemplateBox[
{},
"EmptySet",
DisplayFunction -> ("\[EmptySet]"&),
InterpretationFunction -> ("EmptySet"&)
];
MakeBoxes[UniversalSet, StandardForm] ^= TemplateBox[
{},
"UniversalSet",
DisplayFunction -> (StyleBox["\[DoubleStruckCapitalU]", FontFamily->"Times"]&),
InterpretationFunction -> ("UniversalSet"&)
];


It is convenient to add some input aliases:

CurrentValue[EvaluationNotebook[], InputAliases] = {
"su" -> "⊔",
"si" -> "⊓",
"sb" -> "⊏",
"sp" -> "⊐",
"es" -> TemplateBox[
{},
"EmptySet",
DisplayFunction -> ("\[EmptySet]"&),
InterpretationFunction -> ("EmptySet"&)
],
"us" -> TemplateBox[
{},
"UniversalSet",
DisplayFunction -> (StyleBox["\[DoubleStruckCapitalU]", FontFamily->"Times"]&),
InterpretationFunction -> ("UniversalSet"&)
]
};


Conversion to Boolean expression

This part is pretty simple. The Boolean equivalents are:

• union: $$A \sqcup B \Longleftrightarrow$$Or[A, B]
• intersection: $$A \sqcap B \Longleftrightarrow$$ And[A, B]
• subset: $$A \sqsubset B \Longleftrightarrow$$ Implies[A, B]
• superset: $$A \sqsupset B \Longleftrightarrow$$ Implies[B, A]
• set difference: $$A\backslash B \Longleftrightarrow$$And[A, Not[B]]
• set complement: $$\bar{A} \Longleftrightarrow$$Not[A]
• set equivalence: $$A = B \Longleftrightarrow$$Equivalent[A, B]
• empty set: $$\emptyset \Longleftrightarrow$$False
• universal set: $$\mathbb{U} \Longleftrightarrow$$True

So, the following function will convert our set expressions into equivalent Boolean expressions:

toBoolean[expr_] := ReplaceAll[
expr,
{
SquareUnion -> Or,
SquareIntersection -> And,
SquareSubset -> Implies,
SquareSuperset -> Reverse @* Implies,
Backslash -> (And[#1, !#2]&),
OverBar -> Not,
Equal -> Equivalent,
EmptySet -> False,
UniversalSet -> True
}
]


Boolean minimization

The function I will use to "simplify" boolean expressions is BooleanMinimize. For a nontrivial example, consider the first set expression in the OP:

set = A ⊓ B ⊔ B;


The equivalent Boolean expression is:

toBoolean[set]


(A && B) || B

Using BooleanMinimize on this expression:

BooleanMinimize[toBoolean[set]]


B

as expected.

BooleanMinimize accepts a 2-arg version where the second argument is a condition. We can use this for the second set expression in the OP:

set = A ⊓ B;
cond = A ⊏ B;

BooleanMinimize[toBoolean[set], toBoolean[cond]]


A

as expected.

Conversion back to set expression

Conversions back to a set expression is basically just the reverse of the conversions from a set expression, except that in some cases, the set expression actually represents a predicate. This means that sometimes False and True should be converted to EmptySet and UniversalSet, and sometimes (when the set expression represents a predicate) it should be left alone. Also, it would be convenient to convert Boolean expressions representing subset and set difference expressions to the standard set expressions for them.

First, I will define a setQ expression that determines whether a set expression represents a set or a predicate:

setQ[EmptySet] = True;
setQ[UniversalSet] = True;
setQ[_Symbol] = True;

setQ[(Backslash | SquareUnion | SquareIntersection | OverBar)[a__]] := AllTrue[{a}, setQ]

setQ[_] = False;


Examples:

setQ[A ⊔ B]
setQ[A ⊏ B]
setQ[A == B]


True

False

False

Next, I will define a fromBoolean function:

fromBoolean[expr_] := ReplaceAll[
expr,
{
Or -> SquareUnion,
And -> SquareIntersection,
Not -> OverBar,
Equivalent -> Equal
}
]
fromBoolean[a_ && !b_Symbol] := Backslash[a, b]
fromBoolean[!a_Symbol && b_] := Backslash[b, a]
fromBoolean[a_ || !b_Symbol] := SquareSubset[b, a]
fromBoolean[!a_Symbol || b_] := SquareSubset[a, b]


SetSimplify

Now, we are ready to create a SetSimplify function for symbolic sets:

Options[SetSimplify] = {Method -> Automatic};

SetSimplify[set_, cond_:True, OptionsPattern[]] := Module[{res},
res = fromBoolean @ BooleanMinimize[
toBoolean[set],
toBoolean[cond],
Method->OptionValue[Method]
];
If[setQ[set],
res /. {False -> EmptySet, True -> UniversalSet},
res
]
]


The OP examples:

SetSimplify[(A ⊓ B) ⊔ B]
SetSimplify[A ⊓ B == A, A ⊏ B]
SetSimplify[A ⊔ B == B, A ⊏ B]


B

True

True

A few other examples taken from Wikipedia:

An identity law

set = A ⊓ UniversalSet;
set //TeXForm


$$A\sqcap \mathbb{U}$$

SetSimplify[set]


A

A complement law

set = A ⊔ OverBar[A];
set //TeXForm


$$A\sqcup \bar{A}$$

SetSimplify[set] //TeXForm


$$\mathbb{U}$$

Idempotent laws

SetSimplify[A ⊔ A]
SetSimplify[A ⊓ A]


A

A

Absorption laws

SetSimplify[A ⊔ (A ⊓ B)]
SetSimplify[A ⊓ (A ⊔ B)]


A

A

*One of De Morgan's laws:

law = OverBar[A ⊔ B] == OverBar[A] ⊓ OverBar[B];
law //TeXForm


$$\overline{A\sqcup B}=\bar{A}\sqcap \bar{B}$$

SetSimplify[law]


True

A complement law

set = OverBar[EmptySet];
set //TeXForm


$$\overline{\emptyset }$$

SetSimplify[set] //TeXForm


$$\mathbb{U}$$

Reflexivity

SetSimplify[A ⊏ A]


True

Antisymmetry

SetSimplify[A == B, A ⊏ B && B ⊏ A]


True

Transitivity

SetSimplify[A ⊏ C, A ⊏ B && B ⊏ C]


True

Joins

SetSimplify[A ⊏ A ⊔ B]
SetSimplify[A ⊔ B ⊏ C, A ⊏ C && B ⊏ C]


True

True

Meets

SetSimplify[A ⊓ B ⊏ A]
SetSimplify[C ⊏ A ⊓ B, C ⊏ A && C ⊏ B]


True

True

And a few others:

SetSimplify[A ⊓ B == A, A ⊔ B == B]


True

SetSimplify[A ∖ B, A ⊏ B] //TeXForm


$$\emptyset$$

SetSimplify[A ∖ A] //TeXForm


$$\emptyset$$

set = UniversalSet ∖ A;
set //TeXForm


$$\mathbb{U}\backslash A$$

SetSimplify[set] //TeXForm


$$\bar{A}$$

Finally, here is everything in one code block:

MakeBoxes[EmptySet, form_] ^= TemplateBox[
{},
"EmptySet",
DisplayFunction -> ("\[EmptySet]"&),
InterpretationFunction -> ("EmptySet"&)
];
MakeBoxes[UniversalSet, form_] ^= TemplateBox[
{},
"UniversalSet",
DisplayFunction -> (StyleBox["\[DoubleStruckCapitalU]", FontFamily->"Times"]&),
InterpretationFunction -> ("UniversalSet"&)
];

CurrentValue[EvaluationNotebook[], InputAliases] = {
"su" -> "⊔",
"si" -> "⊓",
"sb" -> "⊏",
"sp" -> "⊐",
"es" -> TemplateBox[
{},
"EmptySet",
DisplayFunction -> ("\[EmptySet]"&),
InterpretationFunction -> ("EmptySet"&)
],
"us" -> TemplateBox[
{},
"UniversalSet",
DisplayFunction -> (StyleBox["\[DoubleStruckCapitalU]", FontFamily->"Times"]&),
InterpretationFunction -> ("UniversalSet"&)
]
};

toBoolean[expr_] := ReplaceAll[
expr,
{
SquareUnion -> Or,
SquareIntersection -> And,
SquareSubset -> Implies,
SquareSuperset -> Reverse @* Implies,
OverBar -> Not,
Backslash -> (And[#1, !#2]&),
Equal -> Equivalent,
EmptySet -> False,
UniversalSet -> True
}
]

setQ[EmptySet] = True;
setQ[UniversalSet] = True;
setQ[_Symbol] = True;

setQ[(Backslash | SquareUnion | SquareIntersection | OverBar)[a__]] := AllTrue[{a}, setQ]

setQ[_] = False;

fromBoolean[expr_] := ReplaceAll[
expr,
{
Or -> SquareUnion,
And -> SquareIntersection,
Not -> OverBar,
Equivalent -> Equal
}
]
fromBoolean[a_ && !b_Symbol] := Backslash[a, b]
fromBoolean[!a_Symbol && b_] := Backslash[b, a]
fromBoolean[a_ || !b_Symbol] := SquareSubset[b, a]
fromBoolean[!a_Symbol || b_] := SquareSubset[a, b]

Options[SetSimplify] = {Method -> Automatic};

SetSimplify[set_, cond_:True, OptionsPattern[]] := Module[{res},
res = fromBoolean @ BooleanMinimize[
toBoolean[set],
toBoolean[cond],
Method->OptionValue[Method]
];
If[setQ[set],
res /. {False -> EmptySet, True -> UniversalSet},
res
]
]

• Only 3 (now 4) upvotes??! I don't understand. Commented Aug 22, 2020 at 10:24

If I understand your question correctly, we can build our own set framework. (If this is not want you want, I'll delete this post.)

First define a set as an orderless collection of elements.

SetAttributes[set, {Flat, Orderless}]

set[args___] := Block[{union},
union = Union[{args}];
(
set @@ union
) /; Length[union] != Length[{args}]
]


Now define operations on sets... There are more we could define here too

set /: Union[s___set] := set[s]
set /: Element[e_, s_set] := MemberQ[s, e]
set /: Subset[s___set] := VectorQ[Partition[Reverse[{s}], 2, 1], SubsetQ @@ # &]
cardinality[s_set] := Length[s]
cardinality[_] = 0;


And custom formatting

set /: MakeBoxes[s : set[args__], fmt_] :=
MakeBoxes[Interpretation[〈args〉, s], fmt]

set /: MakeBoxes[set[], fmt_] := MakeBoxes[Interpretation["∅", set[]], fmt]


Now test

set[1, 1, 2, 2, 1, 3]
(* 〈1, 2, 3〉 *)

set[1, 2, 3] ⋃ set[3, 4, 5] ⋃ set[4, 5, 6]
(* 〈1, 2, 3, 4, 5, 6〉 *)

set[1, 2, 3] ⋂ set[3, 4, 5]
(* 〈3〉 *)

set[1, 2, 3] ⋂ set[4, 5, 6]
(* ∅ *)

set[1, 2, 3] ⋂ set[3, 4, 5] ⋃ set[4, 8]
(* 〈3, 4, 8〉 *)

5 ∈ set[1, 2, 3, 4, 5]
(* True *)

set[1, 2, 3] ⊂ set[1, 2, 3, 4] ⊂ set[1, 2, 3, 4, 5]
(* True *)

cardinality[set[1, 2, 3, 4, 5]]
(* 5 *)

• Thank you for this answer. But i want to know that how I can declare that (A[Intersecton]B)[Union] B =B for every A and B. Where A and B are general sets. Commented Dec 12, 2015 at 3:46