3
$\begingroup$

We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $S\cap e \neq \emptyset \neq e \setminus S$.

Let $(P,\leq)$ be a partially-ordered set (poset). For $p\in P$, let $d(p) = \{x\in P: x\leq p\}$. We assign to $(P,\leq)$ the principal downset hypergraph $H_P = \big(P, D(P)\big)$ where $D(P) = \{d(p):p\in P\}$.

Question. Is it consistent with ${\sf (ZF)}$ that there is a poset $(P,\leq)$ such that $H_P$ does not have property ${\bf B}$? And is the opposite also consistent?

(In other words: no matter how you color the elements of $P$ with "red" and "blue", you will get a principal downset $d(p)$ with more than $1$ element such that every element of $d(p)$ has the same color.)

$\endgroup$
15
  • 1
    $\begingroup$ I'm confused. In your blog post (and here), you seem to say that the existence of a non-Ramsey function $c:[\omega]^\omega\to 2$ is equivalent to the question whether the poset $\langle[\omega]^\omega,\subset\rangle$ does not have property B. But isn't this backwards? A non-Ramsey function shows that the poset does have property B, since the coloring provides the set $S$, the non-Ramseyness means that no set is homogeneous, which makes it fulfill property B. Please help me out. $\endgroup$ Commented Jul 21, 2023 at 15:03
  • 1
    $\begingroup$ More specifically, one uses AC to pick representatives from each finite-difference equivalence class, and then let $S$ be the family of sets that have even-difference from their chosen representative. This shows that $[\omega]^\omega$ fulfills property B, not that it omits it. Right? $\endgroup$ Commented Jul 21, 2023 at 15:36
  • 1
    $\begingroup$ You are right! I got it exactly wrong. I am wondering whether there is a poset $(P, \leq)$ such that no matter how you color $P$, you will get a mono-chromatic down-set (with more than $1$ element). Will modify the question! $\endgroup$ Commented Jul 21, 2023 at 15:49
  • 1
    $\begingroup$ But if you are still asking for a poset without property B, there seems no AC angle any longer. I'm not yet sure how to do it even in ZFC, but you ask about ZF. Indeed, I suspect that ZFC proves that every poset has property B, so we shouldn't expect ZF to prove there is a poset without B. Rather, the question should be: is it consistent with ZF that there is a poset without property B? $\endgroup$ Commented Jul 21, 2023 at 15:58
  • 2
    $\begingroup$ I agree with Andrej that this usage is often bad, since people sometimes use it to mean that all three are different, but that isn't actually what it says. A similar problem arises with $p\iff q\iff r$, which people use to mean that all three are equivalent, but one cannot put brackets in to make it have this meaning. $\endgroup$ Commented Aug 9, 2023 at 20:13

2 Answers 2

4
$\begingroup$

Let $M$ be the ordered Mostowski model (T. Jech, The Axiom of Choice, Section 4.5). Its set of atoms, $A$, has a linear order $\prec$ that makes it isomorphic to the rationals. Let $S\in M$ be a subset of $A$; then $S$ is a union of finitely many intervals. So if $S$ has a lower bound then $S$ is disjoint from (many) sets of the form $d(a)$, and if it does not have a lower bound then it contains (many) sets of the form $d(a)$. So in this model we have a linearly ordered set, $A$, such that $H_A$ does not have property $B$.

The Jech-Sochor embedding theorem (Theorem 6.1 in Jech's book) can be used to transfer this to a model of $\mathsf{ZF}$.

$\endgroup$
3
$\begingroup$

The axiom of choice implies that for every partial order $P$ the hypergraph $H_P$ has property $B$.

Let $(P,\le)$ be a partial order. We first claim the following: for every $p\in P$ there is a $q\le p$ such that for all $r\le q$ one has $\bigl|d(r)\bigr|=\bigl|d(q)\bigr|$. This follows from the obvious fact that $x\mapsto\bigl|d(x)\bigr|$ is a monotone map from $P$ to the class of cardinal numbers plus that the negation of our claim would yield a decreasing sequence $\langle x_n:n\in\omega\rangle$ such that $\bigl|d(x_n)\bigr|>\bigl|d(x_{n+1})\bigr|$ for all~$n$, which is impossible as the cardinal numbers are well-ordered.

Let $Q$ be the set of elements of $P$ with the property in the claim. So if $q\in Q$ then $\bigl|d(r)\bigr|=\bigl|d(q)\bigr|$ for all $r\le q$.

If $q\in Q$ then $d(q)=\{q\}$ or $d(q)$ is infinite. Indeed $d(q)$ were finite and $r<q$ then $q\in d(q)\setminus d(r)$ and so $\bigl|d(r)\bigr|<\bigl|d(q)\bigr|$, a contradiction. Note also: if $q_1,q_2\in Q$ are such that $d(q_1)$ is infinite and $d(q_2)=\{q_2\}$ then $d(q_1)$ and $d(q_2)$ are disjoint. Let $A$ be a maximal antichain in $Q$ in the sense that the family $\{d(q):q\in A\}$ is pairwise disjoint and that $A$ is maximal with this property. Divide $A$ into $A_1=\{q\in A:d(q)=\{q\}\}$ and its complement $A_2$.

If $q\in A_2$ then $d(q)$ is infinite and, as is well-known, one can construct a pairwise disjoint family $\{e(r):r\le q\}$ such that $e(r)\subseteq d(r)$ and $\bigl|e(r)\bigr|=\bigl|d(q)\bigr|$ for all $r\le q$. This makes it easy to define $f_q:d(q)\to\{0,1\}$ such that $f_q$ is not constant on any $d(r)$ with $r\le q$. Then $f_2=\bigcup_{q\in A_2}f_q$ defines a function (colouring) on $R=\bigcup_{q\in A_2}d(q)$. Define $f_1:P\setminus R\to\{0,1\}$ as follows: if $q\in A_1$ then $f_1(q)=0$, otherwise $f_1(p)=1$. Then the map $f=f_1\cup f_2$ witnesses property $B$.

Let $p$ be such that $d(p)$ has at least two elements. By maximality of $A$ there is a $q\in A$ such that $d(p)$ intersects $d(q)$.

If $q\in A_1$ then $d(q)\subset d(p)$ and hence $p\notin R$ because $q\notin R$ and $R$ is downward closed. In this case we have $f(p)=1$ and $f(q)=0$.

If $q\in A_2$ then take $r\in d(q)\cap d(p)$. Then $f$ takes on two values on $d(r)$ and hence on $d(p)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .