Re: Paper and slides on indefiniteness of CH

THE STRONGEST STATEMENT, OVER ZF PLUS THE TRUE \Pi^0_1 SENTENCES, OF THE FORM “SUCH AND SUCH (PURELY UNIVERESAL) SENTENCE IN PREDICATE CALCULUS WITH EQUALITY HAS A MODEL ON EVERY INFINITE DOMAIN”, IS PROVABLY EQUIVALENT TO THE AXIOM OF CHOICE, OVER ZF PLUS THE TRUE \Pi^0_1 SENTENCES.

THE STRONGEST STATEMENT, OVER ZF PLUS THE TRUE \Pi^0_1 SENTENCES, OFTHE FORM “SUCH AND SUCH (PURELY UNIVERESAL) SENTENCE IN PREDICATE CALCULUS WITH EQUALITY HAS A MODEL ON EVERY NONEMPTY DOMAIN”., IS PROVABLY EQUIVALENT TO THE AXIOM OF CHOICE, OVER ZF PLUS THE TRUE \Pi^0_1 SENTENCES.

Such spinoffs very naturally arise in the course of using legitimate methods for conducting foundationally and philosophically motivated research. As you can see in the full email history here, I felt traction well before I had seen the above in any formulation, and saw the above in some formulation before I saw the above in its present formulation above. It is fairly clear that there is a rich new (I always worry about precisely how new anything is, of course) area surrounding the above observations. There is at least some new unifying theory of forms of the axiom of choice (some equivalent to the axiom of choice and others weaker), and probably much more.

My intention is to start dealing directing with “intrinsic maximality in set theory” in the next messages. Let’s see what I come up with.

COPY

Back to my persistent efforts to turn this mostly unproductive rarely generally understandable slogan ridden thread into something more.

In a previous posting, I indicated some important features of my general f.o.m. methodology. I have started to apply it to a notion that has been around for some time

*) intrinsic maximality of the set theoretic universe

as a way of generating or justifying axioms for set theory. It has clearly not been appropriately elucidated, and the notion is also under considerable attack these days.

In fact, there is folklore that it is a sound way of generating the axioms of ZFC. That specifically is being questioned by some even with regard to the AxC = axiom of choice.

Now the way I see it, informally “intrinsic maximality (of the set theoreitc universe)” means something like this:

**) the set theoretic universe is as large as possible or imaginable – consistent with the most elemental features of sets**

What elemental features of sets? Well, for this purpose, we take as a working idea, first and foremost, extensionality = two sets are equal if and only if they have the same elements. But what about foundation? Well, I just don’t know at this point what attitude we should take toward foundation for present purposes.

Prima facie, it would appear that AxC follows from **). Say, given an equivalence relation, we can certainly imagine the idea that we have picked one element from each equivalence class. But how do we systematize this?

I came up with the following more general idea. Instead of starting with an equivalence relation, we can instead start with an arbitrary set X. We can put “basic” conditions on a relation or function on X. We then consider the sentence

#) for all sets X there exists a relation or function satisfying a given condition.

Here are three of the simplest special cases.

For all X there exists a linear ordering on X. For all X there is a one-one function from X to X that is not onto. For all X there is a one-one function from X^2 into X.

Of course, the first is provable in ZFC. However, the other two are refutable in ZFC (even in ZF).

So this suggests the following.

##) for all infinite sets X there exists a relation or function satisfying a given condition.

Then consider these three examples.

For all infinite X there exists a linear ordering on X. For all infinite X there is a one-one function from X to X that is not onto. For all infinite X there is a one-one function from X^2 into X.

These are all provable in ZFC. The third is equivalent to AxC over a weak fragment of ZF. The conjunction of the first two does not imply AxC over ZF, and neither of the first two implies the other over ZF.

Thus it looks like we have stumbled upon a calculus that unifies a lot of important work concerning forms of the axiom of choice in set theory.

So now let’s try to get it all together.

DEFINITION 1. K(\text{infinite}) is the set of all sentences of set theory of the following form. For all infinite D there exists a model of \varphi with domain D. Here \varphi is a sentence in first order predicate calculus with equality. K(\text{nonempty}) is the set of all sentences of set theory of the following form. For all nonempty D there exists a model of \varphi with domain D.

But an important feature of the examples are that they are purely universal.

