Restriction on sets and sequences ================================= Here we will explain the subtleties behind the mechanism dealing with sets and sequences and their universes and parents. Although the same principles apply to their formal counterparts, we will only talk about enumerated sets and sequences here, for two reasons: the enumerated versions are much more useful and common, and the very restricted number of operations on formal sets/sequences make issues of universe and overstructure of less importance for them. In principle, every object :math:`e` in Magma has some parent structure :math:`S` such that :math:`e\in S`; this structure can be used for type checking (are we allowed to apply function :math:`f` to :math:`e`?), algorithm look-up, etc. To avoid storing the structure with every element of a set or sequence and having to look up the structure of every element separately, only elements of a *common structure* are allowed in sets or sequences, and that common parent will only be stored once. Universe of a Set or Sequence ------------------------------ This common structure is called the *universe* of the set or sequence. In the general constructors it may be specified up front to make clear what the universe for the set or sequence will be; the difference between the sets :math:`i` and :math:`s` in .. code-block:: magma i := { IntegerRing() | 1, 2, 3 }; s := { RationalField() | 1, 2, 3 }; lies entirely in their universes. The specification of the universe may be omitted if there is an obvious common overstructure for the elements. Thus the following provides a shorter way to create the set containing :math:`1`, :math:`2`, :math:`3` and having the ring of integers as universe: .. code-block:: magma i := { 1, 2, 3 }; Only empty sets and sequences that have been obtained directly from the constructions .. code-block:: magma S := { }; T := [ ]; do not have their universe defined -- we will call them the *null* set or sequence. (There are two other ways in which empty sets and sequences arise: it is possible to create empty sets and sequences with a prescribed universe, using .. code-block:: magma S := { U | }; T := [ U | ]; and it may happen that a non-empty set/sequence becomes empty in the course of a computation. In both cases these empty objects have their universe defined and will not be *null*.) Usually (but not always; the exception will be explained below) the universe of a set or sequence is the parent for all its elements; thus the ring of integers is the parent of :math:`2` in the set :math:`i = \{1, 2, 3\}`, rather than that set itself. The universe is not static, and it is not necessarily the same structure as the parent of the elements *before* they were put in the set or sequence. To illustrate this point, suppose that we try to create a set containing integers and rational numbers, say :math:`T = \{ 1, 2, 1/3 \}`; then we run into trouble with the rule that the universe must be common for all elements in :math:`T`. The way this problem is solved in Magma is by automatic coercion: The obvious universe for :math:`T` is the field of rational numbers of which :math:`1/3` is already an element and into which any integer can be coerced in a natural way. Hence the assignment .. code-block:: magma T := { 1, 2, 1/3 } will result in a set with universe the field of rationals (which is also present when Magma is started up). Consequently, when we take the element :math:`1` of the set :math:`T`, it will have the rational field as its parent rather than the integer ring! It will now be clear that .. code-block:: magma s := { 1/1, 2, 3 }; is a shorter way to specify the set of rational numbers :math:`1`, :math:`2`, :math:`3` than the way we saw before, but in general it is preferable to declare the universe beforehand using the ``{ U | }`` notation. Of course .. code-block:: magma T := { Integers() | 1, 2, 1/3 } would result in an error because :math:`1/3` cannot be coerced into the ring of integers. So, usually not every element of a given structure can be coerced into another structure, and even if it can, it will not always be done automatically. The possible (automatic) coercions are listed in the descriptions of the various Magma modules. For instance, the table in the introductory chapter on rings shows that integers can be coerced automatically into the rational field. In general, every Magma structure is valid as a universe. This includes enumerated sets and sequences themselves; that is, it is possible to define a set or sequence whose elements are confined to be elements of a given set or sequence. So, for example, .. code-block:: magma S := [ [ 1..10 ] | x^2+x+1 : x in { -3 .. 2 by 1 } ]; produces the sequence :math:`[ 7, 3, 1, 1, 3, 7 ]` of values of the polynomial :math:`x^2+x+1` for :math:`x\in\mathbb{Z}` with :math:`-3\leq x\leq 2`. However, an entry of :math:`S` will in fact have the ring of integers as its parent (and *not* the sequence :math:`[ 1..10 ]`), because the effect of the above assignment is that the values after the :math:`|` are calculated and coerced into the universe, which is :math:`[ 1..10 ]`; but coercing an element into a sequence or set means that it will in fact be coerced into the *universe* of that sequence/set, in this case the integers. So the main difference between the above assignment and .. code-block:: magma T := [ Integers() | x^2+x+1 : x in { -3 .. 2 by 1} ]; is that in the first case it is checked that the resulting values :math:`y` satisfy :math:`1\leq y\leq 10`, and an error would occur if this is violated: .. code-block:: magma S := [ [ 1..10 ] | x^2+x+1 : x in { -3 .. 3 by 1} ]; leads to a run-time error. In general then, the parent of an element of a set or sequence will be the universe of the set or sequence, unless that universe is itself a set or sequence, in which case the parent will be the universe of this universe, and so on, until a non-set or sequence is encountered. Modifying the Universe of a Set or Sequence ------------------------------------------- Once a (non-null) set or sequence :math:`S` has been created, the universe has been defined. If one attempts to *modify* :math:`S` (that is, to add elements, change entries etc. using a procedure that will not reassign the result to a new set or # sequence), the universe will not be changed, and the modification will only be successful if the new element can be coerced into the current universe. Thus, .. code-block:: magma Z := Integers(); T := [ Z | 1, 2, 3/3 ]; T[2] := 3/4; will result in an error, because :math:`3/4` cannot be coerced into :math:`Z`. The universe of a set or sequence :math:`S` can be explicitly modified by creating a *parent* for :math:`S` with the desired universe and using the ``!`` operator for the coercion; as we will see in the next subsection, such a parent can be created using the ``PowerSet`` and ``PowerSequence`` commands. Thus, for example, the set :math:`\{ 1, 2\}` can be made into a set of rationals as follows: .. code-block:: magma I := { 1, 2 }; P := PowerSet( RationalField() ); J := P ! I; The coercion will be successful if every element of the sequence can be coerced into the new universe, and it is *not* necessary that the old universe could be coerced completely into the new one: the set :math:`\{ 3/3 \}` of rationals can be coerced into ``PowerSet(Integers())``. As a consequence, the empty set (or sequence) with any universe can be coerced into the power set (power sequence) of any other universe. Binary functions on sets or sequences (like ``join`` or ``cat``) can only be applied to sets and sequences that are *compatible*: the operation on :math:`S` with universe :math:`A` and :math:`T` with universe :math:`B` can only be performed if a common universe :math:`C` can be found such that the elements of :math:`S` and :math:`T` are all elements of :math:`C`. The compatibility conditions are dependent on the particular Magma module to which :math:`A` and :math:`B` belong (we refer to the corresponding chapters of this manual for further information) and do also apply to elements of :math:`a\in A` and :math:`b\in B` --- that is, the compatibility conditions for :math:`S` and :math:`T` are the same as the ones that determine whether binary operations on :math:`a\in A` and :math:`b\in B` are allowed. For example, we are able to join a set of integers and a set of rationals: .. code-block:: magma T := { 1, 2 } join { 1/3 }; for the same reason that we can do .. code-block:: magma c := 1 + 1/3; (automatic coercion for rings). The resulting set :math:`T` will have the rationals as universe. The basic rules for compatibility of two sets or sequences are then: (#) every set/sequence is compatible with the null set/sequence (which has no universe defined (see above)); (#) two sets/sequences with the same universe are compatible; (#) a set/sequence :math:`S` with universe :math:`A` is compatible with set/sequence :math:`T` with universe :math:`B` if the elements of :math:`A` can be automatically coerced into :math:`B`, or vice versa; (#) more generally, a set/sequence :math:`S` with universe :math:`A` is also compatible with set/sequence :math:`T` with universe :math:`B` if Magma can automatically find an *over-structure* for the parents :math:`A` and :math:`B` (see below); (#) nested sets and sequences are compatible only when they are of the same 'depth' and 'type' (that is, sets and sequences appear in exactly the same recursive order in both) and the universes are compatible. The possibility of finding an overstructure :math:`C` for the universe :math:`A` and :math:`B` of sets or sequences :math:`S` and :math:`T` (such that :math:`A\subset C\supset B`), is again module-dependent. We refer the reader for details to the Introductions of Parts III--VI, and we give some examples here; the next subsection contains the rules for parents of sets and sequences. Perhaps the most common example of universes that are *not* compatible would be a prime finite field with the rationals, as not *every* rational can be coerced into the finite field, while Magma does not allow coercion from finite fields into the rationals in any event. Parents of Sets and Sequences ----------------------------- The universe of a set or sequence :math:`S` is the common parent for all its elements; but :math:`S` itself is a Magma object as well, so it should have a parent too. The parent of a set is a *power set*: the set of all subsets of the universe of :math:`S`. It can be created using the ``PowerSet`` function. Similarly, ``PowerSequence(A)`` creates the parent structure for a sequence of elements from the structure :math:`A` -- that is, the elements of ``PowerSequence(A)`` are all sequences of elements of :math:`A`. The rules for finding a common overstructure for structures :math:`A` and :math:`B`, where either :math:`A` or :math:`B` is a set/sequence or the parent of a set/sequence, are as follows. (If neither :math:`A` nor :math:`B` is a set, sequence, or its parent we refer to the Part of this manual describing the operations on :math:`A` and :math:`B`.) 1. The overstructure of :math:`A` and :math:`B` is the same as that of :math:`B` and :math:`A`. 2. If :math:`A` is the null set or sequence (empty, and no universe specified) the overstructure of :math:`A` and :math:`B` is :math:`B`. 3. If :math:`A` is a set or sequence with universe :math:`U`, the overstructure of :math:`A` and :math:`B` is the overstructure of :math:`U` and :math:`B`; in particular, the overstructure of :math:`A` and :math:`A` will be the universe :math:`U` of :math:`A`. 4. If :math:`A` is the parent of a set (a power set), then :math:`A` and :math:`B` can only have a common overstructure if :math:`B` is also the parent of a set, in which case the overstructure is the power set of the overstructure of the universes :math:`U` and :math:`V` of :math:`A` and :math:`B` respectively. Likewise for sequences instead of sets. We give two examples to illustrate rules (3) and (4). It is possible to create a set with a set as its universe: .. code-block:: magma S := { { 1..100 } | x^3 : x in [ 0..3 ] }; If we wish to intersect this set with some set of integers, say the formal set of odd integers .. code-block:: magma T := {! x : x in Integers() | IsOdd(x) !}; W := S meet T; then we can only do that if we can find a universe for :math:`W`, which must be the common overstructure of the universe :math:`U = \{ 1, 2, \ldots, 100\}` of :math:`S` and the universe 'ring of integers' of :math:`T`. By rule (3) above, this overstructure of :math:`U = \{ 1, 2, \ldots, 100\}` will be the overstructure of the universe of :math:`U` and the ring of integers; but the universe of :math:`U` is the ring of integers (because it is the default for the set :math:`\{ 1, 2, \ldots, 100\}`), and hence the overstructure we are looking for (and the universe for :math:`W`) will be the ring of integers. For the second example we look at sequences of sequences: .. code-block:: magma a := [ [ 1 ], [ 1, 2, 3 ] ]; b := [ [ 2/3 ] ]; so :math:`a` is a sequence of sequences of integers, and :math:`b` is a sequence of sequences of rationals. If we wish to concatenate :math:`a` and :math:`b`, .. code-block:: magma c := a cat b; we will only succeed if we find a universe for :math:`c`. This universe must be the common overstructure of the universes of :math:`a` and :math:`b`, which are the 'power sequence of the integers' and the 'power sequence of the rationals' respectively. By rule (4), the overstructure of these two power sequences is the power sequence of the common overstructure of the rationals and the integers, which is the rationals themselves. Hence :math:`c` will be a sequence of sequences of rationals, and the elements of :math:`a` will have to be coerced.