As usual, let’s refresh some definitions we will use to solve this exercise.
Definition: Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Hence, A × B = {(a, b) | a ∈ A ∧ b ∈ B}.
Definition: The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective.
Definition: The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.
All definitions were taken from the textbook Discrete Mathematics and its Applications by Rosen.
If |A|=|B|, then there exists a one-to-one correspondence f from A to B.
Also, if |C|=|D|, then there exists a one-to-one correspondence g from C to D.
From the definition of the cartesian product, we get that:
|AxC| = {(a,c), such that a ∈ A ∧ c ∈ C}
|BxD| = {(b,d), such that b ∈ b ∧ d ∈ D}
Then, the function h(a,c) = (f(a),g(c)), from |AxC| to |BxD| is also a one-to-one correspondence.
Therefore, |A×C|=|B×D|.
Related posts:
- Show that if A and B are sets and A⊂B then |A|≤|B|
- Determine whether each of these sets is finite, countably infinite, or uncountable.
- Show that a finite group of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest.
- Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set
- Give an example of two uncountable sets A and B such that A−B is
