Two infinities that are surprisingly equal

It has been in the news recently — or rather, the small corner of the news that is of particular interest to mathematicians — that Maryanthe Malliaris and Saharon Shelah recently had an unexpected breakthrough when they stumbled on a proof that two infinities were equal that had been conjectured, and widely believed, to be distinct. Or rather, since both were strictly between the cardinality of the natural numbers and the cardinality of the reals, they were widely believed to be distinct in some models of set theory where the continuum hypothesis fails.

A couple of days ago, John Baez was sufficiently irritated by a Quanta article on this development that he wrote a post on Google Plus in which he did a much better job of explaining what was going on. As a result of reading that, and following and participating in the ensuing discussion, I have got interested in the problem. In particular, as a complete non-expert, I am struck that a problem that looks purely combinatorial (though infinitary) should, according to Quanta, have a solution that involves highly non-trivial arguments in proof theory and model theory. It makes me wonder, again as a complete non-expert so probably very naively, whether there is a simpler purely combinatorial argument that the set theorists missed because they believed too strongly that the two infinities were different.

I certainly haven’t found such an argument, but I thought it might be worth at least setting out the problem, in case it appeals to anyone, and giving a few preliminary thoughts about it. I’m not expecting much from this, but if there’s a small chance that it leads to a fruitful mathematical discussion, then it’s worth doing. As I said above, I am indebted to John Baez and to several commenters on his post for being able to write much of what I write in this post, as can easily be checked if you read that discussion as well.

A few definitions and a statement of the result

The problem concerns the structure you obtain when you take the power set of the natural numbers and quotient out by the relation “has a finite symmetric difference with”. That is, we regard two sets $A$ and $B$ as equivalent if you can turn $A$ into $B$ by removing finitely many elements and adding finitely many other elements.

It’s easy to check that this is an equivalence relation. We can also define a number of the usual set-theoretic operations. For example, writing $[A]$ for the equivalence class of $A$ , we can set $[A]\cap[B]$ to be $[A\cap B]$ , $[A]\cup [B]$ to be $[A\cup B]$ , $[A]^c$ to be $[A^c]$ , etc. It is easy to check that these operations are well-defined.

What about the subset relation? That too has an obvious definition. We don’t want to say that $[A]\subset[B]$ if $A\subset B$ , since that is not well-defined. However, we can define $A$ to be almost contained in $B$ if the set $A\setminus B$ is finite, and then say that $[A]\subset[B]$ if $A$ is almost contained in $B$ . This is well-defined and it’s also easy to check that it is true if and only if $[A]\cap[B]=[A]$ , which is the sort of thing we’d like to happen if our finite-fuzz set theory is to resemble normal set theory as closely as possible.

I will use a non-standard piece of terminology and refer to an equivalence class of sets as an f-set, the “f” standing for “finite” or “fuzzy” (though these fuzzy sets are not to be confused with the usual definition of fuzzy sets, which I don’t know and probably never will know). I’ll also say things like “is f-contained in” (which means the same as “is almost contained in” except that it refers to the f-sets rather than to representatives of their equivalence classes).

So far so good, but things start to get a bit less satisfactory when we consider infinite intersections and unions. How are we to define $\bigcap_{n=1}^\infty[A_n]$ , for example?

An obvious property we would like is that the intersection should be the largest f-set that is contained in all the $[A_n]$ . However, simple examples show that there doesn’t have to be a largest f-set contained in all the $[A_n]$ . Indeed, let $A_1\supset A_2\supset\dots$ be an infinite sequence of subsets of $\mathbb N$ such that $A_n\setminus A_{n+1}$ is infinite for every $n$ . Then $A$ is almost contained in every $A_n$ if and only if $A\setminus A_n$ is finite for every $n$ . Given any such set, we can find for each $n$ an element $b_n$ of $A_n\setminus A_{n+1}$ that is not contained in $A$ (since $A_n\setminus A_{n+1}$ is infinite but $A\setminus A_{n+1}$ is finite). Then the set $B=A\cup\{b_1,b_2,\dots\}$ is also almost contained in every $A_n$ , and $[A]$ is properly contained in $[B]$ (in the obvious sense).

OK, we don’t seem to have a satisfactory definition of infinite intersections, but we could at least hope for a satisfactory definition of “has an empty intersection”. And indeed, there is an obvious one. Given a collection of f-sets $[A_\gamma]$ , we say that its intersection is empty if the only f-set that is f-contained in every $[A_\gamma]$ is $[\emptyset]$ . (Note that $[\emptyset]$ is the equivalence class of the empty set, which consists of all finite subsets of $\mathbb N$ .) In terms of the sets rather than their equivalence classes, this is saying that there is no infinite set that is almost contained in every $A_\gamma$ .

An important concept that appears in many places in mathematics, but particularly in set theory, is the finite-intersection property. A collection $\mathcal A$ of subsets of a set $X$ is said to have this property if $A_1\cap\dots\cap A_n$ is non-empty whenever $A_1,\dots,A_n\in\mathcal A$ . This definition carries over to f-sets with no problem at all, since finite f-intersections were easy to define.

Let’s ask ourselves a little question here: can we find a collection of f-sets with the finite-intersection property but with an empty intersection? That is, no finite intersection is empty, but the intersection of all the f-sets is empty.

That should be pretty easy. For sets, there are very simple examples like $A_n=\{n,n+1,\dots\}$ — finitely many of those have a non-empty intersection, but there is no set that’s contained in all of them.

Unfortunately, all those sets are the same if we turn them into f-sets. But there is an obvious way of adjusting the example: we just take sets $A_1\supset A_2\supset\dots$ such that $A_n\setminus A_{n+1}$ is infinite for each $n$ and $\bigcap_{n=1}^\infty A_n=\emptyset$ . That ought to do the job once we turn each $A_n$ into its equivalence class $[A_n]$ .

Except that it doesn’t do the job. In fact, we’ve already observed that we can just pick a set $B=\{b_1,b_2,\dots\}$ with $b_n\in A_n\setminus A_{n+1}$ and then $[B]$ will be a non-empty f-intersection of the $A_n$ .

However, here’s an example that does work. We’ll take all f-sets $[A]$ such that $A$ has density 1. (This means that $n^{-1}|A\cap\{1,2,\dots,n\}|$ tends
to 1 as $n$ tends to infinity.) Since the intersection of any two sets of density 1 has density 1 (a simple exercise), this collection of f-sets has the finite-intersection property. I claim that any f-set contained in all these f-sets must be $[\emptyset]$ .

Indeed, let $B$ be an infinite set and $(b_1,b_2,\dots)$ the enumeration of its elements in increasing order. We can pick a subsequence $(c_1,c_2,\dots)$ such that $c_n\geq 2^n$ for every $n$ , and the corresponding subset $C$ is an infinite subset of $B$ with density zero. Therefore, $\mathbb N\setminus C$ is a set of density 1 that does not almost contain $B$ .

The number of f-sets we took there in order to achieve an f-empty intersection was huge: the cardinality of the continuum. (That’s another easy exercise.) Did we really need that many? This innocent question leads straight to a definition that is needed in order to understand what Malliaris and Shelah did.

Definition. The cardinal p is the smallest cardinality of a collection $F$ of f-sets such that $F$ has the finite-intersection property but also $F$ has an empty f-intersection.

It is simple to prove that this cardinal is uncountable, but it is also known not to be as big as the cardinality of the continuum (where again this means that there are models of set theory — necessarily ones where CH fails — for which it is strictly smaller). So it is a rather nice intermediate cardinal, which partially explains its interest to set theorists.

The cardinal p is one of the two infinities that Malliaris and Shelah proved were the same. The other one is closely related. Define a tower to be a collection of f-sets that does not contain $[\emptyset]$ and is totally ordered by inclusion. Note that a tower $T$ trivially satisfies the finite-intersection property: if $[A_1],\dots,[A_n]$ belong to $T$ , then the smallest of the f-sets $[A_i]$ is the f-intersection and it isn’t f-empty. So let’s make another definition.

Definition. The cardinal t is the smallest cardinality of a tower $T$ that has an empty f-intersection.

Since a tower has the finite-intersection property, we are asking for something strictly stronger before, so strictly harder to obtain. It follows that t is at least as large as p.

And now we have the obvious question: is the inequality strict? As I have said, it was widely believed that it was, and a big surprise when Malliaris and Shelah proved that the two infinities were in fact equal.

What does this actually say? It says that if you can find a bunch $F$ of f-sets with the finite-intersection property and an empty f-intersection, then you can find a totally ordered example $T$ that has at most the cardinality of $F$ .

Why is the problem hard?

I don’t have a sophisticated answer to this that would explain why it is hard to experts in set theory. I just want to think about why it might be hard to prove the statement using a naive approach.

An immediate indication that things might be difficult is that it isn’t terribly easy to give any example of a tower with an empty f-intersection, let alone one with small cardinality.

An indication of the problem we face was already present when I gave a failed attempt to construct a system of sets with the finite-intersection property and empty intersection. I took a nested sequence $[A_1]\supset[A_2]\supset$ such that the sets $A_n$ had empty intersection, but that didn’t work because I could pick an element from each $A_n\setminus A_{n+1}$ and put those together to make a non-empty f-intersection. (I’m using “f-intersection” to mean any f-set f-contained in all the given f-sets. In general, we can’t choose a largest one, so it’s far from unique. The usual terminology would be to say that if $A$ is almost contained in every set from a collection of sets, then $A$ is a pseudointersection of that collection. But I’m trying to express as much as possible in terms of f-sets.)

Anyone who is familiar with ordinal hierarchies will see that there is an obvious thing we could do here. We could start as above, and then when we find the annoying f-intersection we simply add it to the tower and call it $[A_\omega]$ . And then inside $[A_\omega]$ we can find another nested decreasing sequence of sets and call those $[A_{\omega+1}], [A_{\omega+2}],\dots$ and so on. Those will also have a non-empty f-intersection, which we could call $[A_{2\omega}]$ , and so on.

Let’s use this idea to prove that there do exist towers with empty f-intersections. I shall build a collection of non-empty f-sets $[A_\alpha]$ by transfinite induction. If I have already built $[A_\alpha]$ , I let $[A_{\alpha+1}]$ be any non-empty f-set that is strictly f-contained in $[A_\alpha]$ . That tells me how to build my sets at successor ordinals. If $\alpha$ is a limit ordinal, then I’ll take $A_\alpha$ to be a non-empty f-intersection of all the $[A_\beta]$ with $\beta<\alpha$ .

But how am I so sure that such an f-intersection exists? I’m not, but if it doesn’t exist, then I’m very happy, as that means that the f-sets $[A_\beta]$ with $\beta<\alpha$ form a tower with empty f-intersection.

Since all the f-sets in this tower are distinct, the process has to terminate at some point, and that implies that a tower with empty f-intersection must exist.

For a lot of ordinal constructions like this, one can show that the process terminates at the first uncountable ordinal, $\omega_1$ . To set theorists, this has extremely small cardinality — by definition, the smallest one after the cardinality of the natural numbers. In some models of set theory, there will be a dizzying array of cardinals between this and the cardinality of the continuum.

In our case it is not too hard to prove that the process doesn’t terminate before we get to the first uncountable ordinal. Indeed, if $\alpha$ is a countable limit ordinal, then we can take an increasing sequence of ordinals $\alpha_n$ that tend to $\alpha$ , pick an element $b_n$ from $A_{\alpha_n}\setminus A_{\alpha_{n+1}}$ , and define $A_\alpha$ to be $\{b_1,b_2,\dots\}$ .

However, there doesn’t seem to be any obvious argument to say that the f-sets $[A_\alpha]$ with $\alpha<\omega_1$ have an empty f-intersection, even if we make some effort to keep our sets small (for example, by defining $A_{\alpha+1}$ to consist of every other element of $A_\alpha$ ). In fact, we sort of know that there won’t be such an argument, because if there were, then it would show that there was a tower whose cardinality was that of the first uncountable ordinal. That would prove that t had this cardinality, and since p is uncountable (that is easy to check) we would immediately know that p and t were equal.

So that’s already an indication that something subtle is going on that you need to be a proper set theorist to understand properly.

But do we need to understand these funny cardinalities to solve the problem? We don’t need to know what they are — just to prove that they are the same. Perhaps that can still be done in a naive way.

So here’s a very naive idea. Let’s take a set $F$ of f-sets with the finite intersection property and empty f-intersection, and let’s try to build a tower $T$ with empty intersection using only sets from $F$ . This would certainly be sufficient for showing that $T$ has cardinality at most that of $F$ , and if $F$ has minimal cardinality it would show that p=t.

There’s almost no chance that this will work, but let’s at least see where it goes wrong, or runs into a brick wall.

