|
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:
- (1)
- every set/sequence is compatible with the null set/sequence (which
has no universe defined (see above));
- (2)
- two sets/sequences with the same universe are compatible;
- (3)
- a set/sequence S with universe A is compatible with
set/sequence T with universe B if the elements of A can be
automatically coerced into B, or vice versa;
- (4)
- more generally,
a set/sequence S with universe A is also compatible with
set/sequence T with universe B if Magma can automatically find
an over-structure for the parents A and B (see below);
- (5)
- 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 C for the universe
A and B of sets or sequences S and T (such that A⊂C⊃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.
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.)
- (1)
- The overstructure of A and B is the same as that of B and A.
- (2)
- If A is the null set or sequence (empty, and no universe specified)
the overstructure of A and B is B.
- (3)
- If A is a set or sequence with universe U, the overstructure of
A and B is the overstructure of U and B; in particular, the
overstructure of A and A will be the universe U of A.
- (4)
- If A is the parent of a set (a power set), then A and B
can only have a common overstructure if B is also the parent of a set, in
which case the overstructure is the power set of
the overstructure of the universes U and V of A and 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:
> 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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|