Logicomix Available for Free Online Reading via Scribd

February 24, 2013

The graphic novel, “Logicomix: An Epic Search for Truth” is available for free online reading (pay for download) via Scribd.

It’s a fun story about the early search for mathematical foundations involving figures like Bertrand Russell, George Cantor, Ludwig Wittgenstein, Gottlob Frege, Kurt Gödel and Alan Turing.

http://www.scribd.com/doc/98921232/Bertrand-Russell-Logicomix

And for those interested, here’s a review of Logicomix by noted philosopher of mathematics, Paolo Mancosu:

https://philosophy.berkeley.edu/file/509/logicomix-review-january-2010.pdf

Posted in Peano Arithmetic, Universals | Leave a Comment »

The Nonsense Math Effect

December 28, 2012

An article suggesting that non-math academics are impressed by equations even if the equations are nonsense:

http://journal.sjdm.org/12/12810/jdm12810.pdf

Tags: , , ,
Posted in Perspectives | Leave a Comment »

Well Ordering Infinite Sets, the Axiom of Choice and the Continuum Hypothesis

December 17, 2012

We’re trying to understand the relationship between \aleph_{0}, and other infinite cardinal numbers. We’ve reviewed two ways (here and here) to generate infinite cardinals greater than \aleph_{0}. The first way is by considering the set of all subsets of positive integers, the power set \mathcal{P}(\mathbb{N}) of \mathbb{N} with cardinality 2^{\aleph_{0}}. The second way is by considering the set of countably infinite ordinals, \omega_{1} and its cardinality, \aleph_{1}.

We begin by introducing the axiom of choice. The axiom of choice (AC) is an axiom of set theory that says, informally, that for any collection of bins, each containing at least one element, it’s possible to make a selection of at least one element from each bin. It was first set forth by Zermelo in 1904 and was controversial for a time (early 20th century) due to its being highly non-constructive.

For example, AC is equivalent to the well ordering theorem (WOT) stating that every set can be well ordered, and it can be proven using AC/WOT that there are non-Lebesgue measurable sets of real numbers. Nevertheless, this result is consistent with the result that no such set of reals is definable! And use of the AC to achieve unintuitive mathematical results, like paradoxical decompositions in geometry in the spirit of the Banach-Tarski paradox, have also fueled skepticism and mistrust of the axiom.  But contemporary mathematicians make free use of the axiom and hardly mind that it was ever controversial.

Formally, the axiom of choice says the following:

For each family (X_{i})_{i \in I} of non-empty sets X_{i}, the product set \prod_{i \in I}{(X_{i})} is non-empty.

The elements of \prod_{i \in I}{(X_{i})} are actually “choice functions”
(x_{i})_{i \in I}, I \rightarrow \bigcup_{i \in I}{(x_{i})}, satisfying x(i) = x_{i} for each i \in I.

AC is important when thinking about infinite cardinals in part because of its equivalence to the WOT. Because WOT says that every set can be well ordered, it follows that each cardinal (any set really) can be associated with an ordinal number and you can count them via the ordinals. For instance, \aleph_{0} can be represented by \omega, \aleph_{1} by \omega_{1} and in general AC/WOT enables us to give the von Neumann definition of cardinal numbers where the cardinality of a set X is the least ordinal \alpha such that there is a bijection between X and \alpha.

AC and WOT do a lot of other work as well in terms of ordering infinities. We say that an aleph is the cardinal number of a well ordered infinite set. Because every set is well order able, all infinite cardinals are alephs. It was shown by Friedrich Hartogs in 1915 that trichotomy, which is a property of an order relation on a set A such that for any x, y \in A, x < y, x = y, or x > y, is equivalent to AC.

So with AC we can list, in (a total) order, the infinite cardinals and compare them. Thus we can set up the following infinite list of alephs, \aleph_{0}, \aleph_{1}, \aleph_{2}, \cdots, \aleph_{\alpha}, \cdots. We know that \aleph_{1} is greater than and distinct from \aleph_{0}. The cardinal \aleph_{1} is the cardinality of the ordinal \omega_{1} which is larger than all countable ordinals, so \aleph_{1} is distinguished from \aleph_{0}. What about 2^{\aleph_{0}}?

It’s unclear where 2^{\aleph_{0}} fits in in the list \aleph_{0}, \aleph_{1}, \aleph_{2}, \cdots, \aleph_{\alpha}, \cdots. The infinite cardinal 2^{\aleph_{0}} is the cardinality of the set of subsets of \mathbb{N}, but it’s also the cardinality of the set, \mathbb{R}, of real numbers or the set of points on a line, known as the continuum. (This equality is provable using the Cantor-Schröder-Bernstein theorem and follows from the proof of the uncountability of \mathbb{R}.)

