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.


80 Responses to “Two infinities that are surprisingly equal”

  1. David Roberts Says:

    A trivial observation : you might not be able to engineer an injection, but perhaps a subquotient.

    • gowers Says:

      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:

      Correct, though one might additionally start by throwing away some elements of F, so the equivalence relation is only on a subset.

  2. gowers Says:

    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?

  3. Nick Soapdish Says:

    This seems relevant:

    • gowers Says:

      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.

  4. Greg Stanton Says:

    Perhaps this note by D.H. Fremlin might be relevant:

    • gowers Says:

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

  5. Daniel Soukup Says:

    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:

      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:

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

  6. Daniel Soukup Says:

    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:

      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:

      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.

  7. jean-camille Says:

    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…)

  8. jean-camille Says:

    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:

      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:

      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:

      Sorry the first line contains notation mistakes!! It should be :

      Let’s call \mathbf{R}=\left\{[A], subset \mathbb{N}\right\} For anyA\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:

      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:

      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!

  9. jean-camille Says:

    (when I say very small I meen finite cardinal)

  10. John Says:

    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:

    • gowers Says:

      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.

  11. jean-camille Says:

    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”$.

  12. jean-camille Says:

    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.

  13. jean-camille Says:

    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)

  14. jean-camille Says:

    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!)

  15. jean-camille Says:

    (I forget to precise in the previous post that, $\mathit F$ has the Daniel Soukup hypothesis : no f-inclusion beetwin any two membres)

  16. jean-camille Says:

    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:

      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.

  17. jean-camille Says:

    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:

      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:

      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:

      (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:

      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:

      Oh what a ridiculous mistake!!

    • jean-camille Says:

      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…

  18. gowers Says:

    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:

      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:

      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:

      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:

      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:

      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:

      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:

      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:

      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:

      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:

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

      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:

      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:

      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.

  19. gowers Says:

    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:

      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.

  20. jean-camille Says:

    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:

      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:

      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:

      edit : it’s not “lim F” but “lim f” (defintion of lim f)

    • jean-camille Says:


      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.

      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:

      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:

      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:

      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.

  21. Seth Says:

    In case it is useful, here is another link to lecture notes covering the
    Malliaris-Shelah proof in some detail:

  22. Infinity – Noah B Prince Says:

    […] 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 […]

  23. jean-camille Says:

    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.

  24. jean-camille Says:

    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!

  25. jean-camille Says:

    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)$

  26. jean-camille Says:

    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)

  27. william e emba Says:

    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:

      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:

      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.

  28. jean-camille Says:

    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!

  29. jean-camille Says:

    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!

  30. jean-camille Says:

    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

  31. chalons Says:

    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

  32. jean-camille Says:

    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… )

  33. jean-camille Says:

    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:

      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:

      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:

      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…

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: