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ₙ.

Fact 3.2 (Addition Principle)

Fact 3.3 (subtraction principle)

Defintion 4.1 (even)

An integer n is even if n = 2a for some integer a ∈ Z.

Definition 4.2 (odd)

An integer n is odd if n = 2a + 1 for some integer a ∈ Z.

Definition 4.3 (parity)

Two integers have the same parity if they are both even or they are both odd. Otherwise, they have opposite parity.

Definition 4.5 (prime and composite)

A number n ∈ N is prime provided it has exactly two positive divisors, 1 and n (in the set of divisors). If n has more than two positive divisors, it is called composite. (Thus n is composite if and only if n = ab, with 1 < a,b < n).

Definition 4.6 (greatest common divisor, least common multiple)

The greatest common divisor of integers a and b, denoted gcd(a,b), is the largest integer that divides both a and b.

The least common multiple of non-zero integers a and b, denoted lcm(a,b) is the smallest integer in ℕ that is a multiple of both a and b.

Fact 4.1

If a and b are integers, then so are their sum, product, and difference. That is, if a,b ∈ Z, then a + b ∈ Z, a - b ∈ Z, and ab ∈ Z.

Definition 3.1 (factorial)

If n is a non-negative integer, then n! is the number of lists of length n that can be made from n symbols, without repetition. Thus, 0! = 1 and 1! = 1. If n>1, then n! = n(n-1)(n-2)…(3)(2)(1).

Fact 3.4 (k-permutation)

A k-permutation of an n-element set is a non-repetitive length-k list made from elements of the set. Informally we think of a k-permutation as an arrangement of k of the set’s elements in a row.

The number of k-permutations of an n-element set is denoted P(n,k), and

P(n,k) = n(n-1)(n-2)…(n-k+1)

If 0 <= k <= n, then P(n,k) = n(n-1)(n-2)…(n-k+1) = n! / (n-k)!

Definition 5.1 (congruent modulo n)

Given integers a and b and n ∈ N, we say that a and b are congruent modulo n if n | (a-b). We express this as a ≡ b (mod n). If a and b are not congruent modulo n, we write this as a ≢ b (mod n).

Definition 6.1 (rational)

A real number x is rational if x = a/b ∈ Z. Also, x is irrational if it is not ration, that is if x ≠ a/b for every a/b ∈ Z.

Definition 3.2

If n and k are integers, then

⎛n⎞

⎝k⎠

denotes the number of subsets that cna be made by choosing k elements from an n-element set. We read

⎛n⎞

⎝k⎠

as “n choose k”. Also written as C(n, k).