Set Theory

Instructor

Li Hui

Concepts of Sets

Definition and Representation of Sets

The concept of a set is one of the most fundamental concepts in mathematics. It is difficult to define precisely.

Simply put, a collection of objects grouped together as a whole is called a Set.

These objects are called Elements of the set; they can be concrete or abstract.

Example: All Chinese people, all study tools in a classroom, and all points in the coordinate plane each form a different set.

Sets are usually named with uppercase letters \(A, B, C, \cdots, Z\), and elements are denoted by lowercase letters \(a, b, c, \cdots, z\).

There are two ways to represent a set:

Roster Method (Enumeration)

List all elements of the set (or enough elements to reveal its pattern), separated by commas and enclosed in curly braces.

Examples:

  • \(A=\{a,b,c,d\}\)

  • \(B=\{2 ,4 ,6 ,8 ,\cdots, 2n ,\cdots \}\)

  • \(C=\{\{a,b\}, c, \{1,c\}\}\)

  • \(D=\{m_1, m_2, \cdots, m_n\}\)

  • \(E=\{\)light bulb, pencil, computer\(\}\)

Membership relation between an element and a set:

  • If \(a\) is an element of set \(S\), write \(a\in S\), read “\(a\) belongs to set \(S\)”.

  • If \(a\) is not an element of set \(S\), write \(a\notin S\), read “\(a\) does not belong to set \(S\)”.

Set-Builder Notation (Descriptive Method)

Describe the elements of the set using words or predicates.

\[A=\{x|P(x)\}\]

denotes the set \(A\) consisting of all \(x\) for which \(P(x)\) is true.

Examples:

  • \(P=\{y|y=a \vee y=b\}\)

  • \(Q=\{x|x\) is a prime number\(\}\)

  • \(R=\{x|x\) is an American\(\}\)

  • \(S =\{x|x\in R \wedge x^2=1\}\)

  • \(T=\{x|x\) is a prime less than 10\(\}\)

  • \(U=\{x|x\) is a positive odd number\(\}\)

Properties of Sets

Unorderedness: Within a set, every element has the same standing; elements are unordered.

Example: \(\{1, 2, 3, 4\}\) and \(\{1, 3, 2, 4\}\) are the same set.

Definiteness: Given a set, for any element, that element either belongs or does not belong to the set — one or the other must hold.

Example: Either \(x\in S\) or \(x\notin S\).

Distinctness: In a set, any two elements are distinct; each element can appear only once.

Example: \(\{1, 1, 2\}\) is the same as \(\{1,2\}\) and has only two elements.

There exist sets whose elements are themselves sets. Example: \[X=\{a, 3, \{s,2\}, \{t\}, 8\}\]

In such cases, it is essential to distinguish between the set \(\{a\}\) and the element \(a\).

In the example above, the set \(\{t\}\) is an element of set \(X\), i.e., \(\{t\}\in X\).

And \(t\) is an element of set \(\{t\}\), i.e., \(t\in\{t\}\). But \(t\) is not an element of \(X\), i.e., \(t\notin X\).

Special Sets

For a set \(A\), if it consists of finitely many elements, \(A\) is called a finite set; a set that is not finite is called an infinite set.

For a finite set \(A\), the number of distinct elements in \(A\) is called the cardinality of \(A\), denoted \(|A|\) or \(K(A)\).

If \(A\) contains \(m\) distinct elements, write \(|A|=m\), and \(A\) is called an \(m\)-element set.

Example: \(A=\{1,2,3,a,b,c\}\), \(|A|=6\); \(A\) is a 6-element set.

Commonly used set notation:

  • \(N\): Natural numbers \(N=\{0,1,2,\cdots\}\)

  • \(Z\): Integers \(Z=\{\cdots,-2,-1,0,1,2,\cdots\}\)

  • \(Z_{+}\): Positive integers \(Z_{+}=\{1,2,3,\cdots\}\)

  • \(Z_{-}\): Negative integers \(Z_{-}=\{\cdots,-3,-2,-1\}\)

  • \(P\): Prime numbers \(P=\{2,3,5,7,11,13,\cdots\}\)

  • \(Ev\): Even integers \(Ev=\{\cdots,-4,-2,0,2,4,\cdots\}\)

  • \(Od\): Odd integers \(Od=\{\cdots,-3,-1,1,3,\cdots\}\)

  • \(R\): Real numbers

  • \(C\): Complex numbers

  • \(Q\): Rational numbers

Relations Between Sets

