Cantor's proof

As we are close to the subject, and because it is beautiful and remarkable, here is Cantor's proof of the uncountability of the reals*.

1. For all s, for some n, s = f(n).
2. f(n) = {m: x not in f(m)} (from 1).
3. If n in f(n) then n not in f(n), and if n not in f(n) then n in f(n) (from 2).
4. Contradiction.

It is beautiful because it is short, and all short things are beautiful.  It is remarkable because the scholastic philosophers never produced anything close to it.  In nearly all matters of logic, the culture of the renaissance and early modern period never approached the heights that logic attained in the early 14th century.  But not this.
 
It needs a little explanation, of course.  The first statement follows from the claim that sets of natural numbers are 'countable', i.e. to do this, to any set s of natural numbers, there must correspond some natural number n.
 
The second follows from the first.  There must be some natural number corresponding to the set of natural numbers that are not in the set corresponding to them.  The third draws a simple conclusion from that.  The fourth states that the third is a contradiction.  We can therefore infer that one of the first two statements is false.
 
To forestall impudent hairsplitters, I should add that (as far as I know) Cantor never gave a proof in precisely that form.  His actual proof is in the Logic Museum, with my English translation. 
 
To any other quibblers, I reply that I am not a mathematician.

*Modified this evening o/a of Belette's complaint of sloppiness.

On set construction

Belette asks about rules for ‘constructing’ Ockham sets (osets). It should be noted that there is no sense in which osets are, or need to be ‘constructed’, and in this way osets are fundamentally different from their mathematical counterparts, as should be clear from the following example. Zermelo (1908) says

(A) If a and b are any two objects of the domain, there always exists a set {a, b} containing as elements a and b but no object x distinct from them both

This is a rule (the ‘axiom of pairs’) that tells us that we can ‘construct’ a set {a, b} given the existence of its members a and b. We need this rule because we cannot infer the existence of a mathematical set, an individual object different from either of its two members, from the existence of its members alone. The consequent does not logically follow from the antecedent. In this, by contrast -

(B) If Peter preached in Jerusalem and Paul preached in Jerusalem, then Peter and Paul preached in Jerusalem.

we are not giving a rule for constructing any non-linguistic entity, nor are we making any existence assumptions beyond what is given in the antecedent. (B) simply gives a rule for constructing expressions: it tells us that the consequent means the same thing as the antecedent. Given the propositions ‘Is_F(a) and Is_F(b) and Is_F(c) and …’ the rule allows us to construct the proposition ‘are_F(a and b and c and …)’.

So my question remains. We assume the following

(1) At least one element exists
(2) One element is finite
(3) Any finite x’s and a single element are finite
(4) Any finite x’s are such that there is some y such that y is not one of the x’s.

This does not ‘construct’ anything. Rather, it asserts the existence of certain things. The only things it explicitly asserts are the existence of finite things. For example, it asserts the existence of one thing (the ‘first’ thing). It asserts (by inference) the existence of two things (the first thing plus some y which is not that thing), the existence of three things (the first two things and some other y), all of which are finite. The question is whether from statements 1-4 we can also implicitly infer the existence of infinite things (an infinite oset) in exactly the way that we can infer the existence of Peter and Paul from a statement about Peter and a statement about Paul. Can we construct an expression that refers to all of the elements of the domain? For if we can, it follows that all the elements of the domain exist – whether or not we actually constructed the expression. Peter and Paul exist whether or not we have an expression such as ‘Peter and Paul’. Do all the infinite elements of the domain exist, whether or not we construct the expression ‘all the elements of the domain’?
I hope this makes the problem clearer.

Intuitions about infinity

I must confess my intuition, which rarely lets me down, fails me in the present case.  The question is whether the 'Ockham set' axiom of infinity is possible or not:

(Ockinf) For any x's, there is some y such that y is not one of the x's.

Against: if we can speak of 'any x' in an infinite domain, then surely we can speak of 'all the x's'.  But if the axiom above is true, it follows that we cannot speak of all x's.

For: there is no logical impossibility here. Indeed, if we take x's as being an ordinary mathematical set, the statement corresponds to a version of standard set theory (being part of ZF-inf).  Why should a different in the interpretation of the terms lead to a difference in truth value?

So I shall leave this one for now (but any comments or ideas gratefully accepted).  It's connected with a wider question of whether there could be a nominalist version of set theory, and whether it would differ in any way from standard set theory.

Malezieu and infinite sets

A commenter wondered whether Malezieu's principle (that a number of things - say 20 - exist because the first exists, the second exists,  and so on) applies because there are a finite number of things, and a finite time is all we have to count anything.

I don't think so. First of all, the fact that the first thing exists, the second thing exists, etc., is independent of anyone counting the things.  You object that nominating one of the things as 'first' is arbitrary, and therefore involves human choice.  I reply: take any of the things you like.  Then the fact that this thing exists, and the fact that any other one of the things exist, and the fact that any other one apart from those two exists, etc., ensures that all of them exist, and this fact is independent of any human counting going on.

Moreover, Malezieu's principle, as applied to an infinite universe, is a logical one.  We start with the nominalist assumption that only individual things exist.  We then assume that there are two possible worlds in which every individual in one is identical with some individual in the other.  Malezieu's principle then tells us that any oset of individuals that exists in one world, also exists in the other.  This is a logical consequence of the fact that existence claims relate to individual existence only.

More about Malezieu’s principle

As I have defined an Ockham set or oset, an oset is nothing different from its elements. A term referring to an oset (‘that dozen of eggs’) is referring to all its elements in just the way that a grammatically plural term (‘those 12 eggs’) is referring to them. It just happens to be grammatically singular, and should not be confused with a genuine singular term referring to a thing. It is not a thing, but a number of things (except in the limiting case of the singleton oset, perhaps, which is identical with its only member).

Malezieu’s principle is that if the things exist, then the oset exists. If a exists (singular) and b exists (singular), then a and b exist (plural) , and the oset O (i.e. a and b) exists also. If some or all of the elements do not exist, or cease to exist then the oset does not exist, or ceases to exist, also. The reference of ‘that dozen eggs’ fails as soon as even one egg is broken. This contrasts with set theory, where we have to postulate the existence of a set containing the members.

Thus there cannot be two possible worlds, each of which contains a and b, such that the oset of a and b exists in one possible world, but not the other. This has the following corollary

(M) If an oset exists in one possible world but not another, it follows that at least one of its elements is in the first world, that is not in the other.

This leads to the problem of the infinite universe where there is no oset corresponding to the infinitely many elements. If we allow the possibility at all, it follows from (M) above that there cannot be two possible worlds where any element one is identical with some element in the other, but where the oset of all of them exists in one, but not the other. Either such a world is impossible, or every infinite world is like this. If it is impossible, then Oxinf is not independent – if every finite oset excludes at least one thing, unlike set theory this guarantees the existence of infinite oset. But if it is possible, this rules out infinite osets.

Independence of the axiom of infinity

In my last post, I introduced the 'Ockham' version of the axiom of infinity

(Ockinf) For any X's, there is some y such that y is not one of the X's.

which, for a suitable definition of infinity, gives us an infinitely large universe, but no infinitely large Ockham set to correspond to it.  Every Ockham set is finite, yet the universe is infinite.  As 'Belette' has spotted, this may be no surprise, for it is well known that the axiom of infinity cannot be derived from the rest of the axioms of Zermelo Fraenkel set theory, and we can even construct a model of the axioms where the axiom of infinity is replaced by its negation (called ZF-INF).

But it is not so simple as that, and I will complete my argument by returning to the point I made in my first post on this subject, about the difference between Ockham sets and mathematical ones.  The key difference is that, given the existence of the elements corresponding to an Ockham set, the set itself has to exist, for the set is identical with its members.  This is Malezieu's principle: if twenty men exist, it is because the first, the second, the third man etc., exist.  If a exists and b exists, then the Ockham set a and b exists also.  By contrast, in set theory we have to posit this using an axiom such as the axiom of pairs.

Thus, given a universe with an infinite number of elements but no oset corresponding to them, can we wave a magic wand and bring that corresponding oset into existence, as we can easily do in ordinary set theory?  I suggest we can't.  For an oset simply is its members.  If we bring an oset into existence, we must bring at least one of its elements into existence. But we can't do that here. By hypothesis, every member of the infinitely large universe exists already. What is lacking is the oset of all of them. If we now create the oset, what exactly are we creating?  Nothing.  There are no things to create, for they are already there.  Nor can we suppose that there is any other possible universe corresponding to this possible one, containing identical elements, but also containing the oset itself.  So, if a universe consisting of these elements is possible, it is necessarily the case that there is no oset containing all its elements.  And in general, there can be no universe containing an infinite number of elements, together with the oset of all of them.  If every possible world is such that p, then necessarily p.

This is a surprising result.  The alternative is to reject (Ockinf) above, and thus reject the possibility of an infinite universe without a corresponding oset. But that is equally surprising, for it would amount to rejecting the independence of the axiom of infinity.  We could merely define 'finite oset' as we did before, assert that to every finite oset there is an (equally finite) oset containing one extra element, and then deduce the existence of an infinite oset, based on the logical impossibility of (Ockinf) above.

Comments welcome.

Ockham sets: preliminaries

Judging by the comments from 'Belette', we need some preliminary remarks about Ockham sets. Let's begin with plural reference. In English (and Latin, and probably most natural languages) we have plural terms as well as singular terms. We can form plurals either by concatenating singular terms together, as in 'Peter and Paul'. Or we can use an ordinary plural referring term, as in 'those [two] apostles'. Both of these take verbs in the plural form. Thus "Peter and Paul are apostles", "those apostles are preachers". Finally, we can form a collective noun of the form 'an X [of] Ys'. Thus 'a dozen apostles', 'a pair of shoes' and so on. These nouns are grammatically singular, and usually take verbs in the singular. Thus "a pair of shoes is in the cupboard", "one dozen eggs is a good thing to buy". (Although intuitions differ. Do we say that a number of people are in the room? Or is in the room? But this is merely grammatical accident, and has no relevance to logic, I think).

It is a fundamental assumption of Ockham set theory that the singular form of the collective noun is a grammatical feature only, not a logical one, and that we can assert identities using all three forms of plural noun. Thus

1. Peter and Paul are these apostles.
2. These apostles are a couple of apostles
3. This couple of apostles is [or are] Peter and Paul.

The equivalent to a mathematical set containing more than one member, say {Peter, Paul}, is the reference of the expression formed by concatenating the two proper names with 'and'. Thus 'Peter and Paul'. The equivalent to a set defined by comprehension, e.g {x: apostle(x)}, would be the reference of the plural referring term '[all] the apostles'.

There is no real equivalent to the singleton set {Peter}, because the comma in set notation corresponds to the 'and' in Ockham notation, and once we remove the 'and' from 'Peter and Paul', we are left with 'Peter'. Thus in Ockham set theory, {Peter} = Peter, if that makes any sense. Remember that the curly brace is set theoretical notation, and has no equivalent in natural language. Ockham set theory is meant to capture our logical intuitions about the behaviour of plural and collective nouns in ordinary language, not some invented language like set theoretical notation with modern predicate logic.

There cannot be an empty set in Ockham. Once we remove the name 'Peter' from the expression " 'Peter' ", we are left with nothing at all. An Ockham set is identical with its members, and it is impossible that something is identical with nothing.

Set membership is signified in Ockham by the relational term 'one of'. This can be defined in terms of the primitive 'and' mentioned above, as follows.

a is one of Xs if (def) for some Ys, Xs = a and Ys

For example, let the Xs be Peter and Paul and John. Then there are clearly Ys, namely Paul and John, such that

Xs = Peter and Ys.

I.e. Peter is one of those three persons, Peter and Paul and John.

Belette also asked for a definition of 'infinity'. Let's try starting with 'finity' first, by the recursive definition.

1. Any one thing is finite in number
2. If any Xs are finite in number, then those Xs and any one y are also finite in number.

Thus Peter is finite in number, hence Peter and Paul are finite in number, hence Peter and Paul and John are finite in number, and so on.

Then I say that there are 'finitely many things' when there exists an oset O such that O is finite in number, and such that every thing is one of O. And finally, there are 'infinitely many things' when it is not the case that there are finitely many things. This could happen in two ways. In the first, as I have defined it in the previous post. If every oset is such that at least one thing is not one of it, there cannot be an oset O such that every thing is one of O, and so our condition for finitude fails. Or there can be an oset such that it is not finite, and no finite oset contains everything, and so our condition for finitude fails again. I shall argue that of these two ways in which there could be infinitely many things, only the first is possible.

Ockham sets and infinity

In my previous post about infinity, I distinguished 'Ockham sets' or osets from ordinary mathematical sets.  An Ockham set is like a pair or a dozen.  It is not a thing, but rather a set of things, just as a dozen things is not a thirteenth thing separate from the twelve things it is a dozen of.

Now I shall ask whether it is possible that there could be infinitely many things, without there being an oset of those things.  My aim is to show that while it is possible that there are infinitely many things, it is impossible that there should be an Ockham set of those infinitely many things.  And my first step will be to ask whether it even could be possible that there were infinitely many things, without there being an Ockham set of them.

Assume that at least one thing exists.  Then ask whether the following could be true:

(Ockinf) For any X's, there is some y such that y is not one of the X's.

If it is true, then clearly there are infinitely many things.  For if there were finitely many, we could count through all the things there were, and come to a halt at some point.  Then all the things we had counted would fall within the range of the 'for any X's' above, and there would be at least one y that was not one of the things we had counted, which contradicts the assumption that we had counted all the things.  So there are not finitely many things, if Ockinf is true.  Therefore, if it is true, there are infinitely many things.

But is that even possible?  It is possible in standard set theory. Indeed, there is even a version of set theory where the axiom of infinity is denied.  But is possible in Ockham world?  I believe it is, but it runs counter to our natural assumption that we can talk about or refer to 'all the things there are'. For if the assumption above is possible we can't refer to 'all things'.  Suppose we can.  But the statement above says that for any X's, i.e. for any things whatsoever, there is at least one thing that is not one of them.  Hence there would be at least one thing that was not one of all the things, which is contradictory, for 'all things' includes absolutely everything, leaving no thing out.

You might argue that Ockinf above is impossible, because it is self-evident that, how many things there are, we can always refer to all of them.  But can we?  The statement above denies precisely that.  Is it false in virtue of its meaning?  I don't think so (although I'm not sure either).  Clearly 'any x' must be satisfiable by any x in the domain.  The lasso of a singular variable must be far reaching enough to get its singular loop round any object.  There can't be some x that isn't any x.  But any X's?  The plural variable lasso loops around numbers of objects in the domain.  There can't be some X's that aren't any x's.  But the statement above doesn't claim this.  It says that there are not some plural X's such that they include every singular x.

The lasso of plural quantification is flexible enough to rope around any number of finite things.  But it is not big enough to capture all of infinitely many things.  It will always fall at least one short.  And if we pull it a bit to get that one thing, we find to our frustration that there is yet another one that we missed!

In conclusion, it seems possible that there are infinitely many things, without there being an Ockham set that includes all those things.  Or at least the obvious arguments that would suggest it wasn't possible, are invalid.  In the next post, I shall argue that if this is possible in some domain, then it is so in every domain, i.e. there cannot possibly be any Ockham set that includes infinitely many things.

Are there infinite sets?

I shall argue that there are there no infinite sets. Which I shall immediately qualify by distinguishing between mathematical sets, and Ockham sets. A mathematical set is a thing that can contain things. The set {a, b} contains two things – the elements a and b – and is itself a third thing separate from them both. Since I hold that there are no such things as mathematical sets (which I will not argue here, let’s assume that for now), it immediately follows that there are no such things as infinite mathematical sets, but do not worry about that.

An Ockham set, by contrast, is a set of things that is not itself a thing. Let me explain. We speak of ‘a dozen’ or ‘one dozen’ things. If they are dozen, then they are 12. The ‘one’ dozen is not one thing in addition to those 12 things, but rather ‘a dozen’ is a collective noun for twelve things (and nothing else). I claim that there are no infinite Ockham sets.

This may take a few posts, so I will begin with a feature of Ockham sets that does not apply to ordinary (mathematical sets), and which will be essential to my argument. Since an Ockham set is its elements (i.e. the dozen things is or are those twelve things), it follows that if each element exists. I.e. if a exists and b exists, then a and b exist, i.e. the plural expression ‘a and b’ refers to some things. Therefore the Ockham set – the reference of ‘a and b’ or ‘those two things’ or ‘that pair of things’ also exists. If twelve eggs exist, then a dozen eggs exist, and so on. I shall call this Malezieu’s principle, after the French geometer about whom we know almost nothing except what Hume says about him:

I may subjoin another argument proposed by a noted author [Mons. MALEZIEU], which seems to me very strong and beautiful. It is evident, that existence in itself belongs only to unity, and is never applicable to number, but on account of the unites, of which the number is composed. Twenty men may be said to exist; but it is only because one, two, three, four, &c. are existent, and if you deny the existence of the latter, that of the former falls of course. [link]

I.e. if the elements exist, the Ockham set exists. And if the Ockham set does not exist, at least one of its members fails to exist. This principle is not true of ordinary sets. If a is in the domain, and b is also, we need an assumption – the axiom of pairs – that allows us to assume the exist of the ordinary set {a, b} containing as elements a and b, and nothing else.

More tomorrow.