8
$\begingroup$

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$

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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 ==. $\endgroup$
    – DavidC
    Dec 11, 2015 at 15:25
  • $\begingroup$ @DavidCarraher Mathematica does not handle Union and Intersection symbolically. $\endgroup$
    – Sjoerd C. de Vries
    Dec 11, 2015 at 19:26
  • 2
    $\begingroup$ 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. $\endgroup$
    – Carl Woll
    Mar 17, 2019 at 19:38

2 Answers 2

Reset to default
11
$\begingroup$

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;

Using BooleanMinimize:

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
    ]
]
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Only 3 (now 4) upvotes??! I don't understand. $\endgroup$
    – nilo de roock
    Aug 22, 2020 at 10:24
1
$\begingroup$

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 *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Tarun Gupta
    Dec 12, 2015 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.