Appendix II – Miscellaneous Mathematics

This appendix reviews various mathematical concepts, topics, and related re­sults that are used throughout the main text.

11.1. Sets and Set Operations

11.1.1. General Set Operations

The union A U B of two sets A and B is the set of elements that belong to either A or B or to both. Thus, if we denote “belongs to” or “is an element of” by the symbol e, x e A U B implies that x є A or x є B, or in both, and vice versa. A finite union Un=1 Aj of sets Ai,…, An is the set having the property that for each x e Un=1 Aj there exists an index i, 1 < i < n, for which x e Ai, and vice versa: Ifx e Ai for some index i, 1 < i < n, thenx e Un=1 Aj. Similarly, the countable union Aj of an infinite sequence of sets Aj, j = 1, 2, 3,… is a set with the property that for each x e Aj there exists a finite index i > 1 for which x e Ai, and vice versa: If x e Ai for some finite index i > 1, then x e UjO0=1 Aj.

The intersection A П B of two sets A and B is the set of elements that belong to both A and B. Thus, x e A П B implies that x e A and x e B, and vice versa. The finite intersection nn=1 Aj of sets A1An is the set with the property that, if x e nnj=1 Aj, then for all i = 1,…,n, x e Ai and vice versa: If x e Ai for all i = 1,…, n, then x e nn=1 Aj. Similarly, the countable intersection nj=1 Aj ofan infinite sequence of sets Aj, j = 1, 2,… is a set with the property that, if x e nj= Aj, then for all indices i > 1, x e Ai, and vice versa: If x e Ai for all indices i > 1, then x e nj= Aj.

A set A is a subset of a set B, denoted by A c B, if all the elements of A are contained in B. If A c B and B c A, then A = B.

The difference AB (also denoted by A – B) of sets A and B is the set of elements of A that are not contained in B. The symmetric difference of two sets A and B is denoted and defined by A AB = (A /B) U (B / A).

If A c B, then the set A = B /A (also denoted by ~ A) is called the com­plement of A with respect to B. If Aj for j = 1, 2, 3,… are subsets of B, then ~ Uj Aj = rij A j and ~ Hj Aj = UjA j for finite as well as countable infinite unions and intersections.

Sets A and B are disjoint if they do nothave elements in common: A П B = 0, where 0 denotes the empty set, that is, a set without elements. Note that A U0 = A and A H 0 = 0. Thus, the empty set 0 is a subset of any set, including 0 itself. Consequently, the empty set is disjoint with any other set, including 0 itself. In general, a finite or countable infinite sequence of sets is disjoint if their finite or countable intersection is the empty set 0.

For every sequence of sets Aj, j = 1, 2, 3,…, there exists a sequence Bj, j = 1, 2, 3of disjoint sets such that for each j, Bj c Aj, and U j Aj = UjBj. In particular, let B1 = A1 and Bn = An Uj=1 Aj for n = 2, 3, 4,___

The order in which unions are taken does not matter, and the same applies to intersections. However, if you take unions and intersections sequentially, it matters what is done first. For example, (A U B) П C = (A П C) U (B П C), which is in general different from A U (B П C) except if A c C. Similarly, (A П B) U C = (A U C) П (B U C), which is in general different from A П (B U C) except if A c B.