The Set domain allows one to represent explicit finite sets of values. These are similar to lists, but duplicate elements are not allowed.
Sets can be created by giving a fixed set of values
s := set [x**2-1, y**2-1, z**2-1]
2 2 2
{x - 1,y - 1,z - 1}
Type: Set Polynomial Integer
or by using a collect form, just as for lists. In either case, the set is formed from a finite collection of values:
t := set [x**i - i+1 for i in 2..10 | prime? i]
2 3 5 7
{x - 1,x - 2,x - 4,x - 6}
Type: Set Polynomial Integer
The basic operations on sets are intersect, union, difference, and symmetricDifference.
i := intersect(s,t)
2
{x - 1}
Type: Set Polynomial Integer
u := union(s,t)
2 3 5 7 2 2
{x - 1,x - 2,x - 4,x - 6,y - 1,z - 1}
Type: Set Polynomial Integer
The set difference(s,t) contains those members of s which are not in t.
difference(s,t)
2 2
{y - 1,z - 1}
Type: Set Polynomial Integer
The set symmetricDifference(s,t) contains those elements which are in s or t but not in both.
symmetricDifference(s,t)
3 5 7 2 2
{x - 2,x - 4,x - 6,y - 1,z - 1}
Type: Set Polynomial Integer
Set membership is tested using the member? operation.
member?(y, s)
false
Type: Boolean
member?((y+1)*(y-1), s)
true
Type: Boolean
The subset? function determines whether one set is a subset of another.
subset?(i, s)
true
Type: Boolean
subset?(u, s)
false
Type: Boolean
When the base type is finite, the absolute complement of a set is defined. This finds the set of all multiplicative generators of PrimeField 11—the integers mod 11.
gs := set [g for i in 1..11 | primitive?(g := i::PF 11)]
{2,6,7,8}
Type: Set PrimeField 11
The following values are not generators.
complement gs
{1,3,4,5,9,10,0}
Type: Set PrimeField 11
Often the members of a set are computed individually; in addition, values can be inserted or removed from a set over the course of a computation.
There are two ways to do this:
a := set [i**2 for i in 1..5]
{1,4,9,16,25}
Type: Set PositiveInteger
One is to view a set as a data structure and to apply updating operations.
insert!(32, a)
{1,4,9,16,25,32}
Type: Set PositiveInteger
remove!(25, a)
{1,4,9,16,32}
Type: Set PositiveInteger
a
{1,4,9,16,32}
Type: Set PositiveInteger
The other way is to view a set as a mathematical entity and to create new sets from old.
b := b0 := set [i**2 for i in 1..5]
{1,4,9,16,25}
Type: Set PositiveInteger
b := union(b, {32})
{1,4,9,16,25,32}
Type: Set PositiveInteger
b := difference(b, {25})
{1,4,9,16,32}
Type: Set PositiveInteger
b0
{1,4,9,16,25}
Type: Set PositiveInteger
See Also: