Proving Existence of Injective Binary Operation on $\mathbb{N}\times\mathbb{N}$

[SithsNGiggles]

Homework Statement

Prove or disprove: $\exists$ a binary operation $*:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 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 $*$ to be
$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}$
where $m,n\in\mathbb{N}$.

The problem I have with this is that I think it breaks initial condition that $*$ maps $(a,b)\in\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$ because the list of values of $a*b$ takes on every natural number for $b=1$ (so I have a set with the cardinality of the natural numbers), and then again for $b=2$, and so on.

Basically, and I'm not sure if I'm saying this properly, I (think) I have an operation that maps from $\mathbb{N}\times\mathbb{N}$ onto a set that has cardinality $|\mathbb{N}|^2$, and I'm not sure this helps me in proving the statement. I suppose one question would be if $|\mathbb{N}| = |\mathbb{N}|^2$?

Edit: Another would be, is it even true that $m,n\in\mathbb{N}$? It looks like they might already have been taken on for some combination of $a$ when $b=1$.

 

[jbunniii]

As written, your map is not well defined. Can you please clarify what happens in the sections indicated by "..."? For example, at what value of $a$ does this pattern end:
$$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 \\ \end{cases}$$
If the pattern continues for all $a \in \mathbb{N}$ then there's no way this map can be injective. You will have repeats as soon as you start the $b = 2$ section.

Also, what are the values of $m$ and $n$?

It looks like you are trying to sequence through $\mathbb{N} \times \mathbb{N}$ one column at a time. Hint: I think you will have better success if you try sequencing diagonally.

 

[SammyS]

Homework Statement

Prove or disprove: $\exists$ a binary operation $*:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 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 $*$ to be
$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}$
where $m,n\in\mathbb{N}$.

The problem I have with this is that I think it breaks initial condition that $*$ maps $(a,b)\in\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$ because the list of values of $a*b$ takes on every natural number for $b=1$ (so I have a set with the cardinality of the natural numbers), and then again for $b=2$, and so on.

Basically, and I'm not sure if I'm saying this properly, I (think) I have an operation that maps from $\mathbb{N}\times\mathbb{N}$ onto a set that has cardinality $|\mathbb{N}|^2$, and I'm not sure this helps me in proving the statement. I suppose one question would be if $|\mathbb{N}| = |\mathbb{N}|^2$?

Edit: Another would be, is it even true that $m,n\in\mathbb{N}$? It looks like they might already have been taken on for some combination of $a$ when $b=1$.

How many ordered pairs of natural numbers are there whose sum is k ?

For k < 2. the answer is 0.

For k = 2 the only such ordered pair is (1, 1), so there's one.

For k = 3, the answer is 2; (1, 2) and (2, 1) .

For k = 4, the answer is 3; (1, 3), (2, 2) and (3, 1) .

For k = 5, the answer is 4; (1, 4), (2, 3), (3, 2) and (4, 1) .
...

For k > 2 in general (1, k-1), (2, k-2), (3, k-3), (4, k-4), ... , (k-3, 3), (k-2, 2), and (k-1, 1)

 

[SithsNGiggles]

As written, your map is not well defined. Can you please clarify what happens in the sections indicated by "..."? For example, at what value of $a$ does this pattern end:
$$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 \\ \end{cases}$$
If the pattern continues for all $a \in \mathbb{N}$ then there's no way this map can be injective. You will have repeats as soon as you start the $b = 2$ section.

Also, what are the values of $m$ and $n$?

Oh, I guess it doesn't end. I can't end the pattern because the set of natural numbers is infinite, correct? As for m and n: like you said, the pattern will repeat, so they'd already be listed in first section before the "...".

It looks like you are trying to sequence through $\mathbb{N} \times \mathbb{N}$ one column at a time. Hint: I think you will have better success if you try sequencing diagonally.

