# Discrete Mathematics

## Chapter 1 Set Theory

### 1.1 Variables and Statements

A Variable is a placeholder for something which:

1. has one or more values but you don’t know what they are

Is there a number x with the property that 2x + 3 = x2?

2. is equally true for all elements in a given set, and so you don’t want to be restricted to considering only a particular, concrete value for it.

No matter what number n might be chosen, if n is greater than 2, then n2 is greater than 4.

Statement: A universal declarative sentence which is either true or false.

##### Requirements of a Statement
• Sentence - It must be a grammatically legal sentence.
• Declarative - It must declare something. A question is not a statement.
• Universal - It must have some inherent and verifiable meaning to it.
• Truth Value - It must be analyzed to have either true or false value. It cannot assume both or neither of the values concurrently.

Universal Statement: says that a certain property is true for all elements in a set. Proving universal statements require us to test against all elements of the set, however even a single exception to the statement is enough to disprove it.
(Look For The Terms: "All" or "For All")

All positive numbers are greater than zero.

Conditional Statement: says that if one thing is true then some other thing also has to be true.
(Look For The Terms: "If-Then")

(If 378 is divisible by 18, then 378 is divisible by 6.)

Existential Statement: Given a property that may or may not be true, there is at least one thing for which the property is true. We only need to find one element that satisfies an Existential Statement in order to prove it.
(Look For The Term: "There Exists")

There is a prime number that is even.

There exists a natural number n, such that n x n = 36, or to put it another way:

∃ n ∈ ℕ, ∋ n.n = 36 (mouse over for explanation)

There exists an integer z, such that z2=25

There is at least one number n, belonging to a set of Natural numbers, such that a x n = a

Universal Conditional Statement: A statement that is both Universal and Conditional.

For all animals a, if a is a dog, then a is a mammal.

Existential Universal Statement: A statement that is universal because its first part says that a certain property is true for all objects of a given type, and it is existential because its second part asserts the existence of something.

Every real number has an additive inverse.

### 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
1. $$a \in S$$ denotes that $$a$$ belongs to a Set $$S$$
2. $$a, b \in S$$ denotes that $$a$$ and $$b$$ belong to a Set $$S$$
3. $$\in$$ is the symbol meaning "is an element of."
4. $$\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:

$$\{x \in S\,|\,P(x)\}$$

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.

• 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
1. 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?
2. Is $$\{0\} = 0$$?
3. How many elements are in the set $$\{1, \{1\}\}$$?
4. For each nonnegative integer n, let $$Un_ = \{n,−n\}$$. Find $$U_1$$, $$U_2$$, and $$U_0$$.
##### Solutions: Using the Set-Roster Notation
1. 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.
2. {0} ≠ 0 because {0} is a set with one element, namely 0, whereas 0 is just the symbol that represents the number zero.
3. The set {1, {1}} has two elements: 1 and the set whose only element is 1.
4. $$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
1. $$A \subseteq A$$
2. If $$A \subseteq B$$ and $$B \subseteq A$$, then A = B
3. 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:

1. $$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.

$$A \oplus B = (A \cup B) \setminus (A \cap B)$$ or $$A \oplus B = (A \setminus B) \cup (B \setminus A)$$

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
1. There are $$m=2^n$$ such fundamental products.
2. Any two such fundamental products are disjoint.
3. The Universal Set U is the Union of all fundamental products.

### 1.5 Algebra Of Sets, Duality

Each law in the table above follows from an equivalent logical law. Consider, for example, the proof of DeMorgan's law (10a):

$$(A \cup B)^C = \{ x | x \notin (A or B)\} = \{ x | x \notin A \; and \; x \notin B \} = A^C \cap B^C$$

Here we use the equivalent (DeMorgan's) logical law:

$$\neg (p \lor q) = \neg p \land \neg q$$

Duality

If $$E$$ is an equation in set algebra, the dual of $$E$$, $$E^*$$ is the equation obtained by replacing each occurence of $$\cup, \cap, \mathbf{U}$$, and $$\emptyset$$ in $$E$$ by $$\cap, \cup, \emptyset$$, and $$\mathbf{U}$$, respectively. For example, the dual of:

$$(\mathbf{U} \cap A) \cup (B \cap A) = A$$

is:

$$( \emptyset \cup A ) \cap ( B \cup A ) = A$$

The Duality Principle of set Algebra states that if an equation $$E$$ is an identity, its dual $$E^*$$ is also an identity.

### 1.6 Finite Sets, Counting Principle

Finite Sets, Counting Principle

A set S is said to be finite if S is empty or if S contains exactly m elements where m is a positive integer; otherwise S is infinite. S is countable if S is finite or if the elements of S can be arranged as a sequence, in which case S is said to be countably infinite; otherwise S is said to be uncountable. The set of even positive integers is countably infinite, whereas the unit interval I = [0, 1] is uncountable.

##### Examples:
1. The set A of the letters of the English alphabet and the set D of the days of the week are finite sets. Specifically, A has 26 elements and D has 7 elements.
2. Let E be the set of even positive integers, and let I be the unit interval, that is: $$E = \{2,4,6,\dots\} \; and \: \mathbf{I} = [0,1]= \{ x \; | \; 0 \le x \le 1 \}$$ Then both $$E$$ and I are infinite.

A set $$S$$ is countable if $$S$$ is finite or if the elements of $$S$$ can be arranged as a sequence, in which case $$S$$ is said to be countably infinite; otherwise $$S$$ is said to be uncountable. The above set $$E$$ of even integers is countably infinite, whereas one can prove that the unit interval $$\mathbf{I} = [0,1]$$ is uncountable.

Counting Elements in Finite Sets

$$n(S) or |S|$$ donotes the number of elements in a set.

##### Lemma:

Suppose $$A$$ and $$B$$ are finite disjoint sets. Then $$A \cup B$$ is finite and

1. $$n(A \cup B) = n(A) + n(B)$$ if S is the Disjoint Union of A and B:
2. $$n(S) = n(A) + n(B)$$
##### Corollary:

Let $$A$$ and $$B$$ be finite sets. Then

##### Corollary:

Let $$A$$ be a subset of a finite universal set U. Then

##### Theorem: Inclusion-Exclusion Principle

Suppose $$A$$ and $$B$$ are finite sets. Then $$A \cup B$$ and $$A \cap B$$ are finite and

##### Corollary:

Suppose $$A$$, $$B$$, and $$C$$ are finite sets. Then $$A \cup B \cup C$$ is finite and

$$n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(A \cap C) - n(B \cap C) + n(A \cap B \cap C)$$

##### Example:

Suppose a list $$A$$ contains the 30 students in a mathematics class $$n(A) = 30$$, and a list B contains the 35 students in an English class $$n(B) = 30$$, and suppose there are 20 names on both lists $$n(A \cap B = 20)$$. Find the number of students:

1. only on list A

Remember: $$n(A \setminus B) = n(A) - n( A \cap B)$$

2. only on list B
3. on list A or B (or both)

Remember: $$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

4. on exactly one list

Remember: $$n(A \oplus B) = n(A \setminus B) + n(B \setminus A)$$

##### Solution:
1. Question a. is asking for the number of elements in the Relative Complement of $$(A \setminus B$$). If there are 30 names on list A ( $$n(A) = 30$$ ) and 20 names are on both lists ( $$n(A \cap B = 20)$$ ), 10 names are on list A alone.
2. Question b. is asking for the number of elements in the Relative Complement of $$(B \setminus A$$). If there are 35 names on list B ( $$n(B) = 35$$ ) and 20 names are on both lists ( $$n(B \cap A = 20)$$ ), 15 names are on list B alone.
3. Question c. is asking for the number of elements in the Union of A and B ( $$n(A \cup B)$$ ). We know that $$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$, so 30 + 35 - 20 = 45.
4. Question d. is asking for the number of elements in the Symmetric Difference of A and B. We can deduce that: $$n(A \oplus B) = n(A \setminus B) + n(B \setminus A)$$. In questions a. and b. above we already found that $$n(A \setminus B) = 10$$ and $$n(B \setminus A) = 15$$. When added together, they give 25.

### 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\}]$$
1. 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\}$$.
2. 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:

1. Each $$a$$ in $$S$$ belongs to one of the $$A_i$$.
2. 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. $$[ \{ 1,3,5\}, \{ 2,6\}, \{ 4,8,9\} ]$$
2. $$[ \{ 1,3,5\}, \{ 2,4,6,8\}, \{ 5,7,9\} ]$$
3. $$[ \{ 1,3,5\}, \{ 2,4,6,8\}, \{ 7,9\} ]$$
4. 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:

1. $$[ \; \bigcup \; ( \; A \; | \; A \in \mathscr{A} ) \; ]^C = \bigcap \; ( A^C \; | \; A \in \mathscr{A} )$$
2. $$[ \; \bigcap \; ( \; A \; | \; A \in \mathscr{A} ) \; ]^C = \bigcup \; ( A^C \; | \; A \in \mathscr{A} )$$

### 1.8 Mathematical Induction

An essential property of the set $$\mathbf{N}=\{1,2,3,\dots\}$$ of positive integers follows:

Principle of Mathematical Induction I: Let $$P$$ be a proposition defined on the positive integers $$\mathbf{N}$$; that is, $$P(n)$$ is either true or false for each $$n \in \mathbf{N}$$. Suppose $$P$$ has the following two properties:

1. $$P(1)$$ is true.
2. $$P(k + 1)$$ is true whenever $$P(k)$$ is true

Then $$P$$ is true for every positive integer $$n \in \mathbf{N}$$

##### Example:

Let $$P$$ be the proposition that the sum of the first $$n$$ odd numbers is $$n^2$$; that is, $$P(n) \; : \; 1+3+5+ \dots + (2n - 1) = n^2$$ (The kth odd number is 2k-1, and the next odd number is 2k+1.) Observe that $$P(n)$$ is true for $$n=1$$; namely, $$P(1) = 1^2$$ Assuming $$P(k)$$ is true, we add $$2k + 1$$ to both sides of $$P(k)$$, obtaining: $$1+3+5+\dots+(2k-1) + (2k+1) - k^2 + (2k+1) = (k+1)^2$$ which is $$P(k+1)$$. In other words, $$P(k + 1)$$ is true whenever $$P(k)$$ is true. By the principle of mathematical induction $$P$$ is true for all $$n$$.

There is a form of the principle of mathematical induction which is sometimes more convenient to use. Although it appears different, it is really equivalent to the above principle of induction.

Principle of Mathematical Induction II: Let $$P$$ be a proposition defined on the positive integers $$\mathbf{N}$$ such that:

1. $$P(1)$$ is true.
2. $$P(k)$$ is true whenever $$P(j)$$ is true for all $$1 \le j \lt k$$.

Then P is true for every positive integer $$n \in \mathbf{N}$$.

Sometimes one wants to prove that a proposition P is true for the set of integers $$\{a, a+1, a+2, a+3, \dots \}$$ where $$a$$ is any integer, possibly zero. This can be done simply by replacing 1 by $$a$$ in either of the above Principles of Mathematical Induction.