patternMinor
$A, B$ --- enumerable sets, is $A \times B$ enumerable?
Viewed 0 times
enumerablesetstimes
Problem
$A, B$ – enumerable sets, is $A \times B$ enumerable?
I have some thoughts, that maybe it can be done using something like the proof of countability of $\mathbb{N} \times \mathbb{N}$, but I don't know how to prove this more proper.
I have some thoughts, that maybe it can be done using something like the proof of countability of $\mathbb{N} \times \mathbb{N}$, but I don't know how to prove this more proper.
Solution
There are many ways you could solve this, so here's a hint. $A$ and $B$ are enumerable, which means that injections
$$ f : A \rightarrow \mathbb{N} \quad \text{and} \quad g : B \rightarrow \mathbb{N}$$
exist. Now, given a tuple $t \in A \times B$, how can you map it to a unique element in $\mathbb{N} \times \mathbb{N}$ using $f$ and $g$?
Since $f$ and $g$ are injections, their product must also be an injection (prove this). So the function $h : A \times B \rightarrow \mathbb{N} \times \mathbb{N}$, defined as $(a, b) \mapsto (f(a), g(b))$. Is an bijection on a subset of $\mathbb{N} \times \mathbb{N}$ (because it is an injection on $\mathbb{N} \times \mathbb{N}$).
A subset of an enumerable set is always countable, so this concludes the proof.
$$ f : A \rightarrow \mathbb{N} \quad \text{and} \quad g : B \rightarrow \mathbb{N}$$
exist. Now, given a tuple $t \in A \times B$, how can you map it to a unique element in $\mathbb{N} \times \mathbb{N}$ using $f$ and $g$?
Since $f$ and $g$ are injections, their product must also be an injection (prove this). So the function $h : A \times B \rightarrow \mathbb{N} \times \mathbb{N}$, defined as $(a, b) \mapsto (f(a), g(b))$. Is an bijection on a subset of $\mathbb{N} \times \mathbb{N}$ (because it is an injection on $\mathbb{N} \times \mathbb{N}$).
A subset of an enumerable set is always countable, so this concludes the proof.
Context
StackExchange Computer Science Q#70511, answer score: 5
Revisions (0)
No revisions yet.