# The chain covering number of a poset with no infinite antichains

Uri Abraham, Maurice Pouzet

► To cite this version:

Uri Abraham, Maurice Pouzet. The chain covering number of a poset with no infinite antichains. Comptes Rendus. Mathématique, 2023, 361 (G8), pp.1383-1399. 10.5802/crmath.511. hal-04619063

HAL Id: hal-04619063

https://hal.science/hal-04619063v1

Submitted on 19 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Comptes Rendus
Mathématique

Uri Abraham and Maurice Pouzet

The chain covering number of a poset with no infinite antichains

Volume 361 (2023), p. 1383-1399

Published online: 31 October 2023

https://doi.org/10.5802/crmath.511

<figure><img src="image_2.png" /></figure>

This article is licensed under the
CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.
http://creativecommons.org/licenses/by/4.0/
Combinatorics / Combinatoire

# The chain covering number of a poset with no infinite antichains

## *Le nombre de chaînes recouvrant un ensemble ordonné sans antichaînes infinies*

URI Abraham*, a and MAURICE Pouzetb, c

a Math & CS Dept., Ben-Gurion University, Beer-Sheva, 84105 Israel

b ICJ, Mathématiques, Université Claude-Bernard Lyon1, 43 bd. 11 Novembre 1918, 69622 Villeurbanne Cedex, France

c Mathematics & Statistics Department, University of Calgary, Calgary, Alberta, Canada T2N 1N4

E-mails: abraham@math.bgu.ac.il, uriabr@gmail.com (U. Abraham), pouzet@univ-lyon1.fr (M. Pouzet)

**Abstract.** The chain covering number Cov(P) of a poset P is the least number of chains needed to cover P. For an uncountable cardinal v, we give a list of posets of cardinality and covering number v such that for every poset P with no infinite antichain, Cov(P) ≥ v if and only if P embeds a member of the list. This list has two elements if v is a successor cardinal, namely [v]² and its dual, and four elements if v is a limit cardinal with cf(v) weakly compact. For v = ℵ₁, a list was given by the first author; his construction was extended by F. Dorais to every infinite successor cardinal v.

**Résumé.** Le nombre de recouvrement par chaînes d'un ensemble ordonné P (poset), noté Cov(P), est le plus petit nombre de chaînes nécessaires pour recouvrir P. Pour un cardinal donné v, on donne une liste de posets Q de nombre de recouvrement par chaînes v telle que pour tout poset P sans antichaîne infinie, Cov(P) ≥ v si et seulement si P contient une copie d'un membre de la liste. Cette liste est constituée de posets de cardinal v, elle a deux éléments si v est un cardinal successeur, à savoir [v]² et son dual, et quatre éléments si v est un cardinal limite avec cf(v) faiblement compact. Pour v = ℵ₁, une liste a été donnée par le premier auteur; sa construction a été étendue par F. Dorais à tout cardinal successeur infini v.

**2020 Mathematics Subject Classification.** 03E05, 06A07.

**Funding.** This research benefited from the Abkasian seminar running through the Covid epidemic and was supported by LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon within the program "Investissements d'Avenir (ANR-11-IDEX-0007)" operated by the French National Research Agency (ANR).

Manuscript received 3 April 2023, revised 8 June 2023, accepted 9 June 2023.

<footnote>* Corresponding author.</footnote>
# 1. Introduction

Let $P := (V, \leq)$ be an ordered set (poset). The chain covering number $\text{Cov}(P)$ of $P$ is the least number of chains needed to cover $V$.

A famous result due to R.P. Dilworth [5] asserts that for every poset $P$ and integer $n$, $\text{Cov}(P) \geq n$ if and only if $P$ contains an antichain of cardinality $n$.

If $n$ is replaced by $\aleph_0$, then $\text{Cov}(P) \geq \aleph_0$ if and only if $P$ contains either an infinite antichain or the lexicographical sum of antichains of finite unbounded cardinality indexed by the chain of the integers or its reverse (see [11, Lemma 4.1, p. 491]).

M. Perles [13] and independently E. S. Wolk [20] proved that the assumption that every antichain of the poset is finite does not suffice to get a cover of the poset with a countable number of chains (or with any prescribed number $v$ of chains). Their counter-example is the direct product $v \times v$ of an uncountable cardinal $v$ by itself. It turns out that the subset $[v]^2 := \{(\alpha, \beta) : \alpha < \beta < v\}$ has the same properties. This is the main protagonist in this article.

According to F. Dorais [7], F. Galvin conjectured in 1968 that $\text{Cov}(P) \geq \aleph_1$ if and only if $V$ contains a subset $X$ of cardinality $\aleph_1$ such that $\text{Cov}(P \upharpoonright X) = \aleph_1$. It is not known if the truth of this conjecture is consistent with ZFC. The first author proved in [1] that this conjecture holds with the additional hypothesis that $P$ has no infinite antichain. He introduced *Perles posets* having cardinality and chain covering number $\aleph_1$ and proved that if a poset $P$ has no infinite antichain, $\text{Cov}(P) \geq \aleph_1$ if and only if some poset induced by $P$ is isomorphic to a Perles poset. This result was extended by F. Dorais [6] to infinite successor cardinals.

It was conjectured by R. Rado [16] that Galvin's conjecture holds for interval orders (a poset $P$ is an *interval order* if its vertices can be represented by intervals of a chain, a vertex $x$ being strictly before $y$ in the ordering if the interval associated to $x$ is to the left of the interval associated to $y$, these intervals being disjoint). Todorčević [17] proved that Rado's conjecture is consistent with the existence of a supercompact cardinal. In [18, 19], Todorčević proved that large cardinals are indeed necessary to establish the consistency of Rado's conjecture. He also proved that the truth of Rado's conjecture implies that Galvin's conjecture holds for 2-dimensional posets (see [7]).

In this paper, we prove Galvin's conjecture for posets with no infinite antichain and for each cardinal $v$ we give an explicit list of posets of cardinality and chain covering number $v$.

In order to present our result, we need few *notations*. Let $P := (V, \leq)$ be a poset. If $X$ is a subset of $V$, the poset *induced* by $P$ on $X$ is $P \upharpoonright X := (X, \leq \cap X \times X)$. The term *subposet* always refers here to induced subposet. If $P := (V, \leq)$ is a poset, two elements $x, y$ of $V$ are *comparable* if $x \leq y$ or $y \leq x$; otherwise they are *incomparable*. We write $x \perp y$ to say that they are incomparable. For each subset $A$ of $P$, we write $(\perp A)$ or $A^{\perp}$ for the set of vertices of $P$ that are incomparable to every element of $A$. Also, for $p \in P$, $p^{\perp}$ denotes the set of vertices of $P$ that are incomparable to $p$. We define $\downarrow A := \{x \in P : x \leq a$ for some $a \in A\}$; similarly we have $\uparrow A$. If $A = \{a\}$, we denote these sets by $\downarrow a$ and $\uparrow a$. If $a \leq b$ in $P$, we write $[a, b]_P := \{z \in P : a \leq z \leq b\}$ and $[a, b)$ is similarly defined. The *dual* of $P$ is the poset on the same domain equipped with the opposite order, we denote it by $P^*$. We recall that a subset $I$ of $P$ is an *initial segment* of $P$ if $x \leq y$ and $y \in I$ imply $x \in I$; a subset of $P$ is a *final segment* if this is an initial segment of $P^*$, the dual of $P$. Initial and final segments being ordered by set inclusion, if $A$ is a subset of $P$, $\downarrow A$ is the least initial segment of $P$ containing $A$ and $\uparrow A$ is the least final segment of $P$ containing $A$. A subset $A$ of $P$ is *up-directed* if every pair $x, y$ of elements of $A$ has some upper bound $z$ in $A$. An *ideal* of $P$ is any up-directed nonempty initial segment $J$ of $P$.

The *dominance* relation is defined on subsets of $P$: $B$ dominates $A$, written $A \nearrow B$, when $\forall a \in A \forall b \in B (a \leq_P b)$.

A poset $P$ is *embeddable* in a poset $P'$, and we set $P \leq P'$, if $P$ is isomorphic to some subposet of $P'$. Two posets $P$ and $P'$ are *equimorphic* if each is isomorphic to a subposet of the other.
Clearly, if $P \leq P'$ then $\mathrm{Cov}(P) \leq \mathrm{Cov}(P')$, while $\mathrm{Cov}(P) = \mathrm{Cov}(P^*)$. A subset $A$ of $P$ is cofinal in $P$ if every element of $P$ is majorized by some element $a \in A$, i.e., $\downarrow A = P$. The cofinality of $P$ is the least cardinality of a cofinal subset of $P$, we denote it by $\mathrm{cf}(P)$. Accordingly, if $v$ is an ordinal, we denote by $\mathrm{cf}(v)$ the cofinality of $v$. For a set $X$ of ordinals, $\sup X$ (often notated $\bigvee X$) is the supremum of $X$.

**Definition 1.** Let $v$ be an infinite ordinal, we set $[v]^2 := \{(\alpha, \beta) : \alpha < \beta < v\}$, and order that set by setting $(\alpha, \beta) \leq (\alpha', \beta')$ if $\alpha \leq \alpha'$ and $\beta \leq \beta'$. As a subset of the direct product $v \times v$, this poset is the upper half of $v \times v$ ordered componentwise.

Our main result asserts:

**Theorem 2.** Let $v$ be an uncountable cardinal and $P$ be a poset with no infinite antichain.

(1) If $v$ is a successor cardinal, i.e., $v = \kappa^+$, then $\mathrm{Cov}(P) \geq v = \kappa^+$ if and only if $P$ or $P^*$ contains a copy of $[\kappa^+]^2$.

(2) If $v$ is an uncountable limit cardinal, then $\mathrm{Cov}(P) > v$ if and only if $P$ or $P^*$ contains a poset $Q$ of the form $\sum_{a \in C} Q_a$, where $C$ is a chain of cardinality $\mathrm{cf}(v)$, $Q_a \cong [\kappa_a^+]^2$ and $(\kappa_a^+)$$_{a \in C}$ is a family of distinct cardinals that satisfies $\sup\{\kappa_a^+ : a \in C\} = v$.

**Comments about item (1).** In [1], the first author introduced a collection $\mathbf{P}(\omega_1, \omega_1)$ of posets of size $\aleph_1$ and proved that these posets cannot be covered by less that $\aleph_1$ chains (Proposition 1.15) and furthermore that a poset with no infinite antichain can be covered by less than $\aleph_1$ chains if and only if it does not embed a member of $\mathbf{P}(\omega_1, \omega_1)$ (Theorem 2.1). In [6] F. Dorais extended this result to successor cardinals. For such a cardinal, say $\kappa^+$, he introduced posets of *Perles type* and showed that a poset with no infinite antichain can be covered by at most $\kappa$ chains if and only if it does not embed a *Perles type* poset of cardinality $\kappa^+$. Item (1) is equivalent to the fact that each of these posets embeds a copy of $[\kappa^+]^2$ or its dual. This fact was not stated in [1] nor in [6]. Since this is a fact of independent interest, we give a proof in Subsection 2.1.

**Comments about item (2).** Let $\lambda := \mathrm{cf}(v)$. Suppose that $\lambda$ is *weakly compact*, that is every chain of cardinality $\lambda$ contains either a chain of order type $\lambda$ or of its dual. Then, in item (2), we may replace the chain $C$ by $\lambda$ or its dual. If we compare the posets $Q$ by embeddability, we get only four nonequimorphic posets, namely $\sum_{\alpha \in \lambda}[\kappa_{\alpha}^{+}]^2$, $\sum_{\alpha \in \lambda^*}[\kappa_{\alpha}^{+}]^2$, and their duals, where the sequence $(\kappa_{\alpha})_{\alpha < \lambda}$ is increasing and with limit $v$. Two such families $(\kappa_{\alpha}^{+})_{\alpha \in \lambda}$ give equimorphic posets.

If $\lambda$ is not weakly compact, then among the posets we obtain in item (2), some cannot be expressed as a well-ordered or reversely well ordered chain of type $\lambda$. For an example, suppose that $C$ is the chain $\mathbb{R}$ of real numbers. Let $c$ be a bijective map from $\mathbb{R}$ onto $\kappa := 2^{\aleph_0}$ and $f$ be a strictly increasing map from $\kappa$ in the collection of successor cardinals. If $A$ is any subchain of $C$ set $Q_A := \sum_{a \in A}[f(c(a))]^2$. Then $\mathrm{Cov}(Q_A) = \sup\{f(c(a)) : a \in A\}$. Since a well-ordered or reverse well-ordered subchain $A$ of $\mathbb{R}$ is at most countable, and the cofinality of $2^{\aleph_0}$ is uncountable, $\mathrm{Cov}(Q_A) < \mathrm{Cov}(Q_C)$.

**Problem 3.** Let $v$ be an uncountable limit cardinal such that $\lambda := \mathrm{cf}(v)$ is not weakly compact, find the least number $G(v)$ of posets $Q$ needed in item (2)?

An easy consequence of Item (1) of Theorem 2 is about the notion of indivisibility. A poset $P$ is *indivisible* if for every partition of its domain in two parts, $P$ embeds into a restriction of $P$ to one of these parts; more generally, $P$ is *$v$-indivisible* for some cardinal $v$ if for every partition of $P$ into less than $v$ parts $P$ embeds in a restriction of $P$ to some part. [9] contains several results about the indivisibility of posets and relations.

**Corollary 4.** If $v$ is an infinite successor cardinal, then $[v]^2$ is < $v$-indivisible.
Indeed, let $(A_\alpha)_{\alpha<\kappa}$ where $\kappa^+ = \nu$ be a partition (or a covering) of $[\nu]^2$. If the covering number of each part is at most $\kappa$ then the covering number of $[\nu]^2$ is at most $\kappa$. But this is impossible, hence the covering number of some part is at least $\nu$. From Item 1 of Theorem 2, this part embeds $[\nu]^2$.

Using Lemma 19 the conclusion extends to regular $\nu$. We do not know if $[\nu]^2$ is $< \text{cf}(\nu)$-indivisible. Extension of these results to $[\nu]^n$ need to be considered. This paper was motivated by a question of Abraham, Bonnet, Kubis [2] about two well studied notions in the theory of ordered sets, namely well quasi orders (w.q.o) and better quasi orders (b.q.o), ([9] for reference). They ask whether any w.q.o is a countable union of b.q.o subposets. A positive answer would imply that any $\omega$-indivisible w.q.o is b.q.o.

We present two proofs of Theorem 2. They have a common part, which is a reduction to a special case (Theorem 27). With that reduction, Item (2) reduces to Item (1). Our first proof of Item (1) is based on the definition of the class $\mathcal{P}(\kappa)$ of posets. We prove that any poset in that class embeds $[\nu]^2$ or its dual (Theorem 14). Then we obtain the conclusion of Item 1 by proving that a poset not coverable by $\nu$ chains embeds a poset in $\mathcal{P}(\nu^+)$ (Theorem 14). This latter fact was known for $\aleph_1$-Perles posets [1]. Our second proof relies on a characterization of posets containing $[\nu]^2$ in terms of chains of ideals (Lemma 19) and on a proof that a poset not coverable by $\nu$ chains contains such a chain of ideals. This latter proof relies on the notion of purity introduced in [3]. The reason for including two proofs of the same theorem is that each proof touches on some ideas that we found interesting and which could be useful for other investigations in this field. The reader may choose to read just one proof: read the common part of the two proofs, and then continue with either section.

## 2. Basic tools

Some fundamental tools that are used in the paper are the Erdös–Dushnik–Miller partition theorem [8], a description of cofinal subsets of posets with no infinite antichains due to the second author [15] (see [9, 10, 12]) and the notion of purity with [3, Theorem 24].

**Theorem 5 (Erdös–Dushnik–Miller).** For every infinite cardinal $\lambda$, every graph with $\lambda$ vertices contains either an infinite independent set or a complete subgraph on $\lambda$ vertices. (In arrow notation this is written $\lambda \to (\aleph_0, \lambda)^2$.)

A poset with no infinite antichains is a union of finitely many up-directed subsets (R. Bonnet [4], see also [9, 4.7.2 p. 124]).

The cofinality theorem of Pouzet (see [9]) states:

**Theorem 6.** Every poset $P$ with no infinite antichain has a cofinal subset $A$ which decomposes in a finite union $A_1 \cup \cdots \cup A_k$ with no comparabilities between elements of $A_i$ and $A_j$ for every $i \neq j$, and such that the $<_P$ order on each $A_i$ is isomorphic to a finite product $\alpha_{1,i} \times \cdots \times \alpha_{n_i,i}$ of regular distinct cardinals.

A consequence (in fact an equivalent statement) is this:

**Theorem 7 (Pouzet).** Every up-directed poset $P$ with no infinite antichain has a cofinal subset $A$ which is order isomorphic to a finite product $\alpha_1 \times \cdots \times \alpha_n$ of regular distinct ordinals.

**Definition 8 (Purity).** A poset $P$ is pure if every proper initial segment $I$ of $P$ is strictly bounded above (that is, some $x \in P \setminus I$ dominates $I$).

This condition amounts to the fact that every non cofinal subset of $P$ is strictly bounded above (indeed, if a subset $A$ of $P$ is not cofinal, then $\downarrow A \neq P$ hence from purity, $\downarrow A$, and thus $A$, is strictly bounded above. The converse is immediate).
A pure poset is necessarily up-directed: Given $x, y \in P$ there is $z$ such that $x, y \le z$. If $x$ and $y$ are comparable, this is evident. So we assume that $x \perp y$ and then $x \in I = P \upharpoonright y$. As $I \ne P$ is a proper initial segment there is $z \in \upharpoonright y$ a bound of $I$. Hence $x, y \le z$. Hence a pure poset with infinite cofinality has no maximal element. Indeed, if $x \in P$, then for some $y \in P$, $y \not\le x$ (or else the cofinality of $P$ is 1) and there is $z$ with $x, y \le z$. Necessarily $x < z$.

We extract the following result from [3, Theorem 24].

**Theorem 9.** Let $P$ be a poset with uncountable cofinality $v$. Then $P$ is pure if and only if $P$ is a lexicographical sum $\sum_{a \in v} P_a$ with arbitrary components $P_a$.

**Proof.** To prove that the lexicographical sum of posets is pure does not require that the sum is over a regular $v$. It suffices for the index ordering to be any chain with no maximum. If $P = \sum_{a \in K} P_a$ where $K$ is a chain with no maximum, then $P$ is clearly pure, because any proper initial segment occupies only a bounded in $K$ set of indexes.

For the other direction, assume that $P$ is pure with uncountable cofinality $v$. Let $\{b_\alpha : \alpha < v\}$ be cofinal in $P$. We are going to construct by induction on $\alpha < v$ a strictly increasing sequence $(x_\alpha)_{\alpha < v}$ such that $b_\alpha \le x_\alpha$ (thereby assuring that the constructed sequence is also cofinal). The final segment $S_\alpha = \{p \in P : \forall \zeta < \alpha (x_\zeta \le p)\}$ is defined to satisfy for every $\alpha < v$ that

$$P \setminus S_{\alpha} \upharpoonright S_{\alpha+1}. \qquad (1)$$

The definition of $S_\alpha$ implies that: (1) $\alpha < \alpha' \to S_{\alpha'} \subseteq S_\alpha$. (2) If $\delta < v$ is a limit then $S_\delta = \bigcap \{S_\zeta : \zeta < \delta\}$. (3) $S_{\alpha+1} = \{p \in P : x_\alpha \le p\} = (\upharpoonright x_\alpha)$. (4) $S_0 = P$ and $S_v = \emptyset$.

Start by defining $x_0 \in P$ as any member of $P$ such that $b_0 \le x_0$.

(1) Suppose that $x_\alpha$ is defined, then find $x_{\alpha+1}$ that strictly dominate the proper initial segment $P \upharpoonright x_\alpha$. In fact, we add the requirement that $b_{\alpha+1} \le x_{\alpha+1}$ (which is possible because a pure poset is up-directed). Since $P \upharpoonright x_\alpha \upharpoonright x_{\alpha+1}$, we get that $P \setminus S_{\alpha+1} \upharpoonright S_{\alpha+2}$.

(2) Suppose now that $\alpha < v$ is a limit ordinal and $(x_\zeta : \zeta < \alpha)$ is defined. Since $\alpha < v = \text{cf}(P)$, $I = \downarrow\{x_\zeta : \zeta < \alpha\} \ne P$, and hence $I$ is strictly bounded in $P$. That is, $J = P \setminus S_\alpha$ is a proper initial segment of $P$. Define $x_\alpha$ that strictly dominates $P \setminus S_\alpha$, and suppose additionally that $x_\alpha$ dominates $b_\alpha$. So $P \setminus S_\alpha \upharpoonright x_\alpha \upharpoonright S_{\alpha+1}$. Thus (1) holds also when $\alpha$ is a limit ordinal.

This ends the definition of the strictly increasing and cofinal sequence $(x_\alpha)_{\alpha < v}$.

Define the rings $R_\alpha = S_\alpha \setminus S_{\alpha+1}$ for $\alpha < v$. We get a partition of $P$, $P = \bigcup_{\alpha < v} R_\alpha$. It follows from the definitions that $\alpha + 2 \le \beta < v \to R_\alpha \upharpoonright R_\beta$. (Indeed, $R_\alpha = S_\alpha \setminus S_{\alpha+1} \subseteq P \setminus S_{\alpha+1} \upharpoonright S_{\alpha+2}$, and $R_\beta \subseteq S_\beta \subseteq S_{\alpha+2}$. Thus $R_\alpha \upharpoonright R_\beta$.) Redefine the rings by setting for every limit ordinal $\delta < v$, $\mathcal{R}_\delta = \bigcup_{n \in \omega} R_{\delta+n}$, then we get a coarser partition $P = \bigcup_{\lim_{\delta < v} \mathcal{R}_\delta}$ such that if $\delta_1 < \delta_2$ then $\mathcal{R}_{\delta_1} \upharpoonright \mathcal{R}_{\delta_2}$. Hence $P = \sum_\delta \mathcal{R}_\delta$ as required. $\square$

