Introduction ============ A *set* in Magma is a (usually unordered) collection of objects belonging to some common structure (called the *universe* of the set). There are four basic types of sets: *enumerated sets*, whose elements are all stored explicitly (with one exception, see below); *formal sets*, whose elements are stored implicitly by means of a predicate that allows for testing membership; *indexed sets*, which are restricted enumerated sets having a numbering on elements; and *multisets*, which are enumerated sets with possible repetition of elements. In particular, enumerated sets, indexed sets and multisets are always finite, and formal sets are allowed to be infinite. Enumerated Sets --------------- Enumerated sets are finite, and can be specified in three basic ways (see also section 2 below): by listing all elements; by an expression involving elements of some finite structure; and by an arithmetic progression. If an arithmetic progression is specified, the elements are not calculated explicitly until a modification of the set necessitates it; in all other cases all elements of the enumerated set are stored explicitly. Formal Sets ------------ A formal set consists of the subset of elements of some carrier set (structure) on which a certain predicate assumes the value ``true``. The only set-theoretic operations that can be performed on formal sets are union, intersection, difference and symmetric difference, and element membership testing. .. %%%DETAILS FROM AKS 28/5/96 .. %An fset F really is a structure S, with a predicate P selecting .. %a subset of S. The rule for (x in F) is: bang x into S (error if can't), .. %then return the predicate evaluated on the result. .. %The idea is that S is the "over universe" which you .. %should be able to bang into and then P is the important part of the .. %fset. If you create an fset with trivial predicate (true), that's really .. %silly! I could make it so that an fset over a setq S takes the universe .. %of S, not S itself... but then the predicate could fail when it didn't .. %think it could--the predicate can assume at the moment that its arg is in S... Indexed Sets ------------ For some purposes it is useful to be able to access elements of a set through an index map, which numbers the elements of the set. For that purpose Magma has indexed sets, on which a very few basic set operations are allowed (element membership testing) as well as some sequence-like operations (such as accessing the :math:`i`-th term, getting the index of an element, appending and pruning). Multisets --------- For some purposes it is useful to construct a set with some of its members repeated. For that purpose Magma has multisets, which take into account the repetition of members. The number of times an object :math:`x` occurs in a multiset :math:`S` is called the *multiplicity* of :math:`x` in :math:`S`. Magma has the ``^^`` operator to specify a multiplicity: the expression ``x^^ n`` means the object :math:`x` with multiplicity :math:`n`. In the following, whenever any multiset constructor or function expects an element :math:`y`, the expression ``x^^ n`` may usually be used. Compatibility ------------- The binary operators for sets do not allow mixing of the four types of sets (so one cannot take the intersection of an enumerated set and a formal set, for example), but it is easy to convert an enumerated set into a formal set --- see the section on binary operators below --- and there are functions provided for making an enumerated set out of an indexed set or a multiset (and vice versa). By the limitation on their construction formal sets can only contain elements from one structure in Magma. The elements of enumerated sets are also restricted, in the sense that either some universe must be specified upon creation, or Magma must be able to find such universe automatically. The rules for compatibility of elements and the way Magma deals with these universes are the same for sequences and sets, and are described in the previous chapter. The restrictions on indexed sets are the same as those for enumerated sets. Notation -------- Certain expressions appearing in the sections below (possibly with subscripts) have a standard interpretation: :math:`U` the universe: any Magma structure; :math:`E` the carrier set for enumerated sets: any enumerated structure (it must be possible to loop over its elements --- see the :doc:`../IntroductionToAggregates/introduction` to this Part; :math:`F` the carrier set for formal sets: any structure for which membership testing using ``in`` is defined --- see the :doc:`../IntroductionToAggregates/introduction` to this Part; :math:`x` a free variable which successively takes the elements of :math:`E` (or :math:`F` in the formal case) as its values; :math:`P` a Boolean expression that usually involves the variable(s) :math:`x`, :math:`x_1,\ldots, x_k`; :math:`e` an expression that also usually involves the variable(s) :math:`x`, :math:`x_1, \ldots, x_k`.