Sums and Products of Sets - Essential Dictionary I

Mathematical Writing - Vivaldi Franco 2014

Sums and Products of Sets
Essential Dictionary I

Let $$X$$ and $$Y$$ be sets of numbers. The algebraic sum $$X+Y$$ and product $$XY$$ (also known as Minkowski 7 sum (product)), are defined as follows:

$$\begin{aligned} X+Y \,\mathop {=}\limits ^\mathrm{def}\, \{x+y\,:\,x\in X,\, y\in Y\} \qquad XY \,\mathop {=}\limits ^\mathrm{def}\, \{xy\,:\,x\in X,\, y\in Y\} \end{aligned}$$

(2.21)

with the stipulation that repeated elements are to be ignored. For example, if $$X=\{1,3\}$$ and $$Y=\{2,4\}$$, then

$$ X+Y=\{3,5,7\}\qquad XY=\{2,4,6,12\}. $$

The expression ’sum of sets’ is always understood as an algebraic sum. In the case of product, it is advisable to use the full expression to avoid confusion with the cartesian product.

If $$X=\{x\}$$ consists of a single element, then we use the shorthand notation $$x+Y$$ and $$xY$$ in place of $$\{x\}+Y$$ and $$\{x\}Y$$, respectively (as we did in Sect. 2.1.2 for integers). For example

$$ \frac{1}{2}+\mathbb {N}=\left\{ \frac{1}{2},\frac{3}{2},\frac{5}{2},\ldots \right\} \qquad \uppi \mathbb {Z}=\{\ldots ,-2\uppi ,\uppi ,0,\uppi ,2\uppi ,\ldots \}. $$

This notation leads to concise statements such as

$$ m\mathbb {Z}+n\mathbb {Z}=\mathrm{gcd}(m,n)\mathbb {Z}$$

which combines algebraic sum and product of sets (see Exercise 7.5).

Elementary—but significant—applications of this construct are found in modular arithmetic. Let $$m$$ be a positive integer. We say that two integers $$x$$ and $$y$$ are congruent modulo $$m$$ if $$m$$ divides $$x-y$$. This relation is denoted by8

$$ x\equiv y\,(\mathrm{mod\ }m). $$

Thus

$$ -3\equiv 7\,(\mathrm{mod\ }5) \qquad 1\not \equiv 12\,(\mathrm{mod\ }7). $$

The integer $$m$$ is called the modulus. The set of integers congruent to a given integer is called a congruence (or residue) class. One verifies that the congruence class of $$k$$ modulo $$m$$ is the infinite set $$k+m\mathbb {Z}$$ given explicitly in (2.11). The congruence class of $$k$$ modulo $$m$$ is also denoted by $$[k]_m$$, $$k\,(\mathrm{mod\ }m)$$, or, if the modulus is understood, by $$[k]$$ or $$\overline{k}$$.

The set of congruence classes modulo $$m$$ is denoted by $$\mathbb {Z}/m\mathbb {Z}$$. If $$m=p$$ is a prime number, the notation $${\mathbb F}_p$$ (meaning ’the field with $$p$$ elements’) may be used in place of $$\mathbb {Z}/p\mathbb {Z}$$. The set $$\mathbb {Z}/m\mathbb {Z}$$ contains $$m$$ elements, which form a partition of $$\mathbb {Z}$$:

$$ \mathbb {Z}/m\mathbb {Z}=\{m\mathbb {Z},1+m\mathbb {Z},2+m\mathbb {Z},\ldots ,(m-1)+m\mathbb {Z}\}. $$

Variants of this notation are used extensively in algebra, where one defines the sum/product of more general sets, such as groups and rings.