About finding a group on the set of natural numbers.

Errors are my own. Please do tell me if you find any.

I had been developing an interest in the mathematical aspects of computer science and tried exploring a bit of the basics of group theory.

Still don't know too many applications where groups would be interesting to someone who is not a mathematician, but I read that group theory is highly useful in many fields.

This includes:

- Physics: eg: Standard Model of particle physics)
- Chemistry: eg: Symmetry of molecules
- Computer science: Category theory textbooks mention a lot of group theory stuff.

Found this on a webpage related to chemistry:

Group theory is the mathematical application of symmetry to an object to obtain knowledge of its physical properties.

Talking about symmetry, was quite intrigued to find that the possible moves of a Rubik's cube can be represented using group theory concepts (Rubik's Cube group).

Anyway, a few days ago, I was wondering if it was possible to have a group defined over the set of natural numbers.

Where `0 ∉ ℕ`

. ie, ℕ₁.

Couldn't find any. So I asked one of my friends who is a mathematics student.

Randomly tried a few basic operations like addition, multiplication, maximum element etc.

But in each case, either the identity or the inverse would be missing.

Of course, my friend knew the exact definition of groups, but I keep forgetting it and had to look it up again.

Informally speaking, a group is a set `G`

together with a
binary operation `*`

(commonly called multiplication, but
needn't be the multiplication operation) that accepts two element of
`A`

to give an element of `A`

(ie, maintains
closure) which satisfies the following three conditions (known as
*group axioms*):

- Associativity:
`*`

is an associative operation`∀(x y z:G), x * (y * z) = (x * y) * z`

- Identity: There exists an element
`e ∈ G`

such that applying`*`

on`e`

and any value`n ∈ G`

would result in`n`

itself.`∃(e:G), ∀(x:G), x * e = e * x = x`

- There can be only one identity element for the whole group.

- Inverses: For each element
`n ∈ G`

, there exists an element`v ∈ G`

such that applying`*`

on`v`

and`n`

would result in the identity element`e`

.`∀(x:G), ∃(v:G), x * v = v * x = e`

- Unlike the case of the identity element, the inverses for different
elements of
`G`

can be different.

Such a set is usually written as `(G, *)`

. And the name of
its set is often used to refer to the group itself.

After having recalled the definition, we set out on our quest to find a group on ℕ.

When we came upon this post on math stackexchange, we found out that though we can't have a group on ℕ relying on a function operating with ℕ alone, there are other ways.

Just got to find a bijection between ℕ and a set on which a group can be defined.

The set of integers, with the following, constitutes a group:

- binary operation: addition
- identity element: 0
- inverse element given by:
`λx. (-x)`

This group may be denoted with `(ℤ, +, 0, -)`

.

If the binary operation `*`

, internally made use of
functions that can go from `ℕ`

to `ℤ`

and then
back to `ℕ`

from `ℤ`

, then we can make a group out
of `ℕ`

as well!

Let's use a bijection between `ℕ`

and `ℤ`

for
the group on `ℕ`

that we are making.

Inorder to have the group, we need three things:

- Binary operation
- Identity element
- Inverse elements

To help make the binary operation (`*`

), let's first make
a function `f:ℕ → ℤ`

:

```
⎧
⎮ 0, if x = 1
⎮
f(x) = ⎨ k, if x = 2k
⎮
⎮ -k, if x = 2k+1
⎩
```

(This function reminds one of the Hilbert's hotel problem.)

So the values returned by `f(x)`

would be like:

```
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|------+---+---+----+---+----+---+----|
| f(x) | 0 | 1 | -1 | 2 | -2 | 3 | -3 |
```

And the inverse of this function, `f⁻¹:ℕ → ℕ`

, would
be:

```
⎧
⎮ 1, if x = 0
⎮
f⁻¹(x) = ⎨ 2k + 1, if x = -k
⎮
⎮ 2k, if x = k
⎩
```

```
| x | -3 | -2 | -1 | 0 | 1 | 2 | 3 |
|--------+----+----+----+---+---+---+---|
| f⁻¹(x) | 7 | 5 | 3 | 1 | 2 | 4 | 6 |
```

Let the binary operation `*`

be defined as:

```
* : ℕ → ℕ → ℕ
x * y = f⁻¹[f(x) + f(y)]
```

The `f⁻¹ . f`

would be like `(ℕ → ℤ → ℕ)`

and
results in a value in `ℕ`

itself.

Each of the two `f`

usage generates a `ℤ`

value
given a `ℕ`

. Then `f⁻¹`

, which produces a
`ℕ`

out of a `ℤ`

, is applied on the sum of the two
values made with `f`

.

The operation `*`

is still `ℕ → ℕ`

, though
internally `ℤ`

is involved.

Integer addition is associative. And since `f`

(and
`f⁻¹`

) uses just integer addition, `*`

is
associative as well.

`*`

takes `ℕ`

values and returns a
`ℕ`

value. So closure property is satisfied too.

And as an additional perk of the operation `*`

involving
only integer addition, `*`

is also commutative.

Now we need an identity element and a way to find inverse elements.

Let `e`

be the identity element. Then,

```
∀x ∈ G,
x * e = e * x = x
```

Since `*`

is commutative, let's stick with just

```
∀x ∈ G,
x * e = x
```

and

```
x * e = x
=> f⁻¹[f(x) + f(e)] = x
=> f(x) + f(e) = f(x)
=> f(e) = 0
=> e = f⁻¹(0)
=> e = 1
```

Okay, we got our identity as `e = 1`

.

Let's give it a try for `x = 5`

.

```
x * e
= 5 * 1
= f⁻¹[f(5) + f(1)]
= f⁻¹(-2 + 0)
= f⁻¹(-2)
= 5
```

Right, we got `5`

itself. Sounds okay.

Now it's the turn inverses.

Identity `e`

is `1`

.

Let `v`

denote the inverse element.

Then,

```
∀x ∈ G,
x * v = e
```

which in our case is like

```
∀x ∈ G,
x * v = 1
```

Using the definition of `*`

,

```
x * v = 1
=> f⁻¹[f(x) + f(v)] = 1
=> f(x) + f(v) = f(1)
=> f(x) + f(v) = 0
=> f(v) = -f(x)
=> v = f⁻¹[-f(x)]
```

We got three cases to take care of:

- x = 1
- x = 2k
- x = 2k+1

If x = 1,

```
=> v = f⁻¹[-f(1)]
=> v = f⁻¹[0]
=> v = 1
```

and if x = 2k (ie, an even value),

```
=> v = f⁻¹[-f(2k)]
=> v = f⁻¹[-k]
=> v = 2k+1
```

Finally, if x = 2k+1 (ie, an odd value),

```
=> v = f⁻¹[-f(2k+1)]
=> v = f⁻¹[-(-k)]
=> v = f⁻¹[k]
=> v = 2k
```

So, the function to find the inverse can be expressed as:

`inv: ℕ → ℕ`

is like:

```
⎧
⎮ 1, if x = 1
⎮
inv(x) = ⎨ 2k + 1, if x = 2k
⎮
⎮ 2k, if x = 2k+1
⎩
```

```
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|--------+---+---+---+---+---+---+---|
| f⁻¹(x) | 1 | 3 | 2 | 5 | 4 | 7 | 6 |
```

Let's see if the inverse elements are fine.

With x=5, inverse element should be 4. So `5 * v`

should
gives the identity element `1`

.

```
5 * 4
= f⁻¹[f(5) + f(4)]
= f⁻¹[-2 + 2]
= f⁻¹[0]
= 1
```

Likewise, inverse element of 2 should be 3.

```
2 * 3
= f⁻¹[f(2) + f(3)]
= f⁻¹[1 + (-1)]
= f⁻¹[0]
= 1
```

And `1`

should be its own inverse element.

```
1 * 1
= f⁻¹[f(1) + f(1)]
= f⁻¹[0 + 0]
= f⁻¹[0]
= 1
```

Well, it looks okay!

`ℕ`

groupAnd that's it!

We now have the operation, identity and inverses to make up a group
on `ℕ`

.

```
(ℕ, *, 1, inv)
```

As suggested here,
other bijections between `ℕ`

and a set on which a group can
be defined would work as well to make a group on `ℕ`

.

(Not yet sure if *any* such bijection would be okay.)

**Acknowledgements**: Thanks to Aditya, the friend that
I had mentioned, who helped me understand the stuff mentioned in this
blog post.

*Contemporary abstract algebra*(7e) - Joseph A. Gallian- https://math.stackexchange.com/questions/2805173/looking-for-operations-by-which-the-set-of-natural-numbers-becomes-a-group
- https://math.stackexchange.com/questions/190315/representing-a-countable-field-by-bbb-n-transport-of-algebraic-structure/190326#190326

Had made a few random, trivial and futile attempts to find a group on ℕ at first.

Here are some of them.

Assuming that `0 ∈ ℕ`

.

(`ℕ`

, `+`

):

- closure ✓
`∀(x y z:ℕ), x + y = z`

- associative ✓
`∀(x y z:ℕ), x + (y + z) = (x + y) + x`

`e = 0`

can be identity element.`∀n:ℕ, n + 0 = 0 + n = n`

- no inverse (with
`e = 0`

)`∄v:ℕ, ∀n:ℕ, n + v = v + n = 0`

- Eg:
`4 ∈ ℕ`

, but`4 + v = 0`

means`v = -4 ∉ ℕ`

(`ℕ`

, `*`

):

- closure ✓
`∀(x y z:ℕ), x * y = z`

- associative ✓
`∀(x y:ℕ), x * (y * z) = (x * y) * x`

`e = 1`

can be identity element.`∀n:ℕ, n * 1 = 1 * n = n`

- no inverse (with
`e = 1`

)`∄v:ℕ, ∀n:ℕ, n * v = v * n = 1`

- Eg:
`4 ∈ ℕ`

, but`4 * v = 1`

means`v = 1/4 ∉ ℕ`

. Would've been okay if the set was`ℝ`

instead of`ℕ`

.

(`ℕ`

, `max`

):

- closure ✓
`∀(x y z:ℕ), max(x, y) = z`

- associative ✓
`∀(x y z:ℕ), max(x, max(y, z)) = max(max(x, y), z)`

`e = 0`

can be identity element.`∀n:ℕ, max(n, 0) = max(0, n) = n`

- no inverse (with
`e = 0`

)`∄v:ℕ, ∀n:ℕ, max(n, v) = max(v, n) = 0`

- Eg:
`4 ∈ ℕ`

, but`max(4, v) = 0`

means`v ≥ 4`

which is not`0`

(`ℕ`

, `min`

):

- closure ✓
`∀(x y z:ℕ), min(x, y) = z`

- associative ✓
`∀(x y z:ℕ), min(x, min(y, z)) = min(min(x, y), z)`

- can't have an identity element
`∄e:ℕ, ∀n:ℕ, min(n, e) = min(e, n) = n`

- Eg:
`4 ∈ ℕ`

, but`min(4, e) = 4`

means`e ≤ 4`

, but then again`e`

would've have to be different for other`n ∈ ℕ`

.

Sort of a proof for zero being a number that is neither a positive nor negative.

(At some point my friend and I ended up talking about this. Wanted to write it down somewhere. 😃)

Let's do case analysis.

There are two possibilities that we need to consider:

- zero being positive
- zero being negative

Assume that `0`

is positive, then any negative number
multiplied by `0`

should result in a negative number.

But

```
0 * -5 = 0
```

and as per our assumption at this point, `0`

is positive.
So we got a positive value when a negative number should've showed
up.

That's a contradiction.

So, `0`

can't have been positive.

Now, let's consider the other case.

Assume that `0`

is negative, then any negative number
multiplied by `0`

should result in a positive number.

But

```
0 * -5 = 0
```

and as per our assumption at this point, `0`

is negative.
So we got a negative value when a positive value was expected.

That's another contradiction.

Then, `0`

can't have been negative either.

So, `0`

is neither positive nor negative.

```
∎
```