Meaning of some logical symbols:

  • \(\vee\): or (disjunction)

  • \(\wedge\): and (conjunction)

  • \(\rightarrow\): if…, then… (implication)

  • \(\Leftrightarrow\): equivalent to (if and only if)

A set containing no elements is called the empty set, denoted \(\Phi\).

\[\Phi=\{x|x\neq x\}.\]

Example: \(\{x|x\in R\wedge x^2+1=0\}\) is the set of real solutions of the equation \[x^2+1=0.\] Since this equation has no real solutions, the solution set is empty.

Note: \(\Phi\) and \(\{\Phi\}\) are different sets.

\(\Phi\) is a set containing no elements, whereas \(\{\Phi\}\) is a set containing one element \(\Phi\), so \(\Phi\in\{\Phi\}\).

Let \(A,B\) be any two sets. If every element of \(A\) is also an element of \(B\), then \(A\) is called a subset of \(B\), or \(A\) is contained in \(B\), or \(B\) contains \(A\).

Written \(A\subseteq B\), or \(B\supseteq A\).

Symbolically: \(A\subseteq B \Leftrightarrow (x\in A \rightarrow x\in B)\)

Clearly, for any nonempty set \(S\), we have \(\Phi\subseteq S\) and \(S\subseteq S\).

\(\Phi\) and \(S\) are called the trivial subsets of \(S\).

Example: Let \(A=\{1,2,3\}\), \(B=\{5,9,\{5,9\}\}\), \(C=\{1,3\}\), \(D=\{5,9\}\),

then: \(C\subseteq A\), \(D\subseteq B\).

In this example, \(D\) is both a subset and an element of \(B\), i.e., \(D\subseteq B\) and \(D\in B\).

Let \(A\), \(B\) be two sets. If \(A\subseteq B\) and \(A\neq B\), then \(A\) is called a proper subset of \(B\), written \(A\subset B\).

Example: The set of even integers is a proper subset of the integers (\(Ev\subset Z\)); the integers are a proper subset of the reals \((Z\subset R)\).

Example: Let \(A=\{1, 2, 3\}\), \(B=\{1, 2\}\), \(C=\{1, 3\}\), \(D=\{3\}\).

Then \(B\subset A, C\subset A, D\subset A, D\subset C\).

Theorem: The empty set is a subset of every set.

Proof (by contradiction).

Suppose there exists a set \(A\) such that \(\Phi\) is not a subset of \(A\); then there is at least one element \(x\) with \(x\in\Phi\) and \(x\notin A\).

But the empty set \(\Phi\) contains no elements, so the assumption is false.

Theorem: The empty set is unique.

Proof (by contradiction).

Suppose there are two empty sets \(\Phi_1\) and \(\Phi_2\).

Since the empty set is a subset of every set, we have \(\Phi_1\subseteq\Phi_2\) and \(\Phi_2\subseteq\Phi_1\), hence \(\Phi_1 = \Phi_2\).

Axiom of Extensionality (Zermelo–Fraenkel Axiom): If sets \(A\) and \(B\) have exactly the same elements, then \(A\) and \(B\) are equal, written \(A=B\).

If \(A\) and \(B\) are not equal, write \(A{\neq}B\).

Equality of two sets can be proved by showing mutual inclusion.

\[A=B{\Leftrightarrow}A{\subseteq}B{\wedge} B{\subseteq}A\]

Example: Let \(A=\{3, 6, 9\}\), \(B=\{6, 3, 9\}\), \(C=\{3, \{6\}, 9\}\); then \(A=B\), \(A{\neq}C\).

For any sets \(A\), \(B\), and \(C\):

  • \(A{\subseteq}A\). \(\subseteq\) is reflexive (Reflexivity).

  • If \(A{\subseteq}B\) and \(B{\subseteq}A\), then \(A=B\). \(\subseteq\) is antisymmetric (Antisymmetric).

  • If \(A{\subseteq}B\) and \(B{\subseteq}C\), then \(A{\subseteq}C\). \(\subseteq\) is transitive (Transitivity).

Given a set \(A\), the set whose elements are all the subsets of \(A\) is called the power set of \(A\), denoted \(P(A)\) or \(2^A\). That is: \(P(A)=\{x|x{\subseteq}A\}\)

Example: Let \(A=\{1,2,3\}\), \(B=\{a,b\}\), \(C=\{\Phi\}\). Find the power sets of \(A\), \(B\), and \(C\).

Solution:

\(P(A)=\{\Phi, \{1\}, \{2\}, \{3\},\{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\)

\(P(B)=\{\Phi, \{a\}, \{b\}, \{a,b\} \}\)

\(P(C)=\{\Phi, \{\Phi\}\}\)

Power set of the empty set \(\Phi\): \(P(\Phi)=\{\Phi\}\).

Theorem: If a finite set \(A\) has \(n\) elements, then its power set \(P(A)\) has \(2^n\) elements.

Proof: From set \(A\):

The number of subsets choosing 0 elements is \(C_n^0\)

The number of subsets choosing 1 element is \(C_n^1\)

The number of subsets choosing 2 elements is \(C_n^2\)

\(\cdots\cdots\) 

The number of subsets choosing \(n\) elements is \(C_n^n\)

 

\(C_n^0+C_n^1+C_n^2+\cdots+C_n^n=2^n\)

If all elements of a set \(A\) are themselves sets, \(A\) is called a family of sets. A power set is a family of sets.

\(A=\{ \{1,2\}, \{a\}, \{\)Tom, tiger, 10\(\} \}\) is a family of sets.

Given a set, if all sets under discussion are its subsets, that set is called the universal set. Denoted \(U\).

The universal set is a relative concept; it changes depending on the problem being studied.

Example: When studying lines in the plane, all point coordinates in the plane can serve as the universal set.

Example: When studying integer problems, the universal set can be \(Z\), \(Q\), or \(R\).

In general, the universal set should be chosen as small as possible to simplify description and analysis.

Let \(A\), \(B\) be any two sets. The intersection \(A\cap B\), union \(A\cup B\), relative complement \(A-B\) (of \(B\) from \(A\)), and symmetric difference \(A\bigoplus B\) are defined as follows:

  • \(A\cap B=\{x|x\in A\wedge x\in B\}\)

  • \(A\cup B=\{x|x\in A\vee x\in B\}\)

  • \(A-B=\{x|x\in A\wedge x\notin B\}\)

  • \(A\bigoplus B=(A-B)\cup (B-A)=\{x|(x\in A\wedge x \notin B)\vee (x\in B\wedge x \notin A\}\)

Let \(A=\{a,b,c,d\}\), \(B= \{e,f,a,d\}\). Find: \(A\cap B\), \(A\cup B\), \(A-B\), \(A\bigoplus B\).

Solution: \(A\cap B=\{a,d\}\), \(A\cup B=\{a,b,c,d,e,f\}\), \(A-B=\{b,c\}\), \(B-A=\{e,f\}\), \(A\bigoplus B= \{ b,c,e,f\}\)

Definition: Let \(U\) be the universal set and \(A\) be any subset of \(U\). \(U-A\) is called the absolute complement of \(A\), denoted \(\sim A\) or \(A^c\).

\(\sim A=U- A= \{ x|x\in U\wedge x\notin A\}\)

From the definition of the absolute complement: If \(x{\notin}A\), then \(x\in{\sim}A\); if \(x{\in}A\), then \(x\notin{\sim}A\).

Example: Let \(U=\{0, 1, 2, 3\}\), \(A=\{1, 2, 3\}\), \(B=\{0, 1, 2, 3\}\), \(C=\Phi\). Find \(\sim A, \sim B, \sim C\).

Solution: \[\sim A=\{0\},\,\,\sim B=\Phi,\,\,\sim C=\{0,1,2,3\}.\]

Venn Diagrams

When a set has few elements, Venn diagrams can be used to visualize relationships between sets and the results of set operations.

In a Venn diagram, the universal set \(U\) is typically represented by a rectangle. Inside the rectangle, circles (or other closed curves) represent sets; different circles represent different sets.

Venn diagrams for 2, 3, and 4 sets

Sets \(A\), \(B\) partition the universal set \(U\) into 4 subsets \(m_0\), \(m_1\), \(m_2\), \(m_3\), called minterms.

\[A{\cap}B = m_3\] \[A{\cup}B = m_1{\cup}m_2{\cup}m_3\]

\[A-B=m_2\] \[B-A = m_1\]

\[A{\oplus}B = m_1{\cup}m_2\]

\[{\sim}A= m_0{\cup}m_1\]

\[{\sim}B=m_0{\cup}m_2\]

Any two minterms have empty intersection, so \[m_i\cup m_j = m_i\oplus m_j\]

Minterms

Let \(A\), \(B\) be any sets. The following rules generate set formulas.

  • A set \(A\) is a set formula.

  • If \(A\) is a set formula, then \({\sim}A\) is also a set formula.

  • If \(A,B\) are set formulas, then \((A{\cup}B)\), \((A{\cap}B)\), \((A-B)\), \((A{\oplus}B)\) are also set formulas.

  • Any formula obtained by finitely many applications of the above rules is a set formula.

To reduce the use of parentheses, the outermost parentheses of a set formula are sometimes omitted.

Examples: \[(A{\cup}B){\cap}C, \,\, (A{\oplus}B){\cap}(B-C), \,\, (B{\oplus}D)\oplus((B-C)-D)\]

are all set formulas.

Set Identities

Some fundamental set identities (set laws), where \(A,B,C\) are arbitrary subsets of the universal set \(U\).

  • Idempotent Laws

\[A\cup A=A, \, A\cap A=A\]

  • Commutative Property

\[A\cup B=B\cup A\]

\[A\cap B=B\cap A\]

\[A\oplus B=B\oplus A\]

  • Associative Property

\[(A\cup B)\cup C=A\cup(B\cup C)\]

\[(A\cap B)\cap C=A\cap(B\cap C)\]

\[(A\oplus B)\oplus C=A\oplus(B\oplus C)\]

  • Distributive Property

\[A\cup(B\cap C) = (A\cup B)\cap(A\cup C)\]

\[A\cap(B\cup C) = (A\cap B)\cup(A\cap C)\]

\[A\cap(B-C)=(A\cap B)-(A\cap C)\] Note:

\[A\cup(B-C)\neq(A\cup B)-(A\cup C)\]

\[A\cup(B-C)=(A\cup B)-(C-A)\]

  • Identity

\[A\cup\Phi=A, \, A\cap U=A\]

\[A-\Phi=A, \, A\oplus\Phi=A\]

  • Domination Laws

\[A\cup U=U, \, A\cap\Phi=\Phi\]

  • Complement

\[A\cup\sim A=U, \, A\cap\sim A=\Phi\]

\[\sim U=\Phi, \, \sim\Phi=U\]

  • Absorption Laws

\[A\cup(A\cap B)=A\] \[A\cap(A\cup B)=A\]

  • De Morgan’s Laws

\[\sim(A\cup B)=\sim A\cap\sim B\]

\[\sim(A\cap B)=\sim A\cup\sim B\]

\[A-(B\cup C)=(A-B)\cap(A-C)\]

\[A-(B\cap C)=(A-B)\cup(A-C)\]

  • Double Complement

\[\sim(\sim A)=A\]

  • \(A\oplus A=\Phi, \, A-A=\Phi\)

  • \(A\cap B\subseteq A, \, A\cap B\subseteq B\)

  • \(A\subseteq A\cup B,\, B\subseteq A\cup B\)

  • \(A-B\subseteq A,\, A-B=A\cap\sim B\)

  • \(A\oplus B=(A-B)\cup(B-A)=(A\cup B)-(A\cap B)=(A\cap\sim B)\cup(\sim A\cap B)\)

Since intersection and union of sets satisfy the associative law, multiple intersections or unions can be written as:

\[S_1\cap S_2\cap \cdots \cap S_n=\bigcap_{i=1}^n{S_i}\]

\[S_1\cup S_2\cup \cdots \cup S_n=\bigcup_{i=1}^n{S_i}\]

Let \[S_1=\{3,c\},\,\, S_2=\{a,c\},\,\,S_3=\{c,2\},\,\, S_4=\{c,3\}\]

Then \[\bigcap_{i=1}^4{S_i}=\{c\}\] \[\bigcup_{i=1}^4{S_i}=\{a,c,2,3\}\]

The set identities above can be proved in three ways:

  • Direct Definition Method

  • Venn Diagram Method

  • Algebraic Derivation Method

Example: For any two sets \(A\), \(B\), prove that \(A-B=A\cap{\sim}B\).

Proof (Direct Definition Method): We prove that \(A-B\) and \(A\cap{\sim}B\) contain each other.

For any \(x\), if \(x{\in}A-B\), then \(x{\in}A\wedge x{\notin}B\), that is \(x{\in}A{\wedge}x\in{\sim}B\), so \(x{\in}A\cap{\sim}B\).

Therefore \(A-B\subseteq A\cap\sim B\).

Conversely, for any \(x\), if \(x{\in}A\cap{\sim}B\), then \(x{\in}A{\wedge}x\in{\sim}B\), that is \(x{\in}A{\wedge}x{\notin}B\).

So \(x{\in}A-B\), hence \(A\cap{\sim}B{\subseteq}A-B\).

Therefore \(A-B=A\cap{\sim}B\). \(\square\)

(Venn Diagram Method)

\[A=m_2\cup m_3\]

\[\sim B=m_0\cup m_2\]

\[ A\cap\sim B= m_2\]

\[ A-B = m_2\]

Therefore \(A-B=A\cap\sim B\).

Minterms

Prove the associative law \[(A\cap B)\cap C=A\cap (B\cap C).\]

Proof (Direct Definition Method).

For any \(x\), if \(x\in(A\cap B)\cap C\), then \[x\in (A\cap B)\wedge (x\in C),\] \[(x\in A\wedge x\in B)\wedge (x\in C),\] \[x\in A\wedge (x\in B\wedge x\in C),\] \[x\in A\wedge x\in (B\cap C),\] \[x\in A\cap (B\cap C),\] \[(A\cap B)\cap C \subseteq A\cap (B\cap C)\]

Conversely, for any \(x\), if \(x\in A\cap (B\cap C)\), then \[x\in A\wedge x\in (B\cap C),\] \[x\in A\wedge (x\in B\wedge x\in C),\] \[(x\in A\wedge x\in B)\wedge (x\in C),\] \[x\in (A\cap B)\wedge (x\in C),\] \[x\in (A\cap B)\cap C,\] \[A\cap (B\cap C)\subseteq(A\cap B)\cap C\] Therefore \[(A\cap B)\cap C=A\cap (B\cap C)\]

Prove: \((A\cap B)\cap C=A\cap (B\cap C).\)

(Venn Diagram Method)

\[A= m_3\cup m_5\cup m_6\cup m_7\] \[C= m_1\cup m_4\cup m_5\cup m_7\] \[A\cap B = m_6\cup m_7,\] \[B\cap C= m_4\cup m_7\] \[(A\cap B)\cap C= (m_6\cup m_7 )\cap (m_1\cup m_4\cup m_5\cup m_7 )= m_7\] \[A\cap (B\cap C)=(m_3\cup m_5\cup m_6\cup m_7 )\cap (m_4\cup m_7 ) = m_7\] \[\therefore\,\,(A\cap B)\cap C=A\cap (B\cap C)\]

Let \(A\subseteq B\), \(C\) be any set. Prove: \[A\cap C\subseteq B\cap C.\]

Proof: Since \(A\subseteq B\), if \(x\in A\) then \(x\in B\).

If \(x\in A\cap C\), then \(x\in A\wedge x\in C\), so

\[x\in B \wedge x\in C.\] \[x\in B\cap C.\] Therefore \(A\cap C\subseteq B\cap C.\)

Let \(A\subseteq B\), \(C\subseteq D\). Prove: \[A\cup C\subseteq B\cup D.\]

Proof: Take any \(x\in A\cup C\). By definition of union:

\(x\in A\) or \(x\in C.\)

If \(x\in A\), then since \(A\subseteq B\), we have \(x\in B\), so \(x\in B\cup D\).

If \(x\in C\), then since \(C\subseteq D\), we have \(x\in D\), so \(x\in B\cup D\).

Therefore \(A\cup C\subseteq B\cup D.\)

Prove: \(A\subseteq B\) if and only if \(A\cup B = B.\)

Proof:

(Necessity) Suppose \(A\subseteq B\); then for \(x\in A\), we must have \(x\in B\).

If \(x\in A\cup B\), then \(x\in A\) or \(x\in B\).

In either case \(x\in B\), so \(A\cup B\subseteq B\).

Since \(B\subseteq A\cup B\), we get \(A\cup B=B\).

(Sufficiency) If \(A\cup B=B\), since \(A\subseteq A\cup B\), we have \(A\subseteq B\).

 

Set identities can also be proved using the algebraic derivation method.

Prove the distributive law: \(A\cap (B-C)=(A\cap B)-(A\cap C)\).

Proof: \(A\cap (B-C)=A\cap (B\cap \sim C)=A\cap B\cap \sim C\)

Also \[\begin{gather} (A\cap B)-(A\cap C)\\ =(A\cap B)\cap \sim (A\cap C)\\ =(A\cap B)\cap (\sim A\cup \sim C)\\ =(A\cap B\cap \sim A)\cup (A\cap B\cap \sim C)\\ =\Phi\cup (A\cap B\cap \sim C)\\ =A\cap B\cap \sim C\\ \end{gather}\] Therefore \(A\cap (B-C)=(A\cap B)-(A\cap C).\)

Prove the absorption law: \(A\cup (A\cap B)=A.\)

Proof: \[\begin{gather} A\cup (A\cap B)\\ =(A\cap U)\cup (A\cap B)\\ =A\cap (U\cup B)\\ =A\cap U\\ =A \end{gather}\]

Prove the distributive law: \(A\cap (B\cup C)=(A\cap B)\cup (A\cap C).\)

Proof: \[\begin{gather} x\in A\cap (B\cup C)\\ \Leftrightarrow x\in A\wedge x\in (B\cup C)\\ \Leftrightarrow x\in A\wedge (x\in B\vee x\in C)\\ \Leftrightarrow (x\in A\wedge x\in B)\vee (x\in A\wedge x\in C)\\ \Leftrightarrow (x\in A\cap B)\vee (x\in A\cap C)\\ \Leftrightarrow x\in (A\cap B)\cup (A\cap C) \end{gather}\] Therefore \(A\cap (B\cup C)=(A\cap B)\cup (A\cap C).\)

Prove the commutative law: \(A\cap B=B\cap A.\)

Proof: \[\begin{gather} x\in A\cap B\\ \Leftrightarrow x\in A\wedge x\in B\\ \Leftrightarrow x\in B\wedge x\in A\\ \Leftrightarrow x\in B\cap A \end{gather}\] Therefore \(A\cap B=B\cap A.\)

Prove the associative law: \((A\cap B)\cap C=A\cap (B\cap C).\)

Proof: \[\begin{gather} x\in (A\cap B)\cap C\\ \Leftrightarrow x\in (A\cap B)\wedge (x\in C)\\ \Leftrightarrow (x\in A\wedge x\in B)\wedge (x\in C)\\ \Leftrightarrow (x\in A)\wedge (x\in B\wedge x\in C)\\ \Leftrightarrow (x\in A)\wedge x\in (B\cap C)\\ \Leftrightarrow x\in A\cap (B\cap C) \end{gather}\]

Therefore \((A\cap B)\cap C=A\cap (B\cap C).\)

Similarly \((A\cup B)\cup C=A\cup (B\cup C)\) can be proved.

Prove the idempotent law: \(A\cup A=A.\)

Proof: \[\begin{gather} x\in A\cup A\\ \Leftrightarrow x\in A\vee x\in A\\ \Leftrightarrow x\in A \end{gather}\] Therefore \[A\cup A=A.\]

Prove De Morgan’s Law: \(\sim (A\cup B)=\sim A\cap \sim B.\)

Proof: \[\begin{gather} \sim (A\cup B)=\{x|x\in \sim (A\cup B)\}\\ =\{x|x\notin(A\cup B)\}\\ =\{x|(x\notin A)\wedge (x\notin B)\}\\ =\{x|(x\in \sim A)\wedge (x\in \sim B)\}\\ =\sim A\cap \sim B \end{gather}\]

Let \(A\), \(B\) be any two sets with \(A\subseteq B\). Prove:

\(\sim B\subseteq \sim A\), \((B-A)\cup A=B\)

Proof:

If \(x\in A\), then \(x\in B\).

Therefore, \(x\notin B\) implies \(x\notin A\).

Hence \(x\in \sim B\) implies \(x\in \sim A\).

That is, \(\sim B\subseteq \sim A.\)

\[\begin{gather} (B-A)\cup A\\ =(B\cap \sim A)\cup A\\ =(B\cup A)\cap (\sim A\cup A)\\ =(B\cup A)\cap U\\ =B\cup A \end{gather}\] Since \(A\subseteq B\), we have \(B\cup A=B\).

Therefore \[(B-A)\cup A=B.\]

Basic Counting Principles

Counting is a frequently encountered problem in mathematics. Many combinatorial problems involve counting; sometimes the objects to be considered are very numerous, and we wish to count the elements of a set without listing them all.

This section introduces two basic counting principles: the Addition Principle and the Multiplication Principle.

Theorem (Addition Principle): Suppose there are \(k\) sets, where the first contains \(n_1\) elements, the second contains \(n_2\) elements, and so on.

If all elements are distinct (i.e., the \(k\) sets are pairwise disjoint), then the total number of elements that can be chosen from these sets is: \[n_1+ n_2+\cdots + n_k\]

Example: A student may choose 1 elective course from 3 categories, containing 5, 11, and 9 courses respectively. How many ways can the student choose?

Solution: The student has 5 choices from category 1, 11 from category 2, and 9 from category 3. Therefore, there are \(5+11+9=25\) ways to select a course.

The Addition Principle states: the whole equals the sum of its parts.

Example: How many integers between 1 and 100 (inclusive) are either even or end in 5?

Solution: Let \(A\) be the set of even integers from 1 to 100, and \(B\) the set of integers from 1 to 100 ending in 5. Since \(A\) and \(B\) are disjoint, \(A\cup B\) is the desired set.

\(|A|=50\), \(|B|=10\), so there are \(50+10=60\) integers that are even or end in 5.

Theorem (Multiplication Principle): Suppose a task requires \(k\) steps to complete. If step 1 can be done in \(n_1\) ways, step 2 in \(n_2\) ways, and step \(i\) (\(i=3,4,\cdots,k\)) in \(n_i\) ways,

then the total number of different ways to complete the entire task is: \[n_1 n_2\cdots n_k.\]

Example: An identifier consists of 2 characters: the first character is one of \(a,b,c,d,e\), and the second is one of 1, 2, 3. How many different identifiers are there?

Solution: Step 1: Choose a character from \(a,b,c,d,e\) — 5 ways. Step 2: Choose a character from 1, 2, 3 — 3 ways. By the Multiplication Principle, there are \(5\times 3=15\) different identifiers.

Prove: A set with \(n\) elements has \(2^n\) subsets.

Proof: Let the set be \(X=\{x_1,x_2,\cdots x_n\}\).

Constructing a subset can be done in \(n\) steps: include or exclude \(x_1\), include or exclude \(x_2\), \(\cdots\), include or exclude \(x_n\). Each step has 2 choices, so the total number of possible subsets is: \[2\times 2\times\cdots\times 2\times 2=2^n.\]

Counting problems can be solved using either (or both) of these principles.

Example: Let \(A\), \(B\), \(C\) be 3 cities. There are 3 roads from \(A\) to \(B\), 4 roads from \(B\) to \(C\), and 5 roads directly from \(A\) to \(C\). How many different ways are there to travel from \(A\) to \(C\)?

Solution: \[3\times 4+5=17.\]

Inclusion-Exclusion Principle

Let \(A_1,A_2\) be finite sets. The following are clearly true:

\(|A_1\cup A_2|\leq |A_1|+|A_2|\)

\(|A_1\cap A_2|\leq min(|A_1|,|A_2|)\)

\(|A_1-A_2|\ge |A_1|-|A_2|\)

\(|A_1\oplus A_2|=|A_1|+|A_2|-2|A_1\cap A_2|\)

\(|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|\)

These formulas can be derived from Venn diagrams.

The last formula is called the Inclusion-Exclusion Principle. The Inclusion-Exclusion Principle concerns counting problems involving unions and intersections of finite sets.

Example: Among 10 young people, 5 are from Beijing and 7 are students, with 3 being both from Beijing and students. How many are neither from Beijing nor students?

Solution: Let \(U\): set of all young people, \(A\): set of students, \(B\): set of people from Beijing. \(|U|=10\), \(|A|=7\), \(|B|=5\), then:

\(A\cup B\): set of people who are students or from Beijing.

\(\sim (A\cup B)\): set of people who are neither students nor from Beijing.

\(A\cap B\): set of people who are both students and from Beijing. \(|A\cap B|=3\).

Then \(|A\cup B|=|A|+|B|-|A\cap B|=7+5-3=9\).

So \(|\sim (A\cup B)|=|U|-| A\cup B |=10-9=1\).

That is: there is 1 young person who is neither from Beijing nor a student.

The Inclusion-Exclusion Principle can be extended to multiple sets.

For finite sets \(A\), \(B\), \(C\): \[|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B \cap C|.\] Theorem: For finite sets \(A_1,A_2,A_3,\cdots,A_n\), \[\biggl|\bigcup_{i=1}^n A_i\biggr| = \sum_{i=1}^n\left|A_i\right|\; -\sum_{1 \le i < j \le n}\left|A_i\cap A_j\right|\; + \sum_{1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|\;-\ \cdots\ +\; \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.\]

Example: A university has 38 soccer team members, 15 basketball team members, and 20 baseball team members, for a total of 58 athletes. Exactly 3 athletes are on all three teams. How many athletes are on exactly two teams?

Solution: Let \(A\): soccer players, \(B\): basketball players, \(C\): baseball players. \(|A|=38\), \(|B|=15\), \(|C|=20\), \(|A\cup B\cup C|=58\), \(|A\cap B\cap C|=3\) \[|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B \cap C|\]

\[58=38+15+20-(|A\cap B|+|A\cap C|+|B\cap C|)+3\] \[|A\cap B|+|A\cap C|+|B\cap C|=73+3-58=18\] Since \(|A\cap B\cap C|=3=|m_7|\): \[|A\cap B|=|m_6|+|m_7|,|A\cap C|=|m_5|+|m_7|,|B\cap C|=|m_4|+|m_7|\] \[|A\cap B|+|A\cap C|+|B\cap C|=|m_6|+|m_5|+|m_4|+3\times|m_7|\]

The number of athletes on exactly two teams is \(|m_6|+|m_5|+|m_4|+|m_7|=18-3-3=12\).

Pigeonhole Principle

The Pigeonhole Principle (also known as the Drawer Principle) is an important principle in discrete mathematics. Named after the German mathematician Peter Gustav Lejeune Dirichlet (1805–1855), it is often called Dirichlet’s Drawer Principle. The Pigeonhole Principle is mainly used to prove existence or inevitability results, and has wide applications in number theory, combinatorics, and set theory.

If a flock of pigeons flies into pigeonholes and there are more pigeons than holes, then at least one hole must contain 2 or more pigeons — this is the Pigeonhole Principle.

Theorem (Pigeonhole Principle): If \(n+1\) (\(n\) a positive integer) or more objects are placed into \(n\) drawers, then at least one drawer contains 2 or more objects.

Proof: Suppose no drawer contains more than 1 object; then the total number of objects is at most \(n\), contradicting the assumption that there are at least \(n+1\) objects.

Example: What is the minimum number of elements to choose from \(S = \{1,2,3,4,5,6,7,8,9\}\) to guarantee that two chosen numbers sum to 10?

Solution: Partition 1–9 into 5 groups (pigeonholes):

\(\{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\}\)

By the Pigeonhole Principle, any 6 chosen numbers must include two from the same group, and those two sum to 10.

 

Example: Among any 8 positive integers, when each is divided by 7, at least two have the same remainder. Explain why.

Solution: Any positive integer divided by 7 has one of 7 possible remainders: 0 through 6.

So, with 8 integers divided by 7, place each in the drawer numbered by its remainder (drawer 0 for remainder 0, drawer 1 for remainder 1, …, drawer 6 for remainder 6). With 8 objects and 7 drawers, at least one drawer holds 2 integers, which therefore have the same remainder when divided by 7.

Generalized Pigeonhole Principle

Theorem (Generalized Pigeonhole Principle): If \(n\) drawers are occupied by \(kn+1\) or more objects (\(n,k\) positive integers), then at least one drawer contains \(k+1\) or more objects.

Proof (by contradiction): Assume no drawer holds more than \(k\) objects; then the total is at most \(kn < kn+1\), contradicting the assumption.

The Generalized Pigeonhole Principle can also be stated as: If \(m\) objects are placed into \(n\) drawers, then at least one drawer contains at least \(\lceil m/n \rceil\) objects.

A common type of problem is: given \(m\) objects distributed among \(n\) drawers such that some drawer contains at least \(r\) objects, find the minimum value of \(m\).

Example: What is the minimum number of students in a class needed to guarantee that at least 3 were born in the same month?

Solution: Here \(n=12\) months are the pigeonholes, and \(k+1=3\), so \(k=2\). Therefore, among \(kn+1=25\) students, at least 3 are born in the same month.

 

Example: How many cards must be drawn from a standard 52-card deck to guarantee that at least 3 are of the same suit?

Solution: Suppose there are 4 drawers (\(n=4\)), one per suit, and each drawn card is placed in its suit’s drawer. By the Generalized Pigeonhole Principle, if \(m\) cards are drawn, at least one drawer contains at least \(\lceil m/4 \rceil\) cards.

For \(\lceil m/4 \rceil\ge 3\), we need at least 3 cards of the same suit. The smallest positive integer \(m\) satisfying this is \(m=2\times 4+1=9\).

Therefore, drawing 9 cards guarantees at least 3 of the same suit.

Example: Among any \(n+1\) distinct positive integers each at most \(2n\), there must exist two that are coprime.

Proof: First show that any two consecutive positive integers are coprime.

By contradiction, assume \(n\) and \(n+1\) share a common factor \(q\ge 2\); then \(n=qp_1\) and \(n+1=qp_2\), so \(q(p_2-p_1)=1\), contradicting \(q\ge 2\) and \(p_2-p_1\) being an integer. Therefore, any two consecutive positive integers are coprime.

Now partition \(1,2,3,\cdots,2n\) into the following groups:

\(\{1,2\},\{3,4\},\cdots,\{2n-1,2n\}\)

Choosing any \(n+1\) numbers from these \(n\) groups, by the Pigeonhole Principle at least two come from the same group; they are consecutive integers and therefore coprime.