## 2.1. $\mathcal{P}(\kappa)$, a class of $\kappa$-Perles posets

As we saw, for any cardinal $v$, $[v]^2$ is not a union of less than $v$ chains. This leads to the following definition.

**Definition 10.** For an uncountable cardinal $v$, a poset $P$ with only finite antichains is said to be of $v$-Perles type if it is not a union of less than $v$ chains.

Thus, $[v]^2$ and its dual are examples of $v$-Perles type posets. For regular $\kappa$, we define a class of poset containing only $\kappa$-Perles types which will be found out to be the class of all $\kappa$-Perles types.

**Definition 11.** For a regular uncountable cardinal $\kappa$, a poset is in the class $\mathcal{P}(\kappa)$ if it contains a subposet $P$ whose universe, $|P|$, is $\kappa$ (or a subset of $\kappa$) so that $P$ carries both the partial ordering $<_P$
and the ordinal ordering $<$, and there is a function $F : |P| = \kappa \to \kappa$ whose range is $\kappa$, and is such that the following holds with respect to the the incomparability relation $\perp$ on $P$:

(1) For every $\alpha \in \kappa$, $|F^{-1}\{\alpha\}| = \kappa$,

(2) If $\alpha_1 < \alpha_2 < \kappa$, $\xi_1 \in F^{-1}\{\alpha_1\}$ and $\xi_2 \in F^{-1}\{\alpha_2\}$ are such that $\xi_1 > \xi_2$, then $\xi_1 \perp \xi_2$.

**Remark 12.** If $P = (\kappa, <, <_P) \in \mathcal{P}(\kappa)$ and $Q$ is a subposet of $P$ such that for every $\alpha \in F^Q, F^{-1}\{\alpha\}$ has cardinality $\kappa$, then $Q \in \mathcal{P}(\kappa)$ as well. (Collapse the universe of $Q$ so that it becomes $\kappa$, and likewise collapse $F''Q$.)

**Claim 13.** Let $\kappa$ be a regular uncountable cardinal.

(1) If $P \in \mathcal{P}(\kappa)$ then $P^* \in \mathcal{P}(\kappa)$ as well, where $P^*$ denotes the dual ordering of $P$.

(2) $P$ in $\mathcal{P}(\kappa)$ is not covered by $<\kappa$ chains.

(3) $[\kappa]^2$ (and its dual) are in the $\mathcal{P}(\kappa)$ family of posets.

The following notes indicate the proofs.

(1) Item (1) is obvious since the definition of $\mathcal{P}(\kappa)$ does not mention the ordering of $P$, only the comparability relation is involved.

(2) For item (2), let $F : P = \kappa \to \kappa$ be a witness for $P \in \mathcal{P}(\kappa)$. Suppose that $P$ is covered by $\kappa_0 < \kappa$ chains $\{P_i : i < \kappa_0\}$. Then for any $\alpha < \kappa$, $F^{-1}\{\alpha\}$ has an intersection of size $\kappa$ with (at least) one of the chains $C_i(\alpha)$ (by regularity of $\kappa$). For a set $S$ of size $\kappa$ there is a fixed chain $C_i$ such that for any $\alpha \in S$, $i = i(\alpha)$. This is impossible: take $\alpha_1 < \alpha_2$ in $S$, take any $\xi_2 \in C_i \cap F^{-1}\{\alpha_2\}$, and then take $\xi_1 \in C_i \cap F^{-1}\{\alpha_1\}$ such that $\xi_1 > \xi_2$. Then $\xi_1 \perp \xi_2$ shows that they cannot be in the same chain.

(3) For Item (3), prove that the poset $[\kappa]^2$ is in $\mathcal{P}(\kappa)$: namely there exist an isomorphic copy $P$ of $[\kappa]^2$ whose universe is $\kappa$ and a function $F$ that satisfy Definition 11. Let $<_R$ be the right-order lexicographical ordering on $[\kappa]^2$ defined by $\langle\alpha, \beta\rangle < \langle\alpha', \beta'\rangle$ iff $\beta < \beta'$ or $\beta = \beta' \wedge \alpha < \alpha'$. The order-type of $[\kappa]^2$ in $<_R$ is $\kappa$ in its ordinal ordering $<$. Let $p : (\kappa, <) \to ([\kappa]^2, <_R)$ be the order-isomorphism. We notate $p(\xi) = (\alpha_\xi, \beta_\xi)$. Thus the poset $[\kappa]^2$ induces an isomorphic copy $P = (\kappa, <_P)$ on $\kappa$ by setting $\xi \le_P \xi'$ iff $\alpha_\xi \le \alpha_{\xi'} \wedge \beta_\xi \le \beta_{\xi'}$. Define $F(\xi) = \alpha_\xi$. The function $F$ is used to show that $[\kappa]^2 \in \mathcal{P}(\kappa)$. Define a closed unbounded subset $C \subset \kappa$ such that every $\delta \in C$ has the following property.

If $\delta \in C$, then $\xi < \delta \to \alpha_\xi, \beta_\xi < \delta$ and, for every $\alpha < \beta$ in $\delta$, there is $\xi < \delta$ such that $(\alpha, \beta) = (\alpha_\xi, \beta_\xi)$.

