Let A= {for all m that's an element of the integers | m=3k+7 for some k that's an element of positive integers}. Prove that A is countably infiite. Note: you must define a function from Z+ to A, and then prove that the function you definied is a bijection
So the question is:
A={m∈ℤ : m=3k+7 ∃k∈ℤ+}
Prove that A is countably infinite by defining a function f : ℤ -> A and proving that f is bijective.
A function f is bijective if and only if its inverse is also a function.
Since the inverse of f is relative easy to find, all you need is to prove that the inverse is a function.
If f is bijective (i.e. one-to-one and onto), and if the domain is countably infinite, the range of f, i.e. A, must be also.
To prove that the set A is countably infinite, we need to show that there exists a bijection (a one-to-one correspondence) between A and the set of positive integers (Z+).
First, let's define a function f: Z+ -> A. We will define f(n) = 3n + 10 for every positive integer n.
Now, let's prove that f is a bijection:
1. Injectivity (one-to-one):
Assume that f(a) = f(b) for some positive integers a and b. This means 3a + 10 = 3b + 10. By subtracting 10 and dividing by 3, we get a = b. Therefore, f is injective.
2. Surjectivity (onto):
Given an arbitrary element, x, in set A, we need to find a positive integer n such that f(n) = x. Let's take any element x = 3k + 7 from set A. By subtracting 7 and dividing by 3, we get k = (x - 7)/3. Since x - 7 is an integer, and dividing it by 3 will give us k, we can say that k is a positive integer. Therefore, for any element in set A, we can always find a positive integer n such that f(n) = x. Thus, f is surjective.
Since f is injective and surjective, it is a bijection. This proves that there exists a bijection between the set A and the set of positive integers (Z+). Therefore, A is countably infinite.