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 e in Magma has some parent structure S such that e∈S; this structure can be used for type checking (are we allowed to apply function f to 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.
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 i and s in
> 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 1, 2, 3 and having the ring of integers as universe:
> i := { 1, 2, 3 };
Only empty sets and sequences that have been obtained directly from the
constructions
> 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
> 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 2 in the set 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 T = { 1, 2, 1/3 }; then we run into trouble with the rule that the universe must be common for all elements in T. The way this problem is solved in Magma is by automatic coercion: The obvious universe for T is the field of rational numbers of which 1/3 is already an element and into which any integer can be coerced in a natural way. Hence the assignment
> 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 1 of the set T, it will have the rational field as its parent
rather than the integer ring!
It will now be clear that
> s := { 1/1, 2, 3 };
is a shorter way to specify the set of rational numbers 1, 2, 3
than the way we saw before, but in general it is preferable to declare the universe
beforehand using the { U | } notation.
Of course
> T := { Integers() | 1, 2, 1/3 }
would result in an error because 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,
> S := [ [ 1..10 ] | x^2+x+1 : x in { -3 .. 2 by 1 } ];
produces the sequence [ 7, 3, 1, 1, 3, 7 ] of values of the polynomial
x2 + x + 1 for x∈Z with -3≤x≤2. However, an entry of S
will in fact have the ring of integers as its parent (and not the
sequence [ 1..10 ]), because the effect of the above assignment
is that the values after the | are calculated and coerced into the
universe, which is [ 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
> 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 y
satisfy 1≤y≤10, and an error would occur if this is violated:
> 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.
Once a (non-null) set or sequence S has been created, the universe has been defined. If one attempts to modify 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,
> Z := Integers(); > T := [ Z | 1, 2, 3/3 ]; > T[2] := 3/4;will result in an error, because 3/4 cannot be coerced into Z.
The universe of a set or sequence S can be explicitly modified by creating a parent for 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 { 1, 2 } can be made into a sequence of rationals as follows:
> 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 { 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 applied to sets and sequences that are compatible: the operation on S with universe A and T with universe B can only be performed if a common universe C can be found such that the elements of S and T are all elements of C. The compatibility conditions are dependent on the particular Magma module to which A and B belong (we refer to the corresponding chapters of this manual for further information) and do also apply to elements of a∈A and b∈B --- that is, the compatibility conditions for S and T are the same as the ones that determine whether binary operations on a∈A and b∈B are allowed. For example, we are able to join a set of integers and a set of rationals:
> T := { 1, 2 } join { 1/3 };
for the same reason that we can do
> c := 1 + 1/3;(automatic coercion for rings). The resulting set T will have the rationals as universe.
The basic rules for compatibility of two sets or sequences are then:
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.
The universe of a set or sequence S is the common parent for all its elements; but 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 S. It can be created using the PowerSet function. Similarly, PowerSequence(A) creates the parent structure for a sequence of elements from the structure A -- that is, the elements of PowerSequence(A) are all sequences of elements of A.
The rules for finding a common overstructure for structures A and B, where either A or B is a set/sequence or the parent of a set/sequence, are as follows. (If neither A nor B is a set, sequence, or its parent we refer to the Part of this manual describing the operations on A and B.)
> 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
> T := {! x : x in Integers() | IsOdd(x) !};
> W := S meet T;
then we can only do that if we can find a universe for W, which
must be the common overstructure of the universe U = { 1, 2, ..., 100 }
of S and the universe `ring of integers' of T. By rule (3)
above, this overstructure of U = { 1, 2, ..., 100 } will
be the overstructure of the universe of U and the
ring of integers; but the universe of U is the ring of
integers (because it is the default for the set { 1, 2, ..., 100 }),
and hence the overstructure we are looking for (and the universe for W) will
be the ring of integers.
For the second example we look at sequences of sequences:
> a := [ [ 1 ], [ 1, 2, 3 ] ]; > b := [ [ 2/3 ] ];so a is a sequence of sequences of integers, and b is a sequence of sequences of rationals. If we wish to concatenate a and b,
> c := a cat b;we will only succeed if we find a universe for c. This universe must be the common overstructure of the universes of a and 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 c will be a sequence of sequences of rationals, and the elements of a will have to be coerced.