Chapter 0

Chapter 0
Discrete Mathematics review:Sets and Logic; Functions and RelationsMathematical induction and the Pigeonhole principleCardinality
Sets
A collection of objects calledelements, with no repetition or order.Examples: {a₁, …,aᵢ}; {a₁,a₂,a₃, …} {1, 2} = {2, 1} = {1, 1, 2}Membership:a∈A, a∉Ae.g. 1 ∈ {1, 2}, 3 ∉ {1, 2}Empty set: ∅ = {}x∉ ∅Special:singleton: {a}doubleton: {a,b}a≠bSubset:A⊆B;A⊊B; transitive:A⊆B⊆C⇒A⊆CEquality:A=B⇔A⊆B&B⊆ANotation: {x∈D:P(x)}Dis adomainPis aproperty
Operations
Boolean: union intersection differenceA∪B;A∩B;A∖BCartesian: productA×B= {〈a,b〉 :a∈A,b∈B}Power set: 2A= {B:B⊆A}∅,A∈ 2AExample: 2{a,b,c}= {∅, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}
Propositional logic
Propositions: Boolean statementsp∈ {True,False}Connectives:conjunction;disjunction;negationp∧qp∨q¬pDeMorgan’slaws: ¬(p∧q) = ¬p∨ ¬q; ¬(p∨q) = ¬p∧ ¬qImplication:p→q(ifhypothesisthenconclusion)Converse:q→pContrapositive: ¬q→ ¬pBiconditional:p↔q(if and only if)Tautology: always trueContradiction: always false
Predicate logic
Predicates: statements with free variables ranging over adomain:x² ≥ 0Quantifiers: existential (∃) and universal (∀) ways of binding variables∀x∈Rx² ≥ 0 ∃x∈Cx² < 0¬∀xP(x) = ∃x¬P(x)Aristotelian logic: all men are mortal ∀xMan(x) →Mortal(x)
Functions
Function: a map from a domainXto codomainYf:X→Yf⊆X×Ywhere ∀x∈X∃!y∈Ysuch that (x,y) ∈fI.e.fassigns to each element in the domain a unique element in the codomain. Theapplicationofftox, writtenf(x), is theimageofxunderf. As a set ofargument-valuepairs,f= {〈x,f(x)〉 :x∈X}. Therangeoffisf[X] = {f(x) :x∈X}.Injective(one-one):x₁ ≠x₂ ⇒f(x₁) ≠f(x₂) for allx₁,x₂ ∈XSurjective(onto): for everyy∈Ythere is anx∈Xsuch thaty=f(x)Bijective: injective and surjective (a 1 to 1 correspondence)
Relations
Relation(binary):R⊆A×B, i.e. a set of ordered pairs (usuallyA=B)Example: A (directed) graph hasedgesE⊆V×Vbetweenverticesv₁ →v₂ (v₁,v₂) ∈E⇔ there is an edge from vertexv₁ to vertexv₂Reflexive:sRs(every element is related to itself, via aself loop)Symmetric:s₁Rs₂ ⇔s₂Rs₁ (all edges areundirected)Transitive:s₁Rs₂ &s₂Rs₃ ⇒s₁Rs₃ (all paths are edges)Equivalence relation: reflexive; symmetric; and transitive (written ~)ItpartitionsSinto disjointequivalence classes: [s] = {s'∈S:s'~s}.
Partitions
ApartitionΠofSis a collection of non-empty subsets ofSsuch that every element ofSis an exactly one element ofΠ(cutsSinto pieces).Properties:∅ ∉ΠIfP₁,P₂ ∈ΠandP₁ ≠P₂ thenP₁ ∩P₂ = ∅∪{P∈Π} =SThesizeof a partitionΠis the number of pieces it contains, i.e. |Π|.Examples: the finest isΠ= { {s} :s∈S}; the coarsest isΠ= {S}
Equivalence relations and partitions
Fact: Let ~ be an equivalence relation on a setS. Then its set of equivalence classes {[s] :s∈S} form a partition ofS.Proof: For everys∈S,s∈ [s] sinces~s, so [s] ≠ ∅. Ifs∈ [s₁] ∩ [s₂] thens~s₁ ands~s₂, sos₁ ~s₂ ⇒ [s₁] =[s₂]. Ifs∈Sthens∈ [s], hence ∪{[s] :s∈S} =S. Therefore, {[s] :s∈S} is a partition ofS.Fact: LetΠbe a partition of S. Then the relation defined bys₁ ~s₂ ⇔s₁,s₂ ∈Pfor someP∈Πis an equivalence relation.Proof: For everys∈S, s∈P∈Π, sos~s. Ifs₁ ~s₂ thens₁,s₂ ∈P∈Π, but thens₂ ~s₁. Ifs₁ ~s₂ ~s₃ thens₁,s₂ ∈P∈Πands₂,s₃ ∈Q∈Π. Buts₂ ∈P∩QimpliesP=Q, sos₁,s₂,s₃ ∈P=Q∈Π, hences₁ ~s₃.
Mathematical induction
Show that a statement holds for all natural numbers, by proving it holds for zero and that it is closed under the application of successor.Example: Show |2A| = 2|A|for any finite setA, by induction on |A|.Base case: When |A| = 0,A= ∅. So |2∅| = |{∅}| = 1 = 20= 2|A|.Inductive step: Let |A| =n+ 1. Since |A| ≥ 1, pick anya∈Aand letB=A∖ {a}. Now, 2A= {S⊆A:a∉S} ∪ {S⊆A:a∈S} = {S⊆A:S⊆B} ∪ {S∪ {a} :S⊆B} = 2B∪ {S∪ {a} :S∈ 2B}. These are disjoint, so|2A| = |2B| + |2B|. By induction hypothesis, |2B| = 2|B|= 2nbecause |B| =n. So |2A| =2n+ 2n= 2n+1= 2|A|.Note: There is a non-recursive proof by counting binary strings.
Pigeonhole principle
There cannot be an injective function from a finite set to a proper subset of itself.Proof: Letf:A→BwithAfinite andB⊊A, whence |A| > |B|. Let’s showfis not injective by induction on |B| (whenB= ∅ it is trivial).Base Case: |B| = 1 ⇒B= {b}, which means thatf[A] = {b}. But since |A| > 1 this means there area≠a'such thatf(a) =f(a'), sofis not one-one.Induction Step: Take |B| > 1, and anyb∈B. If |f⁻¹(b)| > 1 we are done. Otherwise, letA'=A∖f⁻¹(b), andB'=B∖ {b}. Then since |B'| < |A'|, by induction hypothesisf:A'→B'cannot be injective. So,f:A→Bis not either.
Using the pigeonhole principle to prove mathematical induction
Pigeonhole principle: IfB⊊Ais finite,thenf:A→Bis not injective.Definition: A subsetPof natural numbers isinductiveif it contains zero and is closed under successor. I.e. 0∈P& for alln∈P,n+ 1 ∈P.Note: Mathematical induction says every inductive setP=N.Proof: SupposePis inductive and has a least counterexamplem∉P. Definef: {0, …,m} → {0, …,m− 1} byf(x) =x− [¬P(x)]. NoteP(0) ⇒f(0) = 0 andf(m) =m− 1.fmust be one-one because the only possible violation is somensuch thatf(n+ 1) =n=f(n), which would meanP(n) and ¬P(n+ 1) which contradictsPbeing inductive.
Cardinality
Size:AandBareequinumerousif there is a bijection between them. A set isfiniteif it isequinumerouswith a natural number. A set isinfiniteif it is not finite, and a set isdenumerableif it isequinumerouswithN.Corollary(of the pigeonhole principle):IfBAfinite, then |B| < |A|.Fact: If infiniteBAdenumerable, thenBis denumerable.Reason: LetA= {a₀,a₁, …}. Pickn₀ smallest such thatan₀∈B, and similarly foranᵢ∈B∖ {an₀, …,anᵢ₋₁}. HenceB= {an₀, …,anᵢ, …}.Fact:Every infinite setXcontains a denumerable subset.Reason: Pick anyx₀ ∈X. After having picked {x₀, …,xᵢ} we knowX∖ {x₀, …,xᵢ} ≠ ∅ becauseXis infinite, so we can pickxᵢ₊₁ ∈X∖ {x₀, …,xᵢ}, etc.
Countable sets
Definition: A set iscountableif it is either denumerable or finite.Theorem: The union of finitely many countable sets is countable.Proof: The cases where either set is finite are obvious. So, letA= {a₁,a₂,a₃, …} andB= {b₁,b₂,b₃, …}ThenA∪B= {a₁,b₁,a₂,b₂,a₃,b₃, …}Note: The union of finitely many countable sets can be reduced to this.
Countable sets continued
Theorem: A countable union of countable sets is countable.Proof: LetA'=A₁ ∪A₂ ∪A₃ ∪ … where eachAᵢ= {aᵢ₁,aᵢ₂,aᵢ₃, …}.DefineA'= {a₁,a₂,a₃, …} by anti-diagonals from the diagram:
Eventually, every element of eachAᵢis visited and given a chance to enterA'= {aᵢⱼ:i+j= 1, 2, 3, …}.
Diagonalization
Theorem: 2Nis uncountable.Proof: Suppose 2N= {S₀,S₁,S₃, …} is countable, where eachSᵢis a subset of natural numbers. LetSbe thecomplementof the diagonal set {i∈N:i∈Sᵢ}.SinceSis also a subset ofN, it must be equal to someSᵢ.Buti∈Sᵢ⇔i∉S, a contradiction.
A one appears in rowicolumnjif and only ifj∈Sᵢ.
Transitive closure
LetR⁺ = {〈a,b〉 : there is a nontrivial path fromatobin the graph determined byR}.ConstructR⁺ inductively (from below) by the following rules:(a,b) ∈R⇒ (a,b) ∈R⁺(a,c), (c,b) ∈R⁺ ⇒ (a,b) ∈R⁺Nothing else
DefineR⁺ as the intersection (from above) of all transitive relations containingR.I.e. the smallest transitive relation containingR.R⊆R⁺R⁺ is transitiveR⊆R'⊊R⁺ ⇒R'not transitive
Transitive closure continued
The bottom-up (BU) and top-down (TD) versions of transitive closure are equivalent.Proof: (1) and (A) are clearly equivalent, as well as (2) and (B).To show (C), suppose toward a contradiction thatR⊆R'⊊R⁺ withR'transitive. Well,R⊆R'andR'transitive means thatR'also satisfies (1) and (2), soR'⊇R⁺ by induction. This is where we implicitly use (3) and the fact that rules (1) and (2) are monotone. This contradictsR'⊊R⁺.To show (3), suppose that (a,b) ∈R⁺ but not from applying (1) or (2). ThenR⊆R⁺ ∖ {(a,b)} ⊊R⁺ by the failure of (1), andR⁺ ∖ {(a,b)} is still transitive by the failure of (2), but then this contradicts (C).