Creating Sets
=============

The customary braces ``{`` ``}`` 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
--------------------------

The formal set constructor has the following fixed format (the
expressions appearing in the construct are defined above):


.. magma:literal:: { ! x in F | P(x) ! }
   :input_types: 
   :output_types: 
   :label:
   :toc_name: Formal set constructor

   Form the formal set consisting of the subset of elements :math:`x` of :math:`F` for which
   :math:`P(x)` is true.
   If :math:`P(x)` is true for every element of :math:`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 :math:`F`.

The Enumerated Set Constructor
------------------------------

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 :doc:`../IntroductionToAggregates/introduction`
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. 

.. magma:literal:: { }
    :input_types: Null 
    :output_types: Set
    :toc_name: The null set

    The null set: an empty set that does not have its universe defined.

.. magma:literal:: { U | }
    :input_types: Str 
    :output_types: Set
    :toc_name: The empty set with universe

    The empty set with universe :math:`U`.

.. magma:literal:: { e_1, e_2, ..., e_n } 
    :input_types: Elt, ..., Elt
    :output_types: Set

    Given a list of expressions :math:`e_1, \ldots, e_n`, defining elements
    :math:`a_1, a_2, \ldots, a_n` all belonging to (or automatically
    coercible into) a single algebraic structure :math:`U`, create the set
    :math:`{ a_1, a_2, ..., a_n}` of elements of :math:`U`.


.. magma:example:: Example: Universe

   We create a set by listing its elements explicitly.

   .. code-block:: magma

      > 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 :math:`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):
   
   .. code-block:: magma

      > 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


.. magma:literal:: { U | e_1, e_2, ..., e_n }
    :input_types: Str, Elt, ..., Elt 
    :output_types: Set

    Given a list of expressions :math:`e_1, \ldots, e_n`, which define elements
    :math:`a_1, a_2, \ldots, a_n` that are all
    coercible into :math:`U`, create the set
    :math:`{ a_1, a_2, ..., a_n }` of elements of :math:`U`.

.. \siglit{\lbrace }}
.. { e(x) : x in E | P(x)\ }\

.. %\syn
.. %Set constructor

.. \des
.. Form the set of elements :math:`e(x)$, all belonging to some common
.. structure, for those :math:`x \in E$
.. with the property that the predicate :math:`P(x)$ is true. The
.. expressions appearing in this construct have the interpretation
.. given in the Introduction (Chapter~\ref{ChapAggr}) (in particular, :math:`E$ must be
.. a finite structure that can be enumerated).
.. \para
.. If :math:`P(x)$ is true for every value of :math:`x$ in :math:`E$, then the set
.. constructor may be abbreviated to ``{ e(x) : x in E\ }}.

.. \siglit{\lbrace }}
.. { U | e(x) : x in E | P(x) }\

.. %\syn
.. %Set constructor

.. \des
.. Form the set of elements of :math:`U$ consisting of the values :math:`e(x)$
.. for those :math:`x\in E$ for which the predicate :math:`P(x)$ is true (an error
.. results if not all :math:`e(x)$ are coercible into :math:`U$). The
.. expressions appearing in this construct have the same
.. interpretation as before.
.. \para
.. If :math:`P$ is always true, it may be omitted (including
.. the :math:`|$).

.. \siglitsplithelp{\lbrace }}
.. { { e(x$_1$,...,x$_k$) : x$_1$ in E$_1$, ..., x$_k$}
.. {in E$_k$ | P(x$_1$, ..., x$_k$) }}

.. %\syn
.. %Set constructor

.. \des
.. The set consisting of those elements :math:`e(x_1,\ldots,x_k)$,
.. in some common structure, for which :math:`x_1,\ldots,x_k$
.. in :math:`E_1, \ldots, E_k$ have the property that
.. $P(x_1,\ldots,x_k)$ is true.
.. The expressions appearing in this construct have the interpretation
.. given in the Introduction (Chapter~\ref{ChapAggr}).
.. \para
.. Note that if two successive allowable structures :math:`E_i$ and :math:`E_{i+1}$ 
.. are identical, then the specification of the carrier sets for :math:`x_i$ 
.. and :math:`x_{i+1}$ may be abbreviated to ``x$_i$, x$_{i+1}$ in E$_i$}.
.. \para
.. Also, if :math:`P(x_1, ..., x_k)$ is always true, it may be omitted (including
.. the :math:`|$).

.. \siglitsplithelp{\lbrace }}
.. { { U | e(x$_1$,...,x$_k$) : x$_1$ in E$_1$, ...,}
.. {x$_k$ in E$_k$ | P(x$_1$, ..., x$_k$) }}

.. %\syn
.. %Set constructor

.. \des
.. As in the previous entry, the set consisting of those elements
.. $e(x_1,\ldots,x_k)$ for which :math:`P(x_1,\ldots,x_k)$ is true, is formed,
.. as a set of elements of :math:`U$ (an error occurs if not all
.. $e(x_1,\ldots,x_k)$ are elements of or coercible into :math:`U$).
.. \para
.. Again, identical successive structures may be
.. abbreviated, and a predicate that is always true may be omitted.

.. \beginex{AlmostFermat}%\>------------------------
.. Now that Fermat's last theorem has been proven, it may be of
.. interest to find integers that almost satisfy :math:`x^n+y^n=z^n$.
.. In this example we find all :math:`2 < x,y,z < 1000$ such that :math:`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 :math:`1$. Note that 
.. we build a {\sl 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.
.. \begincode
.. > 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;
.. \lbrace
.. \       < 9, 10 >,
.. \       < 135, 235 >
.. \       < 334, 438 >,
.. \       < 73, 144 >,
.. \       < 64, 94 >,
.. \       < 244, 729 >
.. }
.. \endcode
.. Note that we spend a lot of time cubing integers this way.
.. A more efficient approach is shown in a subsequent example.
.. \endex

.. \subsection{indexed}
.. The Indexed Set Constructor.
.. \intro
.. The creation of indexed sets is similar to that of enumerated sets.
.. \endintro
.. \sigspec{\lbrace @ @}}
.. \lbrace @\ @}{} : Null -> SetIndx

.. %\syn
.. %The null set: an empty indexed set that does not have its universe defined.

.. \des
.. The null set: an empty indexed set that does not have its universe defined.

.. \sigspec{\lbrace @ @}}
.. \lbrace @\ U | @}{} : Str -> SetIndx

.. %\syn
.. %The empty indexed set with universe :math:`U$.

.. \des
.. The empty indexed set with universe :math:`U$.

.. \sigspec{\lbrace @ @}}
.. \lbrace @\ e$_1$, e$_2$, ..., e$_n$\ @}{} : Elt, ..., Elt -> SetIndx

.. %\res
.. %Elements coercible into same structure
.. %
.. %\syn
.. %Indexed set constructor

.. \des
.. Given a list of expressions :math:`e_1, \ldots, e_n$, defining elements
.. $a_1, a_2, \ldots, a_n$ all belonging to (or automatically
.. coercible into) a single algebraic structure :math:`U$, create the indexed set
.. $Q = \{\ a_1, a_2, ..., a_n\ \}$ of elements of :math:`U$.

.. \sigspec{\lbrace @ @}}
.. \lbrace @\ U |  e$_1$, e$_2$, ..., e$_m$\ @}{} : Str, Elt, ..., Elt -> SetIndx

.. %\res
.. %Elements coercible into :math:`U$
.. %
.. %\syn
.. %Indexed set constructor

.. \des
.. Given a list of expressions :math:`e_1, \ldots, e_m$, which define elements
.. $a_1, a_2, \ldots, a_n$ that are all
.. coercible into :math:`U$, create the indexed set
.. $Q = \{ a_1, a_2, ..., a_n\ \}$ of elements of :math:`U$.

.. \siglit{\lbrace @ @}}
.. \lbrace @\ e(x) : x in E | P(x)\ @}\

.. %\syn
.. %Indexed set constructor

.. \des
.. Form the indexed set of elements :math:`e(x)$, all belonging to some common
.. structure, for those :math:`x \in E$
.. with the property that the predicate :math:`P(x)$ is true. The
.. expressions appearing in this construct have the interpretation
.. given in the Introduction (Chapter~\ref{ChapAggr}) (in particular, :math:`E$ must be
.. a finite structure that can be enumerated).
.. \para
.. If :math:`P$ is always true, it may be omitted (including
.. the :math:`|$).

.. \siglit{\lbrace @ @}}
.. \lbrace @\ U |  e(x) : x in E | P(x) @}\

.. %\syn
.. %Indexed set constructor

.. \des
.. Form the indexed set of elements of :math:`U$ consisting of the values :math:`e(x)$
.. for those :math:`x\in E$ for which the predicate :math:`P(x)$ is true (an error
.. results if not all :math:`e(x)$ are coercible into :math:`U$). The
.. expressions appearing in this construct have the same
.. interpretation as before.
.. \para
.. If :math:`P$ is always true, it may be omitted (including
.. the :math:`|$).

.. \siglitsplithelp{\lbrace @ @}}
.. { \lbrace @\ e(x$_1$,...,x$_k$) : x$_1$ in E$_1$, ..., x$_k$}
.. {in E$_k$ | P(x$_1$, ..., x$_k$) @}}

.. %\syn
.. %Indexed set constructor

.. \des
.. The indexed set consisting of those elements :math:`e(x_1,\ldots,x_k)$
.. (in some common structure), for which :math:`x_1,\ldots,x_k$
.. in :math:`E_1 \times \ldots \times E_k$ have the property that
.. $P(x_1,\ldots,x_k)$ is true.
.. The expressions appearing in this construct have the interpretation
.. given in the Introduction (Chapter~\ref{ChapAggr}).
.. \para
.. Note that if two successive allowable structures :math:`E_i$ and :math:`E_{i+1}$ 
.. are identical, then the specification of the carrier sets for :math:`x_i$ 
.. and :math:`x_{i+1}$ may be abbreviated to ``x$_i$, x$_{i+1}$ in E$_i$}.
.. \para
.. Also, if :math:`P(x_1, ..., x_k)$ is always true, it may be omitted.

.. \siglitsplithelp{\lbrace @ @}}
.. { \lbrace @\ U | e(x$_1$,...,x$_k$) : x$_1$ in E$_1$, ...,}
.. {x$_k$ in E$_k$ | P(x$_1$, ..., x$_k$)@}}

.. %\syn
.. %Indexed set constructor

.. \des
.. As in the previous entry, the indexed set consisting of those elements
.. $e(x_1,\ldots,x_k)$ for which :math:`P(x_1,\ldots,x_k)$ is true is formed,
.. as an indexed set of elements of :math:`U$ (an error occurs if not all
.. $e(x_1,\ldots,x_k)$ are elements of or coercible into :math:`U$).
.. \para
.. Again, identical successive structures may be
.. abbreviated, and a predicate that is always true may be omitted.

.. \beginex{AlmostFermatIndexed}%\>------------------------
.. In the previous example we found pairs :math:`x, y$ such that :math:`x^3+y^3$ differs
.. by one from some cube :math:`z^3$. Using indexed sets it is somewhat easier to
.. retrieve the integer :math:`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.
.. \begincode
.. > cubes := \lbrace @ 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> }
.. \endcodex

.. \subsection{multiset}
.. The Multiset Constructor.
.. \intro
.. The creation of multisets is similar to that of enumerated sets.  An
.. important difference is that repetitions are significant and the
.. operator \hathat{} (mentioned above) may be used to specify the multiplicity
.. of an element.
.. \endintro
.. \sigspec{\bracestar\ \starbrace}
.. \bracestar\ \starbrace{} : Null -> SetMulti

.. %\syn
.. %The null set: an empty multiset that does not have its universe defined.

.. \des
.. The null set: an empty multiset that does not have its universe defined.

.. \sigspec{\bracestar\ \starbrace}
.. \bracestar\ U | \starbrace{} : Str -> SetMulti

.. %\syn
.. %The empty multiset with universe :math:`U$.

.. \des
.. The empty multiset with universe :math:`U$.

.. \sigspec{\bracestar\ \starbrace}
.. \bracestar\ e$_1$, e$_2$, ..., e$_n$\ \starbrace{} : Elt, ..., Elt -> SetMulti

.. %\res
.. %Elements coercible into same structure
.. %
.. %\syn
.. %Multiset constructor

.. \des
.. Given a list of expressions :math:`e_1, \ldots, e_n$, defining elements
.. $a_1, a_2, \ldots, a_n$ all belonging to (or automatically
.. coercible into) a single algebraic structure :math:`U$, create the multiset
.. $Q = \bracestar\ a_1, a_2, ..., a_n\ \starbrace$ of elements of :math:`U$.

.. \sigspec{\bracestar\ \starbrace}
.. \bracestar\ U |  e$_1$, e$_2$, ..., e$_m$\ \starbrace{} : Str, Elt, ..., Elt -> SetMulti

.. %\res
.. %Elements coercible into :math:`U$
.. %
.. %\syn
.. %Multiset constructor

.. \des
.. Given a list of expressions :math:`e_1, \ldots, e_m$, which define elements
.. $a_1, a_2, \ldots, a_n$ that are all
.. coercible into :math:`U$, create the multiset
.. $Q = \bracestar\ a_1, a_2, ..., a_n\ \starbrace$ of elements of :math:`U$.

.. \siglit{\bracestar\ \starbrace}
.. \bracestar\ e(x) : x in E | P(x)\ \starbrace\

.. %\syn
.. %Multiset constructor

.. \des
.. Form the multiset of elements :math:`e(x)$, all belonging to some common
.. structure, for those :math:`x \in E$
.. with the property that the predicate :math:`P(x)$ is true. The
.. expressions appearing in this construct have the interpretation
.. given in the Introduction (Chapter~\ref{ChapAggr}) (in particular, :math:`E$ must be
.. a finite structure that can be enumerated).
.. \para
.. If :math:`P$ is always true, it may be omitted (including
.. the :math:`|$).

.. \siglit{\bracestar\ \starbrace}
.. \bracestar\ U |  e(x) : x in E | P(x) \starbrace\

.. %\syn
.. %Multiset constructor

.. \des
.. Form the multiset of elements of :math:`U$ consisting of the values :math:`e(x)$
.. for those :math:`x\in E$ for which the predicate :math:`P(x)$ is true (an error
.. results if not all :math:`e(x)$ are coercible into :math:`U$). The
.. expressions appearing in this construct have the same
.. interpretation as before.
.. \para
.. If :math:`P$ is always true, it may be omitted (including
.. the :math:`|$).

.. \siglitsplithelp{\bracestar\ \starbrace}
.. { \bracestar\ e(x$_1$,...,x$_k$) : x$_1$ in E$_1$, ..., x$_k$}
.. {in E$_k$ | P(x$_1$, ..., x$_k$) \starbrace}

.. %\syn
.. %Multiset constructor

.. \des
.. The multiset consisting of those elements :math:`e(x_1,\ldots,x_k)$
.. (in some common structure), for which :math:`x_1,\ldots,x_k$
.. in :math:`E_1 \times \ldots \times E_k$ have the property that
.. $P(x_1,\ldots,x_k)$ is true.
.. The expressions appearing in this construct have the interpretation
.. given in the Introduction (Chapter~\ref{ChapAggr}).
.. \para
.. Note that if two successive allowable structures :math:`E_i$ and :math:`E_{i+1}$ 
.. are identical, then the specification of the carrier sets for :math:`x_i$ 
.. and :math:`x_{i+1}$ may be abbreviated to ``x$_i$, x$_{i+1}$ in E$_i$}.
.. \para
.. Also, if :math:`P(x_1, ..., x_k)$ is always true, it may be omitted.

