Exam 2024 (A)

1a

Let G=(V,E) be a simple graph1.Define tree2.Define distance between u,v∈V3.Define path4.Define cycle5.Define connected componentSolution:3.Path is a sequence of vertices: (v1,v1,…,vk+1) such that:∀i∈[1,k]:{vi,vi+1}∈E,∀i≠j∈[1,k]:{vi,vi+1}≠{vj,vj+1}Length of the path is the number of edges in it, which is k4. Cycle is a path such that: v1=vk+12.Distance between vertices u,v∈Vd(u,v) is the length of the shortest path between themIf there is no path between vertices, then d(u,v)=∞5.Let ∼ be a relation on V such that:∀u,v∈V:u∼v⟺d(u,v)<∞In other words: u∼v⟺ There is a path between u,v∼ is an equivalence relation and its equivalence classes are called connected componentsConnected components induce subgraphs: Gu={[u]∼,Eu}where Eu={{v,w}|v,w∈[u]∼}1.Connected graph is a graph with exactly one connected componentAcyclic graph is a graph with no cyclesTree is a connected acyclic graph

1b

Let G=(V,E) be a simple graphDefine the complement G― of graph GTo be G―=(V,E―):E―={{u,v}|u,v∈V,{u,v}∉E}Prove: for any simple graph with n≥5 vertices either G or G― has a cycleProof:|E―|=n(n−1)2−|E|Let |E|≥n⟹G has a cycleLet |E|<n⟹|E―|>n(n−1)2−n=n2−n−2n2=n(n−3)2n≥5⟹n−32≥22=1⟹n(n−3)2≥n⟹|E―|>n⟹G― has a cycle

2

A is a set,|A|≥1Let f:P(A)×P(A)→P(P(A))∀B,C⊆A:f(B,C)={D|D⊆B∩C}Prove or disprove:1.It is possible that f is injective2.It is possible that f is surjectiveDisproof for 1:Let AA≠∅⟹∃a∈Af(∅,{a})=f({a},∅)=P(∅)={∅}⟹∀A:f is not injectiveDisproof for 2:Let AA≠∅⟹∃a∈A⟹{a}∈P(A)⟹{{a}}∈P(P(A))∀X:∅∈P(X)∀B,C⊆A:f(B,C)=P(B∩C)⟹∅∈f(B,C)⟹f(B,C)≠{{a}}⟹∀A:f is nor surjectiveLet A be a set, |A|≥1f:P(A)×P(A)→P(P(A)),f(B,C)={D|D⊆B∩C}In other words f(B,C)=P(B∩C)Dom(f)=P(A)×P(A)Range(f)=P(P(A))Prove or disprove: It is possible for f to be injectiveIn other words ∃A:f is injectiveDisproof:Let A,|A|≥1Let a∈Af({a},∅)=f(∅,{a})={∅}⟹∀A:f is not injectiveProve or disprove: It is possible for f to be surjectiveIn other words ∃A:f is surjectiveDisproof:∅∈P(P(A))f(B,C)=P(B∩C)⟹∅∈f(B,C)⟹f(B,C)≠∅∅∈Range(f),∅∉Im(f)⟹Im(f)≠Range(f)⟹∀A:f is not surjective

3

Let A be a setLet f:A→ALet B⊆ALet B1=B,∀n∈N:Bn+1=f−1[Bn]1.Prove: if for any B⊆A:⋂n∈NBn=∅ then f has no fixed points2.Prove or disprove: f has no fixed points⟹∀B⊆A:⋂n∈NBn=∅Proof for 1:If A is an empty set, then f is an empty function which has no fixed pointsLet A≠∅Let ∀B⊆A:⋂n∈NBn=∅Let f has a fixed point xLet B={x}⟹x∈f[B]Base case. Let n=1x∈B⟹x∈B1Induction step. Let x∈BnBn+1=f−1[Bn]x∈Bn,f(x)=x⟹x∈f−1[Bn]=Bn+1⟹By induction: x∈⋂n∈NBn⟹⋂n∈NBn≠∅−Contradiction!⟹f has no fixed pointsDisproof for 2:Let A=NLet f(n)=2nLet B=NBase case. Let n=1B1=B=NInduction step. Let Bn=NBn+1=f−1[Bn]=f−1[N]Let x∈f−1[N]⟹x∈N⟹f−1[N]⊆NLet x∈N⟹2x∈N⟹f(x)=2x⟹x∈f−1[{2x}]⊆f−1[N]⟹N⊆f−1[N]⟹Bn+1=f−1[N]=N⟹By Induction ∀n∈N:Bn=N⟹⋂n∈NBn=N

4

…

5

Let A be a setA is called transitive if ∀x∈A:∀y∈x:y∈A

5a

Find an example of a transitive and a non-transitive setsSolution:Let A1=∅A1 is vacuously transitiveLet A={{1}}1∉A⟹∃x={1}∈A:∃y=1∈x:y∉A⟹A is not transitive

5b

Let {Ai}i∈I be family of transitive setsProve: ⋂i∈IAi is transitiveProof:Let x∈⋂i∈IAi⟹∀i∈I:x∈Ai⟹∀i∈I:∀y∈x:y∈Ai⟹∀y∈x:y∈⋂i∈IAi⟹⋂i∈IAi is transitive

5c

Let A be a setLet A1=ALet ∀n∈N:An+1=An∪{y|∃x∈An:y∈x}

5c.1

Prove: ⋃n∈NAn is transitiveProof:Let x∈⋃n∈NAn⟹∃n∈N:x∈Anx∈An⟹∀y∈x:y∈An+1⟹y∈⋃n∈NAn⟹⋃n∈NAn is transitive

5c.2

Let B be transitive and A⊆BProve: ⋃n∈NAn⊆BProof:Base case. Let n=1A1=A⟹A1⊆BInduction step. Let An⊆BAn+1=An∪{y|∃x∈An:y∈x}B is transitive⟹∀x∈B:∀y∈x:y∈BAn⊆B⟹∀x∈An:∀y∈x:y∈B⟹{y|∃x∈An:y∈x}⊆B⟹An+1=An∪{y|∃x∈An:y∈x}⊆B⟹By Induction: ∀n∈N:An⊆B⟹⋃n∈NAn⊆B