At first things go swimmingly. Let $[A]\in F$ . Then there must exist an f-set $[A']'\in F$ that does not f-contain $[A]$ , since otherwise $[A]$ itself would be a non-empty f-intersection for $F$ . But then $[A]\cap [A']$ is a proper f-subset of $[A]$ , and by the finite-intersection property it is not f-empty.

By iterating this argument, we can therefore obtain a nested sequence $[A_1]\supset[A_2]\supset$ of f-sets in $F$ .

The next thing we’d like to do is create $[A_\omega]$ . And this, unsurprisingly, is where the brick wall is. Consider, for example, the case where $F$ consists of all sets of density 1. What if we stupidly chose $A_n$ in such a way that $\min A_n\geq 2^n$ for every $n$ ? Then our diagonal procedure — picking an element from each set $A_n\setminus A_{n+1}$ — would yield a set of density zero. Of course, we could go for a different diagonal procedure. We would need to prove that for this particular $F$ and any nested sequence we can always find an f-intersection that belongs to $F$ . That’s equivalent to saying that for any sequence $A_1\supset A_2\supset$ of dense sets we can find a set $A$ such that $A\setminus A_n$ is finite for every $n$ and $A$ has density 1.

That’s a fairly simple (but not trivial) exercise I think, but when I tried to write a proof straight down I failed — it’s more like a pen-and-paper job until you get the construction right. But here’s the real question I’d like to know the answer to right at this moment. It splits into two questions actually.

Question 1. Let $F$ be a collection of f-sets with the finite-intersection property and no non-empty f-intersection. Let $[A_1]\supset[A_2]\supset\dots$ be a nested sequence of elements of $F$ . Must this sequence have an f-intersection that belongs to $F$ ?

Question 2. If, as seems likely, the answer to Question 1 is no, must it at least be the case that there exists a nested sequence in $F$ with an f-intersection that also belongs to $F$ ?

If the answer to Question 2 turned out to be yes, it would naturally lead to the following further question.

Question 3. If the answer to Question 2 is yes, then how far can we go with it? For example, must $F$ contain a nested transfinite sequence of uncountable length?

Unfortunately, even a positive answer to Question 3 would not be enough for us, for reasons I’ve already given. It might be the case that we can indeed build nice big towers in $F$ , but that the arguments stop working once we reach the first uncountable ordinal. Indeed, it might well be known that there are sets $F$ with the finite-intersection property and no non-empty f-intersection that do not contain towers that are bigger than this. If that’s the case, it would give at least one serious reason for the problem being hard. It would tell us that we can’t prove the equality by just finding a suitable tower inside $F$ : instead, we’d need to do something more indirect, constructing a tower $T$ and some non-obvious injection from $T$ to $F$ . (It would be non-obvious because it would not preserve the subset relation.)

Another way the problem might be difficult is if $F$ does contain a tower with no non-empty f-intersection, but we can’t extend an arbitrary tower in $F$ to a tower with this property. Perhaps if we started off building our tower the wrong way, it would lead us down a path that had a dead end long before the tower was big enough, even though good paths and good towers did exist.

But these are just pure speculations on my part. I’m sure the answers to many of my questions are known. If so, I’ll be interested to hear about it, and to understand better why Malliaris and Shelah had to use big tools and a much less obvious argument than the kind of thing I was trying to do above.

This entry was posted on September 19, 2017 at 10:29 am and is filed under News. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

101 Responses to “Two infinities that are surprisingly equal”

David Roberts Says:
September 19, 2017 at 12:16 pm | Reply
A trivial observation : you might not be able to engineer an injection, but perhaps a subquotient.
- gowers Says:
  September 19, 2017 at 1:32 pm
  Just to check I understand this, is the idea you are suggesting that we could define an equivalence relation on $F$ , an order relation on the equivalence classes, and an order-preserving injection from $T$ to the quotient?
- David Roberts Says:
  September 19, 2017 at 8:42 pm
  Correct, though one might additionally start by throwing away some elements of F, so the equivalence relation is only on a subset.
gowers Says:
September 19, 2017 at 9:54 pm | Reply
A further observation is that if $F$ is a non-principal ultrafilter (or more precisely, the set of equivalence classes of sets that belong to a non-principal ultrafilter $\mathcal U$ ), then $F$ has cardinality equal to that of the continuum (since for each f-set, either it or its f-complement belongs to $F$ ). And given any infinite set $X$ , it can’t be contained in all sets in $F$ , since then it would have to belong to $F$ itself, and if we were then to split it into two infinite parts, one of those parts would have to belong to $F$ and would not f-contain $X$ . So that gives another example. Does a non-principal ultrafilter contain a tower with no non-empty f-intersection?
Nick Soapdish Says:
September 20, 2017 at 5:05 am | Reply
This seems relevant:

Click to access tesi-moranarocca.pdf
- gowers Says:
  September 20, 2017 at 7:16 am
  Thanks very much for that reference! It contains a four-page proof of the theorem, but that four-page proof, if written out in full, together with non-trivial results that it assumes, would expand a lot I think. It also requires a lot of advanced set-theoretic concepts. But even for the non-expert it looks like a good place to look to try to get some sort of inkling of what is going on.
Greg Stanton Says:
September 20, 2017 at 7:45 am | Reply
Perhaps this note by D.H. Fremlin might be relevant:

Click to access n14528.pdf
- gowers Says:
  September 20, 2017 at 9:10 am
  That too gives a good impression of what the argument is like, even if I understand almost none of it.
  
  I’m still interested in the following statement, which is much stronger than the assertion that p=t.
  
  Statement. Let $F$ be a family of f-sets with the finite intersection property and empty f-intersection. Then $F$ contains a totally ordered subset $T$ with empty f-intersection.
  
  Is that statement known to be false? Can anyone find the answer to that question in one of the two references above (or some other reference)? If it’s false, then I’ll be much more convinced of the difficulty of the problem. (That’s not to say that I’m sceptical — just that I don’t have even a rough understanding of the difficulty at the moment.)
Daniel Soukup Says:
September 20, 2017 at 10:13 am | Reply
I think the Statement is false: you can find a family of f-sets with the finite intersection property (fip) without f-intersection so that no two distinct elements are contained in one another (so any totally ordered subfamily is a singleton which do have an f-intersection).

To do this, we take a family of f-sets $F$ which has properties (1)-(3) below and is maximal:
(1) $F$ has the fip,
(2) $F^c$ (the family of complements) has the fip, and
(3) if $a\neq b\in F$ then $a\not\subset b$ .
This is possible by Zorn’s lemma. Note that (3) holds for $F^c$ too.

If either $F$ or $F^c$ has no f-intersection then we are done.

Otherwise, we reach a contradiction: let $X$ be an f-intersection for $F$ , and $Y$ be an f-intersection for $F^c$ . Take pairwise disjoint infinite sets $X_0,X_1\subset X$ and $Y_0,Y_1\subset Y$ (all four are disjoint). We let $Z=X_0\cup Y_0$ .
Then Z is not in $F$ (otherwise $Y_0\subseteq Y$ is almost contained in the complement of $Z$ ).
We would like to show that $F^*=F\cup\{Z\}$ still satisfies (1)-(3) which contradicts the maximality of $F$ . (1) holds because $X_0$ will be almost contained in any finite intersection of $F^*$ . (2) holds because $Y_1$ will be almost contained in any finite intersection of $(F^*)^c$ .
Finally $Y_0\subset Z$ shows that $Z$ is not in any $A\in F$ , and $X_1\subset A$ shows that $A\not \subset Z$ for $A\in F$ .
- gowers Says:
  September 20, 2017 at 10:53 am
  Nice! It actually makes me realize that I had managed to confuse myself about something. I had been accidentally understanding “has the finite intersection property” to mean “is closed under finite intersections”, in which case obviously there must be infinite totally ordered subsets, even though that isn’t the definition I gave in the post above.
  
  However, given a set $F$ with the finite intersection property, we can create a set $F'$ that is closed under finite intersections by simply taking all finite intersections of sets in $F$ . Provided $F$ is infinite (as it is in the case of interest), $F'$ will have the same cardinality as $F$ , so for the problem we are free to assume that $F'$ is closed under finite intersections.
  
  It feels to me as though the biggest totally ordered subset of $F'$ shouldn’t be that much bigger than the biggest totally ordered subset of $F$ , so if $F$ is the set you build above, I’d be surprised if $F'$ could have an uncountable totally ordered subset.
  
  But right now I don’t see a proof. So let me ask, therefore, whether if $F$ is closed under finite f-intersections and has empty f-intersection, it must have a totally ordered subset of the same cardinality. (I expect the answer no.)
- gowers Says:
  September 20, 2017 at 12:24 pm
  I want to think a little about the consequences of maximality for your set $F$ . So let’s think what it says if we can’t add a set $X$ . I think one of the following things must go wrong.
  
  (i) $X$ is f-contained in a set that belongs to $F$ .
  
  (ii) $X$ f-contains a set that belongs to $F$ .
  
  (iii) There is a finite f-intersection of sets in $F$ that has empty f-intersection with $X$ .
  
  (iv) There is a finite f-intersection of sets in $F^c$ that f-contains $X^c$ .
  
  Note that (iv) is equivalent to the assertion that there is a finite f-union of sets in $F$ that is contained in $X$ . But this implies (ii), so I think we don’t have to worry about it.
  
  Now let’s suppose I’ve found a nested sequence $A_1\supset A_2\supset\dots$ of f-sets in $F'$ — that is, of finite f-intersections of sets in $F$ . This sequence has an f-intersection $X$ . Since $X$ is f-contained in $A_1$ , which is a finite f-intersection of sets in $F$ , we know that $X$ violates (i) and therefore cannot belong to $F$ . But could it be a finite intersection of sets in $F$ ?
  
  The answer would be yes if we can find two disjoint subsets $B$ and $C$ of $A_1^c$ such that neither $X\cup B$ nor $X\cup C$ violates (i), (ii) or (iii).
  
  I don’t see my way through to the end here, but it seems at least possible that there may be an argument of this style to show that a countable nested sequence in $F'$ has a non-empty f-intersection that also belongs to $F'$ (when $F$ is the set you constructed).
Daniel Soukup Says:
September 20, 2017 at 1:51 pm | Reply
I am not sure about my example there, but here is a way of finding a set $F$ with the fip, without f-intersection, such that the set of finite intersections $F'$ has no decreasing chains of type $\omega+1$ .

We say that $F$ is independent if for any disjoint finite subfamilies $G,H\subset F$ the set $\cap G\setminus \cup H$ is infinite. This is obviously much stronger than the fip.
It can be shown that there are independent families of even size continuum (this is classically done by using that the Tychonoff cube $2^{2^{\aleph_0}}$ is separable). Now there is also a trick to find an independent family with no f-intersection (see Proposition I.1 here).

So let $F$ be an independent family with no f-intersection; we claim that $F'$ has no decreasing chains of type $\omega+1$ . The single observation we need is that if $F_0,F_1\subset F$ are finite then $\cap F_0\subset \cap F_1$ if and only if $F_1\subset F_0$ . Indeed, if $B\in F_1\setminus F_0$ then $B^c\cap \bigcap F_0$ is an infinite set contained in $\cap F_0$ but disjoint from $\cap F_1$ . Now, if $A_0=\cap F_0\supset A_1=\cap F_1\supset \dots$ then the finite sets $F_n$ are strictly increasing and if $\cap F_\omega\subset A_n$ for all $n$ (for some $F_\omega \subset F$ ) then $F_n\subset F$ which forces $F_\omega$ to be infinite.

On a side note, the smallest independent family with no f-intersection has size $\mathfrak p$ too (see the above link).
- gowers Says:
  September 20, 2017 at 2:51 pm
  Thank you very much for these insights, which do go a long way towards explaining why the problem is hard. It seems that if one wanted an elementary proof, one would have to find an extremely non-obvious way of using $F$ to build a tower $T$ .
- gowers Says:
  September 20, 2017 at 3:03 pm
  I’ve just understood the significance of your side note. I started to wonder whether one could hope to find $T$ inside $F$ at least in the case where $F$ has minimal cardinality, but what you say implies that this too is not in general possible.
jean-camille Says:
September 20, 2017 at 5:13 pm | Reply
Let us take $\ll$ to be a total order such that $[A]\subset_f [B]\Rightarrow [A]\ll [B]$ (it’s always possible with axioms weaker than Choice). We note by $]0,[X]]_{\ll}$ all the minorants of $[X]$ for the $\ll$ relation, and we denote by $C$ from $\mathcal F$ to $\mathcal P(\mathbb N)$ a choice function : Let’s call $F$ the image by $C$ of $\mathcal F$ . It is a set with the same cardinality as $\mathcal F$ , obtained by picking a representative in each class of $\mathcal F$ . For any $A\in \mathcal F$ , let’s set $T(A)=\bigcup C[0,[A]]_{\ll}$ . Then it is obvious that $T=\left\{[T(A)], A\in \mathcal F\right\}$ has the intersection property and the same cardinality as $\mathcal F$ . It is also a tower, and the only thing we have to check is that no infinite set is in all the members of $T$ . Am I right? or did I misunderstand something? (because I think $T$ does the job, and this seems too simple…)
jean-camille Says:
September 20, 2017 at 5:30 pm | Reply
Oh I understand my mistake : maybe the $T$ I made is very small… But isn’t there a way to make it as big as $\mathcal F$ anyway? I repeat the general idea : don’t pick elements in $\mathcal F$ but build $T$ with unions of representatives of sets in $\mathcal F$ .
- gowers Says:
  September 20, 2017 at 8:34 pm
  I’ve substantially edited your comments above, so please let me know if I’ve made any mistakes. I’m intrigued by them, but I’m not sure I completely follow them yet. But let me try.
  
  We start with a set $\mathcal F$ that has the finite-intersection property and no non-empty f-intersection. This has a partial order, which we extend to a total order $\ll$ . Then for each element $A\in\mathcal F$ we let $(0,A]$ denote the set of all $B\in\mathcal F$ such that $B\ll A$ . (This isn’t precisely your notation, but I think it should be OK. For me $\mathcal F$ consists of f-sets — that is sets up to finite symmetric differences.)
  
  If I understand you, $C$ chooses for each f-set some representative set. I was going to suggest that this was unnecessary, but I now see that you are going to take infinite unions, so maybe it makes a difference after all. It means that $T(A)$ is equal to the union of all $C(B)$ such that $B\ll A$ . That is, you take all f-sets that precede $A$ in the $\ll$ order and take the union of their representatives.
  
  It’s clear that the sets $T(A)$ form a tower. It’s not clear to me that if $A\ll A'$ then $T(A)$ and $T(A')$ are distinct. In fact, it isn’t obvious to me that the sets couldn’t all be equal to $\mathbb N$ .
  
  But as you suggest, the general idea might have a chance, since we have a lot of freedom to choose the total order $\ll$ . A natural special case to look at is Daniel Soukup’s first example, where no set in $\mathcal F$ is f-contained in any other set in $\mathcal F$ . Then all total orderings on $F$ extend the initial trivial ordering, so basically we’d be looking for some ordering, and some choice of representatives, that worked.
- jean-camille Says:
  September 30, 2017 at 8:09 pm
  Let’s call $\mathbf{R}=\left\{[A], subset \mathbb{N}\right\}$ For any $A\subset \mathbf{R}$ we define $\mathbf{R}_A=\left\{G\in \mathbf{R},\,G\subset_f A\right\}$ . And we will say $\mathcal F\subset \mathbf{R}$ is a “good part” if we have $\mathcal F=\mathbf{R}_A$ for some $A\in \mathbf{R}_A$ .
  
  Let’s now consider $\mathit G=\left\{[\mathbb{N}\setminus A],[A]\in \mathit F\right\}$ the set of complement of $\mathit F$ whom have the fip and no-nom-empty pseudo-interscetion(then $\mathit G$ has the fup and the no-non-full pseudo-union). Then it’s easy to see that $\mathbf{R}(\mathit{G})=\left\{\mathbf{R}_A,\, A\in \mathit{G}\right\}$ is closed under finite intersection, (resp finie union) if and only if $\mathit G$ is closed under finite f-intersection (resp.finite f-union). Now I want to consider general intersection in $\mathbf{R}(\mathit{G})$ , it is not a problem because we deal with “usual sets” , the problem then could be that the sets we get are not “good parts”, but I thing the set we would get is a set of the form $i(\mathcal G)$ like we saw in another comment and that you commented to and noticed that $i(i(\mathcal G))$ was actually empty.
  
  I would like to do the kind of thing I tried to do in the comment above, and in order to build a correct extended total order I will have to extend $\mathit G$ as well, hoping the cardinality of this extension dont get bigger then that of $\mathit{G}$
  
  We now say $R=\mathbf{R}(\mathit{G})$ , because it is shorter, we define for any $F\in \mathbf{R}$ , $R_F=\left\{S_G\in R,\,F\subset_f G\right\}= \mathbf {R}_F\cap R$ , we call it the “$F$-row” and we say that $R^F=\bigcap R_F$ is the $R$-orthogonal of $F$. We will now assume that the orthogonal of each row is in $R$ , you might say that it makes $R$ very big, but (I think…) it won’t make it bigger than $\mathit F$ (I will say later why I claim that the quotient of $\mathbf{R}$ under the relation “having the same R-orthogonal” has actually the same cardinality then that of $\mathit{R}$ if it is closed under “orthogonality”)
  
  The thing that I’m not so sure yet, is that the total order $<<$ that would extend the partial order in $R$ is such that $(0,A]_{<<}$ are good parts… It think would give us a fine tower…
  
  I will develop in next post the precise statement about this "orthogonality", in a more precise way. After that, we will be able to do a better examination of $<<$ , but yet, it would be very heavy… (because I would like to consider an orthogonality for elements of $R$ such as the orthogonal of the orthogonal is an involution, and it will be better for a quick understanding to define it in a general context)
  
  I apology if the way to present this is a bit heavy compare to the notions that I'm talking about, and I hope that my explanations are not so bad that one can't understand it easily, if it is not the case, I think it will be better if I present this "orthogonality" in a general context.
- jean-camille Says:
  September 30, 2017 at 8:17 pm
  Sorry the first line contains notation mistakes!! It should be :
  
  Let’s call $\mathbf{R}=\left\{[A], subset \mathbb{N}\right\}$ For any $A\in \mathbf{R}$ we define $\mathbf{R}_A=\left\{G\in \mathbf{R},\,G\subset_f A\right\}$ . And we will say $\mathcal F\subset \mathbf{R}$ is a “good part” if we have $\mathcal F=\mathbf{R}_A$ for some $A\in \mathbf{R}$
- jean-camille Says:
  September 30, 2017 at 8:21 pm
  Sorry again….
  Let’s call $\mathbf{R}=\left\{[A], A\subset \mathbb{N}\right\}$ .
  
  For any $A\in \mathbf{R}$ we define $\mathbf{R}_A=\left\{G\in \mathbf{R},\,G\subset_f A\right\}$ . And we will say $\mathcal F\subset \mathbf{R}$ is a “good part” if we have $\mathcal F=\mathbf{R}_A$ for some $A\in \mathbf{R}$
- jean-camille Says:
  September 30, 2017 at 8:30 pm
  another mistake is that $R_F$ is NOT $\mathit{R}_F\cap R$…the definition that hold is then the left member…
  
  I’m going to write the whole comment better…maybe longer but better…I’m tired to say I’m “sorry” but I have to, once again!
jean-camille Says:
September 20, 2017 at 5:39 pm | Reply
(when I say very small I meen finite cardinal)
John Says:
September 20, 2017 at 11:26 pm | Reply
Almost certainly there are short direct proofs of the equality. But I’m not sure what is to be gained from it. The model-theoretic machinery Malliaris and Shelah developed is obviously complex and can seem too intricate for any specific problem encountered, but from what I understand it has already produced several important results. They also have a proof improving Szemeredi’s regularity lemma using model theory:

http://www.ams.org/journals/tran/2014-366-03/S0002-9947-2013-05820-5/home.html
- gowers Says:
  September 21, 2017 at 9:13 am
  Different mathematicians have very different instincts about this, and I don’t think one can say that one instinct is right and the other wrong. For some people, the ideal is something like what Grothendieck was famous for — developing more and more theory until previously hard-looking statements become trivial. Others feel that they understand a result much better if they have a short direct proof.
  
  I’m in the latter camp, though I don’t take it to extremes. For example, I completely understand that in algebraic topology, if you develop the basics of homology theory and use those to prove results like the Brouwer fixed-point theorem and the Borsuk-Ulam theorem, you are saving yourself from having to repeat a lot of steps that you need to provide if you give direct proofs of all the things you can do using homology. But quite a lot of my research has been aimed at removing machinery — for example, I have been involved in finding more direct (and quantitative) proofs of results that were obtained using ergodic theory, and I think that has led to genuine gains in understanding.
  
  Incidentally, it’s a slight oversimplification to say that Malliaris and Shelah improved Szeméredi’s regularity lemma. What they did was to improve the bounds significantly if you add a rather strong hypothesis about the graph. My instinct for this result too is to try to find a more elementary proof. The reason is that I find myself asking, “What is this model theory actually doing that makes the proof come out at the end?” And for me, the ideal answer would be something like, “Here’s a direct proof. Now the model theory wraps up these steps into a convenient form and allows one to prove similar results without laboriously writing out similar steps for each one.” Though I suppose I’d be even happier with a direct proof that was clearer and more transparent than the model-theoretic one rather than being essentially the same argument written out at greater length.
jean-camille Says:
September 21, 2017 at 1:13 am | Reply
Yes, that is exactly what I mean! Thank you for the editing operation, and for the clear and nice way to say it!
If I understand notation $\mathcal F= C(\mathit F)$ for some choice fonction $C$ where $\mathit F$ is the Daniel Soukup equivalent special case. The “worse thing” that could happen in order to use the “general idea “(of the upper post) is that, for all $(F,G)\in \mathcal F^^2$, $F\cup G\in [\mathbb N]$. And the “best case” we can have, is that there is infinitly many distinct $[F\cup G]$ . That give me an idee, to considere not only $\mathcal F’$, the finite intersection closure of $\mathcal F$, but also $\mathcal F”$ the closure of $\mathcal F’$ under general union! We have $\bigcap \mathcal F”\in [\emptyset]$, and also $\mathcal F”$ has the intersection property (any two member have an infinite intersection). The only thing that we have to be sure, is that $[\mathcal F”]=\mathit F”:=\left\{[X], \, X\in \mathcal F”\right\}$ and $\mathit F$ have the same cardinality… But if it has not, we are in the “best case” ! So we can assume that $\mathcal F”$ is the set of the open sets of a topological space. We could then try to study the compacity of $\mathbb N\in \mathcal F”$.
jean-camille Says:
September 21, 2017 at 2:19 am | Reply
Unfortunatly we cannot ask right now that $\mathcal F”$ has the same cardinality than $\mathit F”$, that is why we cannot avoid*** the $f$-set version… But I think we can assume that $\mathcal F”_0=:\left\{U\in \mathcal F”,\, [\emptyset,\mathbb N\setminus U]=\emptyset \right\}$ the set of open sets in $\mathcal F”$ that are not $\mathcal F”$-dense in $\mathbb N$ is smaller then $\mathit F$. I don’t know if it will help but, I find this “topological equivalent case” at least funny, and I hope that I’m not mistaking some where when I say that we can reduce the study to this special case, in order to proof that $|\mathit T|=|\mathit F|$

***I’m not triying to say that we shoud get rid of $f$-set formulation, but just that it would be nice if we study statement that are not “so much more easy” to say with $f$-set than without… the $f$-statement would then be an elegant translation of an equivalent usual-set statement. If we need $f$-formulation for more than elenace and nice notations, that we might give the “indication” that we are deviating from the elementary proof goal.
jean-camille Says:
September 21, 2017 at 11:48 am | Reply
I’m sorry, I’m not sure what I wrote is correct, so let’s say again the “idea” : maybe we can assume that the set of representative elements of $\mathit F$ is closed not only under finite interection, but also under general union in order to study compacity. I apologie if what I said before is not correct (I think it’s correct for finite union, but I this was alredy kind of obvious)
jean-camille Says:
September 21, 2017 at 2:25 pm | Reply
Ok I feel sorry to write with bad english so much fuzzy information, so please feel free to delete my three previous posts and this very first sentence, I am going to try to be clear and precise now :

I think the general idea of my first post probably doesn’t work. Here’s why, according to me :

Let’s have $\mathit G\subset \mathit F$ with $\mathit G=([G_i])_{i\in \mathbb N}$ . Then any sequence $S_{i+1}=S_i\cup G_i$ would be such as $\left\{[S_i],\, i\in \mathbb N\right\}$ is a finite set. If it was infinite we would be able to chose $S'_i\in [S_i]$ for all $i\in \mathbb N$ such as $S'_i\subset S'_{i+1}$ with $S'_{i+1}\setminus S'_i$ infinite, we would then have $(S'_{i+1}\setminus S'_0)\setminus (S'_i\setminus S'_0)$ also infinite, and $\left\{[S'_i-S'_0],, \, i\in \mathbb N\right\}$ would be a countable tower, and this is not possible, as you said it in the article.

So the general first idea may go nowhere, as soon as this leads to the fact that the $\mathit T$ that I built in the first post is a finite set. But maybe the general following next idea can help, somehow… : it’s not an proper advance, but just a remark : I think we can build a topological space, with same $f$ -cardinality than $\mathit F$
(let’s say $\mathcal A\subset \mathcal P(\mathbb N)$ , and $\mathcal B\subset\mathcal P(\mathbb N)$ have the same f-cardinality if $\left\{[A],\, A\in \mathcal A\right\}$ and $\left\{[B],\, B\in \mathcal B\right\}$ have the same cardinality).

Indeed, if $\mathcal F'$ is a set of representative elements of $\mathit F'$ , where $\mathit F'$ is closed under finite intersection, then $\mathcal F''$ , the general union closure of $\mathcal F'$ is a topological space. Of course we cannot say (yet?) that $\mathcal F''$ and $\mathcal F'$ have the same cardinality, but I think , that we can deduce from what I just said previously in this post, that $\mathcal F''$ and $\mathcal F'$ have the same f-cardinality.( I hope this is not a irrelevant triviallity, or even some wrong statement!)
jean-camille Says:
September 21, 2017 at 5:12 pm | Reply
(I forget to precise in the previous post that, $\mathit F$ has the Daniel Soukup hypothesis : no f-inclusion beetwin any two membres)
jean-camille Says:
September 21, 2017 at 8:04 pm | Reply
I think I’ve got it !
Let’s define for any $A\subset \mathbb{N}$ , $f_A\in A^{\mathbb{N}}$ the only increasing function from $\mathbb{N}$ to $A$ . And let’s define the convolution of $A$ and $B\subset \mathbb{N}$ as $A*B:=f_A(B)$ . We now build a transfinite sequence of convolutions between repesentative elements in $\mathit{F}$ (we take $\mathit{F}$ well-ordered by $<_{F}$ , and we build $\mathcal {G}\subset \mathcal{P}(\mathbb{N})$ whose elements are indexed by $\mathit{F}$ , in this way : $G_{s(A)}=s(A)*G_A$ , where $s(A)$ is the smaller element of the set of $<_F$ – majorant of $A$ , and then $\mathit{G}=\left\{[G],\,G\in \mathcal{G}\right\}$ should be our tower… )
- gowers Says:
  September 21, 2017 at 9:03 pm
  I like the idea of using these “convolutions”. Let me try to repeat the argument in my own words, just to make sure I understand it. I think it is incomplete, but that doesn’t mean the idea can’t work.
  
  Given two sets $A=\{a_1,a_2,\dots\}$ and $B=\{b_1,b_2,\dots\}$ , with their elements written in increasing order, we are defining $A*B$ to be the set $\{a_{b_1},a_{b_2},\dots\}$ . Note that this is a subset of $A$ .
  
  Now we take a collection of sets $F$ that has the finite intersection property and no pseudointersection. We well-order it somehow, and write $<_F$ for the well-ordering. And now we want to create a tower of cardinality at most that of $F$ and argue that it too has no pseudointersection.
  
  For each ordinal $\alpha$ that is smaller than the order type of $(F,<_F)$ , let $X_\alpha$ be the corresponding set in $F$ . We shall inductively define sets $Y_\alpha$ as follows. (They are to form the tower.)
  
  We start by setting $Y_0$ to be $X_0$ . If we have already defined $Y_\alpha$ , then $Y_{\alpha+1}=Y_\alpha*X_{\alpha+1}$ . (I think you meant $G_A*s(A)$ in your comment above, but that’s a small detail.)
  
  What I don’t see in your comment is a definition of $Y_\alpha$ when $\alpha$ is a limit ordinal. But here’s an idea. Suppose that $\alpha$ is a limit ordinal and the collection of sets $\{Y_\beta:\beta<\alpha\}$ has a pseudointersection. Then let $Y_\alpha$ be such a pseudointersection. If the collection of sets does not have a pseudointersection, then we are done.
  
  The final step in this argument would need to be to prove that the tower created does not have a pseudointersection. I’m not sure I see why this has to be the case.
jean-camille Says:
September 22, 2017 at 7:08 am | Reply
Thank you for the correction and precise and very nice way to answer, it is a great luck for week reeders like me to be able to learn and understand not only exciting maths but also nice way to talk about them!

There is two reason why I thought “I’ve got it”

1) First one is that I thought that for each $X_{\alpha}\in \mathit{F}$ we have $Y_{\alpha}\in \mathit T$ such that, by construction, $Y_{\alpha}\subset X_{\alpha}$ . Thus, if some $[C]$ is f-contained in every $Y$ , it seems to give a contradiction.
Isn’t it possible to take every member of $\mathit{F}$ into the *-machine? I mean If the “no non empty pseudo-intersection” is not already satisfied? (please forgive the fuzzy statement here! I never did any transfinite proof, and I naîvely thought it shouldn’t be a problem.)

2) Second and (seriously wrong) reason : I translated the problem in terme of usual sets, and made the self-statement that we don’t need a (usual set) tower which is not constant by some rank, to have an empty intersection , as soon as we can remove the whole intersection from each member of the tower. .But my usual-set translation is certainly very wrong, because I could deduce from it that $\mathcal{t}$ is …countable**!

**Actually I’m not confortable with this example of “Eratosthene” tower, that seems to have the fip and the “no non empty f-intersection” property, and is clearly countable :
$C_i=\mathbb{N}\setminus (2\mathbb{N} \cup 3\mathbb{N} \cup...p_i\mathbb{N})$ , where $p_i$ is the $i$ -th prime number.
I cannot imagine any proper f-set that is f-contained in every $[C_i]$ anyway!
So… I’m afraid that I do a very serious confusion by now… but wait a minute, I think the set of prime numbers does the job! I feel better!
- gowers Says:
  September 22, 2017 at 8:15 am
  I think your first reason is wrong. $A*B$ is contained in $A$ , but it is not necessarily contained in $B$ . This is important, because when we build $Y_{\alpha+1}$ we need it to be an f-subset of $Y_\alpha$ , so that we will have a tower, so I don’t see how we can use the convolution operation to ensure also that it is a subset of $X_{\alpha+1}$ .
  
  Also, I think limit ordinals do create problems. Suppose, for example, that you have created $Y_1,Y_2,\dots$ . How do you propose to create $Y_\omega$ using the set $X_\omega$ ?
  
  Maybe there is an idea for doing this actually. At each limit ordinal you do what I suggested and take an f-intersection. And at each successor ordinal $Y_{\alpha+1}$ you don’t take $X_{\alpha+1}$ but rather you take the first $X_\beta$ that you have not yet used. In that way it will indeed be guaranteed that every set in $F$ takes part in one of the convolutions. But the first problem remains, I think.
- jean-camille Says:
  September 22, 2017 at 12:05 pm
  I answer to the first answer because I still thing that it works. So there were two problems : the first is that $A*B$ is not included in $A$ and the second is that we have to work a little bit to take all the people in $F$ that we did not take, in a continuation of our transfinite operation : if we include in these people, the “$B$” of first problem that we didn’t take, and as second problem seems to be solved, I think we have it…
  
  An other way to solve the first problem could be to take $G’:= B*A*B\subset A\cap B$.
  Am I too optimistic?
- jean-camille Says:
  September 22, 2017 at 12:26 pm
  (I wrote “I answer to the first answer” but this sentence is useless and might be confusing, so let me explain the context of it : I was scared that what I was going to post might not follow directly the very comment that I was answering too, but would be “isolated” in te main discution, I hope this very edditing post won’t add some more confusion!
  )
- gowers Says:
  September 22, 2017 at 12:12 pm
  I don’t think the second problem is a problem, but I do think the first one is. Your suggestion doesn’t work, because it isn’t necessarily true that $B*A*B$ is contained in $A$ .
- jean-camille Says:
  September 22, 2017 at 1:42 pm
  Oh what a ridiculous mistake!!
- jean-camille Says:
  September 22, 2017 at 2:11 pm
  Maybe we can consider a transfinite sequence of towers with “decreasing” pseudo-intersection (I put quotations mark to mean that I don’t plan to define it properly, but it could also be intersting to do it anyway, in order to solve the problem)
  
  For example we can build $\mathit{T_{\alpha+1}}=X*\mathit{T_{\alpha+1}}$ for some $X\in \mathit F$ , It seems that we are doing “nothing more” here, but maybe a similar idea would work…
gowers Says:
September 22, 2017 at 10:57 am | Reply
Here is another way that one might try to prove the result. I am thinking as I write, so this comment will probably be fairly short and end in failure.

As with jean-camille’s proof attempt, we begin by arbitrarily well-ordering $F$ . Now let us attempt to build a tower $T$ inductively. However, this time, instead of trying to use sets from $F$ , we will make the following weaker promise: that for every set in $F$ there will be a set in $T$ that is f-contained in it. This will ensure that any f-intersection of $T$ is also an f-intersection of $F$ , since $T$ is a tower.

How might this inductive construction go? Let the enumeration of the f-sets in $F$ be $(X_\alpha)$ , where $\alpha$ ranges over the ordinals belonging to the order type of the well-ordering of $F$ . I now want to built a tower $T=(Y_\alpha)$ . I’ll actually make the more specific promise that $Y_\alpha$ will always be f-contained in $X_\alpha$ .

To start with it’s fine: we take $Y_0=X_0, Y_1=X_0\cap X_1, Y_2= X_0\cap X_1\cap X_2$ , and so on. All these are infinite, by the finite intersection property of $F$ . I don’t actually care whether they are distinct: if they aren’t, that makes my tower $T$ smaller, and that’s only good for me.

But then we need to create $Y_\omega$ . There isn’t an obvious way to do that, so what I’ll do instead is find an f-intersection $Y_\omega'$ of the sets $Y_0,Y_1,\dots$ . (If I can’t find one, then I’m done, since it means I’ve got a countable tower with no f-intersection. Of course, that can’t exist, so this case won’t in fact arise until the tower is of size at least p.) Having found $Y_\omega'$ , I will let $Y_\omega=Y_\omega'\cap X_\omega$ .

But it’s not clear that that works. In fact, in general there is no reason at all for it to work: I might accidentally choose an f-intersection that is disjoint from $X_\omega$ .

I think what I need in order to let the proof continue is something that feels hard to achieve: a set $Y_\omega$ with the following two properties.

(i) $Y_\omega$ is an f-intersection of the sets $Y_1,Y_2,\dots$ .

(ii) The set $\{X\cap Y_\omega:X\in F\}$ still has the finite-intersection property.

I don’t see why such a set has to exist, but it also appears to be a necessary condition for this approach to work.
- jean-camille Says:
  September 26, 2017 at 9:19 am
  A)Maybe we could make (i) and (ii) work with other hypotheses on $\mathit F$
  For example let’s ask that if we have $\mathit{G}\subset \mathit{F}$ such that $\mathit{G}$ has an non empty f-intersection, then the f-union of $\mathit{F}\setminus \mathit G$ can only be $[\mathbb{N}]$ (let’s call it the no-split-property).
  Then we let $\mathit{Y_{\omega}}=\mathit{Y'_{\omega}}\cup \mathit{X_{\omega+\alpha}}$ , where ${\alpha}$ is the smallest ordinal such that $\mathit{X_{\omega+\alpha}}$ has an non empty f-intersection with $\mathit{Y'_{\omega}}$ . There will be one because if there were no one $[\mathit{Y'_{\omega}}]^c$ would be a f-union of $\mathit{F}\setminus \left\{\mathit{X_1},\mathit{X_2},...,\mathit{Y'_{\omega}}\right\}$ .
  We even can get rid of the finite intersection property, by doing the same operation for the $\mathit{X_i}$ , where $i$ is a successor ordinal. The process has to stop when we get an empty-intersection tower. The hypothesis we made that we have instead of FIP,may be stronger,but as soon as we get the same cardinality, it’s ok.
  
  B) It has no connection with what I just said, but I wonder if we can sometime hope that a collection of f-sets has a bigger pseudo intersection. You showed that is necessary that the collection is uncountable but maybe there is some sufficient property that we could find and use, and that could be very helpful…
- Toby Kenney Says:
  September 27, 2017 at 2:59 pm
  Unless I’m missing something, if such a Y does not exist, then X intersection Y_1, X intersection Y_2, … is a tower with no f-intersection, and we are done (I think this will work at all limit ordinals) We’ll need each Y_alpha to have nonempty intersection with every X in F where F is closed under finite f-intersection.
- gowers Says:
  September 27, 2017 at 8:44 pm
  Ah yes. So let me try again. As above, we set $Y_n$ to be $X_0\cap\dots\cap X_n$ . Then, following your suggestion, we observe that the sets $X_\omega\cap Y_n$ form a tower, and we pick our f-intersection inside that, and call it $Y_\omega$ .
  
  But as you also say, we’re not out of the woods, since we have to choose the f-intersection in such a way that it intersects all the sets in $F$ , or we run into trouble at the very next step.
  
  So now we have an interesting problem: given a collection $F$ of sets closed under finite intersections and a countable nested sequence of sets $X_1\supset X_2\supset\dots$ from the collection, can we find an f-intersection $X$ of the sequence that intersects all the sets in $F$ ? That is, can we find an f-intersection $X$ that belongs to the dual of $F$ ? If $F$ is an ultrafilter, then the question becomes this: does a countable chain of sets in an ultrafilter have to have an f-intersection that also belongs to the ultrafilter?
  
  Unfortunately, the answer to this is no. Consider the filter on $\mathbb N^2$ that contains a set $A$ if and only if the set of $x$ such that the set of $y$ such that $(x,y)\in A$ is cofinite is cofinite. To put that a bit more comprehensibly, I’m saying that for all but finitely many $x$ it is the case that for all but finitely many $y$ , $(x,y)\in A$ . Now suppose we extend this filter to an ultrafilter on $\mathbb N^2$ . Then the sets $[n,\infty)\times\mathbb N$ form a countable chain of sets in the ultrafilter, but any f-intersection $X$ of these sets has to have the property that for every $x$ there are only finitely many $y$ with $(x,y)\in X$ , which means that the complement of $X$ belongs to the filter, and hence to the ultrafilter, so $X$ does not belong to the ultrafilter.
- jean-camille Says:
  September 28, 2017 at 6:46 am
  Let $I_{\alpha}$ be the set of all pseudo-intersections in $[X_1,X_{\alpha}]$ . Maybe there is a smart way to choose $T_{\alpha} \in I_{\alpha}$ such that $\mathit{T}=\bigl\{T_{\alpha},\, I_{\alpha}\ne \emptyset \bigr\}$ is a good tower…
- gowers Says:
  September 28, 2017 at 8:04 am
  A quick remark for jean-camille: if you type $latex instead of the first dollar symbol, then the TeX will compile. I should have mentioned this a long time ago. Also, the bug you experienced was because WordPress confuses the “less than” and “greater than” symbols with html. So you have to write & lt ; and & gt ; instead (but without the spaces).
- jean-camille Says:
  September 28, 2017 at 10:52 pm
  Thank you very much for for theses kind explanations! Sorry again, and thank you very much for having edited so many comments (although most didn’t deserve such a kind traitement!)
  
  This very trivial idea to consider $I_{\alpha}$ gave me many ideas in a short time, and some of them lead me to the illusion of getting the result (I didn’t actually saw where were the mistakes because I din’t have the time to examine each one yet) Let me develop one of the ideas : I think it can reduce a lot the hypothesis, and -why not – help us getting the elementary proof we look for…
  
  Let’s define $i : \mathcal{\mathcal{P}}\, \to \mathcal{\mathcal{P}},\,\,\mathcal{G}\mapsto i(\mathcal{G})\,=:\,\left\{X\subset \mathbb{N},\, [X]\subset_f [G], \forall G\in \mathcal{G}\right\}$ , as the “pseudo intersection set” fonction.
  
  We can see that $i(i(\mathcal G))\subset i(\mathcal G)$ unless it is equal, and that $i(i(\mathcal G))= i(\mathcal G)$ if and only if it has cardinality $1$ (the single element can then only be the usual intersection of $\mathcal G$ ).
  We can define a transfinite super-tower whose elements are $\mathcal G_a=i(\mathcal G_{a-1})\subset \mathcal G_{a-1}$ if $a$ is successor ordinal and $\mathcal G_a=\bigcap \left\{\mathcal G_b,\, b<a\right\}$ if $a$ is limit ordinal. And it's easy to deduce from this that the cardinality of the super tower is at most the f-cardinality of $i(\mathcal G)$ . Then what is coming write now is quite funny : we can build a f-tower with only one pseudo intersection, just by picking elements in $\mathcal{G}_{a+1}\setminus \mathcal{G}_a$ (for any ordinal $a$ , limit or successor)
  Then before saying anything about $\mathit F$ satisfying the "nnei" and the "fip", we can already assume (in order to eventually lead to a contradiction) that all the set of the form $i(\mathcal G)$ have a bigger cardinality than $\mathit F$ … I must have made some mistake because it sounds to good to be true…
- jean-camille Says:
  September 28, 2017 at 11:06 pm
  I edit the latex mistakes :
  
  Let’s define $i : \mathcal{\mathcal{P}}\, \to \mathcal{\mathcal{P}},\,\,\mathcal{G}\mapsto i(\mathcal{G})\,=:\,\left\{X\subset \mathbb{N},\, [X]\subset_f [G], \forall G\in \mathcal{G}\right\}$ , as the “pseudo intersection set” fonction.
  
  We can see that $i(i(\mathcal G))\subset i(\mathcal G)$ unless it is equal, and that $i(i(\mathcal G))= i(\mathcal G)$ if and only if it has cardinality 1 (the single element can then only be the usual intersection of $\mathcal G$ ).
  We can define a transfinite super-tower whose elements are $\mathcal G_a=i(\mathcal G_{a-1})$ if $a$ is successor ordinal and $\mathcal G_a=\bigcap \left\{\mathcal G_b,\, b<a\right\}$ if $a$ is limit ordinal. And it's easy to deduce from this, that the cardinality of the super tower is at most the f-cardinality of $i(\mathcal G)$ . Then what is coming write now is quite funny : we can build a f-tower with only one pseudo intersection, just by picking elements in $\mathcal{G_{a+1}}\setminus \mathcal{G_a}$ (for any ordinal $a$ , limit or successor)
  Then if we find ANY $\mathcal G$ such that $i(\mathcal G)$ has a cardinality at most $\mathcal p$ , then we will have finish! We can then restrict ourself to the opposite hypothesies.
- jean-camille Says:
  September 29, 2017 at 12:30 am
  A little precision (and edition of a strange notation instead of $p$)
  “we find ANY $\mathcal G$ such that $i(\mathcal G)$ IS INFINITE AND has a cardinality at most $p$ , then we will have finish!”
  
  Maybe that is not so surprising after all, as soon as all the $f$-subset of any f-subset in the pseudo intersection is also in the pseudo intersection…
- gowers Says:
  September 29, 2017 at 10:20 am
  This is another interesting idea. It isn’t clear how to use it (or at least, not clear to me after about 15 minutes of scratching my head), because I don’t see a way of controlling the number of f-intersections. The sort of thing one might try is to begin with a set $F$ with the f.i.p. and no f-intersection, and remove sets from it until the first point at which an f-intersection appears. But if that happens at a large limit ordinal, then it isn’t clear that the number of f-intersections can’t jump from zero to very very big. (I’m assuming here that the sets in $F$ have been well-ordered and we are removing them one by one.)
  
  At a successor ordinal things might be OK though. If $F$ has no f-intersection and we remove a single set $X$ from it, then if $Y$ is an f-intersection of $F\setminus\{X\}$ , it must be not almost contained in $X$ , but almost contained in every other set in $F$ . So $Y\setminus X$ is infinite.
  
  Oh wait, I think I’ve noticed something that shows that the approach as you currently have it can’t work for a simple reason. The reason is that if $X$ is an f-intersection for a set-system $\mathcal G$ , then so is any infinite f-subset of $X$ . Therefore, any non-empty $i(\mathcal G)$ has cardinality equal to that of the continuum, and $i(i(\mathcal G))$ is empty.
- jean-camille Says:
  October 1, 2017 at 12:59 am
  Yes… It make me think about new terminology and definitions that could be relevant.
  
  Like for instance , $i^*=u\,o\,i$ and $u^*=i\,o\,u$ , where $u(\mathcal{G})=\bigl\{A\subset_f [\mathbb{N}],\, \forall G\in \mathcal{G},\, A\supset_f G \bigr\}$ gives the set of all pseudo-union of $\mathcal G$ . Maybe $i^*(\mathcal G)\cap i(\mathcal{G})$ is also a good tool for next. For example we can say that when it is a set with a single element that $\mathcal G$ is “clean”.
  
  Note
  In another comment, I spoke about being a “good part” : $\mathcal{G}$ is a “good part” (of the set of all f-sets) if there exists $A\subset \mathbb{N}$ such that $i(\mathcal{G})=i(\left\{[A]\right\})$ . So maybe, by now, we can give the abbreviation $i_A=i(\left\{[A]\right\})$ (and of course $u_A=u(\left\{[A]\right\})$ ) – Then what I called $\mathbf{R}_A$ in a long previous today-post (that I’m going to write better without notation mistakes (I hope) , and in a clearest way) is now $i_A$ .
- jean-camille Says:
  October 12, 2017 at 5:29 am
  We can without lost of generality suppose that $i(\left\{X_{k},k<\alpha\right\})\ne \left\{[\emptyset]\right\}$ where $\alpha$ is the smallest ordinal such that $i(\left\{X_{k},k<\alpha\right\})\cap i(\left\{X_{\alpha}\right\})=\left\{[\emptyset]\right\}$ .
  Indeed if it is not the case, we consider $X_k\cap_f X_{\alpha}$ instead of $X_k$ .
  It seems te me (but I don't feel so sure about it) that we can also assume that $i(\left\{X_{k},k<\beta\right\})\ne i(\left\{X_{k},k<\beta+1\right\})$ , and then we have tower (with no intersection), because $X_k$ is clearly in every $X_j$ with $j<k$ …
- jean-camille Says:
  October 12, 2017 at 7:25 pm
  rectification : $X_k$ is not f_included in every $X_j$ , with $j<k$ but if we pick $Z_k$ in $ latex i(\left\{X_{k},k<\beta\right\})\setminus i(\left\{X_{k},k<\beta+1\right\})$ we might have tower by considering $T_1=Z_1$ , $T_{k}=T_{k-1}*Z_k$ for $k$ successor ordinal, and if $k$ is a limit ordinal we take as usual $T_k$ in $i(\left\{T_j,\, j<k\right\}$ .
  (where $A*B=A^*\,o\,B^*$ such that $A*$ is the only increasing injection from $\mathbb{N}$ to $A$)
  
  I thought this tower has no intersection because $i(\left\{X_{k},k<\alpha\right\})=\left\{[\emptyset]\right\}$ , but it is not so clear… anyway I post this comment not only to correct the previous one but to give a possible idea quickly before the correct (basic) things that might be in the previous post get spoiled by its wrong end.
- jean-camille Says:
  October 24, 2017 at 10:25 pm
  Let’s take a generalization of the problem and figure out few simple particular case of this generalization where it still holds. This will lead to a new formulation of the problem… considering not f-set, but tr-set, meaning classes of sets equal “up to translation”.
  
  Let $<_o$ be a quasi-ordered relation on $\mathcal{P(\mathbb{N})}$ , such that $\subset$ is thinner than $<_o$ .
  For any $A,B\subset \mathbb{N}$ , we write $A=_o B$ , or $[A]_o=[B]_o$ if $A<_o B$ and $B<_o A$ . We also write for any $\mathcal{A}\in \mathcal{P(\mathbb{N})}$ , $i_o(\mathcal{A})=\left\{X,\, \forall A\in \mathcal{A},\, X<_o A\right\}$ .
  We say that $\mathcal{A}$ has no $o$ -intersection if $i_o(\mathcal{A})=[\emptyset]_o$ that it has the $o$-intersection property (oip) if for any finite set $\mathcal{B}\subset \mathcal{A}$ , we have $i_o(\mathcal{B}$ not equal to $0_o=:[\emptyset]_o$ . We say that $\mathcal{A}$ is o-saturated if it has the oip and no o-intersection. And we say that $\mathcal{T}$ is a o-total if for any $T,S\in \mathcal{T}$ we have $S<_o T$ or $T<_o S$ .Let's call $p_o$ resp. $t_o$ ) the smallest ordinal such that there exists a o-saturated set ( resp. o-saturated and o-total) indexed by ordinals lower than $p_o$ .
  
  We can ask our self whether $p_o=t_o$ …
  We can say that $t=t_f$ and $p=p_t$ , and we hope to prove that they are equal. We can state that $t_{\subset}=p_{subset}=\omega_0$ . And we can also state that the equality holds, for any $<_x$ such that , any $\mathcal{A}\subset \mathcal{P(\mathbb{N})}$ has the xip. Because we can use successfully the argument of the comment of the main comment.
  
  Let's now give an example of such a quasi order. Still calling $A^*$ the increasing injection from $\mathbb{N}\to A$, we'll say that $A<_{fct} B$ if there exists $h,k\in \mathbb{Z}$ such that $A^*(n+h)+k<B^*(n)$ for all $n\in\mathbb{N}$ .
  
  We can see that $A^*(B)=(A\,o\,B)(\mathbb{N}:=A*B<_{fct} A$ and $A*B<_{fct} A$ , We can
  call this (***) then make two statement :
  
  The first one is that $t_{fct}=p_{fct}$. (because (***) leads that any $\mathcal{A}\subset \mathcal{P(\mathbb{N})}$ has the fct.ip. and we just said that the equality holds in that case)
  
  the second statement is that $t_{fct}$ is not smaller than $t=t_f$. Indeed we can then use the argument here : https://gowers.wordpress.com/2017/09/19/two-infinities-that-are-surprisingly-equal/#comment-203684
  (***) assure us that the "composition tower" has no fct-intersection witch is stronger then having no f-intersection. For the same reason of strenght, we have the obvious opposite inclusion and we then have $t_{fct}=t$ .
  
  We can also build an intermediate strongly quasi-order that we can call $<_{tr}$ , for translation : $A<_{tr} B$ if and only if there exists $k\in \mathbb{Z}$ such that $(A^*+k)(\mathbb{N})<_f B$ . We can see easily that $t=t_{tr}$ (by choosing fine representative element of a tr-tower : = total family indexed by ordinals that extend $<_{tr}$ )
  
  We then have :
  
  $p_{tr}$ lower or equal to $p$ lower or equal to $p_{fct}=t_{fct}=t_{tr}=t$
  
  So, the problem $p=t$ have a "translations 's translation" (joke with both meaning of "translation")
  
  We have $p_{tr}=p_{fct}\Leftrightarrow p_f=t_f$
  Note that this a nice thing about this equivalent condition, is that the composition $*$ is compatible with "translations" (the tr-equivalence) and also the fct-equivalence.
  
  It might also be interesting to get other quasi order, by making an eventually non-empty f-intersection empty by some quotient, and consider a digressing family of such quasi order…
  
  It could also be instructive to build quasi-order where $p_o=t_o$ does not hold.
- jean-camille Says:
  October 24, 2017 at 11:27 pm
  EDIT of few LATEX in previous post (it’s better to read this one)
  
  Let’s take a generalization of the problem and figure out when it is simple the cases that we can solve.
  Let $<_o$ be a quasi-ordered relation on $\mathcal{P(\mathbb{N})}$ , such that $\subset$ is thinner than $<_o$ .
  For any $A,B\subset \mathbb{N}$ , we write $A=_o B$ , or $[A]_o=[B]_o$ if $A<_o B$ and $B<_o A$ . We also write for any $\mathcal{A}\in \mathcal{P(\mathbb{N})}$ , $i_o(\mathcal{A})=\left\{X,\, \forall A\in \mathcal{A},\, X<_o A\right\}$ .
  We say that $\mathcal{A}$ has no o-intersection if $i_o(\mathcal{A})=[\emptyset]_o$ that it has the o-intersection property (o-ip) if for any finite set $\mathcal{B}\subset \mathcal{A}$ , we have $i_o(\mathcal{B})$ not equal to $0_o=:[\emptyset]_o$ . We say that $\mathcal{A}$ is o-saturated if it has the oip and no o-intersection. And we say that $\mathcal{T}$ is a o-total if for any $T,S\in \mathcal{T}$ we have $S<_o T$ or $T<_o S$ .Let's call $p_o$ resp. $t_o$ ) the smallest ordinal such that there exists a o-saturated set ( resp. o-saturated and o-total) indexed by ordinals lower than $p_o$ .
  
  We can ask our self whether $p_o=t_o$ …
  We can say that $t=t_f$ and $p=p_f$ , and we hope to prove that they are equal.
  We can also obviously notice that $t_{\subset}=p_{\subset}=\omega_0$ .
  We can also state that the equality $p_x=t_x$ holds, for any $<_x$ such that , any $\mathcal{A}\subset \mathcal{P(\mathbb{N})}$ has the x-ip. Because we can use the argument of the main comment which is precisely : https://gowers.wordpress.com/2017/09/19/two-infinities-that-are-surprisingly-equal/#comment-203713.
  
  Let's then give an example of such a quasi order. Still calling $A^*$ the increasing injection from $\mathbb{N}\to A$ , we'll say that $A<_{fct} B$ if there exists $h,k\in \mathbb{Z}$ such that $A^*(n+h)+k<B^*(n)$ for all $n\in\mathbb{N}$ .
  
  We can see that $A^*(B)=(A\,o\,B)(\mathbb{N}):=A*B<_{fct} A$ and $A*B<_{fct} A$ , We can
  call this (***) then make two statement :
  
  The first one is that $t_{fct}=p_{fct}$.
  (because (***) leads that any $\mathcal{A}\subset \mathcal{P(\mathbb{N})}$ has the fct.ip. and we just said that the equality holds in that case)
  
  the second statement is that $t_{fct}$ is not smaller than $t=t_f$. Indeed we can then use the argument here : https://gowers.wordpress.com/2017/09/19/two-infinities-that-are-surprisingly-equal/#comment-203534
  (***) assure us that the "composition tower" has no fct-intersection witch is stronger then having no f-intersection. For the same reason of strength, we have the obvious opposite inclusion and we then have $t_{fct}=t$ .
  
  We can also build an intermediate strongly quasi-order that we can call $<_{tr}$ , (for "translation") : $A<_{tr} B$ if and only if there exists $k\in \mathbb{Z}$ such that $(A^*+k)(\mathbb{N})<_f B$ . We can see easily that :
  
  $t=t_{tr}$
  
  (by choosing fine representative element of a tr-tower : = total family indexed by ordinals that extend $<_{tr}$ )
  
  We then have :
  
  $p_{tr}$ lower or equal to $p$ lower or equal to $p_{fct}=t_{fct}=t_{tr}=t$ (+++)
  
  This make the hope of picking a fct-tower (then a f-tower with the $*$ -argument) into $\mathcal F_k=:i_f(\left\{F_i,\,i<k\right\}$ a little bit more concrete than before these obervations… because we can suppose that $\mathcal F_k$ is only $0_f$ when $k=p$ , and $p$ is a limit ordinal…
  
  (+++) also show that
  $p=t$ is equivelent to $p_{fct}=p_{tr}$
  
  Witch is a translation of the problem in a context of classes closed "up-to translation" (like fct and tr) – note that the $*$ composition is compatible with both tr-equivalence and fct-equivalence)
  
  It might also be interesting to get other quasi order, by making an eventually non-empty f-intersection empty by some quotient, and consider a digressing family of such quasi order…
  
  It could also be instructive to build $<_x$ , quasi-order where $p_x\neq t_x$ .
- jean-camille Says:
  October 24, 2017 at 11:35 pm
  […] $A*B<_{fct} A$ AND $A*B<_{fct} B$ […]
- jean-camille Says:
  October 24, 2017 at 11:47 pm
  […] $p_{tr}=latex p_{fct} \Rightarrow p=t$ […] …not yet “equivalent”
- jean-camille Says:
  October 25, 2017 at 7:06 pm
  I did another wrong notation in the definition of $<_{fct}$ : I reversed the sens of an inequality!! We should read
  
  $A<_{fct} B$ if there exists $a,b,c,d\in \mathbb Z$ such that $A^*(n+a)+b$ is greater integer than $B^*(n+c)+d$ for all $n\in \mathbb N$ .
  
  Sorry for these notation mistakes! (I'm going to continue these attempt and ideas on mathOverflow, with the same surname, then I will post it here, when I'll be sure that it is correct and relevant!)
  
  I hope I'll get something nice to bring and then bring kind of a compensation for all these inaccuracies, in contrast with the smart behavior and of the high quality of other interventions !
- jean-camille Says:
  November 18, 2017 at 12:46 pm
  I did few mistakes : we don’t have $t_{fct}=t_f$ . But only $t_{f}\leq t_{fct}$ and also $t_{fct}=p_{fct}$ this is interesting because then, if we get $p_{fct}=p$ we are done.
  
  There is kind of an “inverse problem” by asking who are the partial orders such that $p_o=t_o$ .
  
  I say again the definition of $<_{fct}$ :
  $AB^*(n+c)+d$ for all $n$ integer, where $<$ is the usual order on $\mathbb{N}$ and $A^*$ is the increasing injection from $\mathbb{N}$ to $A=A^*(\mathbb{N})$
  
  (the previous definition took $a\in \mathbb{Z}$ so there is some definition problem for the fonction $A^*$ if $n+a<0$ )
  
  Let's also say again the two interesting fact that we have with $<_{fct}$
  
  1) it is extending $\subset_f$ and compatible with $*$ (where $A^*\,o\,B^*=: A*B$ )
  2) $A*B<_{fct} A*$ and $A*B<_{fct} B$
  
  So that 2) get rid of the problem we had before with $A*B\subset B$ that is not true… we pay this nice fact by dealing with $<_{fct}$ instead of $<_f$ but there may be hope to get back to $f$ with new statements that are interesting independently from $p=t$.
  
  One of this statement could be the fact that $p_{fct}=p$ that I spoke about at the beginning of the post but there is another one (that might be very wrong, but we need a weaker version)
  
  monotone no-intersection statement :
  Suppose that $F^k=\left\{F_i^k,i<\alpha\right\}$ is a collection of $\alpha$ families such that $F^{k+1}_i<_{fct} F^k_i$ , for all $i<\alpha$ and suppose that no $F^k$ have a non-empty f-intersection, then $\left\{F^k_k,\,k<\alpha\right\}$ have no f-intersection as well.
  
  This statement, if true, would help us in the particular case of $\alpha=p$ and that $F=F_0$ has the property that any ending segment has no-intersection ( $\left\{F^0_i,\, j<i<p\right\}$ has no f-intersection for all $j<p$ )
  
  There is a construction mixing the usual argument in the main comment, the "more and more tower-like" idea in the next main comment, and the $*$ argument that failed because of $A*B\subset B$ not being true :
  
  If $k$ is successor we say $F^k_i=F^{k-1}_i$ if $i< k$ , and $F^k_i= F^{k-1}_{k-1}* F^{k-1}_i=F^k_k*F^0_i$ .if not
  
  If $k$ is limit, we take $F'_k$ any f-intersection of $\left\{F_i^j,\, i\leq j<k\right\}$ and we say that $F^k_i=F^j_i$ if $i\leq j< k$ , and if $i\geq k$ we take $F^k_i=F'_k*F^0_i$ .
  
  We can imagine other construction, but if the statement is true, and if we can suppose that we can assume the existence** of the particular case of a family with cardinality $p$ where the ending segment have no-intersection (I think this** is not difficult) then $\left\{F^k_k,\,k<p\right\}$ is a tower with no-intersection.
  
  So if either monotone no-intersection statement (and **) is true either $p_{fct}=p$ is true then we have what we want.
- jean-camille Says:
  November 18, 2017 at 1:09 pm
  it seems that the “greater then bug” is still there, so let’s just give the good definition of $<_{fct}$ :
  $A<_{fct} B$ if there exists $a,b,c,d\in \mathbb{N}$ such that :
  $B^*(n+c)+d<A^*(n+a)+b$ for all $n\in \mathbb{N}$
  
  (the decreasing of $A^*$ is quicker than that of $B^*$ , that's why the inequality is this way, that is also why I used the "greater or equal " instead of switch the places of A and B, if the bug doesn't come in this very comment, this will show that it does'nt react to "lt" the same way tan to "gt". *)
  
  *by the way… is it " a &gt b" or " a \&gt b " that works ?
  Well, I'm going to test it, so that you don't loose time by answering that kind of boring details :
  
  test
  $a &gt b$ (with the barre)
  $a \&gt b$ (without the barre)
- jean-camille Says:
  November 18, 2017 at 1:54 pm
  The monotone-no-intersction statement is wrong anyway :
  Take $F^k_i=F_0$ if $i\leq k$ and $F^k_i= F_i$ if not, where $F=\left\{F_i,\, i<\alpha\right\}$ has no f-intersection.
gowers Says:
September 22, 2017 at 12:19 pm | Reply
Here’s another very general idea for an approach. I doubt it can be made to work, but I’ll give it anyway. We start with a set $F$ with the finite intersection property and no f-intersection. We then call this set $F_0$ , and we try to create a transfinite sequence of sets $F_\alpha$ that become more and more tower-like as we continue. For example, perhaps $F_{\alpha+1}$ replaces two sets $A$ and $B$ from $F_\alpha$ by the sets $A$ and $A\cap B$ , or something like that. As usual, it may well be hard to say what to do when $\alpha$ is an uncountable limit ordinal. But the hope would be that each $F_\alpha$ would have the same cardinality as $F$ , as well as no f-intersection, that the process would have to terminate at some point, and that when it terminated we would have a tower. It would be something like an “infinite compression argument”.
- gowers Says:
  September 22, 2017 at 2:40 pm
  To go a tiny bit further with this idea, suppose we have reached a set system $F_\alpha$ . If it is not a tower, then find inside $F_\alpha$ two sets $A,B$ with neither f-contained in the other. Then I will indeed replace $la tex B$ by $A\cap B$ . If $A\cap B$ is already in $F$ , that doesn’t matter, as we just care that the cardinality should not increase. Clearly the new set system still has the finite intersection property and it still has empty f-intersection.
  
  So the problem is, once again, what to do about limit ordinals. Suppose that $\alpha$ is a limit ordinal and that for each $\beta$ with $\beta<\alpha$ I have constructed a set system $F_\beta$ with the finite intersection property and no f-intersection. I now need to construct a limiting set system $F_\alpha$ somehow. This will be fine if I can ensure that no set from $F$ has been changed infinitely many times. But it’s not obvious that that will happen.
  
  Thinking about this further, it seems to be running into the same difficulties.
jean-camille Says:
September 22, 2017 at 8:55 pm | Reply
Here is the proof and discussion about existence of tower with empty intersection that is in the main artical :

“Let’s use this idea to prove that there do exist towers with empty f-intersections. I shall build a collection of non-empty f-sets [A_\alpha] by transfinite induction. If I have already built [A_\alpha], I let [A_{\alpha+1}] be any non-empty f-set that is strictly f-contained in [A_\alpha]. That tells me how to build my sets at successor ordinals. If \alpha is a limit ordinal, then I’ll take A_\alpha to be a non-empty f-intersection of all the [A_\beta] with \beta<\alpha.

But how am I so sure that such an f-intersection exists? I’m not, but if it doesn’t exist, then I’m very happy, as that means that the f-sets [A_\beta] with \beta<\alpha form a tower with empty f-intersection.

Since all the f-sets in this tower are distinct, the process has to terminate at some point, and that implies that a tower with empty f-intersection must exist."

Instead of building one tower let's build a couple of tower, one with $f$-sets and one with representantive element. So we have built our couple $([A_{\alpha}],A_{\alpha})$ exactly the same way, but we just ask that the normal set tower is strictly increasing (it should'nt be a problem, wether $\alpha$ is a limit ordinal or not)
But if the normal set tower is strictly decreasing, the process has to stop at most when $\alpha$ is the first uncontable ordinal. I must be doing a confusion because it seems to give the result pretty easily… I steel post it, and I hope that, if it's wrong or stupid, then it's not stupid in such a way that I would feel ridiculous.
- gowers Says:
  September 23, 2017 at 8:29 am
  I’m not sure what you are trying to do here with the normal set tower. It’s certainly true that you can’t have an uncountable collection of subsets of the natural numbers that is well-ordered by strict inclusion. But there are two things that you can have.
  
  (i) An uncountable collection of the subsets of the natural numbers that is well-ordered by almost inclusion.
  
  (ii) An uncountable collection of the subsets of the natural numbers that is totally ordered by strict inclusion.
  
  One thing I don’t see right now is whether there is a continuum-size collection that is well-ordered by almost inclusion.
- jean-camille Says:
  September 23, 2017 at 12:44 pm
  sorry for the confusion yesterday, I was thinking about this precise example futher, and trying and trying to be more general, I wrote wrong things: this next example convince me somehow that the tower we look for may look like a transfinite self-composition of a set under $*$ , i feel that this construction+the usual pattern of the proof in article give kind of something that look like it self to the way that seem to behave countable ordinal themself! But I’m far to be knowing what I’m talking about , so let’s
  Let’s say it in a normal math way (at least until conclusion(s) that we can hold from it)
  
  Let $\mathcal{C}$ be the set of injective increasing function $f$ from $\mathbb N \to 2\mathbb N$ (so then we have $f(1)>1$ ).
  Let’s write $f^{k+1}:=f\,o\,f^{k}$ where the $o$ means composition of functions. We also define $\lim F\,:\,\mathbb N\to\mathbb{N},\,n\mapsto f^n(1)$ .
  We can show that $[\lim f(\mathbb{N})]\subset_f f^k(\mathbb N)$ for all $k\in \mathbb{N}$
  (to be convinced, we can use the argument in the main page where we find $B$ a greater pseudo intersection then $A$ , here our “ $A$ ” is $\emptyset$ and our “ $b_i$ ” are $f^{i}(1)$ )
  The fact that $f(1)>1$ leads to the other fact that $\lim \lim f(1)>\lim f(1)$
  
  We then build the tower the usual way, and when we have a limit ordinal we take a set of representative element function which can be written $\lim g(\mathbb{N})$ for some $g$ …
  
  and then it seems to me that if we want empty f-interection, we have to use limit ordinal more than a countable many times, like we knew it, but not “much” more …
- jean-camille Says:
  September 23, 2017 at 1:36 pm
  edit : it’s not “lim F” but “lim f” (defintion of lim f)
- jean-camille Says:
  September 23, 2017 at 4:58 pm
  I)
  
  Let me please correct the inaccuracy of what I just wrote. the $f(1)>1$ condition is not sufficient to have the two property that I want
  
  which are
  a) $[(\lim f)(\mathbb N)]$ is a pseudo intersection of the $'[f^n(\mathbb{N}])_{n\in \mathbb{N}}$
  b) $(\lim (\lim f))(1)>(\lim f)(1)$ )
  
  So at the place of $f(1)>1$ we have to take something like $f(n)\leq 2n$
  It is a small detail but, if I don’t say anything, it may be confusing. Indeed, you can find $f$ increasing fonction (for exmaple $n\mapsto n+1$ that doesn’t satisfy a) and b).
  
  We don’t especially need to take a general $f$ and we can for example chose $f : n\mapsto 2n$ : the purpose doesn’t change. Actually, the “$f$ transfinite run” is just a particular case of a more general construction that I could have tried to) make by combining two proofs in the main page (the proof to show that a pseudo-intersection is not unique if a tower has a contable cardinal (1), and the proof that there exists a tower with no pseudo intersection (2))
  
  I use this example with this “running fonction” because it gives an elegant self computing way to chose a representive of a non-empty pseudo intersection, but if it can show something relevant, it won’t show more than what I could have do, combining (1) and (2), by using the choice of the $b_i$ in proof (1) (istead of $f^{i}$)… and I will say later why I like this $f$-running fonction.
  
  This is a lot of word to say nothing more than the argument I ment to use in my verywrong post of yesterday : It is the same idea but cleaned up from one stupidity (the “stupidity” was to hope to take a representant of a pseudo-intersection that in contain in the obvious way, in some reprsentant picked into the previous element of the tower)
  
  And now that it is clean from the obviouss mistake, it can still be to optimistic to hope to combine (1) and (2) to deduce what we want.
  
  I “feel” like the “$f$-run ” is a “run over countable ordinal” : $f$, with an instruction for ordinal that is not a limit ordinal (take $f^{\alpha+1}$, and an instruction for limit ordinal (take $lim g$, where $g$ is the fonction of the previous limit ordinal)
  
  But I think this notion of previous limit ordinal is not aloud in general… but as soon as they are contable, we may be able to aply it, then the b) property shoud tell us that $f$ won’t take a limit cardinal instruction strictly more often than a countable many time
  
  Then I don’t know if I cannot conclude because a) and b) are actually weak, or because I am weak myself.
  
  II)
  Anyway…
  The “nice” thing that we could get from this “$f$-run” is a “fonction” that could be correlated to a precise ordinal type:
  
  for example let’s take $f(n)=2n$, than $f^k(n)=2^k.n$, $(lim f)(n)=2^n$, $lim((lim f))(n)=2^{2n}$ etc…so here $\omega$ could correspond to $2^n$, $\omega+\omega$ could correspond to $2^{2n}$ etc.. this is a bit fuzzy, but I feel like a possible (nice?) idea to develeppe from this inspiration
  
  It would maybe be better if we define, not $f^{n+1}=f\,o\,f^{n)$, but $f_{n+1}=f_{n}\,o\f_{n}$… in order to find a correlation between any limit ordinal and a “$\lim$-fonction”
  
  I hope these ideas are not hidden trivialities that are made-up with some other trivialities (or if they, are, I hope that they are in a way that can leads to something nice)
- jean-camille Says:
  September 24, 2017 at 1:47 am
  EDIT : at line 9 of last comment it is not $f(n)\leq 2n$, but $f(n)\geq 2n$ that does the job.
  
  To resume the idea of the II) : I’m looking for a $f$-tower with NPI (no pseudo-intersection). that would be a “natural copy” of countable ordinal numbers.
- jean-camille Says:
  September 24, 2017 at 4:46 pm
  A) When does there exist forall $\omega_{\mathcal{T}}$ and $\mathcal{T}=\left\{T_{\alpha},\,\alpha <\omega_{\mathcal{T}}\right\}\subset \mathcal{P}(\mathbb{N}$, such that $[[\mathcal T]]=\left\{[T],\, T\in \mathcal T\right\}$ is a tower, and such that : $T_{\alpha}*T_{\beta}=T_{\alpha+\beta}$?
  
  (where $(A*B)^*=A^*\,o\,B^*$, where $A^*=f_A$ is the only strictly increasing fonction from $\mathbb N$ to $A$)
  
  If the answer is yes for intersestings $<\omega_{\mathcal{T}}$ , it may be a good tool, and if the answer is not trivial and is no, it is good to know anyway…
  
  B)Maybe we can also build a super-towers $\mathbb{T}$, whose elements are sets of f-sets, such that when you pick a f-set $[C_{\alpha}]\in \mathcal C_{\alpha}\in \mathbb{T}$, there a f-tower whose elements are [C_{\beta}]\in \mathcal C_{\beta}$ with $\beta<\alpha$
  
  C) We could also build g-towers exactly like f-towers, where the f-topology is thiner than the f-topology. (whose closed set are finite subsets of $\mathbb{N}$) and consider all these topology such that the result still holds. (maybe we can also imagine topologyes, not on $\mathbb N$ but on any $\alpha$, countable ordinal.
- Daniel Soukup Says:
  October 2, 2017 at 3:11 pm
  Regarding the question of possible sizes of towers: I learned from Vera Fisher today that it is possible that there is no tower of size continuum, in some models of ZFC. A reference is Dordal, Peter Lars. “Towers in $[\omega]^\omega$ and $\omega^\omega$ .” Annals of pure and applied logic 45.3 (1989): 247-276.
  
  Actually, Dordal shows that for a ‘fairly closed’ set $A$ of regular cardinals and some regular $\lambda > \max A$ , one can force that there is a tower of order type $\kappa$ iff $\kappa\in A$ , and the continuum is $\lambda$ . E.g. $A$ can be any finite set of regular cardinals and the continuum anything regular above $\max A$ .
  
  This is in quite the contrast with other families we study (e.g. almost disjoint, independent) where maximal witnesses of size continuum always exist.
- jean-camille Says:
  December 24, 2017 at 6:45 pm
  @Daniel Soukup : the question that comes to me from this precious indication is :
  If $\mu$ is the maximal size of a tower, is $\latex \mu$ also the maximal size of a family $F=\left\{F_i,\, i<\mu'\right\}$ such that $F$ has no pseudo-intersection, and such that $\alpha\mapsto i_f(\left\{F_i,\, i<\alpha\right\}$ is injective. (where $i_f(X)$ denote the set of all f-lower bound ("pseudo intersections") of a family $X$ )
  
  Such an $F$ necessary has the fip. Note that we can obtain such a family from any fip family without pseudo intersection $F'$ by considering the family of the members $F_j$ of $F'$ that satisfy $i_f(\left\{F_i,\, i<j\right\}\ne i_f(\left\{F_i,\, i<j+1\right\}$
  
  if $\mu=\mu'$ this could be "kind of" an indication to the way to build a tower from any $F$ with fip and npi.
  
  ——————————————————————————————-
  
  For example by choosing $ latex C_i\in i_f(\left\{F_i,\, i<j\right\}$ for all $i<\mu$ and compose it with th $*$ operation that is defined here https://gowers.wordpress.com/2017/09/19/two-infinities-that-are-surprisingly-equal/#comment-203525
  
  The main difference is instead of composing the $F_i$ we compose the $C_i$ that belong to members of a decreasing family of co-filters* with empty (usual) intersection., so that we can hope in a more realistic way that the tower we get has no pseudo -intersction (npi)
  I will develop in a MSE post some ideas I've got about the way to hope to make it work or at least exhibe a reason why it's not easy by reducing the aim to special cases to discuss : one idea could be to use the preorder that is called $\leq_b$ in the paragraph "motivation" of this link on MSE : https://math.stackexchange.com/questions/2577440/decreasing-family-of-families-with-lower-bound-zero (I already wrote this in upper posts but note that $ latex A*B<_b A$ and also $A*B<_b B$ )
  
  (*the set of complements of $i_f(X)$ is a filter for any family $X$, so I qualify $i_f(X)$ a co-filter, but I don't know if it is the right terminology)
- jean-camille Says:
  December 24, 2017 at 6:52 pm
  Just to correct one of the typos, just after the barre ….——————…. it is not $\mu$ but any ordinal (like $p$ )
Seth Says:
September 24, 2017 at 5:22 am | Reply
In case it is useful, here is another link to lecture notes covering the
Malliaris-Shelah proof in some detail:
https://arxiv.org/abs/1709.02408
Infinity – Noah B Prince Says:
September 24, 2017 at 4:38 pm | Reply
[…] lots of mathematicians just expected that eventually we’d see the same thing play out here. (Tim Gowers, a former Fields Medalist himself, seems to suggest that a defeatist attitude may have held back […]
jean-camille Says:
September 25, 2017 at 12:40 am | Reply
I think some new oredered and quasi-ordered relations may be related to our goal.

For two fonctions $f,g\in\mathbb{N}^{\mathbb{N}}$ let’s say
$fk$, we have $f(n)<g(n)$.\\

($i$ is for "injection" because this quasi-ordrered relation is a partial ordered relation on injective fonctions, whom are all of the form $f_A $, where $A=f_A( \mathbb{N})$)

the first one is $f<_w g$ if and only if there exists $h\in \mathbb{Z}$ such that $f+h<_w g$.

($w$ is for "weak")

And the other one is $f<_s g$ if and only if $f<_i g+h$ where is not a constant fonction like for the $w$-order, but any fonction such that $h<_i \inf_i \left\{f,g\right\}$.

We can say $[f]_x=[g]_x$ if we have both $f<_x g$ and $g<_x f$, where $x\in \left\{i,w,s\right\}$.
And we can say for any $\mathcal A\subset \mathcal{P}(\mathbb{N})$, that his $x$-cardinal is the cardinal of $\left\{[A^*],\, A\in \mathcal A \right\}$ (where $x\in \left\{i,w,s\right\}$, and $A^*=f_A$ is the only injective fonction from $\mathbb N$ to $A$)

Then we can ask ourself what is the maximum (resp. minimum) $x$-cardinal of an $x$-tower?

Because if we can find a f-tower and a sequence of representative elements of each of its f-sets , such that they form a $x$-tower, we would be happy to be able to bound the maximal cardinal of the $x$-tower. (it feel that the "runing fonction" I talked about before is behaving this way, for any $x\in \left\{i,w,s\right\}$, if it is the case it might not be hard to proove it, but I'm scared to try because I'm not used to transfinite induction proofs)

Conversly, minimums can be also good to know, if we build a $f$-tower from a $x$-tower.
jean-camille Says:
September 25, 2017 at 12:48 am | Reply
A part of a sentence diseapered at the bigining ! Here is the entier sentence :

“For two fonctions $f,g\in\mathbb{N}^{\mathbb{N}}$ let’s say
$fk$ we have $f(n)<g(n)$."

Sorry about this!
jean-camille Says:
September 25, 2017 at 12:59 am | Reply
there is a bug,( I think I’m not responsable for it),because it’s exaclty the same cut-sentence ! let me try again with different letters :

we write $fp,\,f(n)<g(n)$
jean-camille Says:
September 25, 2017 at 1:09 am | Reply
Let’s try a last time without the dollars :

f is i-lower than g if there exists an integer k such that for all n greater than k, f(n)<g(n)
william e emba Says:
September 25, 2017 at 8:41 pm | Reply
Most of the set-theoretic background is missing. The notion of “cardinal characteristic of the continuum” was developed in the 80s to provide a very clear organization to the proliferation of consistency results about one combinatorial property of the reals implying another such property. A dozen or so were the first ones named—most had multiple equivalent definitions, of the sort of mostly easy combinatorics that did not prove p=t—and the implications were reduced to inequalities.

(The Wikipedia article is a poor stub—it doesn’t even mention p and t!—but it at least contains a few good references. They are usually denoted with fraktur letters.)

Like special points in a triangle, there is no end of how many there are, just a limit to how many actually catch mathematical interest. A fascinating new one, the “rearrangement” number, was discovered on mathoverflow the other year, based on an elementary real analysis question.

For example, the smallest characteristic seems to be the “Martin Axiom cardinal”. That it is the smallest is why MA implies so many combinatorial results. Some of the characteristics in fact turn out to be the “Martin Axiom restricted to a subfamily of ccc posets” cardinal.
Since all the characteristics are between aleph-one and the continuum, CH implies they are all equal. Many proofs based on CH are best thought of as proofs based on x=y, for two characteristics x and y. For example, Almgren once in his life published a proof assuming CH. Decades later, someone rephrased that proof as one based on some x=y, and was able to prove that Almgren’s conclusion implied x=y. The status of x=y (independent) was well-known to set theorists, so Almgren’s question about his statement was answered.

All but the p vs t question had been resolved for one-on-one comparisons. Proper forcing was the major tool for this, but it is famously restricted to the continuum is aleph-two only. In general, getting a model with three or four characteristics distinct is very difficult, and has only recently been done. The upshot is set theorists know how to say a lot about aleph-two using forcing, but not very much about aleph-three or more.

There’s a whole world of dualities and Galois-Tukey connections and more. If you liked the Oxtoby book, you will love this stuff. And the recent model theory connection is just amazing, probably far more important than resolving p=t.

For the record, Shelah announced a model with p<t about fifteen years ago, but quickly withdrew the claim.

So the short answer why no one was expecting a proof of p=t is that dozens of other same-genre equalities had all been proven, fairly straightforwardly, and in all other cases where no equality was found, a forcing proof of the inequality, sometimes quite involved, was eventually found. The model theoretic connection, with an almost forgotten question, is just remarkable.
- gowers Says:
  September 28, 2017 at 8:15 am
  Thank you very much for this helpful and illuminating comment. It suggests that the probability that a simple argument was overlooked is very small (rather than merely small, which is what I had previously assumed). I still find it interesting to spend a little bit of time searching for such an argument, just to get a feel for why it is a deep question, but I will suppress any fantasies of actually finding one.
- william e emba Says:
  September 29, 2017 at 3:18 pm
  If you assume p=aleph-one, then there exists an elementary proof that p=t, going back to Rothberger 1948. This would later imply that proper forcing can’t prove p<t, as mentioned above, so progress at the time was measured by the piecemeal incremental improvements in understanding forcing the continuum beyond aleph-two.
  
  One breakthrough was Shelah's proof that d<a is consistent, the penultimate one-on-one comparison problem. Shelah introduced a new, fairly complicated form of forcing, which reached its conclusion "globally", instead of the usual "local" iterations. (In particular, I believe it is still open whether aleph-one=d<a=aleph-two=continuum is possible, which is what a more traditional "local" proof would show.) For awhile Shelah thought a variant of that proof gave p<t, and SPM Bulletin 5 was an extended announcement of that result.
  
  If you want to attempt an elementary proof by contradiction, check out Shelah "A comment on p<t". He derives a ZFC consequence, the existence of "peculiar gaps". They are consistent though, but perhaps some kind of "extrapeculiar gap" is not. Either way, the complexity is daunting.
jean-camille Says:
September 28, 2017 at 4:22 pm | Reply
I’m going to build “types” for set : the idea is that the more the type is big, the more it takes steps to define it. It is related to the classic induction proofs. And I think it will be useful in a context of a collection that have the “finite union property” that has “no non full pseudo union” (like the sets of complements of $\mathit F$ and that we would like to “no nonfully towerise” if you permit this expression.

The general idea would be to build a tower by taking the first bricks into elements of “big types” (these elements in the union version looks like the image of integer sequences with huge increasing) , but first of all let’s define these types, in a general way, so that we can adapt definitions to what we need.

Let’s define for each $A\subset \mathbb{N}$ a $(s,\mathcal{E_1})$ -type.
Type 1 are elements in $\mathcal{E}_1\subset \mathcal{P(\mathbb{N})}$ , $s$ is a f-decreasing injection from $\mathcal{P(\mathbb{N})}$ to itself and $\mathcal{E}_i=s(\mathcal{E}_{i-1})\setminus \mathcal{E}_i$ are elements of type at least $i$ , where $i$ is a successor ordinal. Elements of type at least $\alpha$ witch would be a limit ordinal , is a set that is almost contained in every member of a collection of sets of type $\beta < \alpha$ , and that is not itself of type at least $\beta<\alpha$ . In any case we say that the $(s,\mathcal{E_1})$ -type is (exactly) $\alpha$ if it is at least of type $\alpha$ but not at least of type $\alpha + 1$ .
One can take as $\mathcal E_1=\bigl\{k{\mathbb{N}},k\in \mathbb{N}\bigr\}$ and $s(A)=A*A$ , or even $s(A)=A*I$ where $I\in \mathcal E_1$ .

I don't want to make a big comment, and, as my idea to continue is not precise yet (and maybe will never be) I stop there, and I hope the latex is fine now. I feel sorry that you had to edit it so many times the comments I made because of this "$latex" to put before every latex expression!
jean-camille Says:
September 28, 2017 at 4:33 pm | Reply
Oh the latex (almost) worked!!

Please be aware that I did’t use this infinite symbole anywhere.

there was propably a bug with the indice down the $\mathcal E$ (it is not “infinite”, but “1”)

I’ve fixed the formulae that didn’t parse — it’s much quicker than doing the whole thing!
jean-camille Says:
September 28, 2017 at 4:54 pm | Reply
Let me write again the latex part for better understanding , (and turn this $\mathcal{E}$ into a normal $E$ )

Let’s define for each $A\subset \mathbb{N}$ a $(s,E_1)$ -type.
Type 1 are elements in $E_1\subset \mathcal{P(\mathbb{N})}$ , $s$ is a f-decreasing injection from $\mathcal{P(\mathbb{N})}$ to itself and $E_i=s(E_{i-1})\setminus E_i$ are elements of type at least $i$ , where $i$ is a successor ordinal. Elements of type at least $\alpha$ witch would be a limit ordinal , is a set that is almost contained in every member of a collection of sets of type $\beta < \alpha$ , and that is not itself of type at least $latex\beta<\alpha$. In any case we say that the $(s,E_1)$ -type is (exactly) $\alpha$ if it is at least of type $\alpha$ but not at least of type $\alpha + 1$
One can take as $E_1=\left\{k{\mathbb{N}},k\in \mathbb{N}\right\}$ and $s(A)=A*A$ , or even $s(A)=A*I$ where $I\in E_1$
chalons Says:
September 30, 2017 at 10:43 pm | Reply
Hello, sorry for my bad english. Do you know if the Tukey respectively corresponding to p and t have been proved to be equal by Shelah and Malliaris? Or their techniques only prove the equality for cardinals
jean-camille Says:
October 1, 2017 at 4:50 pm | Reply
small edit of the previous note :
$\mathcal{G}$ is a “smart intersection part” (of the set of all f-sets) if there exists $A\subset \mathbb{N}$ such that $i(\mathcal{G})=i(\left\{[A]\right\})$ and a “good part” if there exists $A\subset \mathbb{N}$ such that $\mathcal{G}=i(\left\{[A]\right\})$ .

Let’s speak about one general result that I will call “characterization of preorder relation lemma”

If $R\subset A\times B$ is a relation, let’s denote by $R(.,y)=\left\{x\in A,\, (x,y)\in R\right\}$ the $y$ -row in $R$ .(we denote by $R(x,.)$ the $x$ -row with the obvious dual definition)
We also define the orthogonal of the $x$ -line as :
$R(x,.)^R=\bigcap_{(x,y)\in R}R(.,y)\subset B$
If $A=B$ the following assertions are equivalents :
a) $R$ is a preorder
b) $\forall (x,y)\in A\times A,\,\ ((x,y)\in R\,\Leftrightarrow \, R(.,x)\subset R(.,y))$
c) $\forall x\in A,\,R(x,.)^R=R(.,x)$

We can always see a set $A\in \mathcal{P}(B)$ as the “lines” of a relation $R\subset A\times B$ , if this relation is right (and left) separated ( $y\mapsto R(.,y)$ is injective ) and if it is closed under right and left orthogonal, then the orthogonal of the orthogonal of a line (resp. row) will be the initial line (resp. row) and you can choose an indexation of $A$ and $B$ by $I$ totally ordered set such that the orthogonal of the line $R(a_i,.)$ is the row $R(.,b_i)$ for all $i\in I$ , and we get a natural ordered relation on $I$ whom $I$ is an extended total order. If the family $A$ is not separated we can have a quotient on $B$ under the relation “having the same orthogonal” in order to get a order.

Another important fact is that, for any “line $x$ ” in our order relation $R$ , there exist a total order $T$ that extend $R$ such that $R(x,.)=T(x,.)$ .
(if we take an infinite matrix $M$ indexed by $T$, such that the coefficient $M_{T(x),T(y)}=1$ if $latex $(x,y)\in R$ and $M_{T(x),T(y)}=0$ if not, then you will get a trigonal** matrix such that the $x$ -line will have only $1$ on the non-zero side of the diagonal. (I’m going to use this “one side line” argument later in order to fain a tower from a particular $\mathit F$ with stronger hypothesis.)

**Note that we can always obtain a total order with any separated “matrix” witch is stable under left and right orthogonality by ranging according to the increasing lexicographic order the “lines” and ranging the “rows” of the matrix that we just get according the decreasing lexicographic order… well I’m not sure this particular technique is working with any infinite set, but I think in our case we could make it work, it may be helpful later, if we try to “extend” our order, so when we will get to this step, we will examine better the possibility to have a trigonalisation this way… Of course the “trigonalisation” is always possible as soon as you can extend $R$ to a total order – it is for me a synonyme : the matrix point of view is just a tool to help for “viewing”, … although these matrix, have a “product” (in a semi-ring) so they are not just “tables of 0 and 1”, this product is realted to order relation this way : if $R$ is any separated relation, and $R^*$ is the “complement” of it’s transposition, then the complement of $Support(R.R^*)$ is an ordered relation…(the product is the usual product and the support fonction take any non-zero (positive!) coefficient into a “1”, and leaves the “zeros”, the complement is the matrix you get when you exchange the “0” and the “1”) This could maybe help later…

This was the first general statement but if I want to apply it to f-set I’ve got to find a trick, so I will associate to any family $\mathit{F}$ of f-sets, a family $\mathit{F}^i=\left\{i_A,\, A\in \mathit{F}\right\}$ . This family is like a copy of $\mathit{F}$ with a usual ground set, so we get rid of fuzzy sets, but we pay it by a bigger ground set. $\mathit{F}^i$ is also closed under left-orthogonality, but if we take a right orthogonal closure we might get some set that are not anymore “good parts”. Let’s make the statement that there exists family such that $\mathit{F}^i$ is closed under right and left orthogonal. Then we will be able to build a tower with no intersection this way : we use the “one side argument” to have infinitely many “one side” lines. (we do it by transfinite induction : let’s say we have a matrix up-trigonal relative to a partial order itself related to $\mathit{F}^i$ , then we get a “line $x_1$ ” “one side”-meaning we extend the order such as the minorants of $x_1$ according to the partial order is also the line of minorant of $x_1$ related to the extended total order, and we take $x_2$ in this very minorant set… that you extend to an new total order without changing the non-minorant of $x_1$ (because of trigonality), you do this for all successor ordinal extending smaller subrelations and when we get to a limit ordinal you just take the intersection of all smaller subrelation and the process has to stop when we get a finite matrix : we then have an infinite subset of “one side lines” BUT they may not have the empty intersection : indeed one may say that we “cannot ” get a non empty finite last one-side” line, because each line is infinite (even the side of continuum!!) but as soon as we wanted a separated matrix, we are dealing with a ground set that is quotient of the set of all f-sets (under the relation “having the same orthogonal) but no matter anyway, we just remove the last line of every set, and then we still have “good parts” …)

So what we proved is that the smallest tower is smaller than any $\mathit{F}$ such that $\mathit{F}^i$ is closed under orthogonality.
The question would then be : how to get from $\mathit{F}$ with the fip and no-intersection, a family with the above property… ? (it is possible because we know the result and because a tower has the property : this is then an intermediate result, (but maybe a trivial intermediate result that don’t make the problem easier!)
Maybe we can adapt the proof for family that orthogonal closure is not to big, and such that some of the elements that we add are not necessary “good parts” (maybe take any good part in the pseudo-union set or in the pseudo-intersection set of the added element that would not be a good part… )
- jean-camille Says:
  October 1, 2017 at 10:18 pm
  line 9 : $R(x,.)^R=\bigcap_{(x,y)\in R}R(.,y)\subset A$ (not $\subset B$
  
  line 16 $A\subset \mathcal{P(B)}$ (not $\in\mathcal{P}(B)$
jean-camille Says:
October 2, 2017 at 11:22 am | Reply
Actually the idea of the extended total order seems to work much better on down-f-set!! What I call down-f-set is a usual set of f-sets such that if $[A]$ is one of its element, and if $[A']\subset_f [A]$ then $[A']$ is also one of its element.

Let me try to develop the idea of the extended total order in this context :let $\mathbf{F}$ be a set of downs-f-set that have the usual-set intersection property. Let $\mathbf{S}$ be the support of $\mathbf{F}$ , meaning the set of all the down f sets that are include in some $D\in \mathbf{F}$ . It is an ordered set for usual inclusion. We then extend the usual inclusion in a total order $<<$. What is nice here is that $[0,D]_{<<}$ is a down-f-set for all $D\in \mathbf{S}$ . The set $C=\left\{ [0,F]_{<<},\, F\in \mathbf{F}\right\}$ is now a chain of usual set of f-sets, and the set $T=\left\{ [0,F]_{<<}-\bigcap C,\, F\in \mathbf{F}\right\}$ is a chain of down-f-sets that has an empty (usual) intersection. We can pick a tower with no pseudo intersection inside.We take for $\mathbf{F}=\left\{i_A,\,A\in \mathit{F}\right\}$ our original $\mathit{F}$ with no pseudo-intersection and the fip and it seems done…
I don't see the mistake right now, but I'm sure I will see it just after posting!
- jean-camille Says:
  October 2, 2017 at 10:33 pm
  I think it’s wrong…because I get the same conclusion if $\mathit{F}$ is countable, and that’s not possible…(the other statements may be wrong as well… I’m happy to have present the angle of “preorder caractérisation lemma” anyway, although it’s not working yet…)
- jean-camille Says:
  October 4, 2017 at 6:49 am
  Oh let me try this : (the beginning is the same than the principal comment)
  I call down-f-set is a usual set of f-sets such that if $[A]$ is one of its element, and if $[A']\subset_f [A]$ then $[A']$ is also one of its element.Let’s call $\mathbf{D}$ the set of all down-f-sets
  let $\mathbf{F}\subset \mathbf D$ be such that $\bigcup \mathbf{F}=\mathbf{D}$ (condition 1)
  
  Let’s now consider $\mathbf{F'}$ , the smallest topology such that elements of $\mathbf{F}$ are closed set. As usual we extend the inclusion order in $\mathbf{F}$ to a total order $<<$. Now we consider for all $F\in\mathbf{F}$ the set $G(F)=:[0,F]_{<<}\cap \mathbf{F}$ and $H(F)=\overline{\bigcup G(F)}$ : the adherence of the union of elements in $G(F)$ . Let's make the supposition that if $G(F)$ is a finite set, then $\bigcup G(F)=H(F)$ is not the set of all down -f-sets.(condition 2). Condition 1) tells us that $\mathbf{H}=:\left\{H(F),\, F\in \mathbf{F}\right\}\subset \mathbf{D}$ is an infinite inclusion ordered set such that the $\bigcup \mathbf{H}=\mathbf{D}$ . And we also have $card(\mathbf{H})$ lower or equal to $card(\mathbf{F})$ .
  
  Now we are going to choose in each $\mathcal H\in \mathbf{H}$ a f-set $choice(\mathcal{H}$ that does not belong to any $\mathcal {H'}\in \mathbf{H}$ such that $\mathcal{H'}\subset \mathcal{H}$ .
  But as soon as $\mathcal{H}$ and $\mathcal{H'}$ are down-f-set, we will have $choice(\mathcal{H'})\subset_f choice(\mathcal{H})$ , and $\mathcal{T}=\left\{[\mathbb{N}]\setminus choice(\mathcal{H}),\, \mathcal{H}\in \mathbf{H}\right\}$ is a tower!
  
  Let's get back to: $\mathit{F}$ with no f-intersection and the f.i.p.
  We now remark that if we take $\mathbf{F}=\left\{i_{F^c},\, F\in \mathit{F}\right\}$ , where $i_{F^c}\in \mathbf{D}$ is the set of f-sets f- included in the f-complement of $F$ , then we can conclude.
  
  I'm going to turn everything into complement point of view, it will be more direct…
- jean-camille Says:
  October 4, 2017 at 7:47 am
  I made a mistake with this choice fonction, so it’s not working…but I think I can still have something (I’m quite sure that I can build a tower with no f-intersection) but It won’t be as small as I want to. Next time I’m going to try this intermediate construction…
jean-camille Says:
October 29, 2017 at 3:59 pm | Reply
A tower $T=\left\{T_i, i<c \right\}$ with no pseudo intersection (npi) satisfies two conditions,

(1) $\left\{T_i, i<k \right\}$ has a non empty intersection for all $k<c$ .

(2) $\left\{T_i, k<i<t \right\}$ has no intersection, for all $k<c$

Let's say that a general family (necessarily with fip and npi)
that satisfy (1) and (2) is a quasi-tower, and let's call $q$ the smallest cardinality that can have such a family.

We obviously have $p \leq q\leq t$ .

What seems to be the difficult part in order to prove that $p=t$
Is it $p=q$ or is it $q=t$ ? Are they both difficult?

If we have one of the two results, we can get rid of conditions that could be difficult to handle with. never the less, there is nothing to lose by having one of the two results…
jean-camille Says:
November 23, 2017 at 3:12 pm | Reply
I think I’ve got it (again)

We just have to prove a statement a bit stronger (that seems true in any lattice)

For any $F=(F_i)_{i<\alpha}$ , and any $\beta\leq \alpha$ , let's say that $F(\beta)=(F_i)_{i<\beta}$ .

The "stronger statement" is then :
For any $F=F(\alpha)$ fip-family and any $h\leq \beta<\alpha$ such that $T=T(h)$ is a tower and such that $i(T)=i(F(\beta))$ there exists $k\leq \alpha$ and a tower $Z=Z(k)$ such that $i(Z)=i(F)$ .

We can say that " $Z$ extend $T$ according to $F$ "

To prove this we consider $\alpha$ minimal such that it is not true, and we say without lost of generality that $[0]\ne i(F^a)\ne i(F^b)$ for any $a<b<\alpha$ . Then if $\alpha$ is successor, we have $F_{\alpha-1}\ne [0]$ and then
as $\alpha$ is minimal, we have a tower $Z'$ such that $Z'$ extend $T$ according to $F(\alpha-1)$ and we take $Z$ such that $Z_i=Z'_i$ if $i\leq h$ and $Z_i=Z'_i\cap_f F_{\alpha-1}$ if not. And that's a contradiction.

If $\alpha$ type is limite

we have for any $\beta_1$ such that $\beta<\beta_1<\alpha$ , a tower $Z^1=Z^1(k_1)$ such that $i(Z^1)=i(F^{\beta_1})$ and $k_1\leq \beta_1$ and we built like this $Z^j=Z^j(k_j)$ for any $j<cof(\alpha)$ .

We have $Z^i=Z^j(i)$ for any $i<j<cof$ , so we can define $Z$ such that $Z_a= Z^k_a$ for any $a<k$ , it is clear that $i(Z)=i(F)$ and that $Z^h=T$ so it is a contradiction. $\alpha$ si not limite, and not successor, and it is obviously not $0$ so the "stronger statement " is true.

The result is true for all $F$ with the fip and all $T$ so it is still true if $i(F)=[0]$ and $|T|=1$ , and that seems to be what we wanted to prove.
- jean-camille Says:
  November 23, 2017 at 3:20 pm
  Statement again (with EDIT)
  
  For any $F=(F_i)_{i<\alpha}$ , and any $\beta\leq \alpha$ , let's say that $F(\beta)=(F_i)_{i<\beta}$ .
  
  The "stronger statement" is then :
  For any $F=F(\alpha)$ fip-family and any $h\leq \beta<\alpha$ such that $T=T(h)$ is a tower and such that $i(T)=i(F(\beta))$ there exists $k\leq \alpha$ and a tower $Z=Z(k)$ such that $i(Z)=i(F)$ .
  
  AND SUCH THAT $Z^h=T$
  
  (I forget this $Z^h=T$ that is crucial in the proof)
- jean-camille Says:
  November 23, 2017 at 4:17 pm
  …. I mean $Z(h)=T$ not $Z^h=T$ , I mixed with an older notation…
  
  It also seems that (in the proof) we don’t need the hypothesis that $i(F(a))\ne i(F_(b))$ if $a\ne b$ (it also comes from a previous attempt that was maybe correct but a bit more uselessly complicated, anyway it doesn’t make the proof falser or truer, it’s just useless)
  
  Sorry for all these notations failure… I hope that everything is correct up to the notations/redondances edit…
- jean-camille Says:
  November 23, 2017 at 6:42 pm
  I think there is a problem anyway… when $h$ is limit and $\alpha=h+1$ … but maybe it’s possible to save something
Dima Says:
November 30, 2017 at 5:26 pm | Reply
regarding infinities, I’d like to complain about the recent EMS Surveys (the owner of this blog is on the editorial board there) publication:

Volume 4, Issue 2, 2017, pp. 219–320DOI: 10.4171/EMSS/4-2-3
Published online: 2017-11-13
Numerical infinities and infinitesimals: Methodology, applications, and repercussions on two Hilbert problems
Yaroslav D. Sergeyev

How this could have made it through, it totally beyond me (for it has really 0 content, and the author is well-known in a bad way…).
- gowers Says:
  December 6, 2017 at 4:51 pm
  This comment is not really on topic. However, rather than deleting it, let me simply say that I can’t respond straight away, but will do so when the right moment comes, which I hope will be not too long from now.
- Roy Mandelli Says:
  March 12, 2018 at 5:05 am
  This comment, too, is off topic so feel free to delete. But I’m quite disappointed to find that it’s been over three months and there’s yet to be any public posting from you regarding the EMS Surveys matter, considering your… “avid” opining during the Elsevier controversy.
The (Random) Matrix and more | Combinatorics and more Says:
April 21, 2019 at 7:33 am | Reply
[…] my post A theorem about infinite cardinals everybody should know; Gowers’s post Two infinities that are surprisingly equal about a recent breakthrough result by Maryanthe Malliaris and Saharon Shelah; and a recent 4-page […]
En todos los mundos posibles p = t. – Blog del Instituto de Matemáticas de la Universidad de Sevilla Says:
September 17, 2019 at 7:56 am | Reply
[…] [3] Gowers blog:Two infinities that are surprisingly equal. […]
James Hirschorn Says:
December 5, 2023 at 10:13 am | Reply
As someone who had left the field a long time ago, I was stunned when I come across your blog post a few years back.

The first two papers I published were on the cardinals p and t, and as noted in your blog there was a firm consensus that they were different.

The question you ask about why model theory was needed to solve a purely combinatorial problem, was also the first thing I wondered at, especially since it meant the proof was not readily accessible to me.

Surprisingly, my impression from the literature is that the set theory community simply viewed this as a closed case, and instead focused on distilling the original solution to make it more accessible.

Considering the fundamental nature and importance of the problem, and the number of decades it remained unsolved (I don’t know of another comparable example since the Continuum Hypothesis) one might think that after this breakthrough, research would then be focused on gaining a deeper understanding of the reason for the equality.

This in turn stimulated me to start thinking about mathematics again, to try and understand the “reason” for this equality. The solution I eventually arrived at relies only on core set theory methods, and is published on arXiv: https://arxiv.org/abs/2212.14171

A direct proof might be expected to reveal deeper insights. Indeed, the solution answers a more difficult problem, also from Rothberger’s 1948 paper, on conditions when filter-bases can be refined to towers.