Partitions: The Most Powerful Tool In Mathematics

March 8, 2013

If you have a big object and cannot understand it, what do you do? You break the big object into little objects, try to make sense of them and then build up back to the big object again.

These little objects are partitions of the big object.

Let us see how this tool has been used in some areas of mathematics:

Integration (Analysis)

The first and original integral, the Riemann integral uses partitions of a set and then creates specific sums (Riemann Sum) of these partitions which satisfy certain criterion for integrability.

The result? The integral and in general integration and of course The Fundamental Theorem Of Calculus.

Group Theory (Algebra)

Suppose you have a group. Represent this group as a big box. The things inside this big box clearly make it what it is: the big box.

Partition these things inside into sets and if they have some structure (subgroups), collect all of them and consider the divisibility of the cardinality of the partitions.

What is inside one box may not be what is inside another box (in group talk: a left coset is not necessarily equal to the right coset associated to the group)

The result? Lagrange’s theorem (there are other results but the sheer beauty of that one should be enough)

Graph Theory (Algebra)

Suppose you have a graph. Partition the graph into something smaller: a collection of subgraphs. If this collection is a disjoint union of n-partite graphs, we can understand the graph’s structure.

A specific structure will allow us to understand if the graph is planar and to resolve key, real-life problems such as the utilities problem.

The result: Euler’s characteristic, Four-Colour Theorem, Perron-Frobenius Theorem.

Stochastic Processes (Probability)

Suppose you are doing some event B contained in a sample space W. But to do B you must “be” in some place, say, A. Maybe you are in A_0, A_1, A_2, … and so on. The point is, you must be there. You partition the chance of event B occurring as sum of the chance of B occurring given that you are in A multiplied independently by the chance of you being in A.

This is the Law Of Total Probability.

The result: Chapman-Kolmogorov equation.

Actually this theorem can be represented into a matrix form which then allows us to produce big theorems for Markov chains and (in general) Markov processes.

The result: Markov chains, Ergodic theorem

Even more, the whole of probability theory arises from this.

Introductory stochastic processes classes look at how some initial understanding of probability (and other basic analysis modules) allows us to understand the world: reliability theory (how likely is it that something will break down?), queuing theory (what is that chance of you waiting for a specific time period in a given queue at say, the supermarket, before you go to the till?) and so on.

Graduate classes then use the idea of partitions and breaking things down so much that it links nicely with the “rigorous” definition of probability: measure theory.

These are just some applications, the explanations are not detailed or interesting enough to explain why using partitions is so crucial in all various fields of mathematics.

The point: if you do not understand something, break it down into what you can (or will) understand. Then collect these little pieces together and see what you get.


Lecture 1: Sets, Real Numbers, Fields, Ordered Fields

October 30, 2012

The real number system is a set \{a,b,c, ...\} on which the operations of addition and multiplication are defined so that every pair of real numbers (say a and b) has a unique sum and product, both real numbers, with the following properties:

Given any (and all) a,b,c \in \mathbb{R}, we have

(A) a+b=b+a and a*b=b*a (Commutative laws)

(B) (a+b)+c=a+(b+c) and (a*b)*c=a*(b*c) (Associative laws)

(C) a*(b+c)=a*b+a*c (Distribute law)

(D) There exist distinct real numbers 0 and 1 such that a+0=a and a*1=a, for all a.

(E) For each a there is a real number -a such that a+(-a)=0 and if a \neq 0, there is a real number \frac{1}{a} such that a*\frac{1}{a}=1

A set on which two operations are defined so as to have properties (A) – (E) is a field.

Motivation: Think about these properties for a second before moving on. (A) establishes what the operations do, (B) then asks what happens when we include more elements, a “double operation” if you like. (C) then mixes the two operands into one. (D) and (E) are closely related. Suppose we want to add an element to our given real number that… gives us our real number? So we are adding nothing, or 0. Suppose we have the same idea for our other operand, multiplication, we have the real number 1 to do this for us.

Then we ask, can we find real numbers that give us what we just discovered, namely 0 and 1 from addition and multiplication? For that we have -a and \frac{1}{a} with a \neq 0 for the second condition.

Exercise: Can you think of another example of a field?
Exercise: Do the set of integers \mathbb{Z} form a field? Verify through (A) – (E).

The real number system is ordered by the relation <;, which has the following properties:

(F) For each pair of real numbers a and b, exactly one of the following is true: a <; b, a=b, b<;a.

(G) If a<;b and b<;c then a<;c. (Transitive)

(H) If a<;b, then a+c<;b+c for any c and if b<;c then a*c<;b*c.

A field with an order relation satisfying (F) – (H) is an ordered field. The real numbers (and rationals) form an ordered field.

Suppose we get bored of the real numbers and define a new field satisfying everything \mathbb{R} does but is defined as such. For any a,b \in \mathbb{R} we define a new number z as z = a+b*\imath, where \imath^2 = -1. We call this set \mathbb{C}, the set of complex numbers.

Exercise: Verify that \mathbb{C} is a field.
Exercise: Is \mathbb{C} an ordered field? (Use (F) – (H) to prove order or give a counterexample)
(Hard) Exercise: Why have we defined \imath^2 = -1 and not \imath=\sqrt{-1}?

Questions to think about:

Are all fields ordered fields?
Are finite fields ordered?
What do these two above questions (if and when answered) say about ordered fields? (Hint: Infinite number of…)