Discrete Mathematics

Algebra: Algebra is about operations on sets. You have met many operations; for example:

• addition and multiplication of numbers;
• modular arithmetic;
• addition and multiplication of polynomials;
• addition and multiplication of matrices;
• union and intersection of sets;
• composition of permutations.

Many of these operations satisfy similar familiar laws. In all these cases, the “associative law” holds, while most (but not all!) also satisfy the “commutative law”.

The name “algebra” comes from the title of the book Hisab al-jabr w’al-muqabala by Abu Ja’far Muhammad ibn Musa Al-Khwarizmi, a Persian mathematician who lived in Baghdad early in the Islamic era (and whose name has given us the word ‘algorithm’ for a procedure to carry out some operation). Al-Khwarizmi was interested in solving various algebraic equations (especially quadratics), and his method involves applying a transformation to the equation to put it into a standard form for which the solution method is known.

We will be concerned, not so much with solving particular equations, but general questions about the kinds of systems in which Al-Khwarizmi’s methods might apply. Some questions we might ask include:

(a) We form C by adjoining to R an element i satisfying i2 = −1, and then assert that the “usual laws” apply in C. How can we be sure that this is possible? What happens if we try to add more such elements?
(b) What is modular arithmetic? What exactly are the objects, and how are the operations on them defined? Does it satisfy the “usual laws”?
(c) What are polynomials? Do they satisfy the “usual laws”? What about matrices?
(d) Do union and intersection of sets behave like addition and multiplication of numbers? What about composition of permutations?
(e) What are the “usual laws”? What consequences do they have?

In this section we will define and study two kinds of algebraic object: rings, with operations of addition and multiplication; groups, with just one operation (like multiplication or composition). Groups are in some ways simpler, having just a single operation, but rings are more familiar since the integers make a good prototype to think about.