- #1
SithsNGiggles
- 186
- 0
Homework Statement
Prove or disprove: [itex]\exists[/itex] a binary operation [itex]*:\mathbb{N}\times\mathbb{N}\to\mathbb{N}[/itex] that is injective.
Homework Equations
The Attempt at a Solution
At first, I was under the impression that I could prove this using the following operation. I define [itex]*[/itex] to be
[itex]a*b=\begin{cases}
1, & \mbox{if } a=1 \mbox{ and } b=1 \\
2, & \mbox{if } a=2 \mbox{ and } b=1 \\
3, & \mbox{if } a=3 \mbox{ and } b=1 \\
\vdots \\
m, & \mbox{if } a=1 \mbox{ and } b=2 \\
m+1, & \mbox{if } a=2 \mbox{ and } b=2 \\
m+2, & \mbox{if } a=3 \mbox{ and } b=2 \\
\vdots \\
n, & \mbox{if } a=1 \mbox{ and } b=3 \\
n+1, & \mbox{if } a=2 \mbox{ and } b=3 \\
n+2, & \mbox{if } a=3 \mbox{ and } b=3 \\
\vdots \end{cases}[/itex]
where [itex]m,n\in\mathbb{N}[/itex].
The problem I have with this is that I think it breaks initial condition that [itex]*[/itex] maps [itex](a,b)\in\mathbb{N}\times\mathbb{N}[/itex] onto [itex]\mathbb{N}[/itex] because the list of values of [itex]a*b[/itex] takes on every natural number for [itex]b=1[/itex] (so I have a set with the cardinality of the natural numbers), and then again for [itex]b=2[/itex], and so on.
Basically, and I'm not sure if I'm saying this properly, I (think) I have an operation that maps from [itex]\mathbb{N}\times\mathbb{N}[/itex] onto a set that has cardinality [itex]|\mathbb{N}|^2[/itex], and I'm not sure this helps me in proving the statement. I suppose one question would be if [itex]|\mathbb{N}| = |\mathbb{N}|^2[/itex]?
Edit: Another would be, is it even true that [itex]m,n\in\mathbb{N}[/itex]? It looks like they might already have been taken on for some combination of [itex]a[/itex] when [itex]b=1[/itex].
Last edited: