Group on natural numbers

Tags: / math /

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:

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.

Definition of a group

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

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 ℕ.

An 'indirect' way

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:

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

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.

identity element

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.

Inverse elements

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:

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!

The ℕ group

And 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.

References

Addendum

Random initial attempts to find group on ℕ

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

Here are some of them.

Assuming that 0 ∈ ℕ.

(ℕ, +):

(ℕ, *):

(ℕ, max):

(ℕ, min):

Zero is neither positive nor negative

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:

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.

∎