if A and B are countable sets, then prove AxB is countable
To prove that the Cartesian product AxB of two countable sets A and B is countable, we need to establish a one-to-one correspondence between AxB and the set of natural numbers (N). The idea is to construct a function that assigns a unique natural number to each ordered pair in AxB.
Let's start by assuming that A and B are both countable sets. This means that there exist one-to-one correspondences between A and N (A ∼ N) and between B and N (B ∼ N).
To construct a one-to-one correspondence between AxB and N, we can use a technique called the Cantor pairing function. This function allows us to map a pair of natural numbers onto a unique natural number.
The Cantor pairing function can be defined as follows:
P: N x N → N
P(i, j) = (i + j)(i + j + 1)/2 + j
Now, let's define a function f: AxB → N as follows:
f(a, b) = P(f_a(a), f_b(b))
where f_a: A → N and f_b: B → N are the one-to-one correspondences between A and N, and between B and N, respectively.
Since both A and B have one-to-one correspondences with N, we can define f_a and f_b accordingly. Then, using the Cantor pairing function, we can map each ordered pair (a, b) ∈ AxB to a unique natural number f(a, b) ∈ N.
To show that f is a one-to-one correspondence, we need to demonstrate that it is both injective (one-to-one) and surjective (onto).
Injectivity: Suppose we have two ordered pairs (a, b) and (c, d) in AxB such that f(a, b) = f(c, d). By the definition of f, this implies P(f_a(a), f_b(b)) = P(f_a(c), f_b(d)). By the injectivity of the Cantor pairing function, we can conclude that f_a(a) = f_a(c) and f_b(b) = f_b(d). Since f_a and f_b are both one-to-one correspondences, this implies a = c and b = d. Hence, f is injective.
Surjectivity: Given an arbitrary natural number n ∈ N, we need to find an ordered pair (a, b) ∈ AxB such that f(a, b) = n. We can do this by mapping n back to the corresponding ordered pair using the inverse of the Cantor pairing function and then using the inverse of the one-to-one correspondences f_a and f_b to find the corresponding elements a and b in A and B, respectively. Since both f_a and f_b are surjections, we will always be able to find such (a, b). Hence, f is surjective.
Therefore, we have established a one-to-one correspondence between AxB and N, which proves that AxB is countable.