I think I see what you're saying. I would have to define my operation as something along the lines of
$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=1 \mbox{ and } b=2\\ 4 & \mbox{if } a=1 \mbox{ and } b=3\\ 5 & \mbox{if } a=2 \mbox{ and } b=2\\ 6 & \mbox{if } a=3 \mbox{ and } b=1\\ 7 & \mbox{if } a=4 \mbox{ and } b=1\\ 8 & \mbox{if } a=3 \mbox{ and } b=2\\ 9 & \mbox{if } a=2 \mbox{ and } b=3\\ 10 & \mbox{if } a=1 \mbox{ and } b=4\\ \vdots \end{cases}$, right?

(I've set up a partial array on paper in which I follow a diagonal pattern, and the above is what I get by using it. )

How many ordered pairs of natural numbers are there whose sum is k ?

For k < 2. the answer is 0.

For k = 2 the only such ordered pair is (1, 1), so there's one.

For k = 3, the answer is 2; (1, 2) and (2, 1) .

For k = 4, the answer is 3; (1, 3), (2, 2) and (3, 1) .

For k = 5, the answer is 4; (1, 4), (2, 3), (3, 2) and (4, 1) .
...

For k > 2 in general (1, k-1), (2, k-2), (3, k-3), (4, k-4), ... , (k-3, 3), (k-2, 2), and (k-1, 1)

Sorry, I'm not seeing why the sum of the coordinates would matter. Could you clarify?

 

[Dick]

Oh, I guess it doesn't end. I can't end the pattern because the set of natural numbers is infinite, correct? As for m and n: like you said, the pattern will repeat, so they'd already be listed in first section before the "...".I think I see what you're saying. I would have to define my operation as something along the lines of
$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=1 \mbox{ and } b=2\\ 4 & \mbox{if } a=1 \mbox{ and } b=3\\ 5 & \mbox{if } a=2 \mbox{ and } b=2\\ 6 & \mbox{if } a=3 \mbox{ and } b=1\\ 7 & \mbox{if } a=4 \mbox{ and } b=1\\ 8 & \mbox{if } a=3 \mbox{ and } b=2\\ 9 & \mbox{if } a=2 \mbox{ and } b=3\\ 10 & \mbox{if } a=1 \mbox{ and } b=4\\ \vdots \end{cases}$, right?

(I've set up a partial array on paper in which I follow a diagonal pattern, and the above is what I get by using it. )

Sorry, I'm not seeing why the sum of the coordinates would matter. Could you clarify?

Yes, your array is one right way to do it. SammyS was just trying to trying to give you hint to do what you just did. First assign integers to the pairs where a+b=2, then to the pairs where a+b=3, then to a+b=4, etc. It's a hint to follow the diagonals instead of the horizontals or verticals.

 

[jbunniii]

I think I see what you're saying. I would have to define my operation as something along the lines of
$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=1 \mbox{ and } b=2\\ 4 & \mbox{if } a=1 \mbox{ and } b=3\\ 5 & \mbox{if } a=2 \mbox{ and } b=2\\ 6 & \mbox{if } a=3 \mbox{ and } b=1\\ 7 & \mbox{if } a=4 \mbox{ and } b=1\\ 8 & \mbox{if } a=3 \mbox{ and } b=2\\ 9 & \mbox{if } a=2 \mbox{ and } b=3\\ 10 & \mbox{if } a=1 \mbox{ and } b=4\\ \vdots \end{cases}$, right?

Yes, that's what I had in mind.

 

[SithsNGiggles]

Alright then, thanks! I didn't quite see how it related until just now. Thanks to everyone else, too!

 

[SithsNGiggles]

Actually, I do have another question. I'm fairly convinced that the operation is one-to-one, but I'm not sure how to go about proving it directly.

I know that a function is injective if $\forall \; x,y \in \mathbb{N}\times\mathbb{N}, \; f(x) = f(y) \Rightarrow x = y$, or equivalently, if $x \not= y \Rightarrow f(x) \not= f(y)$.

Would that mean that, in the case of this particular function, I have to show that $(a_1 * b_1 = a_2 * b_2) \Rightarrow (a_1 = a_2 \wedge b_1 = b_2)$?

Here's my thought process: With the way I've defined $*$, it looks like I pretty much guarantee that $f(x) \not= f(y)$ for $x \not= y$, and so I immediately have the contrapositive version of the injective definition. Is this correct?

 

[SammyS]

Actually, I do have another question. I'm fairly convinced that the operation is one-to-one, but I'm not sure how to go about proving it directly.

I know that a function is injective if $\forall \; x,y \in \mathbb{N}\times\mathbb{N}, \; f(x) = f(y) \Rightarrow x = y$, or equivalently, if $x \not= y \Rightarrow f(x) \not= f(y)$.

Would that mean that, in the case of this particular function, I have to show that $(a_1 * b_1 = a_2 * b_2) \Rightarrow (a_1 = a_2 \wedge b_1 = b_2)$?

Here's my thought process: With the way I've defined $*$, it looks like I pretty much guarantee that $f(x) \not= f(y)$ for $x \not= y$, and so I immediately have the contrapositive version of the injective definition. Is this correct?

It is possible to find a formula which gives the same mapping you have.

The following will help with finding such a formula.

The sum of the natural numbers from 1 through n is given by $\displaystyle \ \ \frac{n(n+1)}{2}\ .$

 

[SithsNGiggles]

It is possible to find a formula which gives the same mapping you have.

The following will help with finding such a formula.

The sum of the natural numbers from 1 through n is given by $\displaystyle \ \ \frac{n(n+1)}{2}\ .$

I noticed that what I'm basically doing is proving that $\mathbb{N}\times\mathbb{N}$ is countable, and I distinctly recall having seen the formula you may be talking about in a previous class.

After looking through my notes from that class, I came upon the following formula:
$2^{m-1}(2n-1)$ (m and n can obviously be replaced with a and b).

I never really understood how the instructor or student (I can't remember who wrote the proof) obtained the formula. Does it use the sum of natural numbers $\dfrac{n(n+1)}{2}$ that you're referring to?

 

[SammyS]

I noticed that what I'm basically doing is proving that $\mathbb{N}\times\mathbb{N}$ is countable, and I distinctly recall having seen the formula you may be talking about in a previous class.

After looking through my notes from that class, I came upon the following formula:
$2^{m-1}(2n-1)$ (m and n can obviously be replaced with a and b).

I never really understood how the instructor or student (I can't remember who wrote the proof) obtained the formula. Does it use the sum of natural numbers $\dfrac{n(n+1)}{2}$ that you're referring to?

The mapping you refer to here, $\ \ 2^{m-1}(2n-1)\,, \$ is perfectly valid, but it differs form the previous mapping you gave in post #4.

Let's define the binary operator, ⊗, by $\displaystyle \ \ m\otimes n=2^{m-1}(2n-1)\ .$

Let's investigate this operation. As it turns out, this mapping is not along the "diagonals" of $\ \mathbb{N}\times\mathbb{N}\ .\$

If m=1, then $\ 2^{m-1}=2^0=1\$ so that 1⊗n = 1, 3, 5, 7, … as n = 1, 2, 3, 4, … . (Odd numbers)

If m=2, then $\ 2^{m-1}=2^{2-1}=2\$ so that 1⊗n = 2, 6, 10, 14, … as n = 1, 2, 3, 4, … . (Odd multiples of 2)

If m=3, then $\ 2^{m-1}=2^{2-1}=2\$ so that 1⊗n = 4, 12, 20, 28, … as n = 1, 2, 3, 4, … . (Odd multiples of 4)

…​

This mapping is not only injective (one-to-one) it's also surjective (onto), and thus it's bijective.

It's also quite easy to decompose (invert): Give the result of m⊗n, you can easily recover both m and n as a unique pair. Do you see how to do that ?


My idea regarding the use of $\ \dfrac{n(n+1)}{2}\$ was to obtain an algebraic formula for a binary operation based on going along the "diagonals" of $\ \mathbb{N}\times\mathbb{N}\,,\$ although it was in a slightly different order than what you did. (I planned to always go along any diagonal in the same direction -- as the first number of the ordered pair increased, starting a 1.) I'm not so sure that either diagonal mapping is easy to decompose.

I think this ⊗ operation will work much better for you.

 

[SithsNGiggles]

Let's define the binary operator, ⊗, by $\displaystyle \ \ m\otimes n=2^{m-1}(2n-1)\ .$

Let's investigate this operation. As it turns out, this mapping is not along the "diagonals" of $\ \mathbb{N}\times\mathbb{N}\ .\$

If m=1, then $\ 2^{m-1}=2^0=1\$ so that 1⊗n = 1, 3, 5, 7, … as n = 1, 2, 3, 4, … . (Odd numbers)

If m=2, then $\ 2^{m-1}=2^{2-1}=2\$ so that 1⊗n = 2, 6, 10, 14, … as n = 1, 2, 3, 4, … . (Odd multiples of 2)

If m=3, then $\ 2^{m-1}=2^{3-1}=4\$ so that 1⊗n = 4, 12, 20, 28, … as n = 1, 2, 3, 4, … . (Odd multiples of 4)

…​

This mapping is not only injective (one-to-one) it's also surjective (onto), and thus it's bijective.

It's also quite easy to decompose (invert): Given the result of m⊗n, you can easily recover both m and n as a unique pair. Do you see how to do that ?
...
I think this ⊗ operation will work much better for you.

Yes, I think you're right about that. As for inverting: given any m⊗n, it looks like I can factor out a power of 2 (if it's even) or simply have 2⁰ multiplied by an odd number (if it's odd).

But supposing I stick with my diagonal mapping, would this reasoning still work to show that the operation is one-to-one?

... With the way I've defined $*$, it looks like I pretty much guarantee that $f(x) \not= f(y)$ for $x \not= y$, and so I immediately have the contrapositive version of the injective definition.

Thanks for the help, much appreciated!

 

[Dick]

Yes, I think you're right about that. As for inverting: given any m⊗n, it looks like I can factor out a power of 2 (if it's even) or simply have 2⁰ multiplied by an odd number (if it's odd).

But supposing I stick with my diagonal mapping, would this reasoning still work to show that the operation is one-to-one?



Thanks for the help, much appreciated!

I don't think it's really profitable to try to write down a formula for the diagonal mapping to show it's invertible, though you probably could. It's the sort of mapping you draw a picture of then say that it's obvious that it is onto and injective.

 

[SithsNGiggles]

I don't think it's really profitable to try to write down a formula for the diagonal mapping to show it's invertible, though you probably could. It's the sort of mapping you draw a picture of then say that it's obvious that it is onto and injective.

Does showing the picture qualify as a proof, though? That's what I'm hoping for. The formula SammyS and I were discussing surely can be used in a proof, and I'm pretty confident that I'd be able to outline a proof using it.

Edit: The reason I'm asking is that in one of my proof-writing courses, when we were covering some set theory (simple union/intersection proofs), we weren't allowed to use Venn diagrams or anything.

 

[Dick]

Does showing the picture qualify as a proof, though? That's what I'm hoping for. The formula SammyS and I were discussing surely can be used in a proof, and I'm pretty confident that I'd be able to outline a proof using it.

Edit: The reason I'm asking is that in one of my proof-writing courses, when we were covering some set theory (simple union/intersection proofs), we weren't allowed to use Venn diagrams or anything.

I would say yes. But I'd say Venn diagrams are proofs as well. The standards of the proof-writing course might say no. The (2^(m-1))*(2n-1) mapping might suit it better.

 

[SteveL27]

Homework Statement

Prove or disprove: $\exists$ a binary operation $*:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ that is injective.

Hint: Think about prime factorization in reverse.

Hint2: This is a trivially easy problem once you see the answer.

 

[SithsNGiggles]

I would say yes. But I'd say Venn diagrams are proofs as well. The standards of the proof-writing course might say no. The (2^(m-1))*(2n-1) mapping might suit it better.

That standard was set by another professor, so I'll try submitting the diagonal mapping. If that doesn't work out, I'll work on the (2^(m-1))*(2n-1) mapping. Thanks.