proofs and sets

witness for ∃x

a value of x that makes p(x) true, proving the truth of the existential formula ∃x,p(x)

witness for ∀x

a value of x that makes p(x) false, proving the falsehood of the universal formula ∀x,p(x)

inductive arguments

arguments to prove ∀ formulae or disprove ∃ formulae, or prove theorems

natural induction

For a predicate p(n) about the natural numbers (n = 0, 1, 2, . . .) natural induction is a proof by the following argument. p(0): base case (prove true, sometimes p(1) can be used as the base case instead) p(k) ⇒ p(k + 1): inductive case (assume p(k) is true then prove it's true for p(k+1) is true too) ∴ ∀n, p(n)

set specification

an expression of the form {member | predicate}, or members can simply be listed in any order {…} e.x. {p | prime(p) ∧ p < 10}, or {2, 3, 5, 7}

natural numbers

N, the set of non-negative whole numbers

integers

Z, the set of whole numbers

empty set

Ø

universal set

U, the set of all available elements in some agreed world of one or more values

set membership notation

x ∈ S means x is a member of set s x ∉ S means x is not a member of set s

axioms of membership

{x|x ∈ S} = S "the set of all objects x such that x is a member of s is equal to the set S" y ∈ {x|p(x)} ≡ p(y) "for an object y, y is a member of the set of things that satisfy property p if and only if y satisfies property p"

subset notation

P ⊆ Q

proper subset notation

P ⊂ Q

subsets as logical connectives

P ⊆ Q ≡ ∀x, x ∈ P ⇒ x ∈ Q P ⊂ Q ≡ (∀x, x ∈ P ⇒ x ∈ Q) ∧ (∃x, x ∈ Q ∧ x ∈ / P)

set equality as logical connectives

P = Q ≡ ∀x, x ∈ P ⇔ x ∈ Q

union and intersection as logical connectives

P ∪ Q = {x|x ∈ P ∨ x ∈ Q} P ∩ Q = {x|x ∈ P ∧ x ∈ Q}

difference

notated as P \ Q the set of all items which are in P and not Q

difference as logical connectives

P \ Q = {x|x ∈ P ∧ x ∉ Q}

distributivity and sets

P ∩ (Q ∪ R) = (P ∩ Q) ∪ (P ∩ R) P ∪ (Q ∩ R) = (P ∪ Q) ∩ (P ∪ R)

complement

denoted P' P' = {x|x ∉ P} = U \ P

disjoint sets

sets with no elements in common

disjoint sets notation

P ⊆ Q 0 P \ Q = P P ∩ Q = Ø P ∪ Q 0 = Q 0

disjoint union

the union of two disjoint sets P and Q is notated using a ∪ sign with a + in the middle

cardinality rule

(P ∪ Q) + #(P ∩ Q) = #P + #Q

powerset

the powerset 2^s of set S is the set containing all subsets of S its cardinality is 2^(#S)

partition

a set of disjoint, non-empty subsets of a set, where every element of the parent set is included in one of the subsets (the exception to these rules is the partition of Ø, where the partition will itself be Ø)

∃!

means "there exists only one"

number of distinct partitions of a set

for a sett with n elements

parts(0) = 1

parts(n) = (n-1)Σ (n-1)Cj x parts(n-j-1)

where C(n,j) = n!/j!(n-j)! is the number of ways of choosing an j-element subset from an n element set