Sets, pairs, mappings and equivalence classes

Janovec, V.; Hahn, Th.; Klapper, H.

doi:10.1107/97809553602060000643

International
Tables for
Crystallography
Volume D
Physical properties of crystals
Edited by A. Authier

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. D. ch. 3.2, pp. 380-381

Section 3.2.3.1. Sets, pairs, mappings and equivalence classes

V. Janovec,^a ^* Th. Hahn^b and H. Klapper^c

^a Department of Physics, Technical University of Liberec, Hálkova 6, 461 17 Liberec 1, Czech Republic,^bInstitut für Kristallographie, Rheinisch–Westfälische Technische Hochschule, D-52056 Aachen, Germany, and ^cMineralogisch-Petrologisches Institut, Universität Bonn, D-53113 Bonn, Germany
Correspondence e-mail: janovec@fzu.cz

3.2.3.1. Sets, pairs, mappings and equivalence classes

| top | pdf |

3.2.3.1.1. Sets

| top | pdf |

Definition 3.2.3.1. A set is a collection of distinguishable objects. The objects constituting a set are called elements (or points) of the set.

In Chapter 3.4 we encounter mainly two types of sets: sets the elements of which are crystalline objects (domain states, domain twins, domain walls etc.), and sets, like groups, with elements of mathematical nature, e.g. rotations, transformations, operations etc. The sets of crystalline objects will be denoted by capital sans-serif letters, e.g. $[{\sf A},{\sf B},\ldots]$ , and capital bold letters, e.g. $[\bf{S}, \bf{M}, \bf{N},\ldots]$ or $[{\bf S}_1, {\bf S}_2, {\bf S}_3,\ldots]$ , will be used to denote elements of such sets. Groups will be denoted by capital italic letters, e.g. G, F etc., and their elements by lower-case italic letters, e.g. $[g, h,\ldots]$ . The exposition of this section is given for sets the elements of which are (crystalline) objects, but all notions and relations hold for any other sets.

If an element $[\bf{S}]$ belongs to the set $[{\sf A}]$ , one writes $[{\bf S} \in {\sf A}]$ , in the opposite case $[{\bf S} \not\in {\sf A}]$ . Sets consisting of a small number of elements can be expressed explicitly by writing their elements between curly braces, $[{\sf A}=\{{\bf S}, {\bf M}, {\bf N}, {\bf Q}\}]$ . The order of elements in the symbol of the set is irrelevant. From the definition of a set it follows that there are no equal elements in the set, or in other words, any two equal elements coalesce into one: $[\{{\bf S},{\bf S}\}=\{{\bf S}\}.\eqno(3.2.3.1)]$ If a set contains many (or an infinite number of) elements, the elements are specified in another way, e.g. by stating that they have a certain property in common.

The number of elements in a set is the order of the set. A finite set $[{\sf A}]$ consists of a finite number of elements and this number is denoted by $[|{\sf A}|]$ . An infinite set contains infinite number of elements and an empty set, denoted by $[\emptyset]$ , contains no element. In what follows, the term `set' will mean a `finite nonempty set' unless explicitly stated otherwise.

A set $[{\sf B}]$ is a subset of $[{\sf A}]$ , $[{\sf B} \subseteq {\sf A}]$ or $[{\sf A} \supseteq {\sf B} ]$ , if every element of $[{\sf B}]$ is an element of $[{\sf A}]$ . If each element of $[{\sf B}]$ is an element of $[{\sf A}]$ , and vice versa, then $[{\sf B}]$ is equal to or identical with $[{\sf A}]$ , $[{\sf B}={\sf A}]$ or $[{\sf A}={\sf B}]$ . If there exists at least one element of $[{\sf A}]$ which is not contained in $[{\sf B}]$ , then $[{\sf B}]$ is a proper subset of $[{\sf A}]$ , $[{\sf B} \subset {\sf A}]$ or $[{\sf A} \supset {\sf B}]$ . The subset $[{\sf B}]$ is often defined by a restriction that specifies only some elements of $[{\sf A}]$ as elements of $[{\sf B}]$ . This is written in short as $[{\sf B} =]$ $[\{{\bf S} \in {\sf A}|\hbox{restriction on } {\bf S}\}]$ ; the expression means that $[{\sf B}]$ consists of all elements of $[{\sf A}]$ that satisfy the restriction given behind the sign |.

The intersection of two sets $[{\sf A}]$ and $[{\sf B}]$ , $[{\sf A} \cap {\sf B}]$ or $[{\sf B} \cap {\sf A}]$ , is a set comprising all elements that belong both to $[{\sf A}]$ and to $[{\sf B}]$ . If the sets $[{\sf A}]$ and $[{\sf B}]$ have no element in common, $[{\sf A} \cap {\sf B} = \emptyset]$ , then one says that the sets $[{\sf A}]$ and $[{\sf B}]$ are disjoint. The union of sets $[{\sf A}]$ and $[{\sf B}]$ , $[{\sf A} \cup {\sf B}]$ or $[{\sf B} \cup {\sf A}]$ , is a set consisting of all elements that belong either to $[{\sf A}]$ or to $[{\sf B}]$ . Sometimes the symbol [+] is used instead of the symbol $[\cup]$ . The difference of set $[{\sf A}]$ and $[{\sf B}]$ , or the complement of $[{\sf B}]$ in $[{\sf A}]$ , $[{\sf A}-{\sf B}]$ , comprises those elements of $[{\sf A}]$ that do not belong to $[{\sf B}]$ .

3.2.3.1.2. Pairs

| top | pdf |

A collection of two objects $[{\bf S}_i]$ and $[{\bf S}_k]$ constitutes an unordered pair. The objects of an unordered pair are called elements or points. A trivial unordered pair consists of two identical elements. A non-trivial unordered domain pair comprises two non-identical elements and is identical with a set of order two.

Note that we do not identify an unordered pair with a set of order two where, according to (3.2.3.1), two equal objects coalesce into one. In spite of this difference we shall use the same symbol for the unordered pair as for the set of order two, but reverse the symbol $[\{{\bf S},{\bf S}\}]$ for the trivial unordered pair. With this reservation, the identity $[\{{\bf S}_i,{\bf S}_k\} = \{{\bf S}_k,{\bf S}_i\} \eqno(3.2.3.2)]$ holds for both unordered pairs and for sets of order two.

An ordered pair, denoted $[({\bf S}_i,{\bf S}_k)]$ , consists of the first and the second member of the pair. If $[{\bf S}_i={\bf S}_k]$ , the ordered pair is called a trivial ordered pair, $[({\bf S}_i,{\bf S}_i)]$ ; if $[{\bf S}_i \neq {\bf S}_k]$ the pair $[({\bf S}_i,{\bf S}_k)]$ is a non-trivial ordered pair. The ordered pair $[({\bf S}_k,{\bf S}_i)]$ with a reversed order of elements is called a transposed pair. In contrast to unordered pairs, initial and transposed non-trivial ordered pairs are different objects, $[({\bf S}_i,{\bf S}_k) \neq ({\bf S}_k,{\bf S}_i) \,\,\hbox{ for } \,\,{\bf S}_i\neq {\bf S}_k. \eqno(3.2.3.2a)]$

The members $[{\bf S}_i]$ and $[{\bf S}_k]$ of an ordered pair $[({\bf S}_i,{\bf S}_k)]$ can either belong to one set, $[{\bf S}_i \in {\sf A}, {\bf S}_k \in {\sf A}]$ , or each to a different set, $[{\bf S}_i \in {\sf A}, {\bf S}_k \in {\sf B}]$ .

Two ordered pairs $[({\bf S}_i,{\bf S}_k)]$ and $[({\bf S}_m,{\bf S}_p)]$ are equal, $[({\bf S}_i,{\bf S}_k)=({\bf S}_m,{\bf S}_p)]$ , if and only if $[{\bf S}_i={\bf S}_m]$ and $[{\bf S}_k={\bf S}_p]$ .

