Chapter 2

Question 1

List

Answer 1

an ordered sequence of objects

Question 2

Multiplication Principle

Answer 2

Consider two-element lists for which there are n choices for the first element, and for each choice of the first element there are m choices for the second element. Then the number of such lists is nm.

Question 3

Factorial

Answer 3

Used in a special case of this problem is to count the number of length-n lists chosen from a pool of n objects in which repetition is forbidden.

Question 4

two sets to be equal

Answer 4

the two sets have exactly the same elements. To prove that sets A and B are equal, one shows that every element of A is also an element of B, and vice versa.

Question 5

Subset

Answer 5

Suppose A and B are sets. We say that A is a subset of B provided every element
of A is also an element of B. The notation A ⊆ B means A is a subset of B.

Question 6

Proposition 10.3 (Proof)

Answer 6

Let x be anything and let A be a set; then x ∊ A if and only i f {x} ⊆ A

Question 7

Power set

Answer 7

Let A be a set. The power set of A is the set of all subsets of A.

Question 8

Union

Answer 8

Let A and B be sets.
The union of A and B is the set of all elements that are in A or B (or both). The union of
A and B is denoted A ∪ B.

Question 9

Intersection

Answer 9

The intersection of A and B is the set of all elements that are in both A and B. The
intersection of A and B is denoted A ∩ B.

Question 10

Disjoint, pairwise disjoint

Answer 10

Let A and B be sets. We call A and B disjoint provided A ∩ B = ⦲. Let A1, A2, … , An be a collection of sets. These sets are called pairwise disjoint provided Ai ∩ Aj = ⦲ whenever i ≠ j . In other words, they are pairwise disjoint provided no two of them have an element in common.

Question 11

Addition Principle

Answer 11

Let A and B be finite sets. If A and B are disjoint, then |A ∪ B| = |A| + |B|.

Question 12

Set difference

Answer 12

Let A and B be sets. The set difference, A B, is the set of all elements of A that are not in B

Question 13

symmetric difference of A and B

Answer 13

denoted A ∆ B, is the set of all elements in A but not B or in B but not A.

Question 14

Proposition 12.11, Let A and B be sets. Then

Answer 14

A ∆ B = (A ∪ B) - (A ∩ B)

Question 15

DeMorgan’s Laws

Answer 15

A - (B ∪ C) = (A - B) ∩ (A - C) and A - (B ∩ C) = (A - B) ∪ (A - C)

Question 16

Cartesian product

Answer 16

Let A and B be sets. The Cartesian product of A and B, denoted A B, is the set of all ordered pairs (two-element lists) formed by taking an element from A together with an element from B in all possible ways. A × B

Question 17

Proposition 12.15

Answer 17

Let A and B be finite sets. Then |A × B| = |A| × |B|.