Let A be a set, and suppose that B is an infinite subset of A. Show that A must

Question

Explanation / Answer

1. Let A be a set and let B be a proper subset of A such that f: A -> B is a bijection (one-to-one correspondence). Seeking a contradiction, suppose A is finite. Then B is also finite, and has fewer elements than A. Thus, by the Pigeonhole Principle, there is some element b of B such that f maps two distinct elements of A both to B. This contradicts the fact that f was a bijection. Since the assumption that A was finite led to a contradiction, then A must be infinite. 2. First I'll show that this is true for countable infinite sets, and then I'll generalize this to all infinite sets. Suppose A is a countable infinite set. Then we may list the distinct elements of A indexed by the natural numbers: A = {a_1, a_2, a_3, ...} Define a function f: A -> {a_2, a_3, a_4, ...} by f(a_n) = f(a_{n + 1}). Then f is evidently a bijection (it's surjective because a_k = f(a_{k - 1}), and it's injective because if a_i ? a_j, then a_{i + 1} ? a_{j + 1} ). Furthermore, {a_2, a_3, a_4, ...} is a proper subset of A, so we are done. Now suppose A is any infinite set. Then it has a countable subset B. By the above, we may suppose B = {b_1, b_2, b_3, ...} . Define a function f: A -> (A B) U {b_2, b_3, b_4, ...} by f(a) = a, if a is in A B f(b_n) = b_{n + 1}, if b is in B. Then f is a bijection (it's a one-to-one correspondence on A B, and it's also a one-to-one correspondence between B and {b_2, b_3, b_4, ...} by the same argument as above), and clearly (A B) U {b_2, b_3, b_4, ...} is a proper subset of f, so we are done.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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