Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this community
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.
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.
Solve[ Sin[x] == 1/2, x] gives {{x -> ConditionalExpression[π/6 + 2 π C[1], C[1] ∈ Integers]}, {x -> ConditionalExpression[(5 π)/6 + 2 π C[1], C[1] ∈ Integers]}}.
$\endgroup$
– Ruslan
Feb 21 '16 at 17:54
Lists can work as sets if you take care to sort them. So
setEquals[set1_List,set2_list]:= Sort[set1]==Sort[set2]
should work.
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.)
$\endgroup$
– 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.
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.
OrderedQfunction. Two distinct Mathematica expressions will always have a well defined, though possibly surprising ordering based on this built-in comparison function. Please see here. $\endgroup$ – Szabolcs May 8 '12 at 12:36Realsand 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. $\endgroup$ – Artes May 8 '12 at 23:18