5. Recall: A set B is denumerable if there exists a bijection f: N - B. The elem

Question

5. Recall: A set B is denumerable if there exists a bijection f: N - B. The elements in a denumerable set B can then be listed as {b1, b2-b3, . . . . . . . . .. }. An infinite subset of a denumerable set 1s also denumerable. Two sets A and B are numerically equivalent if there is a bijection f:A-B. a. Homework problem- Done completely in class Show that the union of two disjoint denumerable sets is denumerable. b. Several Examples were given in the lecture List three sets that are denumerable. Justify your answers by giving the explicit bijections. You don't need to prove they are bijections

Explanation / Answer

(a) If A and B are countable (and disjoint) sets, then there exist injective functions f and g from A and B, respectively, to N. Let C=AUB and define a function h : C--->N as follows:

h(z) = 2f(z), if z belongs to A and, h(z) = 2g(z)+1 , if z belongs to B

Then, if x is not equal to y, we clearly have h(x) not equal to h(y) since if x,y belong to A this follows from the fact that f is injective (analogously for x,y belonging to B) and if x belongs to A and y belongs to B, we have that h(x) is even while h(y) is odd (analogously for x belonging to B, y belonging to A). Hence h is an injective function from C to N and thus, by definition, C is countable. So, the disjoint union of two countable (DENUMERABLE) sets is denumerable.

(b)  

1. the set of all positive even integers, E = {2,4,6,8,....} is denumerable. define, f : E--->N by, f(x) = x/2, then f is a bijection

2. the set of all positive odd integers F = { 1,3,5,7,9,....} is denumerable, define , g : F--->N by, f(y) = (y+1)/2, then g is a bijection

3. the set of all integers Z is denumerable.

define, h : N--->Z by, h(z) = z/2 (if z is even) and h(z) = --(1+z)/2 (if z is odd)

then h defines a bijection.

so, all of E, F and Z are denumerable sets.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.