Identity element

Since we'be discussing a lot of mathematics on this forum recently I decided to post and old problem.

Show that a set with a finite number of elements which is closed under the operation * (* is commutative) contains at least one identity element.

Can I assume the operation is associative (in which case I've got a partial proof)?

Originally posted by DeepThought
Can I assume the operation is associative (in which case I've got a partial proof)?

Yes, you can.

Originally posted by adam warlock
Yes, you can.

I'm a bit stuck on this, so I'll present the special case. Then I'll think some more about it. I need an extra axiom, so I'll list the axioms I've got, and add my extra one:

A) Closure, for all a, b there exists c = a*b
B) Associativity, for all a, b, c; a*(b*c) = (a*b)*c
C) Commutativity, for all a, b; a*b = b*a
D) There are a finite number of elements.
E) Extra axiom, for all a, b, c, if a*b = a*c then b = c

We can classify elements of S into three types. Type I elements are identity candidates a*a = a; Type II elements are ones where if we square them and then square the result and so one we end up back where we started. Type III are all others.

So:
Type I) a*a = a
Type II) a*a = b; b*b = c; c*c = d; d*d = a (although the list could be much longer, and there need not be only one such subset of looping elements, the loops do have to be disjoint)
Type III) all other elements, they form chains starting with an element a that is not the square of any element and a*a = b; b*b = c; c*c = element of type I or type II (Again the chain can be of arbitrary length assuming we don't run out of elements).

I'm guaranteed that starting with a type III element and going along the chain of elements will get me to a type I or II element as the set is finite (Axiom D). Consider type II elements.

Lemma: for all x, a there exists y such that x = a*y. Consider the product of a with each member of the set, by closure each such product must be in the set, and each such product must be different by axiom E, so the set of products span the set and y exists.

Now, consider the product of all the elements of type II which form a closed loop (there may be more than one closed loop but they must be disjoint, I only want one of the disjoint ones). Suppose, without loss of generality (the magic words 🙂) the loop is length 4 and the product of them is z = a*b*c*d; a*a = b; b*b = c; c*c = d; d*d = a

a*z = a*(a*b*c*d) = (a*a)*b*c*d = b*b*c*d = c*c*d = d*d = a; where I've used the associativity axiom.
b*z = b*a*b*c*d = a*(b*b)*c*d = a*c*c*d = a*d*d = a*a = b; where I've used both the associativity and commutativity axioms.

similarly for c and d.

By completeness z = a*b*c*d is in the set and it is an indentity w.r.t. a, b, c, and d. z cannot be one of the elements a, b, c, or d - say it is b, then b*z = b*b = c but b*z = b. So now I need to show that z*x = x, when x is any element.

By my lemma (this is what I need the extra axiom for) there exists y such that x = a*y for any x in the set and a of Type II.
Then x*z = (y * a) * z = y * (a * z) = y * a = x
So z is an inverse w.r.t. all elements of the set []

Now I need to work out how to do this for the cases where a*b = a*c does not imply that b = c. Which I'm a bit stuck on.

A few additional comments. There must be at least one element of type I or a set of elements of type II. If there were not then my elements of type III would have nothing to terminate on and the set is finite. The proof works if there are no elements of type II since then there must be an element of type I - a type I element is like a type II element but the loop is of length 1, so the same argument works.

z must be of type I because:
z*z = (a*b*c*d)*(a*b*c*d) = a*a*b*b*c*c*d*d = b*c*d*a = a*b*c*d = z

So my only problem is with elements of type III and sets with two or more disjoint groupings of elements of type II.

Originally posted by DeepThought
I'm a bit stuck on this, so I'll present the special case. Then I'll think some more about it. I need an extra axiom, so I'll list the axioms I've got, and add my extra one:

A) Closure, for all a, b there exists c = a*b
B) Associativity, for all a, b, c; a*(b*c) = (a*b)*c
C) Commutativity, for all a, b; a*b = b*a
D) There are a finite number of e ...[text shortened]... w to do this for the cases where a*b = a*c does not imply that b = c. Which I'm a bit stuck on.

I like your idea of divide and conquer but it seems that you're trying to kill flies with a cannon.

Your extra axiom is equivalent to saying that there exists an inverse element to the * operation. And for an inverse element to exist you need to have the identity element. So in a way you're assuming what you want to prove.

I'll give you a hint for an elegant proof of this result. List all elements of this set and use * on all of them. Take a look at the result and work from there.

The post that was quoted here has been removed

First sentence of your link: "In mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element...". Hence there was nothing wrong with my sentence: "a set with a finite number of elements which is closed under the operation *" because it implies that I'm describing a group (a set of elements together with an operation).

Care to try and solve the problem?

Originally posted by adam warlock
First sentence of your link: "In mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element...". Hence there was nothing wrong with my sentence: "a set with a finite number of elements which is closed under the operation *" because it implies that I'm describing a group (a set of elements together with an operation).

Care to try and solve the problem?

If it's a group then the inverse axiom is present. Although since the presence of an identity is not explicitly in the axioms I've still proved that my extra axiom guarantees an identity element and inverse for each element.

Part of the reason for posting my special case proof was to see if I was barking up the wrong tree or not.

The post that was quoted here has been removed

Sigh, I'll say it more clearly to see if it gets through your thick mathematical genius skull:

If I state the problem with the word group instead of the word set then there is no need to prove that there exists an identity element since by definition a group needs to have an identity element (just check the link you provided in case you don't take my word for it 😵😵😵. But read all the way through because maybe, just maybe you'll get the understand what is a group and what is the difference between a set, a group and a set with an * operation defined (not all of these sets need to be groups)).

Your facade of having great mathematical knowledge is getting thinner as the days pass.

Originally posted by DeepThought
If it's a group then the inverse axiom is present. Although since the presence of an identity is not explicitly in the axioms I've still proved that my extra axiom guarantees an identity element and inverse for each element.

Part of the reason for posting my special case proof was to see if I was barking up the wrong tree or not.

If it is a group then you need not to prove that there is an identity element since a group by definition has an identity element.

The conditions are:

It is a set
It has finite elements
It has an * operation which is commutative and associative.

And only those conditions.

If you insert the extra condition that there exists an inverse element than you are implicitly assuming the existence of an identity element.

Originally posted by adam warlock
If it is a group then you need not to prove that there is an identity element since a group by definition has an identity element.

The conditions are:

It is a set
It has finite elements
It has an * operation which is commutative and associative.

And only those conditions.

If you insert the extra condition that there exists an inverse element than you are implicitly assuming the existence of an identity element.

I'm left wondering if you expect the subset generated by taking product of an arbitrary element x with each element of the set to be the entire set. I added my extra axiom specifically to generate that condition. If not then I don't think it's trivial to show some sort of contradiction if it doesn't. Just checking?

Originally posted by DeepThought
I'm left wondering if you expect the subset generated by taking product of an arbitrary element x with each element of the set to be the entire set. I added my extra axiom specifically to generate that condition. If not then I don't think it's trivial to show some sort of contradiction if it doesn't. Just checking?

Consider that the set has n elements: a_1, a_2,..., a_n

Take the "product" a_1*a_2*...*a_n.

From this, the result will follow.