Now define a subset $X \subset \kappa$ such that for every $\delta \in C$, $X \cap \{\delta, \delta'\}$ is a singleton, and for every $\alpha < \kappa$, $\{\xi \in X : \alpha = \alpha_\xi\}$ is unbounded in $\kappa$. Then $P \upharpoonright X$ and $F : P \upharpoonright X \to \kappa$ show that $[\kappa]^2 \in \mathcal{P}(\kappa)$.

**Theorem 14.** Let $\kappa$ be a regular uncountable cardinal. If $P$ has only finite antichains (P is a FAC poset) then $P$ embeds $[\kappa]^2$ iff $P$ is $\mathcal{P}(\kappa)$.

**Proof.** We noted above that $[\kappa]^2$ is in $\mathcal{P}(\kappa)$. Suppose that $P \in \mathcal{P}(\kappa)$ where $P = (\kappa, <_P)$ and $F : P = \kappa \to \kappa$ is a surjection such that conditions (1) and (2) of Definition 11 hold. We have to prove that $P$ or its dual contain a copy of $[\kappa]^2$. Given $\alpha \in \kappa$ apply the Dushnik–Miller partition theorem, $\kappa \to (\kappa, \omega)^2$, to the set $[F^{-1}\{\alpha\}]^2$ and to the coloring that gives to $\{\xi_1, \xi_2\} \in [F^{-1}\{\alpha\}]^2$ one color if $\xi_1$ and $\xi_2$ are comparable in $<_P$ and another color if they are not. Since there is no infinite antichain, we get a homogeneous set $C_\alpha \subseteq F^{-1}\{\alpha\}$ for the comparability colour which is a $<_P$-chain of cardinality $\kappa$.

An element $\xi \in C_\alpha$ is exceptional (in $C_\alpha$) if the sets $\{\eta \in C_\alpha : \eta \le_P \xi\}$ and $\{\eta \in C_\alpha : \xi \le_P \eta\}$ are both of cardinality $\kappa$.

**Claim 15.** If $\xi_1 \in C_{\alpha_1}$ and $\xi_2 \in C_{\alpha_2}$ are both exceptional in their chains (where $\alpha_1 \neq \alpha_2$) then $\xi_1 \perp \xi_2$.
**Proof.** Suppose on the contrary that $\xi_1$ and $\xi_2$ are comparable. For example, suppose that $\alpha_1 < \alpha_2$ and $\xi_1 \le_P \xi_2$ (any other pattern works as well). Since $\xi_1$ is exceptional in $C_{\alpha_1}$, there are $\kappa$ members $\eta$ of $C_{\alpha_1}$ such that $\eta \le_P \xi_1$. Take such $\eta \in C_{\alpha_1}$ that is above $\xi_2$. Then $\eta \perp \xi_2$. But this contradicts $\eta \le_P \xi_1 \le_P \xi_2$. $\square$

This claim and the finite antichain condition of $P$ imply that there is only a finite number of chains with an exceptional member. Throwing out this finite number of chains $C_\alpha$, we may assume that no chain contains an exceptional member.

We say that $\xi \in C_\alpha$ is of type I if $|\{\eta \in C_\alpha : \eta \le_P \xi\}| < \kappa$. And we say that $C_\alpha$ itself is of type I if it contains $\kappa$ members that are all of type I. In this case, and since $\kappa$ is regular, the set of members of $C_\alpha$ of type I contains a subset $D_\alpha \subset C_\alpha$ of order-type $\kappa$ such that for $\xi_1 < \xi_2$ in $D_\alpha$, $\xi_1 <_P \xi_2$.

If $C_\alpha$ is not of type I then it has $< \kappa$ members of type I, and for each of the remaining members $\xi$ that are not of type I, $|\{\eta \in C_\alpha : \eta \le_P \xi\}| = \kappa$. But $\xi$ is not exceptional and hence $|\{\eta \in C_\alpha : \xi \le_P \eta\}| < \kappa$. In this case, we can find $D_\alpha \subset C_\alpha$ of cardinality $\kappa$ such that for all $\xi_1, \xi_2 \in D_\alpha$, $\xi_1 < \xi_2 \to \xi_2 <_P \xi_1$.

Fixing such sets $D_\alpha$, there is a set $R \subseteq \kappa$ of cardinality $\kappa$ such that for every $\alpha \in R$, either $<_P$ is strictly increasing on $D_\alpha$, or else for every $\alpha \in R <_P$ is strictly decreasing. In the first case we will get an embedding of $[\kappa]^2$ into $P$, and in the second case an embedding into $P^*$. By symmetry of the argument we may suppose that for every $\alpha \in R$, $<_P$ is increasing over $D_\alpha$.

**Claim 16.** If $\alpha_1 < \alpha_2$ are in $R$, and $\zeta_i \in D_{\alpha_i}$ for $i=1,2$ are $\le_P$-comparable, then $\zeta_1 <_P \zeta_2$.

**Proof.** If it is not the case that $\zeta_1 <_P \zeta_2$, then $\zeta_2 <_P \zeta_1$ since $\zeta_1, \zeta_2$ are comparable. Pick $\zeta'_1 \in D_{\alpha_1}$ such that $\zeta_1, \zeta_2 < \zeta'_1$ (namely as ordinals). Then $\zeta_2 \perp \zeta'_1$, but $\zeta_2 <_P \zeta_1 <_P \zeta'_1$ contradicts incomparability. $\square$

By Remark 12, we may assume that $P = \kappa = \bigcup_{\alpha \in R} D_\alpha$ and $F : \kappa \to \kappa$ is a surjection which satisfies definition 11.

Thus we have the following situation. The universe of $P$ is $\kappa$ and a surjection $F : \kappa \to \kappa$ exists such that:

(P1) For every $\alpha \in \kappa$, $D_\alpha = F^{-1}\{\alpha\}$ is unbounded in $\kappa$, and, for every $\xi_1 < \xi_2$ in $D_\alpha$, $\xi_1 <_P \xi_2$.

(P2) If $\alpha_1 < \alpha_2 < \kappa$, $\xi_1 \in D_{\alpha_1}$, $\xi_2 \in D_{\alpha_2}$ and $\xi_1, \xi_2$ are comparable, then $\xi_1 <_P \xi_2$ (see Claim 16).

On the set $\mathcal{D} = \{D_\alpha : \alpha < \kappa\}$ define a partial ordering relation $<_\beta$ by $D_\alpha <_\beta D_\beta$ iff $\forall x \in D_\alpha \exists y \in D_\beta x <_P y$. We have just seen that

$$ \text{if } \alpha < \beta < \kappa \text{ then } \neg (D_{\beta} <_{\alpha} D_{\alpha}). \qquad (2) $$

(In fact, by Claim 16, if $b \in D_\beta$ and $a \in D_\alpha$ then it is not the case that $b <_P a$.)

**Claim 17.** Relation $<$ is a well-quasi-ordering on $\mathcal{D}$.

**Proof.** Let $\langle D_{\alpha_0}, D_{\alpha_1}, \dots \rangle$ be an infinite sequence from $\mathcal{D}$. We may assume that the ordinals $\alpha_k$ are increasing with $k \in \omega$. We have to show that $D_{\alpha_i} <_\beta D_{\alpha_j}$ for some $i < j$. Suppose on the contrary that $\neg (D_{\alpha_i} <_\beta D_{\alpha_j})$ whenever $i < j$. Thus there is $x(i, j) \in D_{\alpha_i}$ such that for every $y \in D_{\alpha_j}$ it is not the case that $x(i, j) <_P y$. Since $\kappa$ is regular uncountable, there is $x_i \in D_{\alpha_i}$ such that $x_i > x(i, j)$ for every $j > i$. But then $\{x_i : i \in \omega\}$ is an infinite antichain in $P$ (by Claim 16 and since $x_i \not< x_j$ when $i < j$). $\square$

Again we use the Erdös–Dushnik–Miller partition theorem $\kappa \to (\kappa, \omega)$, but now on the set of chains $\mathcal{D}$ which forms a w.q.o. If $D_\alpha, D_\beta$ are two chains in $\mathcal{D}$, color the pair in the comparability-incomparability colours of the $<$ ordering. Since there is no infinite set of incomparable members of a wqo, we have a chain of cardinality $\kappa$. In fact, it follows from (2) that the order-type of this
chain is $κ$. So for some set $S ⊆ κ$ of order-type $κ$, if $α_1 < α_2$ are in $S$, then $D_{α_1} < D_{α_2}$. We may assume that $S = κ$, and to the two properties (P1) and (P2) we add (P3):

(P3) If $α_1 < α_2 < κ$ then $D_{α_1} < D_{α_2}$

The following claim concludes the proof of Theorem 14.

**Claim 18.** *Properties* (P1), (P2), (P3) *entail that* $[κ]^{2} \hookrightarrow P$.

**Proof.** Define an order embedding $G : [κ]^2 \to P$, so that $G(α, β) \in D_α$ for every $α < β < κ$. By induction on $β < κ$ we define $G \upharpoonright [β]^2$. Suppose that $G$ is defined on $[β_0]^2$ for some $β_0 < κ$. We then define $G(α, β_0)$ for $α < β_0$ by induction on $α$. Suppose $α_0 < β_0$ is such that for every $α < α_0$, $G(α, β_0)$ is defined. Let $E$ denote the domain of the function $G$ at this stage of the construction, that is $E = [β_0]^2 \cup α_0 \times \{β_0\}$. $E$ contains no pair that is above $(α_0, β_0)$ in the $[κ]^2$ ordering, and so $E$ is partitioned into a set $E_<$ consisting of those members of $E$ that are below $(α_0, β_0)$, and a set $E_⊥$ consisting of those members of $E$ that are incomparable with $(α_0, β_0)$. For $G(α_0, β_0)$ we have to pick $p \in D_{α_0}$ that is above all members of $G''E_<$ and is incomparable with all members of $G''E_{Inc}$. Observe that the cardinality of $E$ is $< κ$ and that for $α < β < κ$:

(1) $(α, β) \in E_<$ iff $α < α_0 \wedge β \leq β_0$ or $α = α_0 < β < β_0$, and

(2) $(α, β) \in E_⊥$ iff $α_0 < α < β < β_0$.

Recall that if $α < α_0$ then for every $ξ \in D_α$, $ξ <_P ζ$ for some $ζ \in D_{α_0}$. And if $α_0 < α$ and $ζ \in D_{α_0}$ then $ζ$ is incomparable with $ζ' \in D_α$ whenever $ζ > ζ'$. Thus $ζ \in D_{α_0}$ that is high enough can be found to satisfy the requirements for $ζ = G(α_0, β_0)$. This ends the proof of Theorem 14. □

Another interesting characterization of posets $P$ such that $P$ of the dual $P^*$ embeds $[κ]^2$ is in the following theorem. Recall that an ideal $I$ in a poset $P$ is an up-directed initial segment of $P$.

**Theorem 19.** *Let $κ$ be a regular cardinal and $P$ be a poset. Then $P$ or its dual contains $[κ]^2$ if and only if $P$ or its dual contains a poset that is the union of a strictly increasing chain $(J_α)_{α<κ}$ of unbounded ideals, each containing a cofinal chain of order-type $κ$.*

**Proof.** Consider $[κ]^2$ and for every $α < κ$ define $I_α = \{(τ, β) : τ ≤ α$ and $τ < β < κ\}$. Then $I_α$ is a proper ideal of $[κ]^2$, and $[κ]^2$ is the union of these ideals. In each $I_α$ the chain $(α, β)$, $α < β < κ$ is cofinal.

Now suppose that $P$ contains a poset that satisfies the condition. For every ideal $J_α$ let $C_α \subset J_α$ be a cofinal subset of order-type $κ$. Note that if $α_1 < α_2 < κ$ then for every $x \in J_{α_1} \subset J_{α_2}$ there is $y \in C_{α_2}$ such that $x <_P y$ (because $J_{α_1} \subset J_{α_2}$). Also, for every $α < κ$ there is a bounded set of points in $C_α$ that are in $J_{α'}$ for some $α' < α$, and hence by trimming $C_α$ we may assume for every $α' < α$ that if $x \in J_{α'}$ and $y \in C_α$ are comparable then the only possible relation is $x <_P y$. Also, since $C_α$ is not bounded in $P$, if $α < β < κ$ then for every $y \in C_β$ there is a cofinal segment of members of $C_α$ that are incompatible with $y$.

We define an embedding from $[λ]^2$ in $P$ such that $f(α, β) \in J_α$ for every $α < β < λ$. Order $[λ]^2$ lexicographically according to the second difference, that is $(α'β') < (α, β)$ if either $β' < β$ or $β = β'$ and $α' < α$. The order-type of $[κ]^2$ under $<$ is $κ$. By induction on $β \in κ$ define $f(α, β) \in C_α$ for every $α < β$. Suppose that $β < κ$ and that $f$ is defined on all of $[β]^2 = \{(ζ, ξ) : ζ < ξ < β\}$. We define $f(α, β) \in C_α$ by induction on $α < β$.

For that, suffices to show that $J_α$ contains some $x_{α,β}$ larger than $f(α, β')$ for all $α < β' < β$ and larger than $f(α', β)$ for all $α' < β$, and yet $x_{α,β}$ has to be incompatible to every $f(α^*, β^*)$ when $α < α^* < β^* < β$. Since the number of these restrictions is less than $κ$, such $x_{α,β}$ can be found and defining $f(α, β) = x_{α,β}$ works. One checks that the map $f$ is an embedding. □
So the following statements about a FAC poset $P$ and regular cardinal $\kappa$ are equivalent: (1) $P$ contains a poset in the class $\mathcal{P}(\kappa)$, (2) $P$ contains $[\kappa]^2$ or the dual of $[\kappa]^2$, (3) $P$ or $P^*$ contains a subposet $Q$ that is the union of an increasing chain of length $\kappa$ of ideals, unbounded in $Q$ and each containing a cofinal chain of order-type $\kappa$.

### 3. Proofs of Theorem 2

The “if” directions of both items (1) and (2) of the theorem are easily obtained, since $\mathrm{Cov}([\kappa^+]^2 = \kappa^+$ for any infinite cardinal $\kappa$.

(1) In case $v = \kappa^+$ is a successor cardinal and $Q := [\kappa^+]^2$ or its inverse is a subposet of $P$, then $\mathrm{Cov}(P) \ge \kappa^+$.

(2) Suppose that $v$ is a limit uncountable cardinal and $P$ or its inverse $P^*$ contains a subposet $Q = \sum_{a \in C} Q_a$, where $C$ is a chain of cardinality $\mathrm{cf}(v)$, $Q_a := [\kappa_a^+]^2$ and $(\kappa_a^+)$$_{a \in C}$ is a family of cardinals such that $\sup\{\kappa_a^+ : a \in C\} = v$. Then $\mathrm{Cov}(Q) = v$, because otherwise $\mathrm{Cov}(Q) = \kappa < v$ despite the fact that $P$ contains a copy of $[\kappa_a^+]^2$ for some $\kappa_a^+ > \kappa$.

Thus the main burden of the proof of Theorem 2 is in the “only if” direction.

It suffices to prove the seemingly weaker version of Theorem 2 in which an additional assumption is made (equation (3)).

**Theorem 20 (Theorem 2").** Let $P$ be a poset with no infinite antichain and let $v$ be an uncountable cardinal such that $\mathrm{Cov}(P) \ge v$ and

$$ \forall p \in P \ \mathrm{Cov}(p^{\perp}) < v. \qquad (3) $$

(1) If $v$ is a successor cardinal, i.e., $v = \kappa^+$, then $P$ or its dual $P^*$ contains a copy of $[\kappa^+]^2$.

(2) If $v$ is a limit cardinal then $P$ or its dual $P^*$ contains a poset $Q$ of the form $\sum_{a \in C} Q_a$, where $C$ is a chain of cardinality $\mathrm{cf}(v)$, $Q_a \cong [\kappa_a^+]^2$ and $(\kappa_a^+)$$_{a \in C}$ is a family of distinct successor cardinals, such that $\sup\{\kappa_a^+ : a \in C\} = v$.

**Lemma 21.** For every uncountable cardinal $v$, if Theorem 2* holds for $v$ then Theorem 2 also holds for $v$, so that these two forms are equivalent.

Assume the statement of Theorem 2*, and let $P$ be a FAC poset such that $\mathrm{Cov}(P) \ge v$. The antichains of $P$ form a well-founded relation under the inverse inclusion relation, and we let $P_0$ be a subposet of $P$ with the least height of its antichains such that still $\mathrm{Cov}(P_0) \ge v$. Then for every $p \in P_0$, the antichain height of $P_0 \cap p^{\perp}$ is smaller than the antichain height of $P_0$, and hence $\mathrm{Cov}(P_0 \cap p^{\perp}) < v$. Thus Theorem 2* can be applied to $P_0$. So $P_0$ contains subposets as required by item (1) or (2), and these are subsets of $P$ which prove that Theorem 2 follows.

Our plan is to first define an equivalence relation $\sim$ on $P$, and get some information on the covering number of the equivalence classes of $\sim$ (in Lemma 23). Then, we formulate a reduction theorem, Theorem 27, which seems to be weaker than Theorem 2* in two aspects: it deals only with the case that $v = \kappa^+$ is a successor cardinal, and it strengthen assumption (3) of Theorem 2* to $\forall p \in P \ \mathrm{Cov}(P \setminus \uparrow p) < v$. With the aid of the analysis of the equivalent classes of $\sim$ it turns out that the reduction theorem suffices to yield the full Theorem 2 for every uncountable cardinal $v$.

**Definition 22.** For any poset $P$, an equivalence relation $\sim$ is defined over $P$ by $a \sim b$ iff $a = b$ or there is a finite sequence $x_1, \dots, x_n$ such that $a = x_1, b = x_n$, and $x_i \perp x_{i+1}$ for every $1 \le i < n$. We say that this sequence joins $a$ to $b$ in $\sim$. Borrowing the language of graph theory, equivalence classes of $\sim$ are also called connected components or just components.

Let $A$ and $B$ be equivalence classes of $\sim$. Recall that $A \frown B$ is a shorthand for $\forall a \in A \forall b \in B (a \le p b)$. We claim that the equivalence classes of $P$ are linearly ordered under the $\frown$ reflexive
and transitive relation. Indeed, if $A \neq B$ are distinct equivalence classes, if $a \in A$ and $b \in B$, then $a$ and $b$ are comparable in $<_P$, and if $a <_P b$ for example, then for every $a' \in A$ and $b' \in B$, $a' <_P b'$. This can be proved by induction on the length of the $\perp$ paths that lead from $a$ to $a'$ and from $b$ to $b'$. It follows immediately that any poset $P$ is the sum of its components along their linear ordering. This result which belongs to the folklore of the theory of ordered sets (see [14, I.1.2] and [1, 2.7]) is used here in connection with the covering numbers of its components in the following.

**Lemma 23.** *Any poset $P$ is the lexicographical sum, $P := \sum_{i \in D} P_i$, of its equivalence classes $P_i$, indexed by the chain $D$ that reflects the $\perp$ ordering on the equivalence classes.*

Suppose that $\text{Cov}(P_i) = \rho_i$ for every $i \in D$, and let $\kappa := \sup\{\rho_i : i \in D\}$ be the supremum of these cardinals. Then

$$ \text{Cov}(P) = \kappa. \qquad (4) $$

Moreover, there are two exclusive possibilities:

(1) Either $\text{Cov}(P_i) < \kappa$ for every $i \in D$, and then $\kappa$ is a limit cardinal, and for some $D' \subset D$ of cardinality $\text{cf}(\kappa)$ and (distinct) successor cardinals $\kappa_i^+$, $\text{Cov}(P_i) \ge \kappa_i^+$ for every $i \in D'$, and

$$ \kappa = \sup\{\kappa_i^+ : i \in D'\}. $$

Or else,

(2) There exists an equivalence class $P_{i_0}$ in $P$ with a maximal cardinality $\text{Cov}(P_{i_0}) = \text{Cov}(P)$ (i.e. $\kappa = \text{Cov}(P_{i_0})$).

**Proof.** For every $i \in D$, let $(L_\xi^i : \xi < \rho_i)$ be an enumeration of chains that cover $P_i$. For every given $\xi < \kappa$, the union of the chains, $L_\xi = \cup\{L_\xi^i : i \in D \wedge \xi < \rho_i\}$, is a chain of $P$, and $P$ is covered by $\mathcal{L} = \{L_\xi : \xi < \kappa\}$. Hence $\text{Cov}(P) \le |\mathcal{L}| \le \kappa$. But as $\rho_i \le \text{Cov}(P)$ for every $i \in D$, $\text{Cov}(P) = |\mathcal{L}| = \kappa$, and thus (4) holds.

In case this supremum is a maximum, i.e. for some $i_0 \in D$, $\text{Cov}(P_i) \le \rho_{i_0} = \text{Cov}(P_{i_0})$ for all $i$, then $\text{Cov}(P) = \rho_{i_0}$. Otherwise $\kappa$ is a limit cardinal, and for any $\mu < \kappa$ there is an equivalence class $P_i$ with $\text{Cov}(P_i) > \mu$. In this case the set $D'$ can easily be chosen so that the first possibility holds. $\square$

The following simple lemma turns out to be very useful in our proof (as was [1, Lemma 2.9]).

**Lemma 24.** *Let $P$ be a poset and $x, y$ be such that $x \sim y$. Suppose that*

$$ x = x_0, \dots, x_n = y \quad \text{is a path that joins } x \text{ to } y. \qquad (5) $$

Then

$$ [x, y]_P \subseteq x_1^{\perp} \cup \cdots \cup x_{n-1}^{\perp}. \qquad (6) $$

**Proof.** Suppose that $z \in [x, y]$, that is $x \le_P z \le_P y$. If $z = x_0$, then $z \perp x_1$ evidently. Assume that $x_0 <_P z \le_P x_n$. Noting that $z \not\le_P x_0$, let $0 < m \le n$ be the first such that $z \le_P x_m$ (thus $m \ge 1$). So $z \not\le_P x_{m-1}$, and since $x_{m-1} \le_P z$ is impossible (for $x_{m-1} \perp x_m$), $x_{m-1} \perp z$ follows. (This proof includes the case that $x \perp y$. In that case $[x, y] = \{x, y\}$ and $x_1^{\perp} \cup \cdots \cup x_{n-1}^{\perp} = x_1^{\perp} \cup x_0^{\perp}$, so that $\{x, y\} \subseteq x_1^{\perp} \cup x_0^{\perp}$ is evident.) $\square$

**Corollary 25.** *Let $v$ be an infinite cardinal, and $P$ be a poset such that $\text{Cov}(x^{\perp}) < v$ for every $x \in P$. If $Q$ is a component of $P$, then $\text{Cov}([x, y]_P) < v$ for every $x, y \in Q$ such that $x <_P y$.*

**Proof.** Since $[x, y]_P \subseteq x_1^{\perp} \cup \cdots \cup x_{n-1}^{\perp}$, $\text{Cov}([x, y]_P) \le \text{Cov}(x_1^{\perp}) + \cdots + \text{Cov}(x_n^{\perp})$ and since $\text{Cov}(x^{\perp}) < v$ for each $x \in P$, the corollary follows immediately. $\square$

Lemma 23 and Corollary 25 are used next.
**Lemma 26.** Let $v$ be an uncountable cardinal and $P$ be a poset such that $\mathrm{Cov}(P) \ge v$, but

$$ \forall p \in P \ \mathrm{Cov}(p^{\perp}) < v. \qquad (7) $$

Then either

(1) each connected component of $P$ has covering number $< v$, and in this case $\mathrm{Cov}(P) = v = \sup\{\mathrm{Cov}(X) : X \text{ is a component of } P\}$, or else

(2) some connected component $Q$ of $P$ contains a subposet $R$ such that $\mathrm{Cov}(R) \ge v$, and $R$ or its dual has the property that $\mathrm{Cov}(R \setminus \uparrow x) < v$ for every $x \in R$.

**Proof.** Decompose $P$ into its ~-equivalence classes. By Lemma 23, $\mathrm{Cov}(P) = \sup\{\mathrm{Cov}(X) : X \text{ is a component of } P\}$.

If each component $X$ has covering number $< v$, then we are in Lemma 26 (1), and $v = \mathrm{Cov}(P)$ is a limit cardinal. Otherwise, there exists $Q$, a connected component of $P$ such that $\mathrm{Cov}(P) = \mathrm{Cov}(Q) \ge v$.

(1) If for every $x \in Q$, $\mathrm{Cov}(Q \cap \uparrow x) < v$ then combining this condition with assumption (7) we get that $\mathrm{Cov}(Q \setminus \downarrow x) < v$ for every $x \in Q$. In this case $R = Q^*$ satisfies Lemma 26 (2).

(2) Otherwise, there is some $x_0 \in Q$ such that $\mathrm{Cov}(Q \cap \uparrow x_0) \ge v$. In this case, we apply Corollary 25 to $Q$ and get that $\mathrm{Cov}[x_0, y]_P < v$ for every $y \in Q$ such that $x_0 <_P y$. Thus, the subposet $R = Q \cap (\uparrow x_0)$ satisfies $\mathrm{Cov}(R \cap (\downarrow x)) < v$ for every $x \in R$. Combining this property of $R$ with assumption (7) we get that $\mathrm{Cov}(R \setminus \uparrow x) < v$ for every $x \in R$. Now condition (2) of our lemma holds for $R$ (which is a subposet of $P$).

In both cases, Lemma 26 (2) holds for $P$ or its inverse. $\square$

Here is the reduction theorem which we intend to prove in the next section.

**Theorem 27.** Let $v = \kappa^+$ be any uncountable successor cardinal, and $P$ be a poset with no infinite antichain, satisfying

$$ \mathrm{Cov}(P) \ge v \wedge \mathrm{Cov}(P \setminus \uparrow x) < v \text{ for every } x \in P. \qquad (8) $$

Then $P$ contains a copy of $[v]^2$.

Evidently, in (8), we can replace $\mathrm{Cov}(P \setminus \uparrow x) < v$ with $\mathrm{Cov}(P \setminus \downarrow x) < v$ and conclude that $P$ contains a copy of $[v]^2$ inverse.

In this section we prove that Theorem 27 implies Theorem 2, and for the proof of this implication some notations are needed. For any uncountable successor cardinal $\kappa^+$ let $\mathrm{Thm}_{27}(\kappa^+)$ denote the statement of Theorem 27 for the specific cardinal $v = \kappa^+$, and for a limit uncountable cardinal $v$, let $\mathrm{Thm}_{27}(<v)$ be the statement that for every successor uncountable cardinal $\kappa^+ < v$, $\mathrm{Thm}_{27}(\kappa^+)$. Similar notations such as $\mathrm{Thm}_2(v)$ and $\mathrm{Thm}_2^*(v)$ will be used. Recall that we proved

$$ \mathrm{Thm}_2(v) \iff \mathrm{Thm}_2^*(v) \qquad (9) $$

for every uncountable cardinal $v$ (this is Lemma 21).

The proof of Theorem 27 will occupy the next section, and we conclude this section with a deduction of Theorem 2 from Theorem 27. This deduction is spread over two theorems, the first for the successor case and the second for the limit case.

**Theorem 28 (Successor case).** Let $\kappa^+$ be any uncountable successor cardinal. Then

$$ \mathrm{Thm}_{27}(\kappa^+) \rightarrow \mathrm{Thm}_2(\kappa^+). \qquad (10) $$

**Proof.** We are going to prove that $\mathrm{Thm}_{27}(\kappa^+) \rightarrow \mathrm{Thm}_2^*(\kappa^+)$, and then use equivalence (9) in order to conclude (10). Assume $\mathrm{Thm}_{27}(\kappa^+)$, and let $P$ be a FAC poset such that $\mathrm{Cov}(P) \ge \kappa^+$ and for every $p \in P$, $\mathrm{Cov}(p^{\perp}) \le \kappa$. We have to prove that $P$ or $P^*$ contains a copy of $[\kappa^+]^2$.

Lemma 26 yields two possibilities for $P$:
(1) For every component $X$ of $P$, $\mathrm{Cov}(X) \leq \kappa$. In this case, the chains that cover the different components can be attached to form a covering of $P$ with $\leq \kappa$ chains in contradiction to $\mathrm{Cov}(P) \geq \kappa^+$. So this case is void.

(2) There is a subposet $Q$ of $P$ such that $\mathrm{Cov}(Q) \geq \kappa^+$ and $Q$ or $Q^*$ satisfies the condition that

$$ \forall x \in Q (\mathrm{Cov}(Q \upharpoonright x) \leq \kappa). \qquad (11) $$

Then we can use $\mathrm{Thm}_{27}(\kappa^+)$ and conclude that $Q$ or $Q^*$ contains a copy of $[\kappa^+]^2$. Evidently, it follows that $P$ or $P^*$ contains such a copy. $\square$

**Theorem 29 (Limit case).** Let $v$ be any uncountable limit cardinal. Then $\mathrm{Thm}_{27}(<v)$ implies $\mathrm{Thm}_{2}(v)$.

**Proof.** Suppose $\mathrm{Thm}_{27}(<v)$, namely that Theorem 27 holds for every uncountable successor cardinal $\kappa^+ < v$. Then, by the previous theorem (the successor case),

$$ \mathrm{Thm}_{2}(\kappa^{+}) \text{ holds for every uncountable successor cardinal } \kappa^{+} < v. \qquad (12) $$

Given a FAC poset $P$ such that $\mathrm{Cov}(P) \geq v$, our aim is to prove that $P$ or $P^*$ contains a sum $\sum_{a \in C}[\kappa_a^+]$ as in item 2 of Theorem 2.

For every connected component $X$ of $P$ define $\rho(X) = \mathrm{Cov}(X)$. Then (by Lemma 23)

$$ \mathrm{Cov}(P) = \sup \{\rho(X) : X \text{ is a component of } P\}. \qquad (13) $$

Apply Lemma 26 to $P$, and consider its two cases.

(1) The first case is when $\rho(X) < v$ for every component $X$ of $P$. In this case, take an increasing sequence of successor cardinals $(\kappa_i^+ : i < \mathrm{cf}(\kappa))$ with supremum $v$, and for each $\kappa_i$ take a specific component $X_i$ with covering number $\rho(X_i) \geq \kappa_i^+$. This procedure yields a linear ordering $D$ (not necessarily well-ordered) of cardinality $\mathrm{cf}(v)$ of components such that $P$ contains a sum of components, $\sum_{i \in D} X_i$, where $\mathrm{Cov}(X_i) \geq \kappa_i^+$.

Since Theorem 2 holds for uncountable successor cardinals smaller than $v$, $X_i$ embeds either $[\kappa_i^+]^2$ or its dual. It follows that for some $C \subseteq D$ of cardinality $\mathrm{cf}(v)$, $P$ or $P^*$ contains a sum of the form $\sum_{i \in C}[\kappa_i^+]^2$ where $\sup\{\kappa_i^+ : i \in C\} = v$.

(2) The second case is that $P$ contains a subposet $Q$ such that $\mathrm{Cov}(Q) \geq v$ and $Q$ or $Q^*$ satisfies

$$ \mathrm{Cov}(Q \upharpoonright x) < v \text{ for every } x \in Q. \qquad (14) $$

The following lemma applies to $Q$ and concludes the proof of Theorem 29.

**Lemma 30.** Suppose that $v$ is an uncountable limit cardinal such that $\mathrm{Thm}_{27}(<v)$ holds. If $Q$ satisfies equation (14), then $Q$ contains a sum $\sum_{a \in C}[\kappa_a^+]^2$ where $C$ is a linear order of order-type $\mathrm{cf}(v)$ and $\sup\{\kappa_a : a \in C\} = v$.

**Proof.** Suppose that assumption (14) holds for a limit uncountable cardinal $v$ (which could be regular or singular). We must conclude that $Q$ contains a sum $\sum_{a \in C}[\kappa_a^+]^2$ as required.

We prove first for any $X \subseteq Q$ that

$$ |X| < \mathrm{cf}(v) \Rightarrow X \text{ is bounded in } Q. \qquad (15) $$

By assumption (14), $\mathrm{Cov}(Q \upharpoonright x) < v$ for every $x$, and hence the covering number of $Y = \bigcup_{x \in X} (Q \upharpoonright x)$ is less than $v$. So there exists some $x_0 \in Q \setminus Y$, which is necessarily an upper-bound of $X$.

Let $(\kappa_\alpha^+)$$_{\alpha < \mathrm{cf}(v)}$ be an increasing sequence of successor cardinals, all less than $v$, such that $\sup\{\kappa_\alpha^+ : \alpha < \mathrm{cf}(v)\} = v$.

We construct an increasing sequence $(x_\alpha)$$_{\alpha < \mathrm{cf}(v)}$ in $Q$ such that $\mathrm{Cov}([x_\alpha, x_{\alpha+1}]) \geq \kappa_\alpha^+$ for every $\alpha < \mathrm{cf}(v)$.
Equation (15) shows that for limit ordinals $\delta < \operatorname{cf}(v)$, if the sequence $(x_\alpha)_{\alpha < \delta}$ is defined, then an upper-bound $x_\delta$ can be obtained (and for $\delta = 0$, $x_0 \in Q$ is arbitrarily chosen). Suppose that $x_\alpha \in Q$ is defined. Since $\operatorname{Cov}(Q) \ge v$ but $\operatorname{Cov}(Q \uparrow x_\alpha) < v$, $\operatorname{Cov}(\uparrow x_\alpha) \ge v > \kappa_\alpha^{++}$. We concluded in (12) that $\operatorname{Thm}_2(\kappa^+)$ holds for any successor cardinals $\kappa^+ < v$, and thus $\uparrow x_\alpha$ contains a copy of $[\kappa_\alpha^{++}]^2$ or its reversed dual. Since $[\kappa_\alpha^{++}]^2$ contains a *bounded copy* of $[\kappa_\alpha^+]^2$, there is some element $x_{\delta+1} \in Q$ such that a copy of $[\kappa_\alpha^+]^2$ or of its reverse is contained in the interval $[x_\delta, x_{\delta+1}]$. (The inverse of any $[\kappa]^2$ is certainly bounded.)

By picking a subsequence, we may assume that all intervals $[x_\delta, x_{\delta+1}]$ contain copies of the corresponding $[\kappa_\alpha^+]^2$ or else that all of them contain copies of the dual of these posets. $\square$

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

This ends the proof of Theorem 29 (the limit case), and together with Theorem 28 we get that

$$ \forall \kappa > \omega (\operatorname{Thm}_{27}(\kappa^+)) \rightarrow \forall v > \omega (\operatorname{Thm}_{2}(v)). \quad (16) $$

Thus it remains to prove that Theorem 27 holds for all uncountable successor cardinals.

### 3.1. *Proofs of Theorem 27*

**Lemma 31.** Let $v = \kappa^+$ be a successor cardinal, and suppose that $P$ is an up-directed FAC poset such that $\operatorname{Cov}(P) \ge v$, but $\operatorname{Cov}(P \uparrow p) < v$ for every $p \in P$. If $P$ does not contain a copy of $[\kappa^+]^2$, then there is a well-ordered chain with order-type some regular $\lambda \ge v$ that is cofinal in $P$.

**Proof.** Since $\operatorname{Cov}(P \uparrow x) < v$ for every $x \in P$ and $\operatorname{Cov}(P) \ge v$, then $P$ is up-directed. Indeed, we proved in (15) that every set of cardinality $< \operatorname{cf}(v)$ is bounded, and thus certainly $P$ is up-directed. According to Theorem 7, $P$ has a cofinal subset $A$ isomorphic to a product $\alpha_1 \times \cdots \times \alpha_n$ of pairwise distinct regular cardinals enumerated (for clarity) in increasing order.

We claim that, assuming $P$ does not contain a copy of $[\kappa^+]^2$, each cardinal $\alpha_j$, for $1 \le j \le n$, is at least $v$. For the proof, suppose on the contrary that $\alpha_1 < v$. Since $v = \kappa^+$ is a successor cardinal and $\alpha_1$ is a cardinal, $\alpha_1 \le \kappa$. Let $A_1 := \{x_\alpha : \alpha < \alpha_1\}$ be the image in $A$ of the chain $\{(z, 0, \dots, 0) \in \alpha_1 \times \cdots \times \alpha_n : z < \alpha_1\}$. Since $\operatorname{Cov}(P \uparrow x_\alpha) \le \kappa$ and $\alpha_1 \le \kappa$, $\operatorname{Cov}(\bigcup_{\alpha<\alpha_1} (P \uparrow x_\alpha)) \le \kappa$. But this union is $P$ since the chain $A_1$ is unbounded. This contradicts $\operatorname{Cov}(P) \ge \kappa^+$. Thus the product $\alpha_1 \times \cdots \times \alpha_n$ consists of cardinals that are $\ge \kappa^+$. If this product consists of two or more cardinals, then $P$ contains a copy of $[\kappa^+]^2$. Thus, if we assume that $P$ does not contain a copy of $[\kappa^+]^2$, then $P$ has a cofinal chain of order-type some regular $\lambda \ge v$. $\square$

<figure><img src="image_5.png" /></figure>

From this point of the article the two proofs of Theorem 27 split. For one proof jump to section 3.1.2, and for the other proof continue reading.

#### 3.1.1. *Completion of proof of Theorem 27*

Let's restate Theorem 27 for convenience.

**Theorem (Theorem 27).** Assume that $P$ has only finite antichains, and that $v = \kappa^+$ is an uncountable successor cardinal such that $\operatorname{Cov}(P) \ge \kappa^+$ but $\operatorname{Cov}(P \uparrow p) \le \kappa$ for every $p \in P$. Then $P$ contains a subposet in $\mathcal{P}(\kappa^+)$ and hence $P$ contains a copy of $[\kappa^+]^2$. (And, correspondingly, if for every $p \in P$, $\operatorname{Cov}(P \downarrow p) \le \kappa$, then $P^*$ contains a copy of $[\kappa^+]^2$.)

**Proof.** With Lemma 31 we may further assume that $P$ has a cofinal chain $A = \{x_\xi : \xi < \lambda\}$ of order-type $\lambda \ge \kappa^+$ ($\lambda$ is regular). Let $\gamma_0 \le \lambda$ be the first ordinal such that the initial segment $I = \bigcup\{\downarrow x_\xi : \xi < \gamma_0\}$ has covering number $\ge \kappa^+$. Then redefine $P := I$, $\lambda := \operatorname{cf}\gamma_0$, so that the assumptions of our theorem remain for the new $P$ and $\lambda$. The set $\{x_\xi : \xi < \lambda\}$ of order-type $\lambda \ge \kappa^+$
is cofinal in $P$, and we gain a useful property that if $Q$ is a subposet of $P$ of cofinality $cf(Q) < \lambda$ then:

$$ \mathrm{Cov}(Q) \leq \kappa. \qquad (17) $$

For every $\zeta < \lambda$ define

$$ D_{\zeta} = (\downarrow x_{\zeta}) \setminus \bigcup_{\xi < \zeta} (\downarrow x_{\xi}). \qquad (18) $$

$D_\zeta$ is said to be the $\zeta$ layer of $P$. Surely $x_\zeta \in D_\zeta$ so that $D_\zeta \neq \emptyset$.

The following is obvious.

(1) $x_\zeta \in D_\zeta$ is the maximum of $D_\zeta$, and $P = \bigcup_{\zeta < \lambda} D_\zeta$ is a partition of $P$ into its layers.

(2) If $\zeta' < \zeta < \lambda$, $x \in D_{\zeta'}$, $y \in D_\zeta$ then $\neg(y \leq_P x)$ so that if $x$ and $y$ are comparable, then $x < y$. Thus any $<_P$ relation that exists between members of $P$ at different layers is in accordance with the layers' indexes.

(3) Since $D_\zeta \subseteq (\downarrow x_\zeta)$, $D_\zeta$ is a union of $\kappa$ chains.

**Definition 32.** Define $F: P \to \lambda$ by $F(p) = \xi$ iff $\xi < \lambda$ is the first ordinal such that $\neg(x_\xi <_P p)$.

**Claim 33.**

(1) For every $\xi < \lambda$, $F^{-1}\{\xi\} \subseteq \{x_\xi\} \cup (P \uparrow x_\xi)$ and hence $F^{-1}\{\xi\}$ is a union of $\kappa$-chains. If $x_\zeta < p$ then $F(p) > \zeta$. If $p \in D_\zeta$ then $F(p) \leq \zeta$.

(2) If $x <_P y$ then $F(x) \leq F(y)$.

(3) If $\zeta' < \zeta < \lambda$, $x \in D_{\zeta'}$, $y \in D_\zeta$ and $F(x) > F(y)$, then $x \perp y$.

(4) For every $\xi < \lambda$, $F(x_\xi) = \xi$.

**Proof.** All items follow directly the definition of $F$. To prove Item (3) for example, suppose that $x$ is comparable to $y$. Then $x <_P y$ follows and Item (2) implies that $F(x) \leq F(y)$, which contradicts assumption $F(x) > F(y)$. Item (3) will lead to the conclusion that $P$ contains a poset in $\mathcal{P}(\kappa^+)$. $\square$

For every $\xi \in \lambda$ define $\gamma(\xi) \leq \lambda$ by

$$ \gamma(\xi) = \sup \{\mu \in \lambda : \exists x \in D_{\mu} (F(x) = \xi)\}. $$

Since $F(x_\xi) = \xi$, $\xi \leq \gamma(\xi)$.

Define a partition of $\lambda$ into two sets, $B$ and $U = \lambda \setminus B$ (Bounded and Unbounded): $\beta \in B$ iff $\gamma(\beta) < \lambda$ (i.e. $F^{-1}\{\beta\}$ intersects only a bounded set of layers). It follows immediately that

$$ p \in D_{\mu} \wedge F(p) = \xi \in B \to \mu \leq \gamma(\xi). \qquad (19) $$

Since $U = \lambda \setminus B$, $\beta \in U$ iff $\gamma(\beta) = \lambda$, i.e. the set of layers that intersect $F^{-1}$ is unbounded in $\lambda$. Define $\mathcal{B} = F^{-1}B$ and $\mathcal{U} = F^{-1}U$, so that $P = \mathcal{B} \cup \mathcal{U}$.

We prove next that $\mathrm{Cov}(\mathcal{B}) \leq \kappa$ and conclude that $\mathrm{Cov}(\mathcal{U}) > \kappa$. Then we will prove that $\mathcal{U}$ contains a copy of $[\kappa^+]^2$ (thereby proving Theorem 27).

**Lemma 34.** $\mathrm{Cov}(\mathcal{B}) \leq \kappa$.

**Proof.** Consider the function $\gamma \upharpoonright B$ defined over $B$. Cardinal $\lambda$ is uncountable and regular, and hence the set $C = \{\delta \in \lambda : \forall \beta \in B \cap \delta (\gamma(\beta) < \delta)\}$ is closed unbounded in $\lambda$. For every $\delta \in C$ let $\delta' \in C$ denote the first ordinal in $C$ above $\delta$, and let $I_\delta = [\delta, \delta')$ be the ordinal interval $\delta' \setminus \delta$. Then $\lambda = \bigcup_{\delta \in C} I_\delta$ is a partition of $\lambda$ into slices of cardinality $< \lambda$ each. Define, for $\delta \in C$,

$$ \mathcal{B}(\delta) := \bigcup_{\xi \in I_{\delta}} D_{\xi} \cap F^{-1}B. \qquad (20) $$

Then $\mathcal{B}(\delta)$ is a union of $\kappa$ chains because $\bigcup_{\xi \in I_\delta} (\downarrow x_\xi)$ is a subset of $P$ with a cofinal subset of cardinality $|I_\delta| < \lambda$, and hence is a union of $\kappa$ chains by (17). Thus its subset, $\mathcal{B}(\delta)$, is also a union of $\kappa$ chains.
**Claim 35.**

(1) Suppose that $p \in \mathcal{B}(\delta)$ (where $\delta \in C$). Then $p <_p x_{\delta'}$ and $F(p) \ge \delta$.

(2) If $\delta_1 < \delta_2$ are in the club set $C$ defined above, then for every $p_1 \in \mathcal{B}(\delta_1)$ and $p_2 \in \mathcal{B}(p_2)$, $p_1 <_p p_2$.

**Proof.** Suppose that $p \in \mathcal{B}(\delta)$. Then $p \in D_\mu$ for some $\mu \in I_\delta$, and hence $p \le x_\mu < x_{\delta'}$. Also, $F(p) \ge \delta$, or else $F(p) = \zeta < \delta$ would imply that $\mu \le \gamma(\zeta) < \delta$, by (19), in contradiction to $\mu \in I_\delta$.

Now, if $\delta_1 < \delta_2$ are in $C$, $p_1 \in \mathcal{B}(\delta_1)$ and $p_2 \in \mathcal{B}(p_2)$, then Item (1) says that $F(p_2) \ge \delta_2$ and that $p_1 <_p x_{\delta_1}$. Hence $p_1 <_p p_2$. $\square$

Claim 35 implies that $\mathcal{B} = \bigcup_{\delta \in C} \mathcal{B}(\delta)$ is a union of $\kappa$ chains. Indeed, we know that $\mathcal{B}(\delta)$ is a union of $\kappa$ chains, and we can enumerate these chains in a sequence of length $\kappa$. Then, for any index $\tau < \kappa$, the chains of $\mathcal{B}(\delta)$ with index $\tau$ for $\delta \in C$ can be united to form a chain of $P$, which yields a covering of $F^{-1}B$ with $\kappa$ chains. This proves Lemma 34. $\square$

So the covering number of $\mathcal{B}$ is $\le \kappa$, and hence the covering number of its complement $\mathcal{U}$ is
> $\kappa$. It remains to prove that $\mathcal{U} = F^{-1}U$ contains a copy of $[\kappa^+]^2$ in order to conclude the proof of
Theorem 27.

We prove first that $|U| \ge \kappa^+$. If not, if $|U| \le \kappa$ then $\mathcal{U} = \bigcup_{\zeta \in U} F^{-1}\{\zeta\}$ is covered by $\kappa$ chains since every $F^{-1}\{\zeta\}$ is so covered (by item (1) of Claim 33).

To prove that $\mathcal{U}$ contains a copy of $[\kappa^+]^2$, let $U_0 \subseteq U$ be a subset of order-type $\kappa^+$. For $\alpha \in U_0$, $\gamma(\alpha) = \lambda$, i.e. $S_\alpha = \{\mu \in \lambda : \exists x \in D_\mu F(x) = \alpha\}$ is a subset of $\lambda$ of cardinality $\lambda$. It is not difficult to find $R_\alpha \subset S_\alpha$ that are pairwise disjoint and of order-type $\kappa^+$ such that $R = \bigcup_{\alpha \in U_0} R_\alpha$ is also of order-type $\kappa^+$. We identify $R \cong \kappa^+$ with $\kappa^+$. For every $\mu \in R$ there is some $\alpha \in U_0$ and $p(\mu) \in D_\mu$ such that $F(p(\mu)) = \alpha$. Define $P_0 = \{p(\mu) : \mu \in R\} \subset P$, and then the injection $p : R \to P_0$ induces a partial ordering on $R \cong \kappa^+$ which is isomorphic to $P_0$. That is, for $\zeta_1, \zeta_2 \in \kappa^+$, we define $\zeta_1 <_P \zeta_2$ iff $p(\zeta_1) <_P p(\zeta_2)$. The function $F : R \to U_0$ defined by $F(\mu) = F(p(\mu))$ shows that $P \in \mathcal{P}(\kappa^+)$ (use item (3) of Claim 33). Thus $[\kappa^+]^2$ is embeddable in $R$. This completes the proof of Theorem 27. $\square$

3.1.2. Second proof of Theorem 27

Recall that in Lemma 31 we proved that if $P$ is a FAC poset such that $\mathrm{Cov}(P) \ge \nu = \kappa^+$, but for every $p \in P$, $\mathrm{Cov}(P \setminus \uparrow p) \le \kappa$, then there is a chain $A$ cofinal in $P$ with well ordered order type some regular $\lambda \ge \nu$ (or else $[\nu]^2$ is embeddable into $P$, and in that case the theorem follows immediately). Hence we may assume in the following discussion that $A = \{x_\zeta : \zeta < \lambda\}$ is an increasing and cofinal in $P$ sequence.

We use the conclusion of Lemma 31 in proving

**Lemma 36.** *Assume that $\nu = \kappa^+$ is a successor cardinal and $P$ is a FAC poset such that $\mathrm{Cov}(P) \ge \nu$ but for every $p \in P$, $\mathrm{Cov}(P \setminus \uparrow p) \le \kappa$. Then $P$ is impure.*

**Proof.** Suppose for the sake of a contradiction that $P$ is pure. According to Theorem 9, $P$ is a lexicographical sum $\sum_{a \in K} P_a$ where $K$ is a chain with cofinality $cf(P) = \lambda$. For each $a \in K$, $\mathrm{Cov}(P_a) \le \kappa$, because $P_a$ is bounded by any member of $P_b$ for $a <_K b$, and $\mathrm{Cov}(\lfloor p \rfloor) < \nu$ for any $p \in P$ since $\lfloor p \rfloor \subseteq P \setminus \uparrow p$. As $\mathrm{Cov}(P_a) \le \kappa$ for every $a \in K$, and since $P$ is a sum of the $P_a$ convex subposets, we get (by union of chains) that $\mathrm{Cov}(P) \le \kappa$. This contradicts our hypothesis that $\mathrm{Cov}(P) \ge \nu = \kappa^+$. $\square$

**Lemma 37.** *Under the assumptions of Lemma 36, $P$ contains a proper initial segment $J$ that is unbounded and has a cofinal sequence of order-type $\lambda$.*

**Proof.** The previous lemma says that $P$ is impure and hence contains a proper initial segment $I$
that is unbounded in $P$. Let $cf(I) = \lambda_0$ be the cofinality of $I$, and let $\{a_\alpha : \alpha < \lambda_0\}$ be a cofinal subset
of I. Define a function $f: \lambda \to \lambda_0$ thus: since $x_\alpha \in A$ is not an upper-bound of I, there is some $a_\beta$ that is not dominated by $x_\alpha$; define $f(\alpha) = \beta$ for the least $\beta < \lambda_0$ such that $\neg(a_\beta \le x_\alpha)$. Note that if $\alpha_1 < \alpha_2 < \lambda$ then either $a_{f(\alpha_1)} \perp a_{f(\alpha_2)}$ or $a_{f(\alpha_1)} \le_P a_{f(\alpha_2)}$.

Apply the Erdös–Dushnik–Miller theorem to the partition of $\lambda$ that gives one color to the pair $\alpha_1 < \alpha_2 < \lambda$ if $a_{f(\alpha_1)} \perp a_{f(\alpha_2)}$ and the other color if not. Since P satisfies the FAC, there is a set $X \subset \lambda$ of cardinality $\lambda$ that is homogeneous for the comparability color. The set $K = \{a_{f(\alpha)} : \alpha \in X\}$ is a chain of P and the function $x_\alpha \rightsquigarrow a_{f(\alpha)}$ is $<_P$ monotonic. Moreover, K is unbounded in P because any $p \in P$ is bounded by some $x_\alpha$ and hence $\neg(a_{f(\alpha)} \le_P p)$. Thus the ideal $J = \downarrow K$ has K as a cofinal sequence of order-type $\lambda$. $\square$

Note that if $x \in P$ then $P' := \uparrow x$ has the same properties of P, i.e. $\text{Cov}(P') \ge \kappa^+$ and for every $p \in P'$, $\text{Cov}(p^\perp) \le \kappa$. Hence Lemma 37 applies to $P'$ and there is a proper initial segment of $P'$ that is unbounded (even in P) and has a cofinal sequence of order-type $\lambda$.

Let $\mathcal{J}_P(\lambda)$ be the set of unbounded ideals of $P$ containing a cofinal chain of type $\lambda$. By hypothesis, $P \in \mathcal{J}_P(\lambda)$. Let $\mathcal{J}_P(\lambda)^- := \mathcal{J}_P(\lambda) \setminus \{P\}$. We order $\mathcal{J}_P(\lambda)^-$ by set inclusion. We saw in Lemma 37 that $\mathcal{J}_P(\lambda)^-$ is not empty, and the following lemma shows more with a similar proof.

**Lemma 38.** $\text{cf}(\mathcal{J}_P(\lambda)^-) \ge \lambda$.

**Proof.** Let $(J_\alpha)_{\alpha<\mu}$ with $\mu := \text{cf}(\mathcal{J}_P(\lambda)^-)$ be a sequence cofinal in $\mathcal{J}_P(\lambda)^-$. For each $\alpha < \mu$, pick $x_\alpha \in A \setminus J_\alpha$. If $\mu < \lambda$ then, since $\lambda$ is a regular cardinal, there is some $x \in A$ majorizing all the $x'_\alpha$s. In order to get a contradiction, it suffices to show that there is some $J$ such that $x \in J \in \mathcal{J}_P(\lambda)^-$. According to our hypothesis, the final segment $\uparrow x$ is impure. Hence, it contains a proper initial segment $I$ which is unbounded (in $\uparrow x$). Let $A_x := \uparrow x \cap A$. For each $y \in A_x$, we may pick some $c_y \in I \setminus \downarrow y$ since $y$ does not majorize I. Apply Erdös–Dushnik–Miller’s Theorem to the sequence $(c_y)_{y \in A_x}$. Since P has no infinite antichain, there is an increasing subsequence $(c_y)_{y \in D}$ with D cofinal in $A_x$. The values of this sequence cannot be bounded in P. (otherwise, if $a$ is an upper bound, pick $y \ge a$ in D and get a contradiction with $c_y$) hence they generate an unbounded ideal; since it is included in $\downarrow I$ it is distinct of P. $\square$

**Claim 39.** $\mathcal{J}_P(\lambda)^-$ has no infinite antichain.

**Proof.** This relies on the fact that $\lambda$ is uncountable and regular. Indeed, suppose the sake of a contradiction that $\mathcal{J}_P(\lambda)^-$ contains an infinite antichain $(J_n)_{n<\omega}$. For each $n \ne m < \omega$ there is some $x_{n,m} \in J_n \setminus J_m$. Since $J_n$ contains a cofinal chain of uncountable regular type, it contains an element $x_n$ majorizing all the $x_{n,m}$. Then $\{x_n : n < \omega\}$ is an infinite antichain in P, which is impossible. $\square$

With this claim, we complete the proof of Theorem 27 as follows. We pick a well founded cofinal subset in $\mathcal{J}_P(\lambda)^-$. It is well quasi-ordered by Claim 39 and by Claim 38, and has cardinality at least $\lambda$. By Erdös–Dushnik–Miller’s theorem, it contains a chain of type $\lambda$. Let $(J_\alpha : \alpha < \kappa^+)$ enumerate an increasing sequence of ideals in $\mathcal{J}_P(\lambda)^-$, and let $I_\alpha \subset J_\alpha$ be a cofinal subset of order-type $\lambda$. We may assume that if $\alpha_1 < \alpha_2$ then no member of $I_{\alpha_2}$ is below one of $I_{\alpha_1}$.

To deduce the proof of Theorem 27 we embed a copy of $[\kappa^+]^2$ into $\bigcup \{I_\alpha : \alpha < \kappa^+\}$. Following the same procedure as in Claim 18, we define inductively an embedding of $[\beta]^2$ into $\bigcup_{\alpha<\beta} I_\alpha$ in such a way that the image of $\{(x, y) \in [\beta]^2 : x = \alpha\}$ is in $I_\alpha$.

## Acknowledgements

The authors would like to thank Professor James Cummings for the extensive discussions that helped to clarify several arguments in the proofs.
References

[1] U. Abraham, "A note on Dilworth's theorem in the infinite case", Order 4 (1987), no. 2, p. 107-125.

[2] U. Abraham, R. Bonnet, W. Kubiś, "Poset algebras over well quasi-ordered posets", Algebra Univers. 58 (2008), no. 3, p. 263-286.

[3] R. Assous, M. Pouzet, "Jónsson posets", Algebra Univers. 79 (2018), no. 3, article no. 74.

[4] R. Bonnet, "On the cardinality of the set of initial intervals of a partially ordered set", in Infinite sets, Keszthely, 1973, NATO ASI Series. Series C. Mathematical and Physical Sciences, vol. 3, North-Holland, Amsterdam, 1975, p. 189-198.

[5] R. P. Dilworth, "A decomposition theorem for partially ordered sets", Ann. Math. 51 (1950), p. 161-166.

[6] F. G. Dorais, "Another note on Dilworth's theorem in the infinite case", 7 pp., https://www.dorais.org/assets/pdf/abraham.pdf, 2008.

[7] ——, "A note on conjectures of F. Galvin and R. Rado", Can. Math. Bull. 56 (2013), no. 2, p. 317-325.

[8] B. Dushnik, E. W. Miller, "Partially ordered sets", Am. J. Math. 63 (1941), p. 600-610.

[9] R. Fraïssé, *Theory of relations*, revised ed., Studies in Logic and the Foundations of Mathematics, vol. 145, North-Holland, 2000, with an appendix by Norbert Sauer.

[10] E. C. Milner, M. Pouzet, "On the cofinality of partially ordered sets", in *Ordered sets (Banff, Alta., 1981)*, NATO ASI Series. Series C. Mathematical and Physical Sciences, vol. 83, Reidel, Dordrecht-Boston, Mass., 1982, p. 279-298.

[11] ——, "Antichain decompositions of a partially ordered set", in *Sets, graphs and numbers (Budapest, 1991)*, Colloquia Mathematica Societatis János Bolyai, vol. 60, North-Holland, 1992, p. 469-498.

[12] E. C. Milner, K. Prikry, "The cofinality of a partially ordered set", Proc. Lond. Math. Soc. 46 (1983), no. 3, p. 454-470.

[13] M. A. Perles, "On Dilworth's theorem in the infinite case", Isr. J. Math. 1 (1963), p. 108-109.

[14] M. Pouzet, "Ensemble ordonné universel recouvert par deux chaines", J. Comb. Theory, Ser. B 25 (1978), no. 1, p. 1-25.

[15] ——, "Parties cofinales des ordres partiels ne contenant pas d'antichaine infinie", unpublished, 1980.

[16] R. Rado, "Theorems on intervals of ordered sets", Discrete Math. 35 (1981), p. 199-201.

[17] S. Todorčević, "On a conjecture of R. Rado", J. Lond. Math. Soc. 27 (1983), no. 1, p. 1-8.

[18] ——, "Conjectures of Rado and Chang and cardinal arithmetic", in *Finite and infinite combinatorics in sets and logic (Banff, AB, 1991)*, NATO ASI Series. Series C. Mathematical and Physical Sciences, vol. 411, Kluwer Academic Publishers, 1993, p. 385-398.

[19] ——, "Combinatorial dychotomies in set theory", Bull. Symb. Log. 17 (2011), no. 1, p. 1-72.

[20] E. S. Wolk, "On decompositions of partially ordered sets", Proc. Am. Math. Soc. 15 (1964), p. 197-199.