Lecture
The creator of set theory, G. Cantor, defined the concept of a set and an element of a set as follows: ”By a set we understand a collection of definite, distinct objects (real or imagined), called elements of the set, taken as a whole”. Usually sets are denoted by uppercase letters of the Latin alphabet, and their elements – by lowercase letters or numbers.
The number of elements in a set A is called the cardinality of the set A and is denoted |A| . If to each element of the set A one can assign a unique element of the set B, and to each element of the set B one can assign a unique element of the set A, then the sets A and B are called equipotent and this is denoted |A|=|B| .
A set consisting of a finite number of elements is called finite .
A set that is not finite is called infinite . An infinite set is called countable if it is equipotent to the set N of all natural numbers. It is said that all elements of a countable set can be enumerated. Otherwise an infinite set is called uncountable .
A set containing no elements is called empty and is denoted 
or {}.
Usually in specific reasoning the elements of all sets are taken from some one, sufficiently broad set U (its own for each case), which is called the universe.
Two sets A and B are called equal if they consist of the same elements (A=B).
If M is a set, and a – is an element of it, then a belongs to M (a
M). If, however, a is not an element of the set M, then a does not belong to M (a
M).
1. Inclusion of A in B 
is true if every element of the set A belongs to the set B. In this case A is called a subset of B, and B – a superset of A.
Sets A and B are equal (A=B) if 
. The empty set is a subset of every set.
The universe is a superset of every set.
The set of all subsets of a set M is called the power set and is denoted 
:
For a finite set 
. To each subset A one can assign a binary vector C of |M| digits in which:
Ci=1, if 
and
Ci=0, if 
, where i – is an element of the set M,
Ci – is the i-th digit of the vector C.
The number of distinct binary vectors of |M| digits equals 2|M|, hence |2M|=2|M|.
2. Strict inclusion of A in B 
is true if 
. If 
, then A is a proper subset of B.
3. The union of A and B (A U B) is the set consisting of all those and only those elements which belong to A or B, i.e.
4. The intersection of A and B (A n B) is the set consisting of all those and only those elements which belong to each of the sets A and B, i.e.
5. The difference of A and B (A-B) is the set consisting of all those and only those elements of the set A which do not belong to the set B, i.e.
To denote the difference of sets, discrete mathematics usually uses the symbol “\”.
6. The symmetric difference of A and B (AΔB) is the set consisting of all those and only those elements of the set A which do not belong to the set B, and only those elements of the set B which do not belong to the set A, i.e.
7. The complement of A to the universe U (
) is the set consisting of all those and only those elements of the universe U which do not belong to the set A, i.e.
For any two sets A and B, at least one of the following five cases (possibilities) holds:
1) A equals B;
2) A is strictly included in B;
3) B is strictly included in A;
4) A and B do not intersect;
5) A and B are in general position.
If both sets A and B are nonempty, then only one case holds.
Fig.1.1 shows Euler diagrams (Euler (1707-1783) proposed depicting sets as circles even before the creation of set theory by Cantor (1845-1918)), illustrating operations on sets. Sets are depicted as figures (ovals), and the result is highlighted graphically.
Fig.1.1. Operations on sets
The set of all subsets of a set U (the power set) together with the operations on sets forms an algebra of subsets (an algebra of Cantor) of the set U. An expression made up of subsets of the set U and operations on sets is called an expression in the algebra of subsets. An expression in the algebra of subsets may contain parentheses defining the order of execution of operations. If parentheses are not specified, then the order of execution of operations is determined by their priorities (table 1.1). The value of an expression in the algebra of subsets is a subset of the set U.
Table 1.1 Priorities of operations on sets
1. Idempotence:
2. Commutativity:
3. Associativity:
4. Distributivity for intersection and union:
5. Distributivity for intersection and difference:
6. Distributivity for intersection and symmetric difference:
7. Distributivity for difference:
8. Absorption:
9. Properties of zero:
10. Properties of the identity:
11. Involution: 
12. De Morgan's laws:
13. De Morgan's laws for difference, intersection, and union:
14. Properties of the complement:
15. Definition of difference:
16. Definition of union:
17. Definition of intersection:
1. By enumerating all elements.
A={a,b,c} , B={b,a,c} , C={a} , D={1,2,3,5,9}. From the definition of equality of sets it follows that A=B.
2. By specifying a characteristic property, distinguishing the elements of a given set among the elements of the indicated other set or sets.
A={x | x 
N and x<10} (N – is the set of natural numbers),
B={1,2,3,4,5,6,7,8,9} , A=B.
3. By describing generating procedure with an indication of the set (or sets) over which the parameter (or parameters) of the procedure “ranges”.
A={x2 | x
N} – the set of all squares of natural numbers.
By enumeration one can specify only a finite set, while with the help of a characteristic property or a generating procedure one can specify a finite or an infinite set.
Various methods can be used to represent a finite set in memory.
1. The elements of the set A are stored in a variable A of array type, and the cardinality of the set A – in a variable KA. The number of elements in the array A equals the cardinality of the universe. The elements of the array A are unordered.
2. The elements of the set A are stored in a variable A of array type, and the cardinality of the set A – in a variable KA. The number of elements in the array A equals the cardinality of the universe. The elements of the array A are ordered in ascending order.
3. The elements of the universe are numbered: U={u1,…,un}. The elements of the set A are stored in a variable A of array type, whose elements are of type boolean. If ui
A, then Ai=true, otherwise Ai=false. The number of elements in the array A equals the cardinality of the universe.
4. The elements of the universe are numbered: U={u1,…,un}. The set A is represented by a code C in which: Ci=1, if ui
A and Ci=0, if ui
A, where Ci – is the i-th digit of the code C. Depending on the cardinality of the universe, the code C can be stored in a simple variable or in an array.
5. A set type can be used to store a set.
There are four main storage options:
Array — is a storage method in which the elements of a set are located sequentially in cells.
The most economical option, if the cardinality of the set is known and the elements are data of one type.
List — a storage method in which memory is allocated for each element separately, and exactly as much as needed.
Disadvantage: it is necessary to store a pointer to the next element and spend time working with it.
The complexity of an array and a list is linear, O(n).
Hash table — is a generalization of the method of storing a set of integers (keys) in the form of a bit vector, for the case when the cardinality of the universe U is very large relative to the cardinality of the sets one needs to work with.
Hash function — converts key values to the interval [0, m – 1], where m — is the size of the hash table, 
Obviously, in this case many different key values will correspond to each index of the hash table. Therefore, firstly, the hash table has to store not bits but the key values themselves, and secondly, it is possible to place in it more than one key for each value of the mapping function (to resolve collisions).
If the table is built correctly and is not overloaded, then all functions (deletion, insertion, etc.) are performed in constant time. In the worst case (if there is a collision - repeating elements) the complexity is linear O(n).
Binary search tree (BST) — is a way of storing a set in the form of an extensible ordered list that preserves the ordering when inserting new elements without moving the elements already present.
BST — is a tree with weighted nodes, the weight at any node of which is greater than any weight in its left subtree and no greater than any weight in the right subtree. The number of steps of the algorithm for searching for an element of a set in such a tree does not exceed its height, i.e. it has complexity O(log n) . The operations of inserting a new element into the tree and deleting an element have the same complexity.
A BST can be obtained from an ordered sequence of keys if a binary tree of the corresponding cardinality is labeled by an internal (symmetric) method, and then the node numbers are replaced by the corresponding elements of the sequence. If the sequence is stored in an array, then the BST can be built by the bisection method: place the median element in order at the root of the tree, then recursively create the left subtree from the first half of the sequence, and the right one — from the second.
The disadvantage of a BST — is that it works well only if it is balanced, i.e. the lengths of the paths from the root to any leaf are approximately the same. However, with element-by-element insertion of an ordered sequence into the tree, the tree degenerates, turning into a linear list. Searching, insertion, and deletion in such a tree will be performed not in logarithmic but in linear time. The probability of degeneration is quite high. Thus, out of 7 nodes only one completely balanced tree can be formed, while there are 64 completely degenerate ones. Therefore, algorithms for working with a BST are often supplemented with auto-balancing after insertion and deletion. The most commonly used schemes are the AVL tree, the RB tree, and the 2-3 tree.
1. The elements of the set A are stored in a variable A of array type, and the cardinality of the set A – in a variable KA. The number of elements in the array A equals the cardinality of the universe. The elements of the array A are unordered.
Algorithm 1.1 (fig.1.3) for computing the inclusion of A in B (A
B).
Input: A-array, storing the elements of the set A, KA=|A|;
B-array, storing the elements of the set B, KB=|B|;
Output: F=true, if A
B, otherwise F=false.
Fig.1.3. Flowchart of the algorithm for computing the inclusion of A in B
Algorithm 1.2 (fig.1.4) for computing the equality of A and B (A=B).
Input: A-array, storing the elements of the set A, KA=|A|;
B-array, storing the elements of the set B, KB=|B|;
Output: F=true, if A=B, otherwise F=false.
Fig.1.4. Flowchart of the algorithm for computing the equality of A and B
Algorithm 1.3 (fig.1.5) for computing the union of A and B (A 
B).
Input: A-array, storing the elements of the set A, KA=|A|;
B-array, storing the elements of the set B, KB=|B|;
Output: C-array, storing the union of the sets A and B, KC=|C|;
Fig.1.5. Flowchart of the algorithm for computing the union of A and B
Algorithm 1.4 (fig.1.6) for computing the intersection of A and B (A 
B).
Input: A-array, storing the elements of the set A, KA=|A|;
B-array, storing the elements of the set B, KB=|B|;
let KA 
KB;
Output: C-array, storing the intersection of the sets A and B, KC=|C|;
Fig.1.6. Flowchart of the algorithm for computing the intersection of A and B
Algorithm 1.5 (fig.1.7) for computing the difference of A and B (A-B).
Input: A-array, storing the elements of the set A, KA=|A|;
B is an array storing the elements of set B, KB=|B|;
Output: C is an array storing the difference of sets A and B, KC=|C|;
Fig.1.7. Flowchart of the algorithm for computing the difference of A and B
Algorithm 1.6 for computing the symmetric difference of A and B (AΔ B).
Input: A is an array storing the elements of set A, KA=|A|;
B is an array storing the elements of set B, KB=|B|;
Output: C is an array storing the symmetric difference
of sets A and B, KC=|C|;
1. C:=A-B 
B-A; {or C:=(A 
B)-(A 
B) }
2. End.
Algorithm 1.7 (fig.1.8) for computing the complement of A (
).
Input: A is an array storing the elements of set A, KA=|A|;
Output: C is an array storing the complement of set A, KC=|C|;
Fig.1.8. Flowchart of the algorithm for computing the complement of A
Comments