We shall encounter ordered and unordered pairs in Sections 3.4.3 and 3.4.4 , where the members of pairs are domain states or domain twins. However, pairs are also essential in introducing further concepts of set theory. The starting point is the following construction of a set of pairs that are formed from two sets:

A Cartesian product $[{\sf A} \times {\sf B}]$ of two sets $[{\sf A}]$ and $[{\sf B}]$ is a set of all ordered pairs $[({\bf S},{\bf M})]$ , where $[{\bf S} \in {\sf A}, {\bf M} \in {\sf B}]$ . The sets $[{\sf A}]$ and $[{\sf B}]$ can be different or identical sets. If the sets $[{\sf A}]$ and $[{\sf B}]$ are finite, then the Cartesian product $[{\sf A} \times {\sf B}]$ consists of $[|{\sf A}|\cdot|{\sf B}|]$ ordered pairs.

3.2.3.1.3. Mappings

| top | pdf |

A mapping $[\varphi]$ of a set $[{\sf A}]$ into a set $[{\sf B}]$ is a rule which assigns to each element $[{\bf S} \in {\sf A}]$ a unique element $[{\bf M} \in {\sf B}]$ . This is written symbolically as $[\varphi:{\bf S} \,\mapsto\,{ \bf M}]$ or $[{\bf M}= \varphi({\bf S})]$ , and one says that $[\bf{S}]$ is mapped to $[\bf{M}]$ under the mapping $[\varphi]$ . The element $[\bf{M}]$ is called the image of the element S under $[\varphi]$ . The assignment $[\varphi:{\bf S} \,\mapsto\, {\bf M}]$ can be expressed by an ordered pair $[({\bf S},{\bf M})]$ , if one ascribes $[\bf{S}]$ to the first member of the pair and the element $[\bf{M}]$ to the second member of the pair $[({\bf S},{\bf M})]$ . Then the mapping $[\varphi]$ of a set $[{\sf A}]$ into a set $[{\sf B}]$ , symbolically written as $[\varphi:{\sf A} \rightarrow {\sf B}]$ , can be identified with such a subset of ordered pairs of the Cartesian product $[{\sf A} \times {\sf B}]$ in which each element $[\bf{S}]$ of $[{\sf A}]$ occurs exactly once as the first member of the pair $[({\bf S},{\bf M})]$ . If $[{\sf A}]$ is a finite set, then $[\varphi]$ consists of $[|{\sf A}|]$ ordered pairs.

We note that in a mapping $[\varphi:{\sf A} \rightarrow {\sf B}]$ several elements of $[{\sf A}]$ may be mapped to the same element of $[{\sf B}]$ . In such a case, the mapping $[\varphi]$ is called a many-to-one mapping. If the mapping $[\varphi:{\sf A} \rightarrow {\sf B}]$ is such that each element of $[{\sf B}]$ is the image of some element of $[{\sf A}]$ , then the mapping $[\varphi]$ is called a mapping of $[{\sf A}]$ onto $[{\sf B}]$ . If $[\varphi]$ is a mapping of $[{\sf A}]$ onto $[{\sf B}]$ and, moreover, each element of $[{\sf B}]$ is the image of exactly one element of $[{\sf A}]$ , then the mapping $[\varphi]$ becomes a one-to-one correspondence between $[{\sf A}]$ and $[{\sf B}]$ , $[\varphi:{\sf A} \leftrightarrow {\sf B}]$ . In this case, $[{\sf A}]$ and $[{\sf B}]$ are of the same order.

One often encounters a situation in which one assigns to each ordered pair $[({\bf S},{\bf M})]$ an element $[\bf{N}]$ , where all three elements $[{\bf S}, {\bf M}, {\bf N}]$ are elements from the same set $[{\sf A}]$ , symbolically $[\varphi:({\bf S},{\bf M}) \,\mapsto\, {\bf N}]$ ; $[{\bf S}, {\bf M}, {\bf N} \in {\sf A}]$ or $[\varphi:{\sf A} \times {\sf A} \rightarrow {\sf A}]$ . Such a mapping is called a binary operation or a composition law on the set $[{\sf A}]$ . A sum of two numbers [a+b=c] or a product of two numbers $[a\cdot b=c]$ , where [a,b,c] belong to the set of all real numbers, are elementary examples of binary operations.

