Let f N rightarrow R and g N rightarrow R be the functions d

Let f: N rightarrow R^+ and g; N rightarrow R^+ be the functions defined by f (n) = 2n^3 + n and g (n) = 10n^3 - n^2 for all n N. Show that f = theta (g). Prove that the integers Z are countable. Prove that the R be a relation on N times N be defined by (a, b) R (c, d) if 5 a- 10 d = 5e - 10 b where (a, b), (c, d) N times N is an equivalence relation. Describe the equivalence classes [(1,1)] and [(2, 1)].

Solution

Solution : 1 )

Proof : We can list the integers in a sequence :

0, 1, 1, 2, 2, 3, 3 ,………..

Let f be a function from N to Z dened as

Showing that a Set is Countable

f(m) = m/2 and f(n) = n/2, it follows that f(m) = f(n) implies m = n.

f(m) = (m1)/2 and f(n) = (n1)/2, it follows that f(m) = f(n) implies m = n.

Therefore, f is injective. We now show that f is surjective by case analysis on the sign of some integer t in Z.

Therefore, f is surjective. (QED)