.. \siglitsplithelp{\bracestar\ \starbrace}
.. { \bracestar\ U | e(x$_1$,...,x$_k$) : x$_1$ in E$_1$, ...,}
.. {x$_k$ in E$_k$ | P(x$_1$, ..., x$_k$)\starbrace}

.. %\syn
.. %Multiset constructor

.. \des
.. As in the previous entry, the multiset consisting of those elements
.. $e(x_1,\ldots,x_k)$ for which :math:`P(x_1,\ldots,x_k)$ is true is formed,
.. as a multiset of elements of :math:`U$ (an error occurs if not all
.. $e(x_1,\ldots,x_k)$ are elements of or coercible into :math:`U$).
.. \para
.. Again, identical successive structures may be
.. abbreviated, and a predicate that is always true may be omitted.

.. \beginex{Multiset}%\>------------------------
.. Here we demonstrate the use of the multiset constructors.
.. \begincode
.. > M := \bracestar\ 1, 1, 1, 3, 5 \starbrace;
.. > M;
.. \bracestar 1^^3, 3, 5 \starbrace
.. > M := \bracestar\ 1^^4, 2^^5, 1/2^^3 \starbrace;
.. > 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;
.. \bracestar\ 7^^95, 3^^102, 6^^94, 2^^103, 9^^106, 5^^97,
.. 1^^116, 8^^101, 4^^93, 0^^93 \starbrace
.. > 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
.. \endcodex
.. \subsection{arithmetic-progression}
.. The Arithmetic Progression Constructors.
.. \intro
.. 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.
.. \endintro
.. \sigspec{{ }}
.. {  i..j }{} : RngIntElt, RngIntElt -> Set

.. \sigspec{{ }}
.. { U | i..j }{} : Str, RngIntElt, RngIntElt -> SetIndx

.. %\syn
.. %(Indexed) set constructor for arithmetic progression of integers

.. \des
.. The enumerated set whose elements form the arithmetic progression
.. $i, i+1, i+2, \ldots, j$, where :math:`i$ and :math:`j$ are (expressions defining) integers. 
.. If :math:`j$ is less than :math:`i$ then the empty set will be created.
.. \para
.. The only universe :math:`U$ that is legal here is the ring of integers.

.. \sigspec{{ }}
.. { i .. j by k }{} : RngIntElt, RngIntElt, RngIntElt -> Set

.. \sigspec{{ }}
.. { U | i .. j by k }{} : Str, RngIntElt, RngIntElt, RngIntElt -> Set

.. %\syn
.. %Enumerated set constructor for arithmetic progression of integers

.. \des
.. The enumerated set consisting of the integers forming the arithmetic 
.. progression :math:`i, i+k, i+2*k, \ldots, j$, where :math:`i$, :math:`j$ and 
.. $k$ are (expressions defining) integers (but :math:`k\ne 0$).
.. \para
.. If :math:`k$ is positive then the last element in the progression 
.. will be the greatest integer of the form :math:`i + n*k$ that is 
.. less than or equal to :math:`j$. If :math:`j$ is less than :math:`i$, the empty 
.. set will be constructed.
.. \para
.. If :math:`k$ is negative then the last element in the progression 
.. will be the least integer of the form :math:`i + n*k$ that is 
.. greater than or equal to :math:`j$. If :math:`j$ is greater than :math:`i$, the 
.. empty set will be constructed.
.. \para
.. As for the previous constructor, only the ring of integers is allowed
.. as a legal universe :math:`U$.

.. \beginex{Progression}%\>--------------------------------------------------
.. 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.
.. \begincode
.. \< 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 }
.. \endcodex