CENG223 -the2 -Solved

Discrete Computational Structures
Question 1
Set theory is the backbone of modern mathematics. Based on it we can rigorously define many of the seemingly complex structure of mathematics. One such structure that will possibly come across in your later studies is that of topology. Below you are given the definition of a topology and asked to put your knowledge on set operations and countability in use.

Definition. A topology on a set A is a set T of subsets of A that has the following properties

i)        ∅ and A are in T .

ii)      The union of the elements of any subset of T is in T . iii) The intersection of the elements of any finite subsets of T is in T .

a.         Let A be a set given as A = {a, b, c, d}. State for each of the below given set of subsets whether it is a topology or not, and briefly explain why.

i)         T1 = {∅, A} ii) T2 = {∅, {a}, {b}, {c}, {d}, A} iii) T3 = {∅, {a,b}, {b}, {b,c}, {a,b,c}, A} iv) T4 = {∅, {a,c}, {b}, {b,c}, {c}, {b,d}, A}

b.        Let A be a set. Show for each of the following sets whether they are a topology on A or not.

i)         the set of all U ⊆ A such that A − U is either finite or is A.

ii)       the set of all U ⊆ A such that A − U is either countable or is all of A. iii) the set of all U ⊆ A such that A − U is infinite or ∅ or A.

Question 2
Let A = {0,1,2,...}. Consider the function

f : A × (0,1) → [0,∞)

where f(a,b) = a + b for all (a,b) ∈ A × (0,1).

a.         Is f injective? Prove your claim.

b.        Is f surjective? Prove your claim.

c.         If there exists an injective g from [0,∞) to A × (0,1) show that A × (0,1) and [0,∞) have the same cardinality. It is enough to name any theorems that you might use in this part.

Note: (0,1) = {x ∈ R|0 < x < 1} and [0,∞) = {x ∈ R|x ≥ 0}.

Question 3
Show whether the following sets are countable or not.

a.         The set A of all functions f : {0,1} → Z+.

b.        The set B of all functions f : {1,...,n} → Z+.

c.         The set C of all functions f : Z+ → Z+.

d.        The set D of all functions f : Z+ → {0,1}.

e.         The set E of all functions f : Z+ → {0,1} that are eventually zero.

(A function is said to be eventually zero if there is a N ∈ Z+ such that f(n) = 0 for all n ≥ N.)

Question 4
a.         Determine whether n! is Θ(nn) or not.

(Hint: Stirling’s approximation)

b.        Determine whether (n + a)b = Θ(nb) or not for a ∈ R and b ∈ Z+.

Question 5
Let x,y ∈ Z+.

a.         Show that (2x − 1) mod (2y − 1) = 2x mod y − 1.

b.        Show that gcd(2x − 1, 2y − 1) = 2gcd(x,y) − 1 using the above result.

Exercise (not graded)
Let f : U → V be a function and A ⊆ U and B ⊆ U.

a.

i)      Prove by natural deduction that f(A ∩ B) ⊆ f(A) ∩ f(B).

ii)    Does the converse hold? If so, prove it by natural deduction, if not give a counter-example. b.

i)      Prove by natural deduction that f(A ∪ B) ⊆ f(A) ∪ f(B).

ii)    Does the converse hold? If so, prove it by natural deduction, if not give a counter-example.

(While presenting proofs by natural deduction, first state what is to be proven using the symbols ∨,∧,→ ,¬,=,∃,∀,` and ∈.)