Skip to main content
1 of 3
KP Hart
  • 11.4k
  • 38
  • 48

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 prperty 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 $\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 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)$.

KP Hart
  • 11.4k
  • 38
  • 48