Asaf Karagila
I don't have much choice...

Flow and the Partition Principle (6 updates)

There are no comments on this post.

Some of you already saw this new preprint on arXiv, and some of you even emailed me about it. I'm reading the paper, but I decided to do something drastic and join Twitter, temporarily, so I can more easily have discussions about this paper.

I will update this post on occasion while I read it, to reflect new understanding, kind of like a live journal, if you will.

9 October, 2020

I've read the paper until the definition of \(\ZF\)-sets. It is still somewhat mysterious to me, and it feels a bit circular at the moment, but I hope it will clarify later.\(\newcommand{\fz}{\mathfrak{\underline 0}}\newcommand{\fo}{\mathfrak{\underline 1}}\newcommand{\fp}{\mathfrak{p}}\)

The way to think about this, so far, which will probably be wrong later, is that the functions are class functions on the universe, only that they can act on one another. Kind of like how if \(j\colon V\to V\) is an elementary embedding, then we have \(j\circ j\) and \(j(j)\) as two different things.

In this sense, \(\fz\) is kind of like the empty set, whereas \(\fo\) is the identity. There is the notion of action, \(f[t]\) which says that \(f\) has a nontrivial action on \(t\), which in turn means that \(\fz\) is really a "filler object" which stands for "undefined". Using this understanding, I think, a lot things are somehow clearer.

Hopefully this will start to make more sense soon.

10 October, 2020

I didn't read anything today, it's the weekend and I have other things to do. But I wanted to document what I felt are the big open questions from myself (and others online) about this at the moment:

  1. Is Flow consistent relative to a known theory? It feels like it should be somewhere in the vicinity of "many inaccessible cardinals" to the point of "inaccessible limit of inaccessible cardinals". But of course we need to understand it in order to see if it can be interpreted there. Maybe it's weaker, or maybe it's just inconsistent?

  2. Is the proof \(\axiom{Flow}\proves``\ZF+\axiom{PP}\not{\proves}\AC"\) sound? If it is, then we move the question of correctness back to the question of consistency of Flow itself, and the methods can illuminate a way to use forcing-based methods (ahemiteratedsymmetricextensionsahem maybe?) to obtain this proof directly in familiar set theory.

  3. In the proof, the model obtained of \(\ZF\) is in fact a model of \(\ZF\) without Regularity. In that case, one has to ask whether or not the failure of \(\AC\) happens in the well-founded sets of that model? If not, then this is not quite a proof from \(\ZF\), but just almost. And this would be a very interesting reverse case of "Every vector basis has a basis implies Choice", where we know the proof in \(\ZF\), but it is open in \(\ZF\) without Regularity.

I hope to have time on Monday to get back to this project.

12 October, 2020

I want to file a complaint about F8, the Coherence axiom. I feel that says something to the effect of \(\Bbb E(f)\implies\Bbb E(\fp(f))\) and \(\Bbb E(\bigcup f)\), where \(\bigcup f\) denotes somehow the union over \(f\), whatever that means. So in other words, if \(f\) was emergent, then going up the rank, and going down in the rank, will preserve emergence.

Going on, restriction and F9 seem to be meant as an analogue of Separation, and very much so when applied to ZF-sets. The restricted power, \(\wp(f)\) is the real analogue of the power set, whereas \(\fp(f)\) is more of a "all partial functions \(f\to f\)".

The authors remark that \(\wp(f)\subseteq\fp(f)\) for all \(f\), even though there is no claim that either of these is a function. Rather the claim is that these are shorthand for formulas. I realise now that nowhere it is claimed that \(\fp(f)\) even exists, let alone \(\wp(f)\), or that if \(\fp(f)\) exists, then \(\wp(f)\) exists. These are interesting points, and I'd be happy to see them cleared up. But hopefully they will be later on in the text.

I'm peeking ahead, and it seems to me that the understanding of \(f[g]\) as "\(g\in\dom f\)" is quite important.

17 October, 2020

Sorry for the silence over the last few days. I've been busy, and every time I peaked in the paper I felt the need to backtrack a bit, and had nothing significant to say. But now I read all the way to the formulation of "\(\mathfrak{F}\)-Choice".

And there's something a bit odd here. Look at the following.

Proposition. \(\AC\) is equivalent to "If \(f\) is a function, there is \(g\subseteq f\) such that \(g\) is injective and \(\rng f=\rng g\).

Proof. Assume \(\AC\), then simply consider the relation \(f^{-1}\); it contains a function with the same domain, say \(h\). But by the fact that \(f\) was a function, \(h\) must be injective (since the fibres of \(f\) are pairwise disjoint). Let \(g=h^{-1}\), and we're done. In the other direction, let \(\{A_i\mid i\in I\}\) be a family of pairwise disjoint non-empty sets, and let \(f(a)=A_i\) if and only if \(a\in A_i\), then if \(g\subesteq f\) is injective, we have that \(g^{-1}\) is a choice function. \(\square\)

But the formulation of \(\mathfrak{F}\)-Choice explicitly states that the choice function is not a restriction of \(f\). Indeed, it can "mix scramble" the actions. In other words, we are merely stating that given a function with domain \(X\) and range \(Y\), there is an injective function from a subset of \(X\) onto \(Y\). This is just restating the Partition Principle itself!

I don't have time to keep reading, but it seems to me now that \(\axiom{Flow}\) is somehow designed to include \(\axiom{PP}\). The question, of course, is whether or not it really negates the correct formulation of the Axiom of Choice? Hopefully, we'll find out more next week.

20 October, 2020

Okay, so today we reach the interpretation (or "immersion") of \(\ZF\) in \(\axiom{Flow}\). There's a straightforward interpretation of the \(\in\) relation first and some preliminary proofs. The axioms of \(\ZF\), except Foundation, are then translated in the most straightforward way possible: ZF-sets will be the interpretation of the sets. Each axiom is proved separately to follow from \(\axiom{Flow}\), and these proofs are quite straightforward, since \(\axiom{Flow}\) is set in a way that mimics \(\ZF\) in a lot of ways.

Next we see that there is a Grothendieck universe in \(\axiom{Flow}\). I think this is a misnomer, and perhaps that authors misinterpreted the definition of a Grothendieck universe. Usually when we say "a Grothendieck universe" we mean a set which is a model of second-order \(\ZF\). In turn, this means \(V_\kappa\) for an inaccessible cardinal \(\kappa\).

Before we go into some other points, let's skip ahead to the universe part. Theorem 52 & Theorem 53 show that the function of "all ZF-sets" is a "proper class" and it is a Grothendieck universe. But that really just means that it's not a set, so it's not a Grothendieck universe in its usual meaning. The situation in \(\axiom{Flow}\) is more akin to \(\axiom{NBG}\) where we can prove that the class of all sets satisfies each of the axioms of \(\ZF\). Or perhaps even a bit more, and maybe we get a truth predicate for this class as well in \(\axiom{Flow}\), but in either case, this looks no more than what you'd have in Morse–Kelley or the likes of it.

Let's go back now.

First comes the definition of equipotence is a bit hard to decipher at first. We say that \(g\) and \(h\) are equipotent if there is a "connector" between them, which is an involution which maps the domain of \(h\) to the domain of \(g\), and vice versa. I think there might be an issue here, or at least in shallow reading there seem to be one. If \(h\) and \(g\) have the same infinite domain, sans one element, then the definition of a connector implies that the common domain is merely permuted. But that leaves the one extra element, say in the domain of \(h\), to be mapped nowhere by the connector.

Next comes the definition of finiteness. This too is a bit hard to decipher, but it really just says that a finite set is a set which is equipotent to some set, but not to the "connector". This is a nice little trick, since it's really the case that if a set is finite, then by changing one element we get an equipotent set, but the "connector function" must be strictly larger, since its domain is greater than the finite set.

The keen-eyed reader (or those who noticed me saying that on Twitter) will recognise that this definition gives us Dedekind-finite sets. This should be fine, since \(\axiom{PP}\) implies that every Dedekind-finite set is finite, although we should verify this in \(\axiom{Flow}\) as well. And in this case, the definition, at least for emergent/ZF-sets can be simplified to read that \(f\) is not equipotent with \(\sigma_f\).

Moving on, the next problem is in the discussion about cardinality. First and foremost, I am a firm believer that cardinality should be exclusively referring to ordinals or well-orderable sets. Especially since if seems that proper classes can be formalised here we can talk about cardinality being a proper class without any problems. So, \(|x|\) is the function \(1|_{f\equiv x}\), or maybe bind the quantifers to small functions if necessary.

But putting my preferences aside, Theorem 49 (and the subsequent Definition 23) have a mistake in the defining formula, which reads \(...\exists x(t[x]\Rightarrow...)\) where it should be reading \(...\exists x(t[x]\land...)\) instead. Theorem 50 claims that this formula defines only the ordinals, which is easily false, it's just the transitive and well-founded sets. The crux of the mistake is the second sentence in the proof of Theorem 50, which is a fine example of "wishful proving" (which I recognise so easily because I am guilty of that mistake much more often than I'd like to admit).

Next is Theorem 51 which says that if \(f\) is a ZF-set, and it happens to have a cardinality (i.e. it is well-orderable), then this cardinality is a ZF-set. The proof is given as a sketch, and seems to attempt to replicate the construction of the ordinals. This seems like an overcomplicated. By definition a cardinality is an ordinal, i.e. a point in the domain of \(\varpi\), which itself was a restriction of \(\fo\) to a formula defined on ZF-sets. In particular that means that every cardinality is a ZF-set by definition.

Okay. So with the discussion on the Grothendieck universes that we covered above, this completes this part. The next part is the dessert, the icing on the cake, the cherry on top of the whipped cream on top of the hot chocolate: the independence proof!

22 October, 2020

Okay. Finally. The reason we're here today. The Partition Principle. The authors suggest a certain non well-founded type of function which they call "hyperfunctions" that will be an infinite set that cannot be well-ordered. The idea, as translated to sets, is that this is a non-empty set \(x\) such that if \(y\in x\), then:

  1. \(y\cup\{y\}\in x\);
  2. \(y\cap x\neq\varnothing\); and
  3. for every \(z\subseteq y\), if \(z\neq\varnothing\), then \(z\in x\).

We now add an axiom stating that hyperfunctions exists, they are all emergent, and there is no common element to all hyperfunctions.

Let us set aside the obvious question (is this even consistent?) we start with the claim that any such hyperfunction is Dedekind-infinite, i.e. there is an injection from \(\omega\) into any hyperfunction. That's an easy exercise in the fact that a hyperfunction is not empty, and \(\axiom{Flow}\) proves that \(x\neq\sigma_x\) for "sets", i.e. \(x\cup\{x\}\neq x\), or \(x\notin x\).

The proof of Theorem 55, that \(\axiom{Flow}\) proves that no hyperfunction can be well-ordered, goes a little bit like this:

  1. Fix a hyperfunction \(\psi\), and suppose it could be well-ordered, then there is an injection to an ordinal \(o\).
  2. Start defining recursively surjections onto smaller ordinals, and use the "choice axiom" (see 17 Oct. part) to show that there is an injection which disagrees with previous choices. Use it to chose "yet another element".
  3. Rinse and repeat, and for some reason the induction has no halting condition.

This feels wrong for several reasons:

  1. Maybe a hyperfunction can be well-ordered by different means? For example, assume there is an infinite set of atoms and \(\AC\) holds, then there's no definition by transfinite recursion of an injection from the set of atoms to the ordinals, but such function still exists (if there was a definition, simply note that any permutation of the atoms is an automorphism of the universe).
  2. It seems that this proof really shows that a subset of an ordinal cannot be well-ordered, which raises questions for the suitability of \(\axiom{Flow}\) for dealing with well-ordered sets.
  3. It is actually not clear to me why the induction must fail. If the starting \(f\) was already a bijection, then in what sense we failed?

So it is very, very, unclear what's going on there. And this is just one more reason to try and figure out in what sense \(\axiom{Flow}\) can be interpreted from a "nice enough model of \(\ZF\)". Because then we can understand its relationship with the Axioms of Choice and Regularity, and we can try and create a model with such hyperfunctions with or without Choice.

The remark that follows seems also very suspicious that the same proof should work if we start with a set interpreting the real numbers. So in effect it would seem to me that any definition of a set that \(\ZF\) does not prove to be well-orderable cannot be proved to be well-orderable by recursive means. Which makes sense, but is not enough to prove that the real numbers cannot be well-ordered.

(There are also some significant typos in the proof of Theorem 55: defining \(f_1\) it should probably be \(h_0\) instead of \(f_0\) in the defining formula; the \(z_0,z_1\) in the part about \(f_\omega\) should probably be \(x_0\) and \(x_1\).)

It seems to me that ultimately the downfall of the authors here is the point of view that let them grasp \(\axiom{Flow}\) much better than what set theorists could. They view \(\axiom{Flow}\) as describing "a changing and expanding universe", whereas first-order logic (and really most of classical mathematics) explores what is seemingly a static universe where things are or aren't. And when you view things as static, you immediately understand that lack of description does not mean lack of existence; whereas a dynamic view of the universe is more amenable to the point of view that things that are not constructed may simply not exist.

In any case, this has been a very interesting journey. I will sum my thoughts in the next blog post after the weekend for a more coherent view on the paper, on \(\axiom{Flow}\), and on the Partition Principle.

There are no comments on this post.

Want to comment? Send me an email!