George Cantor, the inventor of set theory, conjectured in 1878 that there is no set whose cardinality is strictly between the cardinality of the integers (\aleph_{0}) and the cardinality of the continuum (2^{\aleph_{0}}). Since we’re assuming AC, that means that 2^{\aleph_{0}} = \aleph_{1}.

This conjecture is famously known as the Continuum Hypothesis (CH) and was the first of 23 problems in David Hilbert’s famous 1900 list of open problems in mathematics. The problem of whether or not CH is true remains open to this day although Kurt Gödel (in 1940) and Paul Cohen (in 1963) showed that CH is independent of the axioms of Zermelo-Fraenkel set theory, if these axioms are consistent.

There is much of philosophical interest surrounding the mathematics of the continuum hypothesis and I hope to be able to turn my attention to those topics in the future.

Posted in Axiom of Choice, Axioms of Set Theory, Continuum Hypothesis, Set Theoretic Infinity, Transfinite Cardinals | Leave a Comment »

Priest, Beall and Armour-Garb’s “The Law of Non-Contradiction” Available Online via Scribd

November 5, 2012

Priest, Beall and Armour-Garb’s “The Law of Non-Contradiction”, (link below) is a great collection of essays on the philosophy and logic of dialetheism, the belief that that there are sentences A, such that both A and its negation, ¬A are true. Non-classical, paraconsistent logics may be necessary for formalizing and understanding physical and social systems.

http://www.scribd.com/doc/62132941/3/Letters-to-Beall-and-Priest

Posted in Non-Classical Logic | 2 Comments »

Paul Cohen Reflects on the Nature of Mathematics

November 5, 2012

Reflections on the nature of mathematics from Paul Cohen’s “Comments on the foundations of set theory” in Scott and Jech, Axiomatic Set Theory, Vol.1, p. 15.

Posted in Perspectives | Leave a Comment »

A Mathematician’s Survival Guide, by Pete Casazza

April 29, 2012

“All My Imaginary Friends Like Me” -Nikolas Bourbaki

From §2 of “A Mathematician’s Survival Guide“, a good read for all, not just mathematical people.

Posted in Perspectives | Leave a Comment »

The Cardinality of Uncountable Sets II

March 6, 2012

We can get at another infinite cardinal that is greater than \aleph_{0} by thinking about the ordinal numbers. Think of the natural, or counting numbers \textup{N} = (1, 2, 3, \cdots). These numbers double as the finite cardinal numbers. Cardinal numbers, we have seen, express the size of a set or the number of objects in a collection (e.g., as in “24 is the number of hours in a day”). But they also double as the finite ordinal numbers, which indicate a place in an ordering or in a sequence (e.g., as in ” the letter ‘x’ is the 24th letter in the English alphabet”). In the case of finite collections, the finite ordinal numbers are the same as the finite cardinals.

But when we start thinking of infinite collections the similarities diverge. In order to see the differences in the infinite case we should get clear on what an ordinal number is. Say that a set x is transitive if, and only if, every element of x is a subset of x, where x is not a urelement (something that is not a set). Now say that a set x is well-ordered by the membership relation, \in, if \{\langle y, z\rangle \in x \times x : y \in z\}. What this does is simply order the elements of x in terms of membership. We can do this type of thing with transitive sets. Combining these two definitions we get the definition of an ordinal number: a set x is an ordinal if, and only if, x is transitive and well-ordered by \in.

Now, let \omega = \{1, 2, 3, \cdots\} (i.e., the set \textup{N} of natural numbers). \omega is an ordinal because when we think of the natural numbers as constructed by letting 0 = 0 and letting 1 = \{0\}, the singleton set of 0, 2 = \{0, \{0\}\}, and so on and so forth it satisfies the definition above of an ordinal number as a transitive set well-ordered by \in. So we can set up the sequence 1, 2, 3, \cdots, \omega with all ordinals less than \omega either equal to 0 or one of its successors.

Suppose that you take the natural numbers and re-arrange (re-order) them so that 0 is the last element. This is weird because the regular ordering of the natural numbers has no last element. But still, you can think of there being a countable infinity of natural numbers 1, 2, 3, \cdots prior to the appearance of 0. So we have the standard order of \textup{N} and we have added another element, 0. If we let \omega be the standard order of \textup{N}, then we have just described \omega + 1. We can do the same thing by now setting 1 as the last element of \omega + 1 and thus get \omega + 2. Note that addition (and multiplication below) does not commute; e.g., 1 + \omega = \omega and not \omega + 1. This process can be generalized (e.g., n, n +1, \cdots, 0, 1, \cdots, n -1) to get \omega + n.

Again, doing something weird: take the natural numbers and put all the even numbers first, followed by the odd numbers. It’ll look like this, 0, 2, 4, \cdots, 2n, \cdots, 1, 2, 3, \cdots 2n+1, \cdots. Here we have taken \omega (the evens) and appended it to \omega (the odds) so we have \omega + \omega. In each case, \omega, \omega + n and \omega + \omega, we are dealing with the same cardinality, the cardinality of \textup{N}.

We’ve created a variety of different ordinal numbers here, and, as they represent different orderings of the natural numbers, they are all countable. There are many more countably infinite ordinals. For example, the ordinal \omega \cdot 2 = \{ 0, 1, 2, \cdots, \omega, \cdots, \omega+1, \omega+2, \cdots \}, \omega \cdot 2+1, \cdots \omega^{2}, \omega^{3}, \omega^{4}, \cdots \omega^{\omega}, \cdots \omega^{\omega^{\omega}} \cdots.

Taking the countable ordinals and laying them out (kind of like in the previous sentence but starting with 1, 2, 3, \cdots, \omega, \cdots, \omega + 1, \omega + 2, \cdots) we end up with a a set that is itself an ordinal. In order to see this let \alpha be the set of countable ordinals. If \beta \in \alpha then \beta \subset \alpha since the members of \beta are countable ordinals. Therefore \alpha is an ordinal.

It is in fact the first uncountable ordinal because if it were countable, then \alpha would be a member of itself and there would be an infinitely descending sequence of ordinals. But because the ordinals are transitive sets (see definition above), this cannot be the case. So the set of countable ordinals is uncountable. (It is also the smallest such set because the ordinals are well ordered by \in, so every ordinal in \alpha is a member of \alpha and countable.) This uncountable set goes by the name \omega_{1}.

Here we see how the similarities between the ordinal numbers and the cardinal numbers in the finite case diverge in the infinite case. Whereas there is only one countably infinite cardinal, \aleph_{0}, there are uncountably many countably infinite ordinals, namely all countably infinite ordinals less than \omega_{1}.

It is natural to wonder about the cardinality of the set \omega_{1} of countable ordinals. Its cardinality is transfinite and is denoted by the uncountable cardinal number, \aleph_{1}.

So far we’ve talked about \aleph_{0}, 2^{\aleph_{0}} (see here, and here, respectively), and have generated \aleph_{1} by considering the uncountable set of countably infinite ordinals, \omega_{1}. In the next update we’ll talk more about the relationship between these cardinal numbers as well as the celebrated axiom of choice.

Posted in Cardinal Numbers, Ordinal Numbers, Transfinite Cardinals | 1 Comment »

Cantor’s Attic

January 15, 2012

Cantor’s Attic: a resource on mathematical infinity. Philosophically rich mathematics is the best mathematics.

Posted in Cardinal Numbers, Inaccessible Cardinals, Set Theoretic Infinity, Transfinite Cardinals | Leave a Comment »

FOM Posting on A. Kiselev’s claim that “There are no weakly inaccessible cardinals” in ZF

August 17, 2011

Alex Kiselev claims to have shown “There are no weakly inaccessible cardinals” in Zermelo-Fraenkel set theory (ZF).  This would have the consequence that strongly inaccessible cardinals don’t exist either and so on for all the other large cardinals.  Martin Davis on the FOM list cautions that the claim is “highly dubious”.

Here are links to Kiselev’s papers:

Part 1: http://arxiv.org/abs/1010.1956
Part 2: http://arxiv.org/abs/1011.1447

Link to the FOM list entry: http://www.cs.nyu.edu/pipermail/fom/2011-August/015694.html

Posted in Cardinal Numbers, Inaccessible Cardinals | 2 Comments »

The Cardinality of Uncountable Sets I

August 11, 2011

We saw earlier that \aleph_{0} can accommodate a countable infinity of countable infinities. Now we’re going to produce an infinite cardinal number that is bigger than \aleph_{0}. Cardinal numbers express the size of, or number of elements of a set. Countably infinite sets have cardinality \aleph_{0}.  We know that countably infinite sets can be matched up (by way of a one-to-one and onto function) to the set of positive integers. So if we can find a cardinal number greater than \aleph_{0}, we can find a set greater than the set of positive integers, or an uncountably infinite set.

