Discrete-math 14

Discrete-math 14

Image (partial Image) #definition

Let f:A→BLet X⊆AImage of X under f is defined as following:f[X]={f(x)|x∈X}

Inverse Image #definition

Let f:A→BLet Y⊆BInverse image of Y under f is defined as following:f−1[Y]={x∈A|f(x)∈Y}

Example

f:Z→Zf(x)=x2f[{1,2}]={1,4}f−1[{1,4}]={−2,−1,1,2}f−1[{5}]=∅

Partial and Inverse Image properties #theorem

Let f:X→YThen 1.∀B⊆Y:f[f−1[B]]⊆B2.f is surjective⟺∀B⊆Y:f[f−1[B]]=BProof for 1.Let y∈f[f−1[B]]∃x∈f−1[B]:f(x)=y⟺∃x∈X:f(x)∈B∧f(x)=yf(x)∈B∧f(x)=y⟹y∈B⟹f[f−1[B]]⊆BProof for 2.Let f be surjectiveLet B⊆Y,y∈Bf is surjective⟹∃x∈X:f(x)=yy∈B∧f(x)=y⟹x∈f−1[B]⟹y=f(x)∈f[f−1[B]]⟹B⊆f[f−1[B]]⟹∀B⊆Y:B=f[f−1[B]](1)Let ∀B⊆Y:B=f[f−1[B]]Let y∈Y,B={y}y∈B⟹y∈f[f−1[B]]⟹∃x∈f−1[B]:f(x)=yf−1[B]⊆X⟹∃x∈X:f(x)=y⟹f is surjective(2)(1)∧(2)⟹f is surjective⟺∀B⊆Y:f[f−1[B]]=B

Finite set #definition

Set A is called finiteIf it is empty or if there exists n∈Nsuch that there exists a bijective function f:N→ANumber of elements: |A|=nWe denote {1,2,…,n}=[n]

Functions on finite sets #lemma

Let A,B≠∅ be finite setsThen |A|≤|B|⟺∃f:A→B:f is injectiveProof:Let ∃f:A→B:f is injectivef is injective⟹|A|=|Im(f)|≤|B|⟹|A|≤|B|(1)Let |A|≤|B|A={a1,…,an},B={b1,…,bn,…bn+k}f:A→B,∀i∈[n]:f(ai)=bi∀i,j∈[n]:ai≠aj⟹i≠j⟹bi≠bj⟹f(ai)≠f(aj)⟹∃f:A→B:f is injective(2)(1)∧(2)⟹|A|≤|B|⟺∃f:A→B:f is injective

Combinatorics

Addition rule

A∩B=∅⟹|A∪B|=|A|+|B|