# Define a mathematical set

I have a terribly short question:

Is there a way to define a pure mathematical set?

I tried a bit of googling, but the word "set" has two meanings and the other one (as in setting) as by far more dominant and I couldn't find any reference to mathematical sets in Mathematica.

As for the application, I would like to be able to define two sets A, B and test whether the two sets are the same or not, namely have the same elements.

-
There is no set data structure in Mathematica, but there are functions that treat lists as sets: they sort them and remove duplicates. –  Szabolcs May 8 '12 at 12:14
What happens is sorting is not possible? For example when the set's members are real valued functions? –  Dror May 8 '12 at 12:32
Sorting is always possible. Sorting is not by numerical value, but using the OrderedQ function. Two distinct Mathematica expressions will always have a well defined, though possibly surprising ordering based on this built-in comparison function. Please see here. –  Szabolcs May 8 '12 at 12:36
@Dror Infinite sets are represented symbolically e.g. Reals and it concerns also numbers or solutions of equations. You can of course make some mapping to enumerate functions, but only countable sets of functions (e.g. series of functions), uncountable ones are basically impossible to enumarate. See my answer for more details and some useful links. –  Artes May 8 '12 at 23:18

Perhaps the following

SetAttributes[set, Orderless];

set[elms___] :=
With[{nodups = DeleteDuplicates@{elms}},
set @@ nodups /; {elms} =!= nodups]


So set[a, b, c, d] would represent a set with elements a, b, c, and d. To compare, just use == or ===. It automatically sorts and removes duplicates

s1 = set[a, b, c, d];
s2 = set["o", b, a, aa, dd];

s1 == set[b, b, d, a, c]


True

It seems like built-ins Intersection, Union, and Complement work also with any head so you could use them naturally with set (However, they probably sort first, not taking advantage of the fact that your sets are already sorted.)

Intersection[s1, s2]


set[a, b]

Union[s1, s2]


set["o", a, aa, b, c, d, dd]

Complement[set[a, b, c, d, e], s1]


set[e]

If you ever need to convert to lists, just do List@@s1

-

In a strict meaning the answer is no.

A mathematical concept of a set is so basic and general, that one even cannot imagine most of sets and the more it concerns the possibility of their computer representations. For some hints of surprising properties of infinite sets see e.g. Continuum Hypothesis or Gödel's theorem. If you relate your question to finite sets then the answer is certainly yes.

There is only some kind of resemblance between finite sets and Mathematica lists.

Of course we can represent sets as lists (see e.g. Lists as Sets), but some adequate functions treats them not quite like pure sets (i.e. completely orderless), but rather like lists (i.e. with ordering) :

A = {1, 2, 6, 7, 3};
B = {1, 3, 2, 7, 6};
{A === B, Sort[A] === Sort[B]}

{False, True}


I suggest to take a closer look at these functionalities : Union, Intersection, Complement, Subsets etc. being Mathematica counterparts of the basic set theory operations. Intersection gives a sorted list of the common elements, while Union[A] gives a sorted version of a "set" A, moreover it can be used with an option SameTest. These functions work with finite sets, so in principle they cannot be equivalent to mathematical concepts of the set theory.

We can use this to test wether given two "sets" are identical :

Intersection[A, B] === Sort[A] === Sort[B]

True


Representation of infinte sets is a bit more difficult and of course we cannot represent infinite sets as lists, e.g. solving an equation with an infinite number of solutions we get an output in the boolean form :

Reduce[ Sin[x] == 1/2, x]


while Solve returning solutions as a list of rules :

Solve[ Sin[x] == 1/2, x]


yields only one solution with a message saying that some solutions may not be found.

Therefore the above difference is quite analogical to symbolic representation of $\pi$ and its decimal expansion - there is an infinite number of digits to represent but we can process only finite number of them.

So to define symbolically a set of functions you have to decide what kind of set it is. A series of functions can be defined (or enumerated) by natural numbers, but elements of uncountable sets cannot be ennumerated, and you should know that spaces of functions (Hilbert, Banach, etc. ) are uncountable. See e.g. Cantor's theorem

A true challenge would be some kind of representation of unmeasurable sets. See e.g. Banach-Tarski theorem and its constructive toy counterpart by Stan Wagon.

-
This is generally not correct if you define a set as a list in which the elements may be unordered. You have to sort first. See my answer. –  Sjoerd C. de Vries May 8 '12 at 12:17
@SjoerdC.deVries Yes, I agree and added some further clarification of the issue. –  Artes May 8 '12 at 12:20

Lists can work as sets if you take care to sort them. So

setEquals[set1_List,set2_list]:= Sort[set1]==Sort[set2]


should work.

-
Better to use Block[{Internal$SameQTolerance = -Infinity}, Sort[set1] === Sort[set2]]. Otherwise, the sets s1 = {1., 1.} and s2 = {1., 1. +$MachineEpsilon} are considered equal, which in fact they're not. (Also, Equal doesn't always evaluate to True or False.) –  Oleksandr R. May 9 '12 at 1:36

If you prefer to keep the operations on your sets constrained to only Mathematica's set functions you can use the following:

Union[A]===Union[B]


As the Union` function gives a sorted version of its input with duplicates removed.

-
Some types of sets (multisets) may have duplicate members. –  Sjoerd C. de Vries May 8 '12 at 13:59
@SjoerdC.deVries: Multisets are not sets in the mathematical sense of the word (as defined by set theory). –  celtschk May 8 '12 at 14:33
@celtschk Multisets are a generalization of the notion of a set. –  Sjoerd C. de Vries May 8 '12 at 15:35
@SjoerdC.deVries: The key word is generalization. While a set is a multiset, a general multiset is not a set (and in particular those multisets which contain duplicate members aren't). –  celtschk May 8 '12 at 15:56
What the OP wanted was a pure mathematical set, and this means there are NO DUPLICATES. Sets are the most basic mathematical structure. –  Artes May 8 '12 at 20:24

You could use the Set data structure that JVMTools provides. You can use any arbitrary M expression with this. It uses Java, and the formal definition of a set in Java is:

Sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.

JVMTools provides several very useful datastructures, such as deques, queues, stacks, sets, bimaps, multimaps, and multisets. You can use any arbitrary M expression with them (for example a Graphics3D object or a database connection), but if you consistently use primitives of the same type (Integer, Real, String, ...) performance will increase dramatically.

Disclosure: JVMTools is a commercial product sold by Lauschke Consulting, and I am the owner of Lauschke Consulting.

-