2
$\begingroup$

I posted this question on MO, but I've been told by a meta user that it would fit better on MSE. If the comment of the meta user is relevant - and I'm sure it is - then it means that there is a simple counterexample for question (a), and also that the $<_A$ and $<_B$ that I define in the "motivation" paragraph is well known not to form (with the obvious $\psi$) what I call a "fair triplet". The comment of the meta user also makes me think that what I call a fair triplet is a well known concept, and if so I would like to know the usual terminology.

I changed the post that I wrote on MO a little bit, but here it is:


If $(A,\le_A)$ is a partially ordered set and $P\subseteq A$ has a greatest lower bound, we denote it by $\inf_A P$.

Say that $(\le_A,\le_B,\psi)$ is a good triplet if $(A,\le_A,0_A)$ and $(B,\le_B,0_B)$ are posets and $\psi$ an increasing surjection from $A$ to $B$ such that $\psi^{-1}(0_B)=\left\{0_A\right\}$. $(\le_A,\le_B,\psi)$ is a fair triplet if for any ordinal $\alpha>0$, if $\{F_\gamma\mid\gamma<\alpha\}$ is a family of functions $F_\gamma:\gamma+1\to A$ with the following properties:

  1. $x\le y\Rightarrow\psi(F_\gamma(x))\ge_B\psi (F_\gamma(y))$
  2. $\forall x\in \alpha,\ \inf_A \{F_\gamma(x)\mid x\le\gamma<\alpha\}=0_A$ [3. $\psi\,o\,(y\mapsto F_y(y)\,\, : \alpha\to B$ is strictly dicreasing]***

then $\inf_A\{F_\gamma(\gamma)\mid \gamma<\alpha\}=0_A$ holds.

***this third condition had been added to avoid special trivial case that Mario Carneiro figure out. After this edit, Mario Carneiro then completed his first answer in an edit by giving a necessary and sufficient condition for $A$ to satisfy (good=>fair), as well as a couterxample!

Questions

(a) Is any good triplet a fair triplet?

(b) Is any good triplet a fair triplet when $A$ and $B$ are lattices? If not, is there any property on $\psi$ that makes the triplet a fair triplet?

(c) The same question when only $A$ is a lattice.

(d) With $A$ and $B$ defined in "Motivation" paragraph below, is $(\le_A,\le_B,\psi)$ a fair triplet, for the obvious canonical $\psi$ that factorizes the identity function?

Motivation

If $u$ and $v$ are infinite subsets of $\Bbb N$ we define $\le_b$ as follows:

$u\le_b v$ if and only if there exists $a,b,c,d\in \Bbb N$ such that for any $n\in \Bbb N$, $u^*(n+a)+b>v^*(n+c)+d$, where $u^*$ (resp. $v^*$) is the only increasing bijection from $\mathbb N$ to $u$.

If $u$ is finite subset of $\Bbb N$ we state that $u\le_b v$ for any $v$.

$\le_b$ is a preorder on $\mathcal P(\mathbb N)$, and if we call $b$ the associated equivalence relation, we say that $B=:\mathcal P(\mathbb N)/b$ is canonically ordered by $\le_B$ (such that $u\le_b v$ if and only if $[u]_b\le_B[v]_b$, where $[u]_b$ denotes the class of $u$ under $b$, meaning all subsets $u'$ of $\mathbb N$ such that $u\le_b u'$ and $u'\le_b u$ both hold).

If $A$ is $\mathcal P(\mathbb N)/a$ where $a$ is equality up to finite subset, and $\le_a$ is inclusion "up to finite subset" (meaning for any $u,v\subseteq \mathbb N$, $u\subseteq v \cup f$ for some finite $f\subseteq \mathbb N$) we define $\le_A$ to be such that $u\le_a v\Leftrightarrow [u]_a\le_A [v]_a$.

Then if question (a) is true - or at least question (d) about this very case is true - then it should not be difficult* to build from any $F\subseteq A$ with lower bound $0_A=0_B=0$, a $T\subseteq A$ with lower bound $0$, such that the restriction of $\le_A$ to $T$ is a total order. It is a result proved (I think in 2015) by Malliaris and Shelah, but you need to be aware of set theory to understand the proof, and I'm far from being able to! I'm looking for a simple argument, after I read Tim Gowers' blog, indeed the great mathematician hoped for a simple argument, but it seems that the problem is so difficult that he abandoned this hope, so it would really be astonishing if question (a) was true with a simple proof. Is it even true in the particular case of the "motivation"?
I think the question(s) are interesting independently from the "motivation" - which is implied by questions (a) and (c) but not (b).

*I will give more details about the link between "questions" and "motivation" in the comments if anyone needs it, but this post is quite long already...

$\endgroup$
  • $\begingroup$ Saying a question is a better fit here than on MO doesn't mean there's an easy solution, it just means the problem is not math research. $\endgroup$ – Gerry Myerson Dec 23 '17 at 3:38
  • $\begingroup$ What does "ordered set" mean? Is it a linear order? A partial order? I assume that by using the notation $<_A$ you mean the relation to be irreflexive, but then condition (1) of the function $F$ is trivially false. And when you say $\psi$ is increasing, do you mean strictly or weakly? If strictly, then the condition (1) can be simplified by removing $\psi$. $\endgroup$ – Mario Carneiro Dec 23 '17 at 3:55
  • $\begingroup$ You assert that there is a unique increasing injection from $u\subseteq\Bbb N$ to $\Bbb N$, but this is not true. Maybe you wanted to assert that ${\rm ran}\;u^*$ is an initial segment of $\Bbb N$? $\endgroup$ – Mario Carneiro Dec 23 '17 at 4:17
  • $\begingroup$ I made a fairly substantial edit to your post to make some things clearer, please double check that I haven't confused your intent. $\endgroup$ – Mario Carneiro Dec 23 '17 at 4:24
  • $\begingroup$ Re: your edit, do you mean $u,v$ to be infinite? Otherwise there are obviously no bijections from $\Bbb N$. $\endgroup$ – Mario Carneiro Dec 23 '17 at 4:34
1
$\begingroup$

Let $A$ be any poset with zero. I will show that [$\forall B,\psi,$ $(A,B,\psi)$ good $\Rightarrow(A,B,\psi)$ fair] if and only if $A=\{0\}$ or $\inf(A-\{0\})\ne 0$. Since this latter condition essentially says that $A$ is trivial, the answer to (a), (b), and (c) is no.

Obviously if $A=\{0\}$ then $(A,B,\psi)$ is fair. So suppose that $A\ne\{0\}$ and $\inf(A-\{0\})\ne 0$. Let $a$ be a nonzero lower bound of $A-\{0\}$; then since $a\in A-\{0\}$ in fact $a=\min(A-\{0\})$. Now let $\alpha$ and $F$ be given as in the conditions. Since $\inf\{F_\gamma(0)\mid \gamma<\alpha\}=0$, this means that there exists $\gamma$ such that $F_\gamma(0)=0$ (otherwise the inf would be at least $a$). Then $\psi(F_\gamma(0))=0$, so $\psi(F_\gamma(\gamma))\le \psi(F_\gamma(0))=0$. Thus $\inf\{F_\gamma(\gamma)\mid \gamma<\alpha\}=0$, so $(A,B,\psi)$ is fair.

For the more interesting case, suppose $A\ne\{0\}$ and $\inf(A-\{0\})=0$. Let $B=\{0,1\}$ with $0\le 1$, and $\psi(x)=0$ iff $x=0$. This is clearly an increasing surjection, and it satisfies $\psi^{-1}(\{0\})=\{0\}$, so $(A,B,\psi)$ is a good triple.

Now let $\alpha$ be the smallest infinite ordinal such that there exists a sequence $\{s_\gamma\mid\gamma<\alpha\}$ of elements of $A-\{0\}$ (not necessarily injective) with $\inf\{s_\gamma\mid\gamma<\alpha\}=0$. Then $\alpha$ is an infinite cardinal, and we can define $F_\gamma(x)=s_{\gamma-x}$ where $\gamma-x$ denotes the unique ordinal satisfying $x+(\gamma-x)=\gamma$.

Now $F_\gamma(\gamma)=s_0$, so $\inf\{F_\gamma(\gamma)\mid\gamma<\alpha\}=s_0\ne0$. It remains to show the conditions hold:

  1. Let $x\le y$ (this doesn't matter). Since $F_\gamma(x)$ and $F_\gamma(y)$ are both in $A-\{0\}$, $\psi(F_\gamma(x))=\psi(F_\gamma(y))=1$.
  2. $\inf\{F_\gamma(x)\mid \gamma\le x<\alpha\}=\inf\{s_\beta\mid \beta<\alpha\}=0$, because for any $\beta<\alpha$, $\beta=(\gamma+\beta)-\gamma$ and $\gamma+\beta<\alpha$ (using that $\alpha$ is an infinite cardinal) so $s_\beta=F_\gamma(\gamma+\beta)$.

Thus $(A,B,\psi)$ is not a fair triple.


The problem has been edited to add a third condition to "fair triple". With this, it is now less trivial, but still far from true generally. As before, I will characterize the posets $A$ satisfying "good implies fair".

(Note: I just noticed an issue with $\alpha=0$ in the fair definition: the empty family of functions always satisfies the conditions, so the conclusion means that $(A,B,\psi)$ is fair iff $A=\{0\}$. This is probably an unintentional trivial case, so I will assume $\alpha\ne 0$ in the definition of fair.)

$A$ satisfies "good implies fair" if and only if the following configuration does not exist:

  • $\alpha$ a limit ordinal (which we may assume is additively indecomposable, i.e. $\alpha=\omega^\delta$ for some $\delta$)
  • two sequences $\{s_\gamma\mid\gamma<\alpha\}$, $\{t_\gamma\mid\gamma<\alpha\}$ of elements of $A-\{0\}$
  • $s_\beta,t_\beta\not\le t_\gamma$ for $\beta<\gamma<\alpha$
  • $\inf\{s_\gamma\mid\gamma<\alpha\}=0$
  • $\inf\{t_\gamma\mid\gamma<\alpha\}\ne 0$ (this does not mean the $\inf$ exists, only that there is a $t\ne 0$ such that $t_\alpha\ge t$ for all $\gamma<\alpha$)

An example of a poset with this arrangement is the set $\{0,1\}\times[0,\alpha]^*$ with the product order. That is, elements of the form $(i,\gamma)$ where $i=0$ or $1$ and $0\le\gamma\le\alpha$, where $(i,\beta)\le(j,\gamma)$ iff $i\le j$ and $\beta\ge\gamma$. We can take $s_\gamma=(0,\gamma)$ and $t_\gamma=(1,\gamma)$; then the $t$ sequence is decreasing, and $s_\beta\not\le t_\gamma$ for any $\beta,\gamma$. Both sequences have infima but $\inf\{s_\gamma\mid\gamma<\alpha\}=(0,\alpha)=0$ and $\inf\{t_\gamma\mid\gamma<\alpha\}=t$ where $t=(1,\lambda)\ne 0$.

Let $F_\gamma:[0,\gamma]\to A$ for $\gamma<\alpha$ be a counterexample to the fair property. If $\alpha=\beta+1$ is a successor ordinal, then $\inf\{F_\gamma(\gamma)\mid\gamma<\alpha\}\le \inf\{F_\gamma(\beta)\mid\beta\le\gamma<\alpha\}=0$, a contradiction, so $\alpha$ must be a limit.

To show that it suffices to consider additively indecomposable $\alpha$, note that if $\alpha=\delta+\alpha'$ then we can let $F'_\gamma(x)=F_{\delta+gamma}(x+\gamma)$ for $\gamma<\alpha'$, and this will also be a fair counterexample if $F$ is.

Let $t_\gamma=F_\gamma(\gamma)$ and $s_\gamma=F_\gamma(0)$. Since $F$ is a fair counterexample, there exists $t\ne 0$ such that $t\le t_\gamma$ for all $\gamma<\alpha$, and in particular $t_\gamma>0$. If $s_\gamma=0$ then $\psi(F_\gamma(0))=0\ge \psi(F_\gamma(\gamma))$ so $t_\gamma=0$ as well, contradiction. Thus both $s$ and $t$ sequences are nonzero.

If $t_\beta\le t_\gamma$ for some $\beta<\gamma$, then $F_\beta(\beta)\le F_\gamma(\gamma)$ so $\psi(F_\beta(\beta))\le\psi(F_\gamma(\gamma))$ contradicting that $\gamma\mapsto\psi(F_\gamma(\gamma))$ is strictly decreasing.

If $s_\beta\le t_\gamma$ for some $\beta<\gamma$, then $\psi(F_\beta(0))\le \psi(F_\gamma(\gamma))<\psi(F_\beta(\beta))\le \psi(F_\beta(0))$, a contradiction.

Finally, $\inf\{s_\gamma\mid \gamma<\alpha\}=\inf\{F_\gamma(0)\mid \gamma<\alpha\}=0$, so the forbidden configuration obtains.


Conversely, suppose that we are given the forbidden configuration, and let $\alpha$ be minimal. We want to construct a fair counterexample. Let $B=1+[0,\alpha]^*$, which is to say, the elements $0\le\gamma\le\alpha$ ordered in reverse with an additional element $0$ at the bottom. (I will notate these as $0,\alpha^*,\dots,2^*,1^*,0^*$.) The surjection $\psi$ takes $0$ to $0$ and maps $x\ne 0$ to $\beta^*$ if $\beta$ is the least ordinal such that $x\not\le t_\gamma$ for all $\gamma>\beta$; if there are no such ordinals then $\psi(x)=\alpha^*$.

Clearly $\psi(t_\gamma)=\gamma^*$, and $\psi(s_\gamma)\ge\gamma^*$. It is also not hard to show that $\psi$ is increasing, and it is a surjection because $\psi(t)=\alpha^*$. Without loss of generality, we can permute the $s_\gamma$ so that $\psi$ is decreasing (i.e. its underlying ordinal function is weakly increasing), and still maintain the property $\psi(s_\gamma)\ge\gamma^*$.

Now let $F_\gamma(\gamma)=t_\gamma$, and $F_{\gamma+1+\beta}(\gamma)=s_\beta$. (Note that $\gamma+1+\beta<\alpha$ because $\alpha$ is additively indecomposable.) Then $\inf\{F_\gamma(\gamma)\mid\gamma<\alpha\}\ge t\ne0$.

  1. If $x<y<\gamma$, say $x=\gamma+1+\beta$ and $y=\gamma+1+\delta$ with $\delta<\beta$, then $F_\gamma(x)=s_\beta$ and $F_\gamma(y)=s_\delta$, so $\psi(s_\beta)\ge \psi(s_\delta)$ because $\psi$ is decreasing on $s$.

    If $x<y=\gamma$, say $x=\gamma+1+\beta$, then $\psi(s_\beta)\ge \psi(t_\gamma)=\gamma^*$ by construction.

  2. $\inf\{F_\gamma(x)\mid\gamma\le x<\alpha\}=\inf(\{t_\gamma\}\cup\{s_\gamma\mid\gamma<\alpha\})=0$.

  3. If $\beta<\gamma$, then $\psi(F_\beta(\beta))=\psi(t_\beta)=\beta^*>\gamma^*=\psi(t_\gamma)=\psi(F_\gamma(\gamma))$.

Thus $F$ is a fair counterexample.

$\endgroup$
  • $\begingroup$ Thank you! This $B$ is clearly a counterexample : $\psi$ is constant on $F_A(A)$ so the statement is equivalent to the same statement without the mention of $B$ and $\phi$, and this statement is obviously wrong! One way to make the problem relevant (in order to solve d) could be to ask that $\psi\,o\, F$ is not constant. I edit it now, temporally, maybe a same kind of argument make this last hypothesis not sufficient to hope for a true statement or at least a sophisticated counterexample... $\endgroup$ – jcdornano Dec 23 '17 at 9:56
  • $\begingroup$ After a little reflection I think the non constant condition that I added in 3 is to weak and we should be able to build a counterexample with the same idea : I think asking that $B$ is such that for any $x,y\in B$ there exists $z$ such that $x\ne z\ne y$ and $x\leq_B z\leq_B y$ should be more relevant... $\endgroup$ – jcdornano Dec 23 '17 at 10:29
  • $\begingroup$ I added the much stronger 3th condition on $F$, that $\psi \,o\,(y\mapsto F_y(y))$ is strictly decreasing. Then $B$ cannot be a finite set anymore. I originally thought about the problem with this 3th condition, and removed it, to have a stronger statement, but your answer shows that this statement was necessary to get something nice and general that would be true for all good tripllet and solve the motivation as the same time. Maybe this very [1,2,3 oldest+new]-version does the job? $\endgroup$ – jcdornano Dec 24 '17 at 5:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.