Book of Proof cited theorems, definitions, facts, etc

Definition 1.1 (ordered pair)

An ordered pair is a list (x,y) of two things x and y, enclosed in parentheses and separated by a comma.

Fact 1.1

If A and B are finite sets, then |A × B| = |A| × |B|

Definition 1.3 (subset)

Suppose A and B are sets. If every element of A is also an element of B, then we say A is a subset of B, and we denote this as A ⊆ B. We write A ⊈ B if A is not a subset of B, that is, if it is not true that every element of A is also an element of B. Thus A ⊈ B means that there is at least one element of A that is not an element of B.

Fact 1.2

The empty set is a subset of all sets, that is, ∅ ⊆ B for any set B.

Fact 1.3

If a finite set has n elements, then it has 2ⁿ subsets

Definition 1.4 (power set)

If A is a set, the power set of A is another set, denoted as 𝒫(A) and defined to be the set of all subsets of A. In symbols, 𝒫(A) = {X : X ⊆ A}

Fact 1.4

If A is a finite set, then I𝒫(A)I = 2^|A|

Definition 1.5 (union, intersection, difference of sets)

Suppose A and B are sets.

The union of A and B is the set A ∪ B = { x : x ∈ A or x ∈ B}

The intersection of A and B is the set A ∩ B = {x : x ∈ A and x ∈ B}

The difference of A and B is the set A - B = {x : x ∈ A and x ∉ B}

Definition 1.6 (complement of a set)

Let A be a set with a universal set U. The complement of A, Ā, is the set Ā = U - A. [Note that when using this definition, a U must be defined.]

Definition 1.7 (indexed sets unions and intersection)

Suppose A₁, A₂, ⋯, Aₙ are sets. Then

A₁ ∪ A₂ ∪ ⋯ ∪ Aₙ = {x : x ∈ Aᵢ for at least one set Aᵢ, for 1 <= i <= n}

denoted ⋃ᵢ₌₁ⁿ Aᵢ

A₁ ∩ A₂ ∩ ⋯ ∩ Aₙ = {x : x ∈ Aᵢ for every set Aᵢ, for 1 <= i <= n}

denoted ⋂ᵢ₌₁ⁿ Aᵢ

Definition 1.8 (big union and big intersection)

Fact 1.5 (division algorithm)

Given integers a and b with b > 0, there exists unique integers q and r for which a = qb + r and 0 <= r <= b

Fact 3.1 (multiplication principle)

Suppose in making a list of length n there are a₁ possible choices for the first entry, a₂ possible choices for the second entry, a₃ possible choices for the third entry, and so on. Then the total number of different lists that can be made this way is the product a₁ · a₂ · a₃ · ... · aₙ