3.2.3.1.4. Equivalence relation on a set, partition of a set

| top | pdf |

The notion of the ordered pair allows one to introduce another useful concept, namely the relation on a set. An example will illustrate this notion. Let $[{\bb Z}]$ be a set of integers, $[{\bb Z}=\{\ldots,-2,-1,0,1,2,\ldots\}]$ . For each ordered pair [(m,n)] , $[m,n\in {\bb Z}]$ , one can decide whether m is smaller than n, $[m \,\lt\, n]$ , or not. All pairs [(m,n)] that fulfil the condition $[m \,\lt\, n]$ form a subset $[{\sf R}]$ of all possible ordered pairs $[{\bb Z} \times {\bb Z}]$ . In other words, the relation $[m \,\lt\, n]$ defines a subset $[{\sf R}]$ of the set $[{\bb Z} \times {\bb Z}]$ , $[{\sf R} \subset {\bb Z} \times {\bb Z}]$ . Similarly, the relation [|m|=|n|] ( [|n|] denotes absolute value of n) defines another subset of $[{\bb Z} \times {\bb Z}]$ .

To indicate that an element $[{\bf S}]$ is related to $[\bf M]$ by $[\lower2pt\hbox{${{\buildrel {\sf R}\over{\sim}}}$}]$ , where $[{\bf S},{\bf M} \in {\sf A}]$ , one writes $[{\bf S}\,\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}\, {\bf M}]$ , where the relation $[{\sf R}]$ defines a subset $[{\sf R}]$ of all ordered pairs $[{\sf A} \times {\sf A}]$ , $[{\sf R} \subset {\sf A} \times {\sf A}]$ (the same letter $[{\sf R}]$ is used for the subset and for the relation on $[{\sf A}]$ ). The opposite also holds: Each subset $[{\sf R}]$ of $[{\sf A} \times {\sf A}]$ defines a certain relation $[\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}]$ on $[{\sf A}]$ .

A relation $[\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}]$ is called an equivalence relation on the set $[{\sf A}]$ if it satisfies three conditions: $[\displaylines{\hfill{\bf S}\,\,{\buildrel{\sf R}\over{\sim}}\,\,{\bf S} \,\, \hbox{for all} \,\,{ \bf S} \in {\sf A} \,\,(reflexivity), \hfill(3.2.3.3)\cr \hfill{\rm if} \,\, {\bf S}, {\bf M} \in {\sf A} \,\, {\rm and} \,\,{\bf S}\,\,{\buildrel{\sf R}\over{\sim}}\,\,{\bf M}, \,\, {\rm then} \,\, {\bf M}\,\,{\buildrel{\sf R}\over{\sim}}\,\,{\bf S} \,\, (symmetry), \hfill(3.2.3.4)\cr \hfill{\rm if} \,\,{\bf S}, {\bf M}, {\bf N} \in {\sf A}, \,\, {\bf S}\,\,{\buildrel{\sf R}\over{\sim}}\,\,{\bf M} \,\, {\rm and} \,\, {\bf M}\,\,{\buildrel{\sf R}\over{\sim}}\,\,{\bf N}, {\rm then} \,\, {\bf S}\,\,{\buildrel{\sf R}\over{\sim}}\,\,{\bf N}\,\, (transitivity).\hfill\cr\hfill(3.2.3.5)}%fd3.2.3.5]$ Thus, for example, it is easy to corroborate that the relation [|m|=|n|] on the set of integers $[{\bb Z}]$ fulfils all three conditions (3.2.3.3) to (3.2.3.5) and is, therefore, an equivalence relation on the set $[{\bb Z}]$ . On the other hand, the relation $[m \,\lt\, n]$ is not an equivalence relation on $[{\bb Z}]$ since it fulfils neither the reflexivity (3.2.3.3) nor the symmetry condition (3.2.3.4).

Let $[\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}]$ be an equivalence relation on $[{\sf A}]$ and $[{\bf S} \in {\sf A}]$ ; all elements $[{\bf M} \in {\sf A}]$ such that $[{\bf M}\,\lower2pt\hbox{${\buildrel{\sf R}\over{\sim}}$}\,{\bf S}]$ constitute a subset of $[{\sf A}]$ denoted $[[{\bf S}]_{\sf R}]$ and called the equivalence class of $[{\bf S}]$ with respect to $[\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}]$ (or the $[{\sf R}]$ -equivalence class of S). The element $[{\bf S}]$ is called the representative of the class $[[{\bf S}]_{\sf R}]$ . Any other member of the class can be chosen as its representative. Any two elements of the equivalence class $[[{\bf S}]_{\sf R}]$ are $[{\sf R}]$ -equivalent elements of $[{\sf A}]$ .

From the definition of the equivalence class, it follows that any two elements $[{\bf M}, {\bf N} \in {\sf A}]$ are either $[{\sf R}]$ -equivalent elements of $[{\sf A}]$ , $[{\bf M}\,\lower2pt\hbox{${\buildrel{\sf R}\over{\sim}}$}\,{\bf N}]$ , and thus belong to the same class, $[[{\bf M}]_{\sf R}=[{\bf N}]_{\sf R}]$ , or are not $[{\sf R}]$ -equivalent, and thus belong to two different classes that are disjoint, $[[{\bf M}]_{\sf R} \cap [{\bf N}]_{\sf R}=\emptyset]$ . In this way, the equivalence relation $[\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}]$ divides the set $[{\sf A}]$ into disjoint subsets (equivalence classes), the union of which is equal to the set itself. Such a decomposition is called a partition of the set $[{\sf A}]$ associated with the equivalence relation $[\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}]$ . For a finite set $[{\sf A}]$ this decomposition can be expressed as a union of equivalence classes, $[{\sf A}=[{\bf S}]_{\sf R} \cup [{\bf M}]_{\sf R} \cup\ldots \cup [{\bf Q}]_{\sf R}, \eqno(3.2.3.6)]$ where $[{\bf S}, {\bf M},\ldots , {\bf Q}]$ are representatives of the equivalence classes.

Generally, any decomposition of a set into a system of disjoint non-empty subsets such that every element of the set is a member of just one subset is called a partition of the set. To any partition of a set $[{\sf A}]$ there corresponds an equivalence relation $[\lower2pt\hbox{${\buildrel{\sf R}\over {\sim}}$}]$ such that the $[{\sf R}]$ -equivalence classes of $[{\sf A}]$ form that partition. This equivalence relation defines two elements as equivalent if and only if they belong to the same subset.

The term `equivalent' is often used when it is clear from the context what the relevant equivalence relation is. Similarly, the term `class' is used instead of `equivalence class'. Sometimes equivalence classes have names that do not explicitly indicate that they are equivalence classes. For example, in group theory, conjugate subgroups, left, right and double cosets form equivalence classes (see Section 3.2.3.2). Often instead of the expression `partition of a set $[{\sf A}]$ ' an equivalent expression `classification of the elements of a set $[{\sf A}]$ ' is used. The most important equivalence classes in the symmetry analysis of domain structures are called orbits and will be discussed in Section 3.2.3.3.

More details on set theory can be found in Kuratowski & Mostowski (1968), Lipschutz (1981), and Opechowski (1986).

References

Kuratowski, K. & Mostowski, A. (1968). Set theory. Amsterdam: North-Holland.Google Scholar

Lipschutz, S. (1981). Theory and problems of set theory and related topics. Singapore: McGraw-Hill.Google Scholar

Opechowski, W. (1986). Crystallographic and metacrystallographic groups. Amsterdam: North-Holland.Google Scholar

International Tables for Crystallography (2006). Vol. D. ch. 3.2, pp. 380-381