We’re going to begin with an infinite list of subsets of the set of positive integers:S_{1}, S_{2}, S_{3} \cdots  And we’re going to represent each of these sets by a function of positive integers:

s_{n}(x)= \begin{cases} 1, &\text{if } x \in S_{n};\\ 0, &\text{if } x\notin S_{n}. \end{cases}

For example, if the third set in our list, S_{3} is the set of positive even integers, then the values of the function s_{3}(x) are s_{3}(1) = 0, s_{3}(2) = 1, s_{3}(3) = 0 \cdots And if the fourth set in our list, S_{4} is the set of squares, then the values of the function s_{4}(x) are s_{4}(1) = 1, s_{4}(2) = 0, s_{4}(3) = 0 \cdots and so on.

Imagine now that we set up an infinite table like this.  The top row will be our header row, or our x-axis and will contain, in the first position the label “Sets of positive integers”.  To the right of this label we list out the positive integers, 1, 2, 3, \cdots  These are our columns.  Immediately below the label “Sets of positive integers” we list the names of the each subset of positive integers, S_{1}, S_{2}, S_{3} \cdots This is our y-axis and extends infinitely downwards.  We now fill out the values of each coordinate using the values of the functions s_{1}, s_{2}, s_{3} \cdots extending to the right of each set name on the y-axis.  Basically the rows of the infinite table contain the 0-1 representation of each of the sets.

It looks like this:

You may have noticed that the diagonal values of the table are in bold.  The bold values form a sequence, s_{1}(1), s_{2}(2), s_{3}(3), \cdots called the diagonal sequence.  We’ll return to the diagonal sequence in a moment.  But first we want to ask: does our list (along the y-axis) contain all of the sets (subsets) of positive integers? It doesn’t if we can always produce a set different from each of the sets on the list.

Here is where the diagonal comes in.  The diagonal sequence is just a sequence of 0′s and 1′s and and may very well encode a set of positive integers appearing in our list. But we’re trying to find a set that does not appear on the list.  It’s easy to find one if we think of a sequence that contains positive integers that do not appear in the diagonal sequence.  So we can take the diagonal sequence and create the antidiagonal by changing 1′s to 0′s and 0′s to 1′s in the the diagonal sequence.  So let the antidiagonal be given by subtracting each element of the diagonal sequence from 1.  The antidiagonal is 1 - s_{1}(1), 1 - s_{2}(2), 1 - s_{3}(3), \dots and does not appear anywhere as a row in our table.

But suppose that the antidiagonal did appear as, say, the kth row in our table, thus representing the kth subset of positive integers. It would look like this: s_{k}(1) = 1 - s_{1}(1), s_{k}(2) = 1 - s_{2}(2), s_{k}(3) = 1 - s_{3}(3), \cdots s_{k}(k) = 1 - s_{k}(k), \cdots  But s_{k}(k) = 1 - s_{k}(k) can never obtain because s_{k}(k) has to either be 0 or 1.  If it’s a 0, then we have 0 = 1 - 0 = 1.  But if it’s a 1 then we have 1 = 1 - 1 = 0.  In either case, it is absurd, so the antidiagonal, whatever it may be, must be different from any set appearing in the list S_{1}, S_{2}, S_{3} \cdots of subsets of positive integers.  If we take the antidiagonal and append it to our list of subsets of positive integers all we have to do is repeat the argument and we will end up with another distinct antidiagonal sequence that does not appear on our list.

The set of all subsets of the positive integers is called the power set of the set of positive integers.  If the set of positive integers is denoted by \textup{N} then the power set of \textup{N} is \mathcal{P}(\textup{N}).

What can we say about the cardinality of \mathcal{P}(\textup{N})?  Well, for any one of the sequences given by our list of subsets of positive integers, the first digit can be either 0 or 1, and the same is true for the second and third digits, and so on for all \aleph_{0} digits in the sequence.  This means that there are 2 \times 2 \times 2 \times \cdots (for \aleph_{0} factors) possible sequences of 0′s and 1′s and so there are 2^{\aleph_{0}} sets of positive integers.  And we have just shown by means of the antidiagonal that 2^{\aleph_{0}} > \aleph_{0}.

So 2^{\aleph_{0}} is an infinite cardinal number that is greater than \aleph_{0} and the power set, \mathcal{P}(\textup{N}), of the positive integers is an uncountably infinite set.

In the next update we’ll produce anothe cardinal number, \aleph_{1} greater than \aleph_{0}.

Posted in Cardinal Numbers, Elementary Logic, Transfinite Cardinals | 2 Comments »

« Older Entries
Follow

Get every new post delivered to your Inbox.