Self-Description in Mathematics

The foundations of mathematics is a strange, strange place - and not only because of philosophical disagreements on constructivism, incompleteness of logical systems, and set-theoretic paradoxes (although all of that is indeed weird). No, one of the strangest things about mathematics is its uncanny ability to describe itself.

Ideally, we like to think of the flow of mathematics almost as a directed acyclic graph: The propositional calculus extends to predicate logic; set theory builds on predicate logic; order theory, algebra, and topology build on set theory; analysis builds on all of these. Where things get weird, however, is when things move backwards through this hierarchy. This can perhaps be seen no more clearly than in order theory, and in particular, lattice theory.

The following relationship exists:

• A lattice can be described as:
• A partial order in which each pair of elements has a unique infimum and supremum.
• An algebraic structure which consists of a set together with two operations, "\wedge" and "\vee" such that the operations obey laws of associativity, commutativity, idempotence, and absorption.
• Algebraic structures are defined in terms of sets, the axioms of which are defined in terms of predicate and propositional logic.
• Propositional logic, with its AND and OR operations, form a distributive lattice (specifically a Boolean algebra).

So in other words, algebra and lattices are defined with the help of propositional calculus, lattices can be defined in terms of algebra, and propositional calculus can be defined in terms of algebraic lattices. It is amazing to me how mathematics is continually able to so gracefully "turn around" and, in a sense, define itself. Such self-reference has in some cases resulted in major philosophical difficulties, but in others, such as this one, all appears to work fine. How is it though that mathematics is able to adequately define structures more fundamental than those doing the defining? I personally believe that this exact phenomenon is symptom of mathematics being not a fundamental deductive science which guides the universe, but a careful, consistent, and beautiful language whose precision grants it power far-reaching enough even to predict events which have not yet come to pass (solar eclipses, weather patterns, etc). Interesting stuff, eh?

Classification of Algebraic Structures (Reference)

Below is an incomplete list of common algebraic structures together with a short definition. I've come to realize that I would've loved to have something like this when I was learning it all, so I figured I'd write one for others. I'll update this as I continue to learn. This list is by no means exhaustive, and I'm sure that others have probably done similar things elsewhere with greater success. This is simply partly for my own records and partly for those interested who might not otherwise have the motivation to find such a list on their own.

An Interesting View of Differentiation

I've never studied any functional analysis (my background in traditional analysis is not yet nearly strong enough), but I do find the topic quite interesting. It's partly due to its place at the convergence of Linear Algebra and Analysis. It's partly because I love the notion of function spaces. It's partly because it plays a central role in some areas of physics which I find quite interesting. And it's partly (probably mostly) because it just seems so exotic that I can't help but be attracted to it.

Despite having never studied function spaces properly, I occasionally run into them in my readings. Today in particular, I was reading about inner product spaces. I eventually came across the topic of Hilbert Spaces, which are inner product spaces which are also complete metric spaces with respect to the metric induced by the norm implicit in the inner product. One way or another, this got me thinking about derivatives from a viewpoint very different from that usually presented in an undergraduate calculus course.

Logic and Godel's Incompleteness Theorems

I've always been fascinated by the work of Kurt Gödel. It has always seemed to me that few human beings have ever successfully probed so deeply into the nature of the Universe. Gödel was among the foremost logicians of the early twentieth century movement of analytic philosophy and is most famous for his wide-reaching results, the Completeness Theorem and the Incompleteness Theorems. In particular, I will focus this post on the Incompleteness Theorems and attempt to explain their profound results, without diminishing their full power (and scope of applicability), in a manner accessible to those less familiar with formal logical reasoning. First, a little bit of history.


Although in some ways, the roots of the Incompleteness Theorems can be traced back to the beginnings of mathematics, the relevant history begins in the nineteenth century with logicians such as Augustus De Morgan, George Boole, and Charles Sanders Pierce who gave birth to the notion of rigorous, formal logic in the modern sense. Herman Grassmann, father of Linear Algebra, showed that many properties of arithmetic can be reduced to the operations of succession and induction, which spurred the work of such illustrious scientists as Giuseppe Peano and Gottlob Frege. Somewhat separately, Georg Cantor developed the theory of sets while working in Topology. All of this increase in rigor and precision, all of this focus on reducing mathematics to bare logic, led David Hilbert, one of the most prominent mathematicians of the early twentieth century, to in 1920 begin a program of research (now remembered as simply "Hilbert's Program"), the aim of which was to uncover a minimal set of complete, consistent logical axioms, from which all of mathematics could be derived - no small task indeed. The mathematicians of the philosophical school of Formalism championed this noble pursuit, and for the next several years, mathematicians around the world chased this holiest of holy grails of science. Gödel's Incompleteness Theorems, proven by Kurt Gödel, completely dismantled Hilbert's Program by showing that its intended goals were impossible to achieve.

Interesting Note on the Development of Set Theory

I was reading Walter Rudin's "Principles of Mathematical Analysis" and came across the notion of a perfect set.

"[A subset] E is perfect if E is closed and if every point of E is a limit point of E."

Of course, this also implies that, since a set in a topological space is closed if and only if it contains all of its limit points, E is exactly equivalent to the set of its limit points. I found this rather interesting, so I searched Wikipedia for an article on "perfect sets" and was redirected to the article on "Derived sets".

The article informed me that the derived set of a subset of a topological space is the set of its limit points (thus a perfect set is one equal to its own derived set). While I found this interesting, what I really found fascinating was a brief one-line note:

"The concept was first introduced by Georg Cantor in 1872 and he developed set theory in large part to study the derived sets on the real line."

I had always known that Cantor studied topology prior to developing set theory, but I had never been able to find the crucial link that led Cantor to develop the general theory of sets. Well, there you go. I love science history.

Beyond the Cardinality of the Reals

I feel that when studying mathematics (besides set theory), one typically encounters three types of sets.

1. Finite sets
2. Countably infinite sets
3. Uncountable sets bijective to the reals

But very rarely does one see any mention to cardinalities greater than that of the continuum. I recently made a post on the Mathematics StackExchange website asking whether anybody could think of a useful mathematical object whose cardinality is greater than that of the continuum and what properties it might have. Although the members of that website shared some great insight, no really good examples were provided.

I thought of one myself. If we take the uncountable Cartesian product of the set of real numbers:

S = \prod\limits_{i \in \mathbb{R}}(\mathbb{R})
Then we can consider S to be the set of all transfinite sequences from R into itself - in other words, the space of all functions on the real numbers. Since the cardinality of S is the cardinality of the continuum raised to itself, we have the following:
|S| = |\mathbb{R^{R}}| = B_{2}
(where B is a Beth number)
Thus the space of all functions on the real numbers is more numerous than the continuum, and we have our desired object. Though I have not studied functional analysis (yet), I understand that such function spaces are of great importance to the subject. Pretty cool stuff.

"Transfinite" vs "Infinite"

Ask a third grader how large the set of alllll the numbers are and he'll cry out "infinity!"
Ask a set theorist and he'll very likely say "transfinite". Transfinite? Really asshole? Come on...

So why are the cardinalities of infinite sets referred to as "transfinite cardinals"? It turns out that the reason is somewhat historical. Georg Cantor, the man responsible for placing set theory at the very foundation of all modern mathematics (and, therefore, science) was a deeply religious man who adhered to the idea that the one true god was the only "absolutely infinite" construct which could exist in the Universe; He is beyond any concept, whether it be a set or a world or a galaxy. This led Cantor to coin the term "transfinite" to describe the notion of a quantity which is not finite, but which is not the absolute infinity which he believed could only describe God - it is somewhere in between. It is the naturals; it is the reals; it is every subsequent power set of these sets, etc.

At first glance, the matter seems trivial at best and childish at worst, especially to those deeply skeptical of religion. But one must be careful to look at the perspective of the time: Cantor's Theorem, which directly implies that there are an infinite amount of successively larger infinities, was exotic. More than exotic. Ludicrous. Insane. Heretical to the omnipresence, omnipotence, and omniscience of God. A challenge - a provably correct challenge! - to the very fabric of how human beings understand the notion of abstract quantity, and, by extension, mathematics, science, philosophy, ontology, and the Universe as a whole. I find it reasonable that Cantor would draw a distinction between the hierarchy of infinities and the "absolute infinity" which he believed to be only attainable by God.

Even if the notion of God is removed, however, the question remains relevant. What is the "largest" object which can be constructed while remaining logically consistent with the rest of mathematics? Does such a construction exist? If so, should "less numerous" infinities, such as the cardinality of the natural numbers, still be titled "infinite"? Should an infinite set be one which always contains more elements, or should it be defined as a set which contains all elements? Can such a set exist? Can an infinite set exist at all in the physical world beyond the abstract universe of mathematical thought?

Answers are sought to many of these questions within the domain of large cardinal theory, and although they admittedly rarely come into practical consideration in any remotely applicable area of mathematics, it is nonetheless instructive to consider them, if only to feel a bit humble and to realize just how fucked up and confused the foundations of mathematics and science remain.

Aleph Numbers vs. Beth Numbers

Note: Since the Google Chart API does not seem to support the Hebrew "Beth" character, I will instead use the letter "B" where that character would ordinarily appear.

The difference between Aleph Numbers and Beth Numbers is not one that I ever understood. From what I could tell,
\aleph_{i}=B_{i}
and that was that. Both represent cardinalities of infinite sets. The first such number of each system is the countable infinity, the size of the natural numbers. So what's the difference?

Well, that depends whether you subscribe to belief in the Continuum Hypothesis, and I am sincere in calling it a belief. The Continuum Hypothesis is the somewhat unresolved statement that there can be no set whose cardinality is strictly greater than the cardinality of the natural numbers and strictly less than the cardinality of the real numbers. The work of Kurt Gödel and Paul Cohen in the 1900s proved that the Continuum Hypothesis cannot be decided - that is, cannot be proven or disproven - within the usual formulation of axiomatic set theory used in mathematics, Zermelo-Fraenkel Set Theory (regardless of whether one includes the Axiom of Choice).

Transfinite Sequences

Sequence - Given a set X, a sequence is an ordered list of elements of X {x1, x2, x3, ...}. If the number of elements of the sequence is finite, the sequence is referred to as a "finite" sequence. A sequence can also be infinite.

More formally, a sequence is, strictly speaking, a function from some subset of the natural numbers N into some set X:

f:M \rightarrow X,\ M \subseteq \mathbb{N}

But wait a moment! What if we want for our function to range over a number of values which is greater than that in N? What if we want an uncountable sequence of numbers? What would that even mean?!

It turns out that mathematics does in fact give the machinery needed to handle this, although one must dig into set theory to find it. The notion of Transfinite Sequences allows for a sequence to be constructed whose length is that of any ordinal on any well-ordered set. If we accept the Axiom of Choice, then the Well Ordering Theorem holds (or visa versa; the axiom and the theorem are in fact logically equivalent) and we can produce a so-called "transfinite sequence" on any set, including the reals. The notions of Transfinite Induction and Transfinite Recursion also help to properly extend their respective notions which are classically limited to sets of countable order. Pretty cool stuff if you think about exactly what a sequence really is. Also sheds some light on just how extreme the consequences of the Axiom of Choice really are. On a side-note, I have only just begun reading on the topic of transfinite sequences today, so if something in this post is inaccurate, please feel free to correct me.