The Cardinality of Uncountable Sets II

Posted by —

0

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 ordering them by size (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.

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

Posted by —

2

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

The Cardinality of Uncountable Sets I

Posted by —

1

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}.

What is Aleph-Null?

Posted by —

1

Someone asked for an explanation of \aleph_{0} (Aleph-null) for non-mathematicians.

Here goes.  Begin with the concept of counting a set of objects.  We can count a set of objects if we can arrange the objects in a list: first object, second object, third object, and so on, so that each object in the set appears on the list.  Listing the objects in a set is the same as assigning a positive integer to each member of the set.  Some countable sets are infinite.  For example, the set of positive integers itself, the set of positive even integers, the set of positive odd integers as well as the set of primes.

To see that the positive even integers are countable just line up the members of that set and match each member of the positive even integers to a member of the positive integers.  The function f(n) = 2n expresses this matching of the two sets because each positive even number 2n is matched up with just one positive integer n.

Having the property of being able to be put into such a correspondence is called a set’s cardinality.  The cardinality of finite sets is just the number of elements they have; two sets have the same cardinality if, and only if, they have the same number of members/elements.  For example, the cardinality of a set of a dozen eggs and a set of a dozen pencils is 12.

Any infinite set that can be put into a one-to-one correspondence with the positive integers is countably infinite. We can also speak of the cardinality of countably infinite sets (like the set of positive integers and the set of positive even integers).  We can speak of the number of elements in these sets, which is an infinite, or transfinite number, denoted by \aleph_{0}.  So we can say that the number of positive even integers is \aleph_{0}.

So the set of positive integers (1, 2, 3, \cdots) has cardinality \aleph_{0}. Say we list out each positive integer and say  we want to add the number 0 at the beginning of this list.  Well, we can just add it and shift every other number out to the right (to position n+1).  The cardinality of this set is still \aleph_{0} since this set can also be matched up to the positive integers. This means that \aleph_{0} + 1 = \aleph_{0}.  Suppose we go off the deep end and want to add a countable infinity of other numbers to the set of positive integers, say the negative integers (-1, -2, -3, \cdots).  We can do this by letting each n in the original set move over to position 2n. We can match this resulting list to the positive integers, and the cardinality of the resulting set will also be \aleph_{0}.  This means that \aleph_{0} + \aleph_{0} = \aleph_{0}.

Finally, suppose we’re really crazy and want to add \aleph_{0} sets each of \aleph_{0} members to our original list.  The list can always be “expanded” to accommodate each member of each set. For example, since each of the sets we want to accommodate are countably infinite, each of their members can be listed 1, 2, 3, \cdots Take the first set and list out each element in this fashion: for each n place the first element of the set in position n and leave n spaces open on the list before placing the subsequent element. The first element will be in the first position, the second element will be in the third position, the third member will be in the 6th position, etc.  So now we have 1 empty space after the first element, two spaces after the second, three spaces after the third, four after the fourth, and so on and so forth. Taking the second countably infinite set, place each of its members in the leftmost space open after setting out the first countably infinite set. The situation now is analogous to when we laid out the first countably infinite set: place each member of the third countably infinite set and place it in the leftmost open space available after having set out the second countably infinite set.  You can do this for each of the countably infinite sets of countably infinite members. The resulting list can be matched up to the positive integers, meaning that \aleph_{0} \times \aleph_{0} = \aleph_{0}.

So we have shown that \aleph_{0} + \aleph_{0} = \aleph_{0} = \aleph_{0} \times \aleph_{0}. These are elementary equations of the arithmetic of infinite cardinals that are a bit different from those of the arithmetic of finite cardinals that everyone is familiar with, like, 2 +1 = 3, 1 \neq 3; 2 + 2 = 4, 2\neq 4; 2 \times 2 = 4, 2 \neq 4.

While \aleph_{0} can accommodate quite a bit, there are sets that have a cardinality higher than \aleph_{0}.  I’ll produce two such cardinal numbers in the next update.

FOM Discussion on Consistency of Peano Arithmetic and Foundations of Mathematics

Posted by —

0

I’ve been folloiwing a discussion on the Foundations of Mathematics List (FOM) regarding these two videos (1, 2) on what noted Field’s Medalist Vladimir Voevodsky thinks regarding the consistency of Peano Arithmetic and the foundations of mathematics.  His comments have caused quite a stir on the list.  Below is a message to Voevodsky by Harvey Friedman and Voevodsky’s reply.

“Dear Professor Voevodsky,

I have become aware of your online videos at http://video.ias.edu/voevodsky-80th and http://video.ias.edu/univalent/voevodsky. I was particularly struck by your discussion of the “possible inconsistency of Peano Arithmetic”. This has created a lot of attention on the FOM email list. As a subscriber to that list, I would very much like you to send us an account of how you view the consistency of Peano Arithmetic. In particular, how you view the usual mathematical proof that Peano Arithmetic is consistent, and to what extent and in what sense is “the consistency of Peano Arithmetic” a genuine open problem in mathematics. It would also be of interest to hear your conception of what foundations of mathematics is, or should be, or could be, as it appears to be very different from traditional conceptions of the foundations of mathematics.

Respectfully yours,

Harvey M. Friedman
Ohio State University
Distinguished University Professor
Mathematics, Philosophy, Computer Science”

And Voevodsky’s reply:

“Dear Harvey,

such a comment will take some time to write …

“To put it very shortly I think that in-consistency of Peano arithmetic as well as in-consistency of ZFC are open and very interesting problems in mathematics. Consistency on the other hand is not an interesting problem since it has been shown by Goedel to be impossible to proof [sic].

Vladimir.”

I think that this reply still leaves a lot of room for interpretation. It could simply mean that Hilbert’s program is no longer interesting or it could be an call for finitism in foundations or it could indicate the possibility of fruitful mathematics by means of searching for an inconsistency proof of these well established systems.  “Curiouser and curiouser!” Cried Alice …

Clarity In Talking About The Status Of Attributes

Posted by —

0

When the ontological status of a property or attribute is in question, the central issue is the ontological status of an object’s possessing or exemplifying a property.  When the ideological status of a property or attribute is in question, the central issue are the kinds of predicates that express the property.  The following example brings this out starkly:  A property can be mental, but not physical (ideologically), but can be ontologically physical, but not mental.

If a mental predicate \textup{A}(x) \in \Psi is not lawlike coextensive with a physical predicate \textup{B}(x) \in \Phi, where \Psi and \Phi are appropriate vocabularies, the attribute expressed by \textup{A}(x) is mental, but not physical.  Nevertheless, by the principle of physical exhaustion (PE), the attribute is physical, but not mental (ontologically), as it is possessed solely by physical objects.

Entity-wise, every attribute is mathematical-physical, but only those attributes are mathematical-physical that are expressible by mathematical-physical predicates.  So, if physical reductionism is false (which is likely the case), there are attributes which are mathematical-physical entities, but are not mathematical physical attributes.

The confusion arises when terms like “mental” or “material” are used to call out properties or attributes without clearly setting out whether one is talking about the ontological or ideological status of the attribute.  This is an important point by Hellman, and we will see how this distinction and physicalist materialism in general are useful in clarifying questions of reductionism and materialism in the philosophy of mind when we turn to an analysis of Chalmers’ anti-materialist claims.

The Ontological and Ideological Status of Attributes

Posted by —

0

With the principle of Physical Exhaustion (PE: (\forall x)(\exists \alpha)(x \in \textup{R}(\alpha)) where \textup{R}(\alpha) is a rank in the hierarchy of the physical), which allows us to say that everything is exhausted by the physical, every attribute is mathematical-physical (i.e., existing somewhere (possibly high-up) on the set-theoretic hierarchy; see this and this). Thus the ontological status of attributes is mathematical-physical.  Now, for a given vocabulary \psi, and for any attribute that expressed by a predicate that makes essential use of members of \psi, call that attribute a \psi-attribute. So, for example, attributes expressed by physical predicates are physical attributes and those expressed by psychological predicates are psychological. This is their ideological status.

The ontological status of a thing has to do with which extensions of predicates (of ontological kind) under which the thing falls. The most encompassing of such predicates is “is mathematical physical’.  But there are other, narrower ways to distinguish the ontological status of things.  For example, some metaphysical predicates, “is abstract”, “is concrete”, or some scientific ones, “is an elementary particle”, “is an event”, “is a person”, “is a social process”, “is a physical magnitude”, etc. Some other ontological kind predicates have empty extensions: “is a soul”, “is a phenomenally raw feel not identifiable with any entity in the hierarchy of the physical”.  But if something were to satisfy these predicates, the predicates would indicate the ontological kind of these things.  So the important semantic relationship here is satisfaction of ontological kind predicates.

This is different than in the case of the ideological status of attributes, where the important semantic relationship is expression of an attribute by a predicate –i.e., the relationship between the argument and value of a universalizing function. Every entity has an ontological status, but only universals have ideological status determined by the types of predicates for which the universal under consideration is the value of the universalizing function.

So the ideological status of an attribute, is given by the predicates that express it.  These predicates themselves can be classified, for instance, according to scientific discipline, psychological-predicates, physical-predicates, Economic/Sociological-predicates, etc.  These classifications are historical and are subject to change due to a variety of factors –not all of them scientific.  Hellman explains that attributes themselves may have more than one ideological status: for the predicate ‘is in pain at t‘ is coextensive in a law-like fashion with a complex physical predicate then ‘being in pain’ is both a psychological and a physical attribute since it is expressed by both psychological and physical predicates.

In the next update I’ll go into Hellman’s discussion of the confusion that results when the ideological and ideological status of attributes is not clearly stated in debates concerning materialism and the mental.

Introduction To Hellman’s Treatement of Universals

Posted by —

0

Universals, for our purposes, are sets, predicates, properties, relations and attributes –the same universal can instantiate or subsume numerically distinct things.  Among universals we distinguish between those that are extensional, like sets and predicates and those that are intensional, like properties, relations and attributes.

Roughly, the distinction between these two types of universals is the following.  Those that are extensional obey the principle that equivalence implies identity, while those that are intensional are in violation of this principle.  In cases of non-deformity, the property of being a creature with a kidney is extensionally the same as the property of being a creature with a heart insofar as the same things have each, but the properties are different.  Sets and predicates, on the other hand, do satisfy the principle of extensional equivalence: the set of creatures with a kidney and the set of creatures with a heart have the same members, and are thus identical.

Now, universals in general are taken to fall within the range of functions from the set \textup{P} of predicates of a language \textup{L} to the universal they give expression to f: \textup{P} \mapsto \textup{U}, where \textup{U} is the set of universals of \textup{L}.  Hellman explains that among such functions there are some that assign universals with much discrimination: two predicates are mapped to the same universal only if the predicates are identical. And others do so with less discrimination: coextensionality is enough. Hellman imagines a partial ordering of universals based on discrimination criteria with predicates being among the most discriminating and extensions among the least.

Since Hellman is concerned with properties and relations used in science, so the first thing we need to do is set up identity criteria for these attributes. For example, we want to say that temperature is the very same magnitude as mean molecular kinetic energy. So two predicates \textup{F} and \textup{G} are mapped to the same universal u just in case it is a scientific necessity that these two predicates apply to the same things.  In other words, \textup{F} and \textup{G} express the same attribute only in case in every model in \alpha, \textup{F} and \textup{G} have the same interpretation.  Remember that \alpha is the set of structures modeling scientific possibility.

So, how do we express attributes given this way of thinking about them?  Hellman suggests using the technique from modal logic, such that the function from members of \alpha to the extensions assigned to that predicate by each model in \alpha is identified with the attribute expressed by that predicate.  In this way, two predicates express the same attribute in case they do so in every structure representing a scientific possibility; thereby getting the desired necessity.

If we need to represent universals that discriminate differently than scientific attributes, we can use sets or collections of structures different from \alpha insofar as the universalizing function is no more discriminating than those functions that assign predicates to the same universal in case the predicates are logically equivalent.

For these universals, the identity conditions are the following:  functions (i.e., attributes) are identical just in case they assign the same arguments (i.e., members of \alpha) to the same values (i.e., extensions of predicates).   Or simply say that two predicates \textup{F} and \textup{G} express the same attribute if, and only if, \forall (x_{1}, \dots, x_{n})(\textup{F}x_{1}, \dots, x_{n} \leftrightarrow \textup{G}x_{1}, \dots, x_{n}) is a law of science.

This last bit will be what links the discussion of attributes to that of reducibility –since we need to make use of explicit definability.

In the next set of notes I’ll go into the difference that Hellman notes between the ideological and ontological status of universals.