Discrete Mathematics: Set Theory and Countability of Rationals

This assignment focuses on proving the countability of rational numbers within the framework of discrete mathematics and set theory. The solution demonstrates the construction of bijections between different sets, including the set of rational numbers (Q) and the set of positive integers (Z+). It involves defining injections, such as g from Z to A and g1 from Z×Z to A×A, and demonstrating the injective property of a function f: A×A ? Z+. The assignment also explores the application of the Schroeder-Bernstein Theorem to prove the countability of Q. Furthermore, the solution includes proofs of the same cardinality for the sets (0, 1), [0, 1), (0, 1], [0, 1], and R. The assignment utilizes concepts from set theory, combinatorics, and graph theory and references relevant literature on discrete mathematics.

Running head: DISCRETE MATHEMATICS 1
Discrete Mathematics
Name of Student
Institution
Date

DISCRETE MATHEMATICS 2
1. Show that there is bijection between the set of rational numbers, denoted Q, and the set
of positive integers in steps as asked below. Thus proving that the set of rational is
countable. Let A = Z+ ? {0}. [5 points]
a) Define an injection g from Z and A, use the injection g to obtain an injection g1 from
Z×Z to A×A.

DISCRETE MATHEMATICS 3
b) Define f : A×A ? Z+, as follows: For any (i,j) ? A×A, f((i,j)) = (i+j)(i+j+1) +j+1. 2
Show that f is injective.

DISCRETE MATHEMATICS 4
c) Find an injection from Z+ to Q.

DISCRETE MATHEMATICS 5
d) Find an injection from Q to Z × Z.

DISCRETE MATHEMATICS 6
e) Use Schroeder Bernstein Theorem and above parts to show that Q is an infinite
countable set.

DISCRETE MATHEMATICS 7
2. Show that the following sets have the same cardinality (i.e., there is a bijection
between any two sets among the following sets) (0, 1), [0, 1), (0, 1], [0, 1] and R. [5
points]

DISCRETE MATHEMATICS 8

DISCRETE MATHEMATICS 9

DISCRETE MATHEMATICS 10

DISCRETE MATHEMATICS 11
Work cited
Greenberg, M., & Osborn, J. C. (2019). Teaching discrete mathematics to early undergraduates
with software foundations.
Lipschutz, S. (2016). Schaum's Outlines of Theory and Problems of Discrete Mathematics.
Rosen, K. H., & Krithivasan, K. (2012). Discrete mathematics and its applications: with
combinatorics and graph theory. Tata McGraw-Hill Education.
Toth, C. D., O'Rourke, J., & Goodman, J. E. (2017). Handbook of discrete and computational
geometry. Chapman and Hall/CRC.