Posts Tagged ‘set theory’

Group Theory

December 14, 2008

I already wrote about Set theory and I eventually want to write about symmetry, so this seems like the perfect opportunity to discuss Group theory.  Let’s start where we left off with Set theory.  We had a very abstract concept of a Set: a collection of “things”.  Then we added some basic structure to that collection (the operation of set concatenation), and before we knew it we were counting and adding.

Well, to formalize it a bit, when you take a set and add a binary operation, and an identity element, then what you get is called a monoid.  Monoids are extremely abstract yet very powerful.  (In a way they even form the underpinning of all of computer science, where the set is a collection of functions, and the product is simply chaining these functions together, called function composition, and the identity is simply a “noop“.)  I’ll talk more about this in a future post because it is so cool how these ideas tie together.

A Group is just like a Monoid, except every element in the set must also contain its inverse.  When an element operates on its inverse, it results in the identity!  Some basic examples, are the integers\mathbb{Z}, where every element also has its addtive inverse, called its “negative”.  Another example are the rationals, \mathbb{Q}, where every element has its multiplicative inverse, called its “reciprocal”.  In the former example, the operation is addition and addtive identity is 0, while in the latter the product is multiplication and the multiplicative identity is 1.  Both of these groups also commute (i.e. the order of operation does not matter), and we call these groups “abelian“.  They are named after the mathematician Niels Henrik Abel, but strangely the word is not capitalized.

These groups may seem pretty abstract at first, but here are a few more tangible examples.  First, is that to physicists, a set with elements and their inverses will immediately remind one of a set of particles and their antiparticles.  But we can actually get much more tangible than that if we pull the same trick we pulled above with our monoid:  instead of thinking about objects, get Categorical, and think about processes.  It’s easy to imagine a set of transformations and their inverses: raise and lower, shrink and grow, cut and paste.  All of these examples have the identity of  “do nothing”.

Groups are strongly related to symmetry because an object which is equivalent to the original after transformations is at the heart of symmetry!  In future posts we will talk about the groups of rotations and reflections to explore these concepts.

Abstract Thinking

November 16, 2008

As a software engineer, abstracting problems is an important step in creating modular code.  Good abstract concepts are not only useful for a given problem, but they can also be applied in a variety of different situations.  It is especially exciting when 2 seemingly completely different problems can be described by the same abstraction, as this can lead to new insights and perspectives.  In fact, this paragraph itself can be abstracted by applying it to various fields besides software engineering!  I’m sure this analysis of the analysis would make Douglas Hofstadter proud ;) .

The most abstract ideas are those in mathematics.  Alone, the rules of math are not terribly useful (like a software interface without an underlying implementation), but they can be applied in extremely powerful ways to all other fields.  Let’s take the simple, yet incredible, example of numbers.

What is a number?  One explanation is to think of a practical example: pretend you have a basket of tomatoes.  You may want to count how many tomatoes you have and assign some label as the result.  These labels are numbers (or more specifically integers).  Why would you perform such a measurement?  Well in this case it seems very useful to take an inventory for storing, selling, cooking, or whatever you would like to do with your tomatoes. Now let’s say someone else gives you some more tomatoes or takes some away from you.  Numbers appear useful here too.  So we can define “operations” of addition and subtraction to accomplish this.

This concept of numbers and operations is abstract enough that you can clearly apply it to more than just baskets of tomatoes! In fact, you can apply it to “sets” composed of any “element” you can possibly imagine!  That is what a good abstraction is all about.

Let’s get formal about this in mathematical terms using Set Theory.  Given a Set S, there is a function f:S\rightarrow \mathbb{Z} which takes a set and counts how many elements are in it. This measure is called the cardinality of the set.

This function is often expressed by inserting the set in between vertical bars . Here are some examples of sets and their cardinality:

  • The empty set: |{}| = 0
  • A set of one tomato: |({tomato}| = 1
  • A set of letters: |({A, B, C, X, Y, Z}| = 6
  • A set of sets: |{{telephone}, {}, {1, 3}}| = 3

We can also talk about adding sets with another function: g:S\times S\rightarrow S.  This function takes two sets and outputs a third.  You can come up with a bunch of simple functions which do this, but one nice example is a function which concatenates the elements from both input sets and puts them into a single output set.  For example:$latex g({1, 3, 5}, {A}) = {1, 3, 5, A}.  What’s nice about this is that we can use this function to perform addition! since |{1, 3, 5}| = 3, |{A}| = 1, and |{1, 3, 5, A}| = 4.  And what is the additive identity?  It’s the empty set of course!  You can obviously cook up a bunch of other functions which relate to other mathematical operations as well.

This is all just scratching the surface, so we’ll have more cool stuff to go over in future posts.