- #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: