|
The customary braces { and } are used to define
enumerated sets. Formal sets are delimited by the composite braces
{! and !}.
For indexed sets {@ and @} are used.
For multisets {* and *} are used.
The formal set constructor has the following fixed format (the
expressions appearing in the construct are defined above):
Form the formal set consisting of the subset of elements
x of F for which P(x) is true.
If P(x) is true for every element of F, the set
constructor may be abbreviated to
{! x in F !}.
Note that the universe of a formal set will always be equal
to the carrier set F.
Enumerated sets can be constructed by expressions enclosed in braces,
provided that the values of all expressions can be automatically
coerced into some common structure, as outlined in the Introduction,
(Chapter INTRODUCTION TO AGGREGATES).
All general constructors have an optional universe (U in the
list below) up front, that allows the user to specify into which structure
all terms of the sets should be coerced.
The null set: an empty set that does not have its universe defined.
The empty set with universe U.
Given a list of expressions e1, ..., en, defining elements
a1, a2, ..., an all belonging to (or automatically
coercible into) a single algebraic structure U, create the set
{ a1, a2, ..., an } of elements of U.
We create a set by listing its elements explicitly.
> S := { (7^2+1)/5, (8^2+1)/5, (9^2-1)/5 };
> S;
{ 10, 13, 16 }
> Parent(S);
Set of subsets of Rational Field
Thus S was created as a set of rationals, because /
on integers has a rational result. If one wishes to obtain a
set of integers, one could specify the universe (or one could
use div, or one could use ! on every element to coerce
it into the ring of integers):
> T := { Integers() | (7^2+1)/5, (8^2+1)/5, (9^2-1)/5 };
> T;
{ 10, 13, 16 }
> Parent(T);
Set of subsets of Integer Ring
Given a list of expressions e1, ..., en, which define elements
a1, a2, ..., an that are all
coercible into U, create the set
{ a1, a2, ..., an } of elements of U.
Form the set of elements e(x), all belonging to some common
structure, for those x ∈E
with the property that the predicate P(x) is true. The
expressions appearing in this construct have the interpretation
given in the Introduction (Chapter INTRODUCTION TO AGGREGATES) (in particular, E must be
a finite structure that can be enumerated).
If P(x) is true for every value of x in E, then the set
constructor may be abbreviated to { e(x) : x in E }.
Form the set of elements of U consisting of the values e(x)
for those x∈E for which the predicate P(x) is true (an error
results if not all e(x) are coercible into U). The
expressions appearing in this construct have the same
interpretation as before.
If P is always true, it may be omitted (including
the |).
The set consisting of those elements e(x1, ..., xk),
in some common structure, for which x1, ..., xk
in E1, ..., Ek have the property that
P(x1, ..., xk) is true.
The expressions appearing in this construct have the interpretation
given in the Introduction (Chapter INTRODUCTION TO AGGREGATES).
Note that if two successive allowable structures Ei and Ei + 1
are identical, then the specification of the carrier sets for xi
and xi + 1 may be abbreviated to xi, xi + 1 in Ei.
Also, if P(x1, ..., xk) is always true, it may be omitted (including
the |).
As in the previous entry, the set consisting of those elements
e(x1, ..., xk) for which P(x1, ..., xk) is true, is formed,
as a set of elements of U (an error occurs if not all
e(x1, ..., xk) are elements of or coercible into U).
Again, identical successive structures may be
abbreviated, and a predicate that is always true may be omitted.
Now that Fermat's last theorem has been proven, it may be of
interest to find integers that almost satisfy x n + y n=z n.
In this example we find all 2 < x, y, z < 1000 such that x 3 + y 3=z 3 + 1.
First we build a set of cubes, then two sets of pairs for
which the sum of cubes differs from a cube by 1. Note that
we build a set rather than a sequence of cubes
because we only need fast membership testing.
Also note that the resulting sets of pairs do not have their
elements in the order in which they were found.
> cubes := { Integers() | x^3 : x in [1..1000] };
> plus := { <a, b> : a in [2..1000], b in [2..1000] | \
> b ge a and (a^3+b^3-1) in cubes };
> plus;
{
< 9, 10 >,
< 135, 235 >
< 334, 438 >,
< 73, 144 >,
< 64, 94 >,
< 244, 729 >
}
Note that we spend a lot of time cubing integers this way.
A more efficient approach is shown in a subsequent example.
The creation of indexed sets is similar to that of enumerated sets.
The null set: an empty indexed set that does not have its universe defined.
The empty indexed set with universe U.
Given a list of expressions e1, ..., en, defining elements
a1, a2, ..., an all belonging to (or automatically
coercible into) a single algebraic structure U, create the indexed set
Q = { a1, a2, ..., an } of elements of U.
Given a list of expressions e1, ..., em, which define elements
a1, a2, ..., an that are all
coercible into U, create the indexed set
Q = { a1, a2, ..., an } of elements of U.
Form the indexed set of elements e(x), all belonging to some common
structure, for those x ∈E
with the property that the predicate P(x) is true. The
expressions appearing in this construct have the interpretation
given in the Introduction (Chapter INTRODUCTION TO AGGREGATES) (in particular, E must be
a finite structure that can be enumerated).
If P is always true, it may be omitted (including
the |).
Form the indexed set of elements of U consisting of the values e(x)
for those x∈E for which the predicate P(x) is true (an error
results if not all e(x) are coercible into U). The
expressions appearing in this construct have the same
interpretation as before.
If P is always true, it may be omitted (including
the |).
The indexed set consisting of those elements e(x1, ..., xk)
(in some common structure), for which x1, ..., xk
in E1 x ... x Ek have the property that
P(x1, ..., xk) is true.
The expressions appearing in this construct have the interpretation
given in the Introduction (Chapter INTRODUCTION TO AGGREGATES).
Note that if two successive allowable structures Ei and Ei + 1
are identical, then the specification of the carrier sets for xi
and xi + 1 may be abbreviated to xi, xi + 1 in Ei.
Also, if P(x1, ..., xk) is always true, it may be omitted.
As in the previous entry, the indexed set consisting of those elements
e(x1, ..., xk) for which P(x1, ..., xk) is true is formed,
as an indexed set of elements of U (an error occurs if not all
e(x1, ..., xk) are elements of or coercible into U).
Again, identical successive structures may be
abbreviated, and a predicate that is always true may be omitted.
In the previous example we found pairs x, y such that x 3 + y 3 differs
by one from some cube z 3. Using indexed sets it is somewhat easier to
retrieve the integer z as well. We give a small example.
Note also that it is beneficial to know here that evaluation of
expressions proceeds left to right.
> cubes := {@ Integers() | z^3 : z in [1..25] @};
> plus := { <x, y, z> : x in [-10..10], y in [-10..10], z in [1..25] |
> y ge x and Abs(x) gt 1 and Abs(y) gt 1 and (x^3+y^3-1) in cubes
> and (x^3+y^3-1) eq cubes[z] };
> plus;
{ <-6, 9, 8>, <9, 10, 12>, <-8, 9, 6> }
The creation of multisets is similar to that of enumerated sets. An
important difference is that repetitions are significant and the
operator ^^ (mentioned above) may be used to specify the multiplicity
of an element.
The null set: an empty multiset that does not have its universe defined.
The empty multiset with universe U.
Given a list of expressions e1, ..., en, defining elements
a1, a2, ..., an all belonging to (or automatically
coercible into) a single algebraic structure U, create the multiset
Q = {* a1, a2, ..., an *} of elements of U.
Given a list of expressions e1, ..., em, which define elements
a1, a2, ..., an that are all
coercible into U, create the multiset
Q = {* a1, a2, ..., an *} of elements of U.
Form the multiset of elements e(x), all belonging to some common
structure, for those x ∈E
with the property that the predicate P(x) is true. The
expressions appearing in this construct have the interpretation
given in the Introduction (Chapter INTRODUCTION TO AGGREGATES) (in particular, E must be
a finite structure that can be enumerated).
If P is always true, it may be omitted (including
the |).
Form the multiset of elements of U consisting of the values e(x)
for those x∈E for which the predicate P(x) is true (an error
results if not all e(x) are coercible into U). The
expressions appearing in this construct have the same
interpretation as before.
If P is always true, it may be omitted (including
the |).
The multiset consisting of those elements e(x1, ..., xk)
(in some common structure), for which x1, ..., xk
in E1 x ... x Ek have the property that
P(x1, ..., xk) is true.
The expressions appearing in this construct have the interpretation
given in the Introduction (Chapter INTRODUCTION TO AGGREGATES).
Note that if two successive allowable structures Ei and Ei + 1
are identical, then the specification of the carrier sets for xi
and xi + 1 may be abbreviated to xi, xi + 1 in Ei.
Also, if P(x1, ..., xk) is always true, it may be omitted.
As in the previous entry, the multiset consisting of those elements
e(x1, ..., xk) for which P(x1, ..., xk) is true is formed,
as a multiset of elements of U (an error occurs if not all
e(x1, ..., xk) are elements of or coercible into U).
Again, identical successive structures may be
abbreviated, and a predicate that is always true may be omitted.
Here we demonstrate the use of the multiset constructors.
> M := {* 1, 1, 1, 3, 5 *};
> M;
{* 1^^3, 3, 5 *}
> M := {* 1^^4, 2^^5, 1/2^^3 *};
> M;
> // Count frequency of digits in first 1000 digits of pi:
> pi := Pi(RealField(1001));
> dec1000 := Round(10^1000*(pi-3));
> I := IntegerToString(dec1000);
> F := {* I[i]: i in [1 .. #I] *};
> F;
{* 7^^95, 3^^102, 6^^94, 2^^103, 9^^106, 5^^97,
1^^116, 8^^101, 4^^93, 0^^93 *}
> for i := 0 to 9 do i, Multiplicity(F, IntegerToString(i)); end for;
0 93
1 116
2 103
3 102
4 93
5 97
6 94
7 95
8 101
9 106
Some special constructors exist to create and store enumerated
sets of integers in arithmetic progression efficiently.
This only works for arithmetic progressions of elements of
the ring of integers.
{ U | i..j } : Str, RngIntElt, RngIntElt -> SetIndx
The enumerated set whose elements form the arithmetic progression
i, i + 1, i + 2, ..., j, where i and j are (expressions defining) integers.
If j is less than i then the empty set will be created.
The only universe U that is legal here is the ring of integers.
{ U | i .. j by k } : Str, RngIntElt, RngIntElt, RngIntElt -> Set
The enumerated set consisting of the integers forming the arithmetic
progression i, i + k, i + 2 * k, ..., j, where i, j and
k are (expressions defining) integers (but k≠0).
If k is positive then the last element in the progression
will be the greatest integer of the form i + n * k that is
less than or equal to j. If j is less than i, the empty
set will be constructed.
If k is negative then the last element in the progression
will be the least integer of the form i + n * k that is
greater than or equal to j. If j is greater than i, the
empty set will be constructed.
As for the previous constructor, only the ring of integers is allowed
as a legal universe U.
It is possible to use the arithmetic progression constructors to save
typing in the creation of `arithmetic progressions' of elements of other
structures than the ring of integers, but it should be kept in mind
that the result will not be treated especially efficiently like the
integer case. Here is the `wrong' way, as well as two correct ways
to create a set of 10 finite field elements.
> S := { FiniteField(13) | 1..10 };
Runtime error in { .. }: Invalid set universe
> S := { FiniteField(13) | x : x in { 1..10 } };
> S;
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
> G := PowerSet(FiniteField(13));
> S := G ! { 1..10 };
> S;
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|