Hi.
I think math is really cool, but, most people (sadly) don't think so. This includes many programmers who in fact enjoy many of the same things that mathematicians do, but, are more practical for most of the time.
I'll show you why abstract algebra (in particular, group theory) is really cool, and why you don't have to be a freaking genius to get it.
Firstly, in order to understand most of this, you'll need to understand a tiny bit of Set theory, and to save time, I'll just refer you to wikipedia for that one (you just need to understand basic unions and intersections).
Let's begin with a simple definition, of a group (note: for hardcore types, this isn't fully rigorous because I haven't defined what an operation is, but, you get the idea).
A group is defined:
1)
A set (usually called $S$) with an operation attached (we call the operation $*$), so, if $G$ is a group,
$G = <S, *>$
2) Closure is one property that all groups must have in order for them to be a group. Closure means:
If $G = <S, *>$ and $x \epsilon S$ and $y \epsilon S$, then $x*y \epsilon S$
Note: $*$ does NOT NECESSARILY MEAN MULTIPLICATION!
3)
All groups have an identity element $e$, such that ( we are still considering the group $G$ with operation $*$):
For all $x \epsilon S$, $x*e = x$
4)
All elements in a group have an inverse,
If $a \epsilon S$, $a^{-1} \epsilon S$ such that:
$a * a^{-1} = e$
5)
The operation $*$ is associative. That means:
$(a*b)*c = a*(b*c)$
Alright, why in the world would anyone in their right mind define something like that?!
Let's take a step back, and understand where this comes from.
Around the 19th century or so, people realized that elementary algebra wasn't the only type of algebra that existed. There were all kinds of other algebras, like matrix algebra, and vector algebra and boolean algebra, and all these new all these new kinds of algebras kept cropping up with all these new rules (like, matrix multplication isn't commutative, that means: $A*B$ is not necessarily equal to $B*A$ when $B$ and $A$ are matrices) because mathematicians now had to solve all kinds of new problems.
And, the problem was, mathematics was losing its "connectivity", all these new algebras had little to no connection to each other, and it was very difficult to make progress in a few of these algebras at once.
Then, there was a clever idea. All of these algebras still were only doing a few operations on a set (or crossproducts of sets) and then were equating those operations on sets. That's how abstract algebra came along. Mathematicians realized that they could define "algebraic structures" (i.e. define algebraic systems so they followed a few axioms), and prove things about those algebraic structures, and any algebra that was then invented that could be proven to fit that algebraic structure would automatically have all the properties that people had proved about those structures!
Basically, if you came up with a new algebra, called "Cheese Algebra" and it has all these funny rules, but, it handles only one operation and you can prove that Cheese Algebra has all the properties of a Group, you're done! That means that all the things people have proven for Groups are automatically true for Cheese Algebra!
Isn't that awesome?
Let's try it.
The definition of a group is pretty simple, but, there are a few catches. First and foremost, the $*$ operation is not multiplication. Read the sentence over again. And again.
Secondly, in a group $a*b$ is not necessarily equal to $b*a$. Groups in which this is true are called Abelian groups and they make your life much easier, but, not all groups are like that.
Then, there are some basic theorems about groups that can be proven, and these are some important ones:
The first one is pretty easy, we assume there are two identities, $e_1$ and $e_2$ for a group $G = <S, *>$ and this would mean,
$e_1*e_2 = e_1$ (consider $e_2$ as the identity element)
$e_1*e_2 = e_2$ (consider $e_1$ as the identity element)
Which means $e_1=e_2$, which is a contradiction.
The second one is really similar, so, I won't go into the details.
The third one is a bit different, you first prove $(a*b)^-1 = b^{-1} * a^{-1}$ and then use the associative property of groups.
Okay, so, what does this mean?
Well, each of these properties hold for every algebraic system that's a group!
So, for example, matrices (the ones that do have inverses) form a group under the operation of multiplication, so, we've figured out a bunch of cool properties about matrices, like
The inverse of the inverse of a matrix is the matrix itself.
And, we haven't dealt with a single $a_ij$ component (although we would in proving that "inverseable" matrices do indeed form a group under multiplication)!
Also, the real numbers (excluding zero) form a group under multiplication, so, we can say this, too,
The reciprocal of the recipocral of a real number is the real number itself.
And, vectors form a group under addition (this one's really easy to prove, I suggest you try with the axioms given, hint: the identity is the vector <0,0,0>), too:
If you negate the negative of a vector, you get the vector itself.
Notice that the inverse operations change with each of them, but, the idea is still the same, so, with the single idea of a group, we've solved problems in a bunch of different areas of mathematics.
Let's try something a bit more complex, let's solve an equation on a group. What does that mean? Well, we can't use our knowledge of existing algebra, we can only use the axioms about groups, and the things we proved from them in order to solve the equation.
Now, I'll show you the equation, but, try solving it first if you can before looking at the solution, it'll give you a different kind of appreciation for the solution.
Solve the equation $a*x*b = c$ for $x$ in terms of $a, b, c$, which are constants.
Solution
=======
Multiply both sides by $b^{-1}$,
$a*x*b*b^{-1} = c*b^{-1}$
Since $b*b^{-1} = e$,
$a*x*e = c*b^{-1}$
Since, $a*x*e = (a*x)*e = a*x$,
$a*x = c*b^{-1}$
Now, since each element of the group has a unique inverse, we can take the inverse of both sides of the equation, and the equation will still hold true:
$(a*x)^-1 = (c*b^{-1})^{-1}$
Which is the same as:
$x^{-1}*a^{-1} = b*c^{-1}$
Multiply both sides by $a$,
$x^{-1} = b*c^{-1}*a$
Take the inverse of both sides again, and notcie $(a^{-1})^{-1}$,
$x = a^{-1}*c*b^{-1}$
Yay!
Now, what's (again) really cool, is that this works for every, single freaking algebraic system that you can think of that's a group. Matrices with multiplication? Done. Real numbers with multiplication (aside from 0)? Done. Vectors with addition? Done.
Abstract algebra doesn't stop there, it defines all these structures that have similar properties like Rings and Fields that you can use to prove things in a bunch of different algebras in one fell swoop.
I hope you liked this article, and I'd love your feedback, email me at dhaivatpandya at g mail dot com, or comment below :)
EDIT: I forgot to mention some applications to CS.
Alright, you guys know how Haskell?
Haskell (and any ML-type language, really) uses something known as Algebraic data types, which basically let you specify datatypes that follow certain axioms, in a way.
Even though it is completely your responsibility to make sure that these structures form some kind of helpful algebra, the relation is still there.
And, about classes in OOP languages, there's a very close correlation.
You can very nearly think of classes as a algebraic structure that have many operations (methods) and elements (fields, variables, etc.), but, this isn't a perfect correlation because of many things that OOP languages let you do that are functionally "impure", and mathematics is a completely pure functional language (which is why it maps to Haskell so nicely), there is no state.
I think math is really cool, but, most people (sadly) don't think so. This includes many programmers who in fact enjoy many of the same things that mathematicians do, but, are more practical for most of the time.
I'll show you why abstract algebra (in particular, group theory) is really cool, and why you don't have to be a freaking genius to get it.
Firstly, in order to understand most of this, you'll need to understand a tiny bit of Set theory, and to save time, I'll just refer you to wikipedia for that one (you just need to understand basic unions and intersections).
Let's begin with a simple definition, of a group (note: for hardcore types, this isn't fully rigorous because I haven't defined what an operation is, but, you get the idea).
A group is defined:
1)
A set (usually called $S$) with an operation attached (we call the operation $*$), so, if $G$ is a group,
$G = <S, *>$
2) Closure is one property that all groups must have in order for them to be a group. Closure means:
If $G = <S, *>$ and $x \epsilon S$ and $y \epsilon S$, then $x*y \epsilon S$
Note: $*$ does NOT NECESSARILY MEAN MULTIPLICATION!
3)
All groups have an identity element $e$, such that ( we are still considering the group $G$ with operation $*$):
For all $x \epsilon S$, $x*e = x$
4)
All elements in a group have an inverse,
If $a \epsilon S$, $a^{-1} \epsilon S$ such that:
$a * a^{-1} = e$
5)
The operation $*$ is associative. That means:
$(a*b)*c = a*(b*c)$
Alright, why in the world would anyone in their right mind define something like that?!
Let's take a step back, and understand where this comes from.
Around the 19th century or so, people realized that elementary algebra wasn't the only type of algebra that existed. There were all kinds of other algebras, like matrix algebra, and vector algebra and boolean algebra, and all these new all these new kinds of algebras kept cropping up with all these new rules (like, matrix multplication isn't commutative, that means: $A*B$ is not necessarily equal to $B*A$ when $B$ and $A$ are matrices) because mathematicians now had to solve all kinds of new problems.
And, the problem was, mathematics was losing its "connectivity", all these new algebras had little to no connection to each other, and it was very difficult to make progress in a few of these algebras at once.
Then, there was a clever idea. All of these algebras still were only doing a few operations on a set (or crossproducts of sets) and then were equating those operations on sets. That's how abstract algebra came along. Mathematicians realized that they could define "algebraic structures" (i.e. define algebraic systems so they followed a few axioms), and prove things about those algebraic structures, and any algebra that was then invented that could be proven to fit that algebraic structure would automatically have all the properties that people had proved about those structures!
Basically, if you came up with a new algebra, called "Cheese Algebra" and it has all these funny rules, but, it handles only one operation and you can prove that Cheese Algebra has all the properties of a Group, you're done! That means that all the things people have proven for Groups are automatically true for Cheese Algebra!
Isn't that awesome?
Let's try it.
The definition of a group is pretty simple, but, there are a few catches. First and foremost, the $*$ operation is not multiplication. Read the sentence over again. And again.
Secondly, in a group $a*b$ is not necessarily equal to $b*a$. Groups in which this is true are called Abelian groups and they make your life much easier, but, not all groups are like that.
Then, there are some basic theorems about groups that can be proven, and these are some important ones:
- A group has a single, unique identity element
- Every element of a group has a single, unique inverse
- $(a_1*a_2*a_3* ... * a_n)^ {-1} = (a_n^{-1} * a_{n-1}^{-1} * a_{n-2}^{-1} * ... * a_1^{-1})$
- $(a^{-1})^{-1} = a$
The first one is pretty easy, we assume there are two identities, $e_1$ and $e_2$ for a group $G = <S, *>$ and this would mean,
$e_1*e_2 = e_1$ (consider $e_2$ as the identity element)
$e_1*e_2 = e_2$ (consider $e_1$ as the identity element)
Which means $e_1=e_2$, which is a contradiction.
The second one is really similar, so, I won't go into the details.
The third one is a bit different, you first prove $(a*b)^-1 = b^{-1} * a^{-1}$ and then use the associative property of groups.
Okay, so, what does this mean?
Well, each of these properties hold for every algebraic system that's a group!
So, for example, matrices (the ones that do have inverses) form a group under the operation of multiplication, so, we've figured out a bunch of cool properties about matrices, like
The inverse of the inverse of a matrix is the matrix itself.
And, we haven't dealt with a single $a_ij$ component (although we would in proving that "inverseable" matrices do indeed form a group under multiplication)!
Also, the real numbers (excluding zero) form a group under multiplication, so, we can say this, too,
The reciprocal of the recipocral of a real number is the real number itself.
And, vectors form a group under addition (this one's really easy to prove, I suggest you try with the axioms given, hint: the identity is the vector <0,0,0>), too:
If you negate the negative of a vector, you get the vector itself.
Notice that the inverse operations change with each of them, but, the idea is still the same, so, with the single idea of a group, we've solved problems in a bunch of different areas of mathematics.
Let's try something a bit more complex, let's solve an equation on a group. What does that mean? Well, we can't use our knowledge of existing algebra, we can only use the axioms about groups, and the things we proved from them in order to solve the equation.
Now, I'll show you the equation, but, try solving it first if you can before looking at the solution, it'll give you a different kind of appreciation for the solution.
Solve the equation $a*x*b = c$ for $x$ in terms of $a, b, c$, which are constants.
Solution
=======
Multiply both sides by $b^{-1}$,
$a*x*b*b^{-1} = c*b^{-1}$
Since $b*b^{-1} = e$,
$a*x*e = c*b^{-1}$
Since, $a*x*e = (a*x)*e = a*x$,
$a*x = c*b^{-1}$
Now, since each element of the group has a unique inverse, we can take the inverse of both sides of the equation, and the equation will still hold true:
$(a*x)^-1 = (c*b^{-1})^{-1}$
Which is the same as:
$x^{-1}*a^{-1} = b*c^{-1}$
Multiply both sides by $a$,
$x^{-1} = b*c^{-1}*a$
Take the inverse of both sides again, and notcie $(a^{-1})^{-1}$,
$x = a^{-1}*c*b^{-1}$
Yay!
Now, what's (again) really cool, is that this works for every, single freaking algebraic system that you can think of that's a group. Matrices with multiplication? Done. Real numbers with multiplication (aside from 0)? Done. Vectors with addition? Done.
Abstract algebra doesn't stop there, it defines all these structures that have similar properties like Rings and Fields that you can use to prove things in a bunch of different algebras in one fell swoop.
I hope you liked this article, and I'd love your feedback, email me at dhaivatpandya at g mail dot com, or comment below :)
EDIT: I forgot to mention some applications to CS.
Alright, you guys know how Haskell?
Haskell (and any ML-type language, really) uses something known as Algebraic data types, which basically let you specify datatypes that follow certain axioms, in a way.
Even though it is completely your responsibility to make sure that these structures form some kind of helpful algebra, the relation is still there.
And, about classes in OOP languages, there's a very close correlation.
You can very nearly think of classes as a algebraic structure that have many operations (methods) and elements (fields, variables, etc.), but, this isn't a perfect correlation because of many things that OOP languages let you do that are functionally "impure", and mathematics is a completely pure functional language (which is why it maps to Haskell so nicely), there is no state.
You lost me right after "The first one is pretty easy".
ReplyDeleteWhy are there two identities when there should only be one? And what is an identity anyway? A number? Why is e1 = e2 a contradiction?
Why is the second theorem really similar? In what way is it similar?
For theorem #4, What is that "1" with the upper bar in front of it? Is that supposed to be an equals?
"The inverse of the inverse of a matrix is the matrix itself." I don't get where this conclusion is coming from.
The rest of it requires knowledge from before, so I'm completely lost at this point.
Groups are invented for a different purpose. I hate the theorem, proof approach. One has to be present with the problem, and then tools to solve them. Groups have at least 300 years of history. One the most important, easy and beautiful tools of math.
DeleteNow to your question. The statement should begin like this " we assume there are two identities, e1 and e2 for a group G=, and e_1 <> e_2 and this would mean" e_1 <> e_2 was missing.
But again, you don't learn math in blog comments. ;)
Its pretty hard to come up with a problem that people can relate to easily when working with something like group theory, but, I have tried that approach in newer posts.
DeleteThanks a lot for the feedback!
Do follow (top right) if you like it :)
You present a very clear introduction to algebra here, which is much more accessible than, say, the relevant wikipedia articles. You keep it nice and simple and to the point.
ReplyDeleteFor math geeks, I think this is great -- you start off with some definitions, then a little history, and then start to show the power of this abstract concept. I imagine that you'd follow this up with some practical uses (e.g. computer graphics).
I'm worried that for computer engineers, and to a lesser extent computer scientists, this may still be too abstract. I recall several math courses starting off this way, with definitions, some history, then looking at properties and deriving interesting theorems. Maybe it would be possible to motivate the power of group theory by starting with a problem in computer science and describing how an understanding of group theory can lead to a better understanding of the problem and solution? I'm thinking of something like quaternions and understanding how they interact (without needing to deal with imaginary numbers). I'm sure you know many more interesting problems in computer science and engineering, and I can't wait to read more about them.
Wolter:
ReplyDeleteThe contradiction occurs because we assumed that it had two different identities, but, they turn out to be the same, which means that there is only one identity per group.
The second theorem is very similar because it requires that you use the same idea as the first:
i.e. Assume $a$ has two inverse $a^{-1}_1$ and $a^{-1}_2$, and then we know:
$a * a^{-1}_1 = e = a * a^{-1}_2$
Therefore,
$a^{-1}_1 = a^{-1}_2$
As for the Theorem #4 question, that was a fault in my part, its supposed to mean:
$(a^{-1})^{-1}$
And the matrix conclusion is coming from the fact that matrix multiplication is forms a group,
so, if you have a matrix $M$, then:
$(M^{-1})^{-1} = M$
by Theorem #4.
@coshx
Thanks a lot for the feedback! I will be doing more stuff on this considering the postive feedback I've gotten, and I will be doing more applications, but, as always, applications are slightly more difficult to understand than just pure math, so, I'll be presenting a proper application in the next one (which will probably introduce Rings as well).
Dhaivat,
ReplyDeleteThanks for your post. It lost me about halfway through. I may try again in the morning when I'm rested. You say that applications are more difficult to understand than pure math. If you're talking about programming applications, they may be slightly more difficult for you, but for most of us, the pure math is more difficult, which is why we became programmers and not mathmaticians. If you're specifically targeting programmers, then starting off with a practical application, even one involving a language that not many programmers know, such as Haskell (I'm learning it now), would be extremely beneficial.
The thing is, with group theory, a subject so abstract, a very practical matter would be more difficult to understand than the pure math because most practical applications require a strong understanding of group theory (isomorphisms, rings, fields, etc.), that's why I refrained from using practical applications. But, with the next one, I assure you there'll be much more practical stuff :)
ReplyDeleteIf you're getting stuck with it, try going slow, group theory is very abstract subject, so taking it slow would be best :)
If are still having trouble, contact me on dhaivatpandya AT gmail DOT com, my twitter at dhaivatpoincare, or just leave a comment here, I'll do my best to help :)
Hey Dhaivat,
ReplyDeleteThis is a bit nit-picky, but...
Your definition of an "identity" element is not quite right:
>"All groups have an identity element e, such that:
For all xϵS, x∗e=x"
This is a right-identity. It's also important that e is a left-identity as well for it to be an "identity".
i.e. For all xϵS, e*x=x
Your later proof shows that if there is a left identity and a right identity, they must be equal (and therefore unique).
Basically there are three statements which are equivalent:
A) The set has at least one left identity and at least one right identity (not necessarily the same).
B) The set has at least one element which is both a left and a right identity.
C) The set has exactly one element which is both a left identity and a right identity.
I don't think it matters which one you take as the definition, and which one you later prove the equivalence of.
Hi Dhaivat,
ReplyDeleteYour explanation is fantastically good. You are brilliant at exposing concepts that are not necessarily easy to understand. I hope you will write many more such articles, because they are truly refreshing.
I have been looking for articles such as yours, that clarify with real examples and exercises, how to compute LALR1 lookahead sets in the presence of numerous epsilon rules, and how to understand the results intuitively. Unfortunately, nobody in that area seems to have pen as good as yours ...
Your definition of an identity element is incomplete. You also need that if e is the identity element, e * x = x for all x in S (for example, to prove that there can be only one identity element).
ReplyDeleteWithout this, I could define S to be the reals, and the * operation to be an identity operation, so that x * y = x for all x, y in S. This is obviously not a group, but it satisfies your definition.
"The contradiction occurs because we assumed that it had two different identities, but, they turn out to be the same"
ReplyDeleteSo if e1 turned out to be "1" and e2 turned out to be "2", then 1 = 2? Is that the contradiction?
"(a−1)−1"
But what does that mean? There's no equals sign in there anywhere.
Also, looking further ahead, why not just multiply both sides by a-1 and then multiply by b-1 to get x = a-1 * c * b-1? It seems like all the other steps just complicate things.
On a related note, proving inverses to be unique (your second theorem) is perhaps similar to proving the identity unique (your first theorem), but you should probably mention that you first have to prove that a * a^-1 = e implies a^-1 * a = e (this follows from the uniqueness of the identity element and some fiddling with associativity).
ReplyDelete@Jeremy: I have read about left and right identities, but, I sort of left them out for the sake of decreasing complexity, but, they do leave a small hole, yes.
ReplyDelete@Erik
Thanks for your feedback, its really encouraging. I will be covering more and more stuff, so, stay tuned.
@Alex
See what I said to Jeremy. Basically, I'm trading complete rigor for a more understandable idea.
@Wolter
No, no see, $e_1$ and $e_2$ were assumed to be *different* identity elements, but it turns out that they are in fact the same, so, we can only have one identity element $e$, so, there's no question of $e_2=2$ and $e_1=1$ because they're the same, and we assumed that they were different.
(a-1)-1 isn't what it says, it says $(a^{-1})^{-1}$
Where $a^{-1}$ is the inverse of $a$ such that:
$a * a^{-1} = e$
And, for your last question, you can't do that since you would be assuming that the * operation is commutative which isn't necessarily true.
Hopefully that made sense, if it didn't, I'm still awake for another hour :)
I understand your comments about rigor, and maybe I will include most things in the next one, but, I really wanted this one to be understandable to all audiences and not to be bogged down into details.
ReplyDeleteHowever, I did miss the
$a*e = a = e*a$
which should have been mentioned.
So how do you decide what the identity element is?
ReplyDeleteAlso, I thought multiplication was commutative?
Oh almost forgot. I wrote (a-1)-1 this way because that's how it copy/pastes. But I still don't understand what it's supposed to means since there's no equals in there.
ReplyDelete@Wolter
ReplyDeleteMultiplication is commutative, but, the * operand just represents a generic operation, not necessarily multiplication.
The identity element is usually found using some ideas of the set and operation you're considering.
Like, if you're consider integers as your set, and addition as your operation, your identity element would be 0, since any integer + 0 = that integer.
And, for the $(a^{-1})^{-1}$, it was my mistake again, I'm sorry I didn't understand you earlier, now its fixed, you should go look :)
I like your post. It seems the definition of a group you give is very similar to the definition of Monoids in Haskell or Scala (aka type theory). As a matter of fact, as currently learning about it, application of monoids can lead to very useful code patterns like unfolding data in tree structures (nodes in the trees being seen as context holding data values). Thank you for sharing.
ReplyDeleteyes, since mathematics is a purely functional language, languages like haskell, scala (even clojure to some extent) map very nicely to it, and especially group theory since functional programming languages can be a special type of algebra.
ReplyDelete"Multiplication is commutative, but, the * operand just represents a generic operation, not necessarily multiplication."
ReplyDeleteOk, but in your example, you're saying to multiply both sides, so isn't it multiplication in this case?
"Like, if you're consider integers as your set, and addition as your operation, your identity element would be 0, since any integer + 0 = that integer."
OK, so if you were to assume that 0 and 1 were identity elements in this case, then 0 = 1 would be the contradiction?
No, i'm not multiplying, I'm just using the operand * on both sides (its called the multiplicative operand, but its got nothing to do with multiplication
ReplyDeleteNo, 0 and 1 are not the identity elements, only 0 is the identity element. Because if you take any number, say 6 and add 1 to it, you don't get 6 back, you get 7, so, 1 is not the identity element.
But in your example, you say "Multiply both sides by b−1"...
ReplyDelete"No, 0 and 1 are not the identity elements, only 0 is the identity element."
Yes, I understand this, but I'm talking about the assumption of 2 identity elements as you stated before: "e1 * e2 = e1" and "e1 * e2 = e2", thus e1 = e2. But if you chose 0 and 1 as your assumed identity elements that would mean 0 = 1... Is that what you mean by the contradiction?
I say "multiply both sides by" because the * is called the multiplicative operand, even though its got nothing to do with multiplication (that's really stupid, I know, but that's the way it works)
ReplyDeleteFair enough.
ReplyDeleteSo partway through the example you end up with "a∗x=c∗b−1". From there, why can't you just multiply both sides by a-1?
Because a*x*a^(-1) != a*a^(-1)*x
ReplyDeleteIt's wonderful to see 14 year old write about math, especially with some actual background story to go along with it, but I feel like you're missing your audience (if you aim to reach programmers). For example, you state that proving things about abstract algebras is great, but fail to give any concrete examples beyond "it's neat".
ReplyDeleteAnd rather than ground it by starting from a known quality (i.e. an algebra people know), you explicitly dive in with things like "* is not multiplication!", and make it sound very important, without answering the next thought 95% of your readers will have: "then what is it?" i.e. The reader should be able to build up a concrete picture of what you're describing so they can reason about it, not have to take your word for things.
Do keep writing and teaching, but try to be more aware that everyone approaches topics from their own perspective, and you need to cover all bases. Your opening problem, that many people don't think math is cool, is mostly due to the fact that math is taught in the same way everywhere, by the book, and starting from formulas that, taken at face value, are meaningless runes carved in stone, when they actually represent things that we can easily grasp with our mind: lines, curves, quantities, sets, orientations, topologies, etc. A gifted mathematician loves abstraction so that they will quickly build up their own picture and relish the chance to abstract it. Most people however need stuff that's grounded in the familiar.
I should add this link, as it's one of the best reads I've ever had on the topic of math, and teaching it:
ReplyDeletehttp://www.maa.org/devlin/LockhartsLament.pdf
Wolter, just in case, here's how I understand your original question:
ReplyDelete"Why are there two identities when there should only be one?"
There isn't - its a proof through contradiction. That is, you assume the opposite of what you want to prove (in this case the opposite of "there is only one identity") and prove that this cannot be possible because it would be a contradiction.
"And what is an identity anyway?"
An identity is an element of the set in question. So, if your set is a set of numbers, then yes, its a number. If you're working with a set of vectors, then the identity is a vector. If a set of apples existed where some operation on this set were to form a group, then the identity would be an apple. For something to be an identity it simply needs to meet the rule that x op e = x, where x is any element of your set, op is the operation of the group and e is the identity.
"Why is e1 = e2 a contradiction?"
He is proving that a group with two (or more) identities is a contradiction. To prove this he takes any two (different - if he took two that are actually the same, then he is not proving that a group can or cant have more than one identity, since he is only working with one!) identities and shows that it would only be possible if they were the same. But if they're the same then he didn't really pick two identities at all - he only picked one - therefore the setup of two identities is a contradiction. This means that a group with two or more identities cannot exist.
We probably need to include the axiom "e * x = x" for proving identity element uniqueness.
ReplyDeleteDan: That makes a lot more sense. So can you explain why you can multiply both sides of "a∗x∗b=c" by b-1, but you can't multiply "a∗x=c∗b−1" by a-1? All he said is "a*x*a^(-1) != a*a^(-1)*x", which doesn't mean anything to me.
ReplyDeleteWolter, let me show you why your idea of multiplying both sides doesn't quite work (though with the traditional definition of a group, for example from wikipedia, it does):
ReplyDeleteYou are at the step where you have a ∗ x = c ∗ b^−1.
From this, it follows that a^-1 * (a * x) = a^-1 * (c * b^-1). By associativity, this means that (a^-1 * a) * x = a^-1 * c * b^-1.
Now we are almost there. If we knew that a^-1 * a = e then we could substitute that fact in and get the final answer. But we never actually proved that. Our axiom about inverses never stated that a^-1 * a = e when a^-1 and a are written in this opposite order. This is actually a true fact, but you would need more steps to prove it.
By the way, the wikipedia definition includes this fact as an axiom, which is defining slightly more than you need. You need either e * a = a * e = e, or a^-1 * a = a * a^-1 = e. If either of these properties hold for a group, you can derive the other.
@Steven
ReplyDeleteA lot of people have told me similar things, I will really try to include more applications in the next one, but, in such basic group theory, it is very difficult to have any real applications, because they all require atleast some idea of what groups are and how they're used.
BTW, I love the Lockhart's Lament :)
@Wolter and Steven
Stupid commutativity. Screws it up for everyone.
"And, about classes in OOP languages, there's a very close correlation."
ReplyDeleteThis is utter nonsense. Object orientation isn't even one thing - it's two things (the Kay style Smalltalk message passing between interfaces mindset or the C++ compile-time virtual pointer table abstraction to call interfaces.)
You're just saying "oh, and these two things are similar."
They're not even remotely similar. The math you're talking about is about proving properties. Object orientation outside ML/Coq is not provable in any meaningful way, and the purpose of OOP is not to show proof. OOP in both cases are about decomposing complex systems into simpler systems so that they're easier to reason about and maintain.
The stunningly obvious nonsensical nature of this claim throws the rest of the article into doubt.
Did you read the explanation why I thought they were similar?
ReplyDeleteI said that it was absolutely up to the writer of the classes that they formed any sort of algebraic structure, but, the idea is there. You're taking elements (data), and you're defining operations on them, which is the exact point of algebraic systems.
I'm not sure if that's what you understood, and still gave that response, and if that's the case, it would be better if you could explain why "The math you're talking about is about proving properties"
Dhaivat: the thing is, every lesson should start with a light bulb going off that says "Isn't that interesting?". If you look at your post, you chose to start with "a simple definition" that is actually 5 separate definitions full of 'math words' and symbols.
ReplyDeleteIf you want to illustrate the universality of these rules, you should at the very least show how they work in concrete, familiar groups, e.g. integers, matrices, modular arithmetic, ... That way, you can show and convince your reader that there is a universal pattern, rather than telling them.
Also, if you like Lockhart's Lament, go seek out texts and videos by Richard Feynman, arguably one of the greatest teachers of the last century. But he may convince you to become a physicist instead of a mathematician ;).
Yeah, that makes sense. BTW, my next one most likely won't be out until Saturday; I have a lot of stuff going on.
ReplyDeleteI like Richard Feynman as well :) I've read all the "Lectures in Physics" books he has, they're really excellent, he starts out with simple observations and turns them into a complete study.
Im a programmer, I read your article 5 times, still couldn't understand diddly dime squat,.. I started reading up on SET theory (the wiki).. Didnt understand squat there as well, tried to read up on the closure property of SETS,.. nope no luck there.... tried to understand what an axiom is, dont get me started, Tried everything... sniff, I give up.. I wish I can understand it all.. Cant call myself a coder till then..
ReplyDeleteRohit,
ReplyDeleteOkay, can you tell me roughly where you start getting lost?
An axiom (don't look this up on Wikipedia; it'll sound like meaningless junk) means something you assume in order to prove other things. Like, in Geometry, you assume that the shortest distance between two points is a line.
Dhaivat, I start getting lost when you say G=. So A group Is a Set and an operation. I assume that an operation is a something like a union or intersection. So I start to wonder, dont you need two sets to complete an operation ? So whats with the comma and the prompt signs ?.. Sorry im sounding too new. Okay when you say xϵS, what does the "ϵ" mean ? its like a "belongs to".. I Can't figure. And when you say "inverse" of a group. I cant figure what. I remember in school, we learnt "matrices" and how to form an inverse of them. The thing is we never learnt what is matrix is and where it is applied.. We were just thought that, "this is the way to invert a matrix". No now when Im free from previous conditioning, Im begining to question every little small thing, I cant go through the full article when I have doubts at every single line. I only have myself to blame, Im giving your article another shot, this time, Im reading up on SETS, Matrices, algebra again. Thanks man, From the other comments, everyone thinks this is an awesome read. I wish i could be there too
ReplyDeleteOkay, I see where your problem is.
ReplyDeleteFirstly, you only need one set ($S$), because you can have two elements from $S$, like $x$ and $y$, and perform the operation $*$ on them to get $x*y$. Does that make sense so far?
The $x \epsilon S$ means $x$ is a member of the set $S$.
See if you can understand anything from that.
And, I've had that exact same problem with matrices (even though aren't related to this subject in particular), and mostly, school math is a load of BS.
If you still have questions, I'm ready to answer :)
Nice post ,Best Mobile Phone Solutions says I read your post many times but I never understand what you exactly want to say .So can you explain in which step you are facing problem.
ReplyDeleteYour last proof could be much shorter if you went on and said that $a^{-1} \ast a \ast x = a^{-1} \ast c \ast b^{-1}$. The reason this works is trivial: you are effectively doing $a^{-1} \ast (a \ast x) = a^{-1} \ast (a \ast x)$, then performing a substitution.
ReplyDeletePerhaps this was what another poster attempted to point out.
Yeah, that's true.
ReplyDeleteThanks a lot for the input!
Hi Dhaivat,
ReplyDeletethanks for the article.
I have one suggestion, though I don't know if it makes sense.
Since you are targeting programmers maybe you could use some programming metaphores like explaining an abstract operation with operator overloading or xϵS is like S is a class x,y are objects.
This may be not totally true but could help getting an idea.
Cheers,
Ramon
Hi!
ReplyDeleteNice Post. I've never looked at algebra like this. Thanks.
Thanks :)
ReplyDeleteFollow if you'd like!
I just want to say your post is tremendous. The clarity in your post is simply spectacular and i can assume you are an expert on this field.
ReplyDeletetravel to Egypt
Thanks.
DeleteI'm actually a student.
This comment has been removed by a blog administrator.
ReplyDeleteWould you like to leave? Thanks.
DeleteAlgebra is a major component of math that is used to unify mathematic concepts. Algebra is built on experiences with numbers and operations, along with geometry and data analysis. Some students think that algebra is like learning another language. This is true to a small extent, algebra is a simple language used to solve problems that can not be solved by numbers alone. It models real-world situations by using symbols, such as the letters x, y, and z to represent numbers.
ReplyDeletesimplify the expression