Discrete Mathematics
Chapter 1 Set Theory
1.2 Set Elements And Subsets
A Set may be viewed as any well-defined collection of objects called the elements or members of the set. One usually uses capital letters, \(A, B, X, Y, …\), to denote sets and lowercase letters, \(a, b, x, y, …\), to denote elements of sets. Synonyms for "set" are "class," "collection", and "family."
Membership in a Set
- \(a \in S\) denotes that \(a\) belongs to a Set \(S\)
- \(a, b \in S\) denotes that \(a\) and \(b\) belong to a Set \(S\)
- \(\in\) is the symbol meaning "is an element of."
- \(\notin\) means "is not an element of."
Specifying Sets
Set-Roster Notation: When a set is specified by writing all of its elements (or ellipses) between braces.
\(A = \{1, 3, 5, 7, 9\}\)
\(A = \{1,\, 2,\, 3,\, …,\, 100\}\) (all integers from 1 to 100).
\(B = \{2,\, 4,\, 6,\, …\}\).
Set-Builder Notation Let \(S\) denote a set and let \(P(x)\) be a property that elements of \(S\) may or may not satisfy. We may define a new set to be the set of all elements \(x\) in \(S\) such that \(P(x)\) is true. We denote this set as follows:
Occasionally we will write \(\{x | P(x)\}\) without being specific about where the element x comes from. It turns out that unrestricted use of this notation can lead to genuine contradictions in set theory. We will be careful to use this notation purely as a convenience in cases where the set S could be specified if necessary.
\(B = \{x\,|\,x\,is\,an\,even\,integer,\;x > 0\}\)
Read as: B is the set of x such that x is an even integer and x is greater than 0.
Symbols and Reading Sets
- Before the | read as: "The set of all…"
- | (pipe character) read as: "such that"
- , (comma) read as: "and"
- … read as: "and so forth"
\(A = \{1, 3, 5, 7, 9\}\) (Set-Roster Notation)
\(A = \{x\, |\, x\, is\, an\, odd\, positive\, integer,\, x < 10\}\) (Set-Builder Notation)
The Axiom of Extension says that a set is completely determined by what its elements are—not the order in which they might be listed or the fact that some elements might be listed more than once.
Examples: Using the Set-Roster Notation
- Let \(A = \{1, 2, 3\}\), \(B = \{3, 1, 2\},\) and \(C = \{1, 1, 2, 3, 3, 3\}\). What are the elements of A, B, and C? How are A, B, and C related?
- Is \(\{0\} = 0\)?
- How many elements are in the set \(\{1, \{1\}\}\)?
- For each nonnegative integer n, let \( Un_ = \{n,−n\} \). Find \(U_1\), \(U_2\), and \(U_0\).
Solutions: Using the Set-Roster Notation
- A, B, and C have exactly the same three elements: 1, 2, and 3. Therefore, A, B, and C are simply different ways to represent the same set.
- {0} ≠ 0 because {0} is a set with one element, namely 0, whereas 0 is just the symbol that represents the number zero.
- The set {1, {1}} has two elements: 1 and the set whose only element is 1.
- \( U_1 =\{1, -1\}, U_2 =\{2, -2\}, U_0 =\{0, -0\} = \{0, 0\} = \{0\} \).
Subsets
Suppose every element in a set A is also an element of a set B, that is, suppose a \(\in\) A implies a \(\in\) B. Then A is called a Subset of B. We also say that A is contained in B or that B contains A. This relationship is written:
A \(\subseteq\) B or B \(\supseteq\) A
Two sets are equal if they both have the same elements or, equivalently, if each is contained in the other. That is:
A = B if and only if A \(\subseteq\) B and B \(\subseteq\) A
If A is not a subset of B, that is, if at least one element of A does not belong to B, we write \(A \subsetneq B\).
Consider the sets:
A = {1, 3, 4, 7, 8, 9}, B = {1, 2, 3, 4, 5}, C = {1, 3}
Then \(C \subseteq A\) and \(C \subseteq B\) since 1 and 3, the elements of C, are also members of A and B. But \(B \subsetneq A\) since some of the elements of B, e.g., 2 and 5, do not belong to A. Similarly, \(A \subsetneq B\).
Technically, \(A \subseteq A\). If \(A \subseteq B\) and \(A \neq B\) then we say that A is a Proper Subset of B (sometimes written as\(A \subset B\)).
Suppose every element of a set A belongs to a set B and every element of B belongs to a set C. Then every element of A also belongs to C. In other words, if \(A \subseteq B\) and \(B \subseteq C\), then \(A \subseteq C\).
Theorem 1.1
- \(A \subseteq A\)
- If \(A \subseteq B\) and \(B \subseteq A\), then A = B
- If \(A \subseteq B\) and \(B \subseteq C\), then \(A \subseteq C\)
Special Symbols
Some sets occur often and they have their own symbols:
Special Symbols
- ℕ or N = The set of natural numbers or positive integers: 1, 2, 3, …
- ℤ or Z = The set of all integers: …, -2, -1, 0, 1, 2, …
- ℚ or Q = The set of rational numbers.
- ℝ or R = The set of real numbers.
- ℝ+ or R+ = The set of positive real numbers.
- ℂ or C = The set of complex numbers.
Note that ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ ⊆ ℂ.
Cartesian Products
Given elements a and b, the symbol (a, b) denotes the ordered pair consisting of a and b together with the specification that a is the first element of the pair and b is the second element. Two ordered pairs (a, b) and (c, d) are equal if, and only if, a = c and b = d. Symbolically: (a, b) = (c, d) means that a = c and b = d.
Definition
Given sets A and B, the Cartesian product of A and B, denoted A × B and read “A cross B,” is the set of all ordered pairs (a, b), where a is in A and b is in B. Symbolically:
\( A × B = \{(a, b)| a \in A \; and \; b \in B\} \)
The Universal Set: All sets under investigation in any application of set theory are assumed to belong to some fixed large set called the Universal set, denoted by: U.
The Empty Set or Null Set: A set with no elements. Denoted by: ∅ An example:
\(S = \{ x\, |\, x\, is\, a\, positive\, integer,\, x^2\, =\, 3\}\)
There is only one empty set, and the empty set is a subset of every other set.
Theorem
For any set \(A\), we have:
Disjoint Sets: Sets which have no elements in common.
1.3 Venn Diagrams
Venn Diagrams: Pictorial representation of sets in which sets are represented by enclosed areas in the plane. The universal set U is represented by the interior of a rectangle, and the other sets are represented by disks within the rectangle.
1.4 Set Operations
Union: The union of two sets is the set of all elements that belong to A or to B.
\(A \cup B = \{ x\,|\,x\,\in\,A\,or\,x\in\,B\}\)
Intersection: The intersection of two sets is the set of all elements that belong to both A and B.
\(A \cap B = \{ x\,|\,x\,\in\,A\,and\,x\in\,B\}\)
Theorem
For any set \(A\) and \(B\), we have:
Theorem
The following are equivalent:
Absolute Complement: The set of elements which belong to U but which do not belong to A
\(A^C = \{ x\,|\,x\,\in\,\mathbf{U},\,x\notin\,A\}\)
Relative Complement: The set of elements which belong to A but which do not belong to B, aka the difference of A and B. A\B is read as: "A minus B."
\( A \setminus B = \{ x | x \in A, x \notin B \} \)
Symmetric Difference: The set of elements which belongs to A or belongs to B, but which does not belong to both.
Fundamental Products
Consider n distinct sets \( A_1, A_2, \ldots, A_n \). A Fundamental Product of the sets is a set of the form:
\( A_1^*, \cap A_2^*, \cap \ldots \cap A_n^* \) where \( A_i^* = A \, or \, A_i^* = A^C \)
Fundamental Products
- There are \( m=2^n \) such fundamental products.
- Any two such fundamental products are disjoint.
- The Universal Set U is the Union of all fundamental products.
1.7 Classes Of Sets, Power Sets, Partitions
Given a set \(S\), we might wish to talk about some of its subsets. Thus we would be considering a set of sets. When such a situation occurs, to avoid confusion, we will speak of a class of sets or collection of sets rather than a set of sets. If we wish to condider some of the sets in a given class of sets, then we speak of a subclass or subcollection.
Example:
Suppose \( S = \{ 1,2,3,4 \} \).
-
$$ A = [ \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}] $$
- Let \(A\) be the class of subsets of \(S\) which contain exactly three elements of \(S\). Then That is, the elements of \(A\) are the sets \( \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \;and\; \{2,3,4\} \).
- Let \(B\) be the class of subsets of \(S\), each of which contains 2 and two other elements of \(S\). Then: $$ B=[\{ 1,2,3\}, \{ 1,2,4\}, \{2,3,4\}] $$ The elements of \(B\) are the sets \( \{ 1,2,3,\}, \{ 1,2,4,\}, \; and \; \{2,3,4\}\). Thus \(B\) is a subclass of \(A\), since every element of \(B\) is also an element of \(A\).
Power Sets
For a given set \(S\), we may speak of the class of all subsets of \(S\). This class is called the power set of \(S\), and will be denoted by \(P(S)\). If \(S\) is finite, then so is \(P(S)\). In fact, the number of elements in \(P(S)\) is 2 raised to the power \(n(S)\). That is, $$ n(P(S)) = 2^{n(S)} $$
( For this reason, the power set of \(S\) is sometimes denoted by \( 2^S \) )
Example:
Suppose \( S = \{ 1,2,3 \} \). Then: $$ P(S) = [ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, S] $$ Note that the empty set \( \emptyset \) belongs to \(P(S)\) since \( \emptyset \) is a subset of \(S\). Similarly, \(S\) belongs to \(P(S)\). As expected from the above remark, \(P(S)\) has \(2^3 = 8\) elements.
Partitions
Let \(S\) be a nonempty set. A partition of \(S\) is a subdivision of \(S\) into nonoverlapping, nonempty subsets, Precisely, a partition of S is a collection \({A_1}\) of nonempty subsets of \(S\) such that:
- Each \(a\) in \(S\) belongs to one of the \(A_i\).
- The sets of \(\{A_i\}\) are mutually disjoint; that is, if
$$ A_j \neq A_k \; then \; A_j \cap A_k = \emptyset $$ The subsets in a partition are called cells. The figure below is a Venn diagram of a partition of the rectangular set S of points into five cells, \(A_1, A_2, A_3, A_4, A_5, \).
Example:
Consider the following collection of subsets of \( S= \{1,2,\dots,8,9\}\):
- \( [ \{ 1,3,5\}, \{ 2,6\}, \{ 4,8,9\} ] \)
- \( [ \{ 1,3,5\}, \{ 2,4,6,8\}, \{ 5,7,9\} ] \)
- \( [ \{ 1,3,5\}, \{ 2,4,6,8\}, \{ 7,9\} ] \)
Then i. above is not a partition of \(S\) since 7 in \(S\) does not belong to any of the subsets. Furthermore, ii. is not a partition of \(S\) since \(\{1,3,5,\} \; and \; \{5,7,9\}\) are not disjoint. On the other hand iii. is a partition of \(S\).
Generalized Set Operations
The set operations of Union and Intersection were defined above for two sets. These operations can be extended to any number of sets, finite or infinite as follows.
Consider first a finite number of sets, say \( A_1, A_2, \dots, A_m \). The Union and Intersection of the sets in the collection A is denoted and defined, respectively, by: $$ A_1 \cup A_2 \cup \dots \cup A_m = \bigcup_{i=1}^m A_i = \{ x \; | \; x \in A_i \; for \; some \; A_i \} $$ $$ A_1 \cap A_2 \cap \dots \cap A_m = \bigcap_{i=1}^m A_i = \{ x \; | \; x \in A_i \; for \; every \; A_i \} $$
That is, the union consists of those elements which belong to at least one of the sets, and the intersection consists of those elements which belong to all of the sets.
Now let \(\mathscr{A}\) be any collection of sets. The union and the intersection of the sets in the collection \(A\) is denoted and defined, respectively, by:
$$ \bigcup \; (A \; | A \; \in \mathscr{A} ) = \{ x \; | \; x \in A_i \; for \; some \; A_i \in \mathscr{A} \} $$ $$ \bigcap \; (A \; | A \; \in \mathscr{A} ) = \{ x \; | \; x \in A_i \; for \; every \; A_i \in \mathscr{A} \} $$That is, the union consists of those elements which belong to at least one of the sets in the collection \(\mathscr{A}\) and the intersection consists of those elements which belong to every set in the collection.
Example:
Consider sets: $$ A_1 = \{ 1,2,3, \dots \}=\mathbf{N}, \quad A_2 = \{ 2,3,4, \dots \}, \quad A_3 = \{ 3,4,5, \dots \}, \quad A_n = \{ n,n+1,n+2, \dots \}. $$
Then the union and intersection of the sets are as follows: $$ \bigcup \; (A_k \; | \; k \; \in \mathbf{N} ) = \mathbf{N} \; and \; \bigcap \; (A_k \; | \; k \; \in \mathbf{N} ) = \emptyset $$
DeMorgan's laws also hold for the above generalized operations. That is:
Theorem
Let \(\mathscr{A}\) be a collection of sets. Then:
- \( [ \; \bigcup \; ( \; A \; | \; A \in \mathscr{A} ) \; ]^C = \bigcap \; ( A^C \; | \; A \in \mathscr{A} ) \)
- \( [ \; \bigcap \; ( \; A \; | \; A \in \mathscr{A} ) \; ]^C = \bigcup \; ( A^C \; | \; A \in \mathscr{A} ) \)