Interesting note on the history of symbolic logic

Very short blurb...While reading through a chapter of Stephen Kleene's "Mathematical Logic", I came across an interesting fact. The symbol in mathematical logical for "inclusive or" (nonexclusive disjunction) is traditionally expressed as "\vee" - that much I knew. What I didn't know is that this symbol is descendant from the Latin word for "inclusive or": vel. Pretty cool stuff.

Implications of Godel's Theorems on a Physical "Theory of Everything"

Disclaimer: I'm no expert on physics. If I've mischaracterized anything in this article, please let me know so I can correct it.

I've been on something of a logic binge lately. For the past several days, I've had Godel's Incompleteness Theorems, Paraconsistent Logic, and more floating through my head. I've always been interested as to what the Incompleteness Theorems mean for the notion of a physical Theory of Everything. After writing my recent post on the subject, I feel that I have a much more solid understanding of the Theorems now than I ever have before, thus I feel somewhat confident in revisiting this idea with a fresh perspective. I'm a bit tired, so I'll keep things pretty simple.

Godel's Theorems consider the inherent limitations of axiomatic systems, and the goal of a Theory of Everything certainly fits under this category. Theoretical physicists have for many years searched for a minimal set of all-guiding universal laws which underlie all physical phenomena. So far, this quest has met little success. According to the Incompleteness Theorems, there are two obvious possibilities: Either the axioms of the universe are incomplete or they are inconsistent - presumably, they are not both.

Philosophical Digression on Paraconsistent Logic

While reading about Godel's Incompleteness Theorems before writing my post on it, I encountered a strange idea: The notion of "paraconsistent logic". As I explain in my Godel post, the Principle of Explosion states that "from a contradiction, all else follows"; if a formal theory is capable of expressing a contradiction, then both a statement and its negation can be used for proofs. This often leads to all statements being true in a theory. Such a theory is termed inconsistent.

But certainly not all contradictions lead to the principle of explosion! If I simultaneously believe, for instance, that an apple is both green and red, this will not lead me to the contradiction that a number can be both odd and even. Therefore, the Principle of Explosion applies only within the scope of what objects the contradiction speaks of (directly or indirectly). The study of paraconsistent logic considers the implications of having rigorous logic theories in which some contradictions are possible.

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.