Scheinerman Propositions and Theorems

Mathematics : A Discrete intro by da goat scheinerman

Statement 4.2 (vacuous)

If an integer is both a perfect square and prime, then it is negative

Conjecture 5.1 (Goldbach)

Every even integer greater than two is the sum of two primes

Prop 5.2

The sum of two even integers is even

Prop 5.3

Let a,b, and c be integers. If a∣b and b∣c, then a∣c

Prop 5.4

Let x be an integer. If x > 1, then x³ + 1 is composite.

Prop 5.5

Let x be an integer. Then x is even if and only if x + 1 is odd.

Prop 5.6

Let a,b,c, and d be integers. If a∣b, b∣c, and c∣d, then a∣d

statement 6.1

let a and b be integers. If a∣b and b∣a then a = b

Prop 7.1

¬(x∧y) and (¬x) ∨ (¬y) are logically equivalent

Theorem 7.2

x ∧ y = y ∧ x and x ∨ y = y ∨ x (commutative properties)

(x ∧ y) ∧ z = x ∧ (y ∧ z) and (x ∨ y) ∨ z = x ∨ (y ∨ z) (associative properties)

x ∧ TRUE = x and x ∨ FALSE = x (identity elements)

¬(¬x) = x

x ∧ x = x and x ∨ x = x

x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ z) and ¬(x ∨ y) ≡ ¬x ∧ ¬y (DeMorgan’s)

Prop 7.3

x ⇒ y and (¬x) ∨ y are logically equivalent

Theorem 8.2 (Multiplication principle)

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.

Theorem 8.6

The number of lists of length k whose elements are chosen from a pool of n possible elements =

{ nᵏ if repetitions are permitted

{ nₖ if repetitions are forbidden

where nₖ = n(n-1)(n-2)…(n-k+1) known as the falling factorial

Prop 10.1

The following two sets are equal :

E = {x ∈ Z : x is even}, and

F = {z ∈ Z : z = a + b where a and b are both odd}

Def 10.4 (Pythagorean triple)

A list of three integers (a,b,c) is called a Pythagorean triple provided a² + b² = c²

Theorem 10.7

Let A be a finite set. The number of subsets of A is 2|ᴬ|

Corollary 12.8 (Addition Principle)

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

Prop 12.12 (DeMorgan’s Laws)

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

Prop 12.15

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

n! notation

• ∏ₖ₌₁ⁿ k = n!

Prop 13.1

Let n be a positive integer. Then

2⁰ + 2¹ + 2² + ... + 2ⁿ⁻¹ = 2ⁿ - 1

Prop 13.2

Let n be a positive integer. Then

1 × 1! + 2 × 2! + 3 × 3! +…+ n × n! = (n+1)! - 1

Prop 14.6

Let R be a relation. Then (R⁻¹)⁻¹ = R

Theorem 15.5

Let n be a positive integer. The is-congruent-to-mod-n relation is an equivalent relation on the set of integers.

Prop 15.9

Let R be an equivalent relation on a set A and let a ∈ A. Then a ∈ [a]

where [a] = {x ∈ A : x R a}

Prop 15.10

Let R be an equivalent relation on a set A and let a,b ∈ A. Then a R b if and only if [a] = [b]

Prop 15.11

Let R be an equivalent relation on a set A and let a,x,y ∈ A. If x,y ∈ [a], then x R y.

Prop 15.12

Let R be an equivalent relation on A and suppose [a] ∩ [b] ≠ ∅. Then [a] = [b].

Corollary 15.13

Let R be an equivalence relation on a set A. The equivalent classes of R are nonempty, pairwise disjoint subsets of A whose union is A

Prop 16.3

Let A be a set and let 𝒫 be a partition on A. Then the relation 𝒫_≡ is an equivalence relation on A.

Prop 16.4

Let 𝒫 be a parition on a set A and let 𝒫_≡ be the is-in-the-same-part-as relation. The equivalence classes of 𝒫_≡ are exactly the parts of 𝒫.

Theorem 16.6 (Counting equivalence classes)

Let R be an equivalence relation on a finite set A. If all the equivalence classes of R have the same size, m, then the number of equivalence classes is |A|/m

Prop 17.5

Let n be an integer with n>=2.

Then

⎛n⎞

⎝2⎠=

1 + 2 + 3 + … + (n-1) =

n-1

∑ k

k=1

Prop 17.7

Let n, k ∈ N with 0 <= k <= n. Then

⎛n⎞

⎝k⎠=

⎛n ⎞

⎝n-k⎠

Theorem 17.8 (Binomial)

Let n ∈ N. Then,

(x + y)ⁿ =

n

∑ ⎛n⎞ xⁿ⁻ᵏ yᵏ

k=0⎝k⎠

Theorem 17.10 (Pascal’s identity)

Let n and k be integers with 0 < k < n. Then,

⎛n⎞ ⎛n-1⎞ ⎛n-1⎞

⎝k⎠ = ⎝k-1⎠ + ⎝ k ⎠

Theorem 17.12 (Formula for n choose k)

Let n and k be integers with 0 <= k <= n. Then,

⎛n⎞

⎝k⎠ = n! / k!(n - k)!