DEFINITION 2. K(\text{infinite},\pi) consists of “for all infinite D there exists a model of \varphi with domain D” where \varphi is purely universal. K(\text{nonempty},\pi) consists of “for all nonempty D there exists a model of \varphi with domain D” where phi is purely universal.

It appears that every element of the K’s, from the point of view of ZF, has two orthogonal components – its arithmetic part and its set theoretic part.

THEOREM 1. The following is provable in a weak fragment of ZFC. A sentence lies in K(\text{infinite}) if and only if it is satisfiable in some (every) infinite domain. A sentence lies in K(\text{nonempty}) if and only if it is satisfiable in every domain if and only if it is satisfiable in some (all) infinite domains and satisfiable in all nonempty finite domains. Thus the set of all true sentences in K(\text{infinite}) and K(\text{nonempty}) are complete and \Pi^0_1, respectively.

DEFINITION 3. Let ZFC* be ZFC together with the true \Pi^0_1 sentences.

THEOREM 2. Every element of K(\text{infinite}) and K(\text{nonempty}) is provable or refutable in ZFC*. In fact, every such element is either provable in a weak fragment of ZFC* or refutable in a weak fragment of ZF.

There are plenty of interesting special fragments of first order predicate calculus with equality that where validity and validity for infinite models are decidable – and demonstrably so in ZFC (even in a weak fragment of ZF). For K(\text{infinite}) and K(\text{nonempty}) based on such fragments, Theorem 2 will clearly hold with ZFC* replaced by ZFC. For these fragments of K(\text{infinite}) and K(\text{nonempty}), we should be able to get a particularly clear understanding of the status of the elements over ZF.

The program is to understand the status and relative status of the elements of K(\text{infinite}) and K(\text{nonempty}) over ZF*.

We have already seen that there is a variety of elements of K(\text{infinite},\pi) over ZF*, some of which are provably equivalent to AxC over a weak fragment of ZF*. However, what about elements of K(\text{nonempty}) and K(\text{nonempty},\pi)?

THEOREM 3. There is an element of $latex K(\text{infinite},\pi)$ and of K(\text{nonempty},\pi), respectively, that is provably equivalent to AxC over a weak fragment of ZF.

We have already seen that we can use “for every infinite D there is a one-to-one f:D^2 \to D“. But about about K(\text{nonempty},\pi)?

We now show that

*The axiom of choice can be expressed as the assertion that some given purely universal sentence is satisfiable in every nonempty domain. Same with “infinite domain”.

I looked into this more deeply than I did in posting #550. I think that a good way of proving this is as follows.

The sentence \varphi asserts the following.

  1. Equivalence relation E on D.
  2. Set D’ obtained by removing 0,1, or 2 elements from each equivalence class of E on D, as long as you leave at least one element after removal. Work with E on D’.
  3. Set S which picks exactly one from each equivalence class of E on D’.
  4. Map which, given x in D’, produces a bijection between [x] and S, depending only on [x].
  5. D\setminus D' is embeddable in D' \times D'.

Note that \varphi has a model with domain any nonempty finite set.

Let D = B \cup \lambda^+, where \lambda is an infinite cardinal, and \lambda cannot be embedded into B. We prove that B is well ordered.

Case 1. |S| \geq \lambda^+. Then each [x], x \in D', has at least \lambda^+ elements. Hence each [x], x in D', has at least one element of \lambda^+. Hence |S| = lambda^+. For each x \in D', we associate first the unique element of S that is equivalent to x, and then the result of the bijection between [x] and S given by 4. Thus we have a one-one map from D' into S \times S. Hence D' is well ordered. By 5, D\setminus D' is well ordered. Hence D is well ordered. In particular, B is well ordered.

Case 2. |S| \ngeq \lambda^+. Then no equivalence class has cardinality  \geq\lambda^+. Hence every equivalence class of E on D’ has fewer than \lambda^+ elements of \lambda^+. Hence every equivalence class of E on D has at most \lambda elements of lambda^+. Hence there are at least \lambda^+ equivalence classes of E on D. Hence there are at least \lambda^+ equivalence classes of E on D’. Hence every equivalence class of E on D’ has at least \lambda^+ elements. This is a contradiction.

QED

Next posting will start to engage with maximality.

Another way of saying this: we have characterized AxC as the strongest statement in any of K(\text{infinite}), K(\text{nonempty}), K(\text{infinite},\pi), K(\text{nonempty},\pi), over ZF plus the true \Pi^0_1 sentences.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>