# 28 Sets

A very important mathematical concept, maybe the most important of all, are sets. Mathematically a set is an abstract object such that each object is either an element of the set or it is not. So a set is a collection like a list, and in fact GAP uses lists to represent sets. Note that this of course implies that GAP only deals with finite sets.

Unlike a list a set must not contain an element several times. It simply makes no sense to say that an object is twice an element of a set, because an object is either an element of a set, or it is not. Therefore the list that is used to represent a set has no duplicates, that is, no two elements of such a list are equal.

Also unlike a list a set does not impose any ordering on the elements. Again it simply makes no sense to say that an object is the first or second etc. element of a set, because, again, an object is either an element of a set, or it is not. Since ordering is not defined for a set we can put the elements in any order into the list used to represent the set. We put the elements sorted into the list, because this ordering is very practical. For example if we convert a list into a set we have to remove duplicates, which is very easy to do after we have sorted the list, since then equal elements will be next to each other.

In short sets are represented by sorted lists without holes and duplicates in GAP. Such a list is in this document called a proper set. Note that we guarantee this representation, so you may make use of the fact that a set is represented by a sorted list in your functions.

In some contexts (for example see Combinatorics), we also want to talk about multisets. A multiset is like a set, except that an element may appear several times in a multiset. Such multisets are represented by sorted lists with holes that may have duplicates.

The first section in this chapter describes the functions to test if an object is a set and to convert objects to sets (see IsSet and Set).

The next section describes the function that tests if two sets are equal (see IsEqualSet).

The next sections describe the destructive functions that compute the standard set operations for sets (see AddSet, RemoveSet, UniteSet, IntersectSet, and SubtractSet).

The last section tells you more about sets and their internal representation (see More about Sets).

All set theoretic functions, especially `Intersection` and `Union`, also accept sets as arguments. Thus all functions described in chapter Domains are applicable to sets (see Set Functions for Sets).

Since sets are just a special case of lists, all the operations and functions for lists, especially the membership test (see In), can be used for sets just as well (see Lists).

Previous Up Next
Index

GAP 3.4.4
April 1997