---
abstract: 'For a lattice $L$, let ${\textup{Princ}(L)}$ denote the ordered set of principal congruences of $L$. In a pioneering paper, G. Grätzer characterized the ordered sets ${\textup{Princ}(L)}$ of finite lattices $L$; here we do the same for countable lattices. He also showed that each bounded ordered set $H$ is isomorphic to ${\textup{Princ}(L)}$ of a bounded lattice $L$. We prove a related statement: if an ordered set $H$ with least element is the union of a chain of principal ideals, then $H$ is isomorphic to ${\textup{Princ}(L)}$ of some lattice $L$.'
address: 'University of Szeged, Bolyai Institute. Szeged, Aradi vértanúk tere 1, HUNGARY 6720'
author:
- Gábor Czédli
date: 'May 7, 2013'
title: The ordered set of principal congruences of a countable lattice
---

[^1]

Introduction {#introsection}
============

Historical background
---------------------

A classical theorem of Dilworth [@dilwcollect] states that each finite distributive lattice is isomorphic to the congruence lattice of a finite lattice. Since this first result, the *congruence lattice representation problem* has attracted many researchers, and dozens of papers belonging to this topic have been written. The story of this problem were mile-stoned by Huhn [@huhn] and Schmidt [@schmidtidnl], reached its summit in Wehrung [@wehrung] and Ržička [@ruzicka], and was summarized in Grätzer [@grbypict]; see also Czédli [@czgrepres] for some additional, recent references.

In [@ggprincl], Grätzer started an analogous new topic of Lattice Theory. Namely, for a lattice $L$, let ${\textup{Princ}(L)}={{\langle {\textup{Princ}(L)},\subseteq\rangle}}$ denote the ordered set of principal congruences of $L$. A congruence is *principal* if it is generated by a pair ${{\langle a,b\rangle}}$ of elements. Ordered sets and lattices with 0 and 1 are called *bounded*. Clearly, if $L$ is a bounded lattice, then ${\textup{Princ}(L)}$ is a bounded ordered set. The pioneering theorem in Grätzer [@ggprincl] states the converse: each bounded ordered set $P$ is isomorphic to ${\textup{Princ}(L)}$ for an appropriate bounded lattice $L$. Actually, the lattice he constructed is of length 5. Up to isomorphism, he also characterized finite bounded ordered sets as the ${\textup{Princ}(L)}$ of finite lattices $L$.

Terminology
-----------

Unless otherwise stated, we follow the standard terminology and notation of Lattice Theory; see, for example, Grätzer [@GGLT]. Our terminology for weak perspectivity is the classical one taken from Grätzer [@grglt]. *Ordered sets* are nonempty sets equipped with *orderings*, that is, with reflexive, transitive, antisymmetric relations. Note that an ordered set is often called a *partially ordered set*, which is a rather long expression, or a *poset*, which is not tolerated by spell-checkers, or an *order*, which has several additional meanings.

Our result
----------

Motivated by Grätzer’s theorem mentioned above, our goal is to prove the following theorem. A set $X$ is *countable* if it is finite or countably infinite, that is, if $|X|\leq \aleph_0$. An ordered set $P$ is *directed* if each two-element subset of $P$ has an upper bound in $P$. Nonempty down-sets of $P$ and subsets ${\mathord\downarrow c}={\{x\in P: x\leq c\}}$ are called *order ideals* and *principal $($order$)$ ideals*, respectively.

\[thmmain\]

\[thmmaina\] An ordered set $P={\langle P;\leq\rangle}$ is isomorphic to ${\textup{Princ}(L)}$ for some *countable* lattice $L$ if and only if $P$ is a countable directed ordered set with zero.

\[thmmainb\] If $P$ is an ordered set with zero and it is the union of a chain of principal ideals, then there exists a lattice $L$ such that $P\cong {\textup{Princ}(L)}$.

An alternative way of formulating the condition in part is to say that $0\in P$ and there is a cofinal chain in $P$. For a pair ${{\langle a,b\rangle}}\in L^2$ of elements, the least congruence collapsing $a$ and $b$ is denoted by ${\textup{con}(a,b)}$ or ${\textup{con}_{L}(a,b)}$. As it was pointed out in Grätzer [@ggprincl], the rule $${\textup{con}(a_i,b_i)}\subseteq 
{\textup{con}(a_1\wedge b_1\wedge a_2\wedge b_2,a_1\vee b_1\vee a_2\vee b_2)}\,
\text{ for }i\in{\{1,2\}}
\label{prdirT}$$ implies that ${\textup{Princ}(L)}$ is always a directed ordered set with zero. Therefore, the first part of the theorem will easily be concluded from the second one. To compare part of our theorem to Grätzer’s result, note that a bounded ordered set $P$ is always a union of a (one-element) chain of principal ideals. Of course, no *bounded* lattice $L$ can represent $P$ by $P\cong{\textup{Princ}(L)}$ if $P$ has no greatest element.

Method
------

First of all, we need the key idea, illustrated by Figure \[fig4\], from Grätzer [@ggprincl].

Second, we feel that without the quasi-coloring technique developed in Czédli [@czgrepres], the investigations leading to this paper would have not even begun. As opposed to colorings, the advantage of quasi-colorings is that we have joins (equivalently, the possibility of generation) in their range sets. This allows us to decompose our construction into a sequence of elementary steps. Each step is accompanied by a quasiordering. If several steps, possibly infinitely many steps, are carried out, then the join of the corresponding quasiorderings gives a satisfactory insight into the construction. Even if it is the “coloring versions” of some lemmas that we only use at the end, it is worth allowing their quasi-coloring versions since this way the proofs are simpler and the lemmas become more general.

Third, the idea of using appropriate auxiliary structures is taken from Czédli [@112gen]. Their role is to accumulate all the assumptions our induction steps will need.

Auxiliary statements and structures
===================================

The rest of the paper is devoted to the proof of Theorem \[thmmain\].

Quasi-colorings and auxiliary structures
----------------------------------------

A *quasiordered set* is a structure ${\langle H;\nu\rangle}$ where $H\neq {\varnothing}$ is a set and $\nu\subseteq H^2$ is a reflexive, transitive relation on $H$. Quasiordered sets are also called preordered ones. Instead of ${{\langle x,y\rangle}}\in \nu$, we usually write $x {\mathrel{\leq_\nu}}y$. Also, we write $x{\mathrel{<_\nu}}y$ and $x{\mathrel{\parallel_\nu}}y$ for the conjunction of $x{\mathrel{\leq_\nu}}y$ and $y\not{\mathrel{\leq_\nu}}x$, and that of ${{\langle x,y\rangle}}\notin\nu$ and ${{\langle y,x\rangle}}\notin \nu$, respectively. If $g\in H$ and $x{\mathrel{\leq_\nu}}g$ for all $x\in H$, then $g$ is a *greatest element* of $H$; *least elements* are defined dually. They are not necessarily unique; if they are, then they are denoted by $1_H$ and $0_H$. If for all $x,y\in H$, there exists a $z\in H$ such that $x{\mathrel{\leq_\nu}}z$ and $y{\mathrel{\leq_\nu}}z$, then ${\langle H;\nu\rangle}$ is a *directed* quasiordered set. Given $H\neq {\varnothing}$, the set of all quasiorderings on $H$ is denoted by ${\textup{Quord}(H)}$. It is a complete lattice with respect to set inclusion. For $X\subseteq H^2$, the least quasiorder on $H$ that includes $X$ is denotes by ${\textup{quo}(X)}$. We write ${\textup{quo}(x,y)}$ instead of ${\textup{quo}({\{{{\langle a,b\rangle}}\}})}$.

![The lattice $N_6$ \[fig1\]](czg-princl1.eps)

Let $L$ be a lattice. For $x,y\in L$, ${{\langle x,y\rangle}}$ is called an *ordered pair* of $L$ if $x\leq y$. The set of ordered pairs of $L$ is denoted by ${{\textup{Pairs}^{\leq}(L)}}$. Note that we shall often use that ${{\textup{Pairs}^{\leq}(S)}}\subseteq {{\textup{Pairs}^{\leq}(L)}}$ holds for sublattices $S$ of $L$; this explains why we work with ordered pairs rather than intervals. Note also that ${{\langle a,b\rangle}}$ is an ordered pair if[f]{} $b/a$ is a quotient; however, the concept of ordered pairs fits better to previous work with quasi-colorings.

By a *quasi-colored lattice* we mean a structure ${{\mathcal L}}={\langle L;\gamma,H,\nu\rangle}$ where $L$ is a lattice, ${\langle H;\nu\rangle}$ is a quasiordered set, $\gamma\colon {{\textup{Pairs}^{\leq}(L)}}\to H$ is a surjective map, and for all ${{\langle u_1,v_1\rangle}},{{\langle u_2,v_2\rangle}}\in {{\textup{Pairs}^{\leq}(L)}}$,

-   if $\gamma({{\langle u_1,v_1\rangle}}){\mathrel{\leq_\nu}}\gamma({{\langle u_2,v_2\rangle}})$, then ${\textup{con}(u_1,v_1)}\leq {\textup{con}(u_2,v_2)}$;

-   if ${\textup{con}(u_1,v_1)}\leq {\textup{con}(u_2,v_2)}$, then $\gamma({{\langle u_1,v_1\rangle}}){\mathrel{\leq_\nu}}\gamma({{\langle u_2,v_2\rangle}})$.

This concept is taken from Czédli [@czgrepres]. Prior to [@czgrepres], the name “coloring" was used for surjective maps onto antichains satisfying in Grätzer, Lakser, and Schmidt [@grlaksersch], and for surjective maps onto antichains satisfying in Grätzer [@grbypict page 39]. However, in [@czgrepres], [@grlaksersch], and [@grbypict], $\gamma({{\langle u,v\rangle}})$ was defined only for covering pairs $u\prec v$. To emphasize that ${\textup{con}(u_1,v_1)}$ and ${\textup{con}(u_2,v_2)}$ belong to the ordered set ${\textup{Princ}(L)}$, we usually write ${\textup{con}(u_1,v_1)}\leq {\textup{con}(u_2,v_2)}$ rather than ${\textup{con}(u_1,v_1)}\subseteq {\textup{con}(u_2,v_2)}$. It follows easily from , , and the surjectivity of $\gamma$ that if ${\langle L;\gamma,H,\nu\rangle}$ is a quasi-colored set, then ${\langle H;\nu\rangle}$ is a directed quasiordered set with least element; possibly with many least elements.

We say that a quadruple ${\langle a_1,b_1,a_2,b_2\rangle}\in L^4$ is an *$N_6$-quadruple* of $L$ if $${\{b_1\wedge b_2=a_1\wedge a_2,\,\, a_1<b_1,\,\,a_2<b_2,\,\, a_1\vee a_2=b_1\vee b_2\}}$$ is a six-element sublattice, see Figure \[fig1\]. If, in addition, $b_1\wedge b_2=0_L$ and $a_1\vee a_2=1_L$, then we speak of a *spanning $N_6$-quadruple*. An $N_6$-quadruple of $L$ is called a *strong $N_6$-quadruple* if it is a spanning one and, for all $i\in{\{1,2\}}$ and $x\in L$, $$\begin{aligned}
0_L < x \leq b_i &{\mathrel{\Longrightarrow}}x\vee a_{3-i}=1_L, \text{ and} \label{labsa}\\
1_L>x \geq a_i&{\mathrel{\Longrightarrow}}x\wedge b_{3-i}=0_L\text.\label{labsb}
$$ For a subset $X$ of $L^2$, the least lattice congruence including $X$ is denoted by ${\textup{con}(X)}$. In particular, ${\textup{con}({\{{{\langle a,b\rangle}}\}})}={\textup{con}(a,b)}$. The least and the largest congruence of $L$ are denoted by $\Delta_L$ and ${\nabla_{\kern -2pt L}}$, respectively.

Now, we are in the position to define the key concept we need. In the present paper, by a *auxiliary structure* we mean a structure $${{\mathcal L}}={\langle L;\gamma, H,\nu,\delta ,{\varepsilon}\rangle}\label{auxstr}$$ such that the following eight properties hold:

-   ${\langle L;\gamma, H,\nu\rangle}$ is a quasi-colored lattice;

-   the quasiordered set ${\langle H;\nu\rangle}$ has exactly one least element, $0_H$, and at most one greatest element;

-   $\delta $ and ${\varepsilon}$ are $H\to L$ maps such that $\delta (0_H)={\varepsilon}(0_H)$ and, for all $x\in H\setminus{\{0_H\}}$, $\delta (x)\prec{\varepsilon}(x)$; note that we often write $a_x$ and $b_x$ instead of $\delta (x)$ and ${\varepsilon}(x)$, respectively;

-   for all $p\in H$, $\gamma({{\langle \delta (p),{\varepsilon}(p)\rangle}})=p$;

-   if $p$ and $q$ are distinct elements of $H\setminus{\{0_H\}}$, then ${\langle \delta (p),{\varepsilon}(p), \delta (q),{\varepsilon}(q)\rangle}$ is an $N_6$-quadruple of $L$;

-   if $p,q\in H$, $p{\mathrel{\parallel_\nu}}q$, and ${\langle \delta (p),{\varepsilon}(p), \delta (q),{\varepsilon}(q)\rangle}$ is a spanning $N_6$-quadruple, then it is a strong $N_6$-quadruple of $L$;

-   If $L$ is a bounded lattice and $|L|>1$, then $$\begin{aligned}
    \bigl|\bigl\{x\in L:{} &0_L\prec x\prec 1_L\text{ and, for all elements }y \text{ in }\cr
    &L\setminus\{0_L,1_L,x\},\,\, x\text{ is a complement of }y\bigr\}\bigr|\geq 3;\end{aligned}$$

-   if $1_H\in H$ and $|L|>1$, then ${\textup{con}\bigl( {\{{{\langle \delta (p),{\varepsilon}(p)\rangle}}: p\in H\text{ and } p\neq 1_H \}}\bigr)} \neq {\nabla_{\kern -2pt L}}$.

It follows from that ${\{\delta(x),{\varepsilon}(x)\}}={\{a_x, b_x\}}$ is disjoint from ${\{0_L,1_L\}}={\varnothing}$, provided $|H|\geq 3$ and $x\in H\setminus{\{0_H\}}$.

If ${\langle H;\nu\rangle}$ is a quasiordered set, then $\Theta_\nu=\nu\cap\nu^{-1}$ is an equivalence relation, and the definition ${[x]\Theta_\nu}\leq {[y]\Theta_\nu}\iff x{\mathrel{\leq_\nu}}y$ turns the quotient set $H/\Theta_\nu$ into an ordered set ${\langle H/\Theta_\nu;\leq\rangle}$. The importance of our auxiliary structures is first shown by the following lemma.

\[impclM\] If ${{\mathcal L}}$ in is an auxiliary structure, then the ordered set ${\textup{Princ}(L)}$ is isomorphic to ${\langle H/\Theta_\nu;\leq\rangle}$. In particular, if $\nu$ is an ordering, then ${\textup{Princ}(L)}$ is isomorphic to the ordered set ${\langle H;\nu\rangle}$.

Clearly, ${\textup{Princ}(L)}={\{{\textup{con}(x,y)}: {{\langle x,y\rangle}}\in{{\textup{Pairs}^{\leq}(L)}}\}}$. Consider the map ${\varphi}\colon {\textup{Princ}(L)}\to H/\Theta_\nu$, defined by ${\textup{con}(x,y)}\mapsto {[\gamma({{\langle x,y\rangle}})]\Theta_\nu}$. If ${\textup{con}(x_1,y_1)}={\textup{con}(x_2,y_2)}$, then ${[\gamma({{\langle x_1,y_1\rangle}})]\Theta_\nu} = {[\gamma({{\langle x_2,y_2\rangle}})]\Theta_\nu}$ follows from . Hence, ${\varphi}$ is a map. It is surjective since so is $\gamma$. Finally, it is bijective and an order isomorphism by and .

We say that an auxiliary structure ${{\mathcal L}}={\langle L;\gamma, H,\nu,\delta ,{\varepsilon}\rangle}$ is *countable* if $|L|\leq\aleph_0$ and $|H|\leq\aleph_0$. Next, we give an example.

\[exegy\] Let $H$ be a set, finite or infinite, such that $0_H,1_H\in H$ and $|H|\geq 3$. Let us define $\nu={\textup{quo}\bigl(({\{0_H\}}\times H) \cup (H\times {\{1_H\}})\bigr)}$; note that ${\langle H;\nu\rangle}$ is an ordered set (actually, a modular lattice of length 2). Let $L$ be the lattice depicted in Figure \[fig2\], where ${\{h,g,p,q,\dots\}}$ is the set $H\setminus{\{0_H,1_H\}}$. For $x\prec y$, $\gamma({{\langle x,y\rangle}})$ is defined by the labeling of edges. Note that, in Figure \[fig2\], we often write $0$ and $1$ rather than $0_H$ and $1_H$, because of space consideration. Let $\gamma({{\langle x,x\rangle}})=0_H$ for $x\in L$, and let $\gamma({{\langle x,y\rangle}})=1_H$ for $x<y$ if $x\not\prec y$. Let $\delta (0_H)={\varepsilon}(0_H)=x_0$. For $s\in H\setminus{\{0_H\}}$, we define $\delta (s)=a_s$ and ${\varepsilon}(s)=b_s$. Now, obviously, ${{\mathcal L}}={\langle L;\gamma, H,\nu,\delta ,{\varepsilon}\rangle}$ is an auxiliary structure. If $|H|\leq \aleph_0$, then ${{\mathcal L}}$ is countable.

![The auxiliary structure in Example \[exegy\] \[fig2\]](czg-princl2.eps)

Substructures are defined in the natural way; note that $\nu=\nu'\cap H^2$ will not be required below. Namely,

\[defbeagy\] Let ${{\mathcal L}}={\langle L;\gamma, H,\nu,\delta ,{\varepsilon}\rangle}$ and ${{\mathcal L}}'={\langle L';\gamma', H',\nu',\delta ',{\varepsilon}'\rangle}$ be auxiliary structures. We say that ${{\mathcal L}}$ is a *substructure* of ${{\mathcal L}}'$ if the following hold:

$L$ is a sublattice of $L'$, $H\subseteq H'$, $\nu\subseteq\nu'$, and $0_{H'}=0_H$;

$\gamma$ is the restriction of $\gamma'$ to ${{\textup{Pairs}^{\leq}(L)}}$, $\delta$ is the restriction of $\delta'$ to $H$, and ${\varepsilon}$ is the restriction of ${\varepsilon}'$ to $H$.

Clearly, if ${{\mathcal L}}$, ${{\mathcal L}}'$, and ${{\mathcal L}}''$ are auxiliary structures such that ${{\mathcal L}}$ is a substructure of ${{\mathcal L}}'$ and ${{\mathcal L}}'$ is a substructure of ${{\mathcal L}}''$, then ${{\mathcal L}}$ is a substructure of ${{\mathcal L}}''$; this fact will be used implicitly. The following lemma indicates how easily but efficiently we can work with auxiliary structures.

For an auxiliary structure ${{\mathcal L}}={\langle L;\gamma, H,\nu,\delta ,{\varepsilon}\rangle}$ and an arbitrary (possibly empty) set $K$, we define the following objects. Let ${{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$ be the disjoint union $H\cup K\cup{\{1_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}\}}$, and let $0_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}=0_H$. Define ${{\nu^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}\in{\textup{Quord}({{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}})}$ by $${{\nu^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}={\textup{quo}\bigl(\nu \cup({\{0_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}  \}} \times {{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}} )  \cup  ({{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}\times{\{  1_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}\}}) \bigr)}\text.$$ Consider the lattice ${{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$ defined by Figure \[fig3\], where $u,v,\dots$ denote the elements of $K$. The thick dotted lines indicate $\leq$ but not necessarily $\prec$; they are edges only if $L$ is bounded. Note that all “new” lattice elements distinct from $0_{{{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}$ and $1_{{{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}$, that is, all elements of ${{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}\setminus(L\cup {\{0_{{{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}, 1_{{{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}\}})$, are complements of all “old” elements. Extend $\delta$ and ${\varepsilon}$ to maps ${{\delta^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}},{{{\varepsilon}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}\colon {{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}} \to{{{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}$ by letting ${{\delta ^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}(w)=a_w$ and ${{{\varepsilon}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}(w)=b_w$ for $w\in K\cup{\{1_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}\}}$. Define ${{\gamma^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}\colon {{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}})}}\to{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$ by $${{\gamma^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}(
{{\langle x,y\rangle}})=
\begin{cases}
\gamma({{\langle x,y\rangle}}),& \text{if } {{\langle x,y\rangle}}\in{{\textup{Pairs}^{\leq}(L)}},\cr
w, &\text{if } x=a_w,\,\, y=b_w,\text{ and }w\in K,\cr
0_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}},&\text{if }x=y,\cr
1_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}},&\text{otherwise.}
\end{cases}$$ By space consideration again, the edge label $1$ in Figure \[fig3\] stands for $1_{{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}$. Finally, let ${{{{\mathcal L}}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}={\langle {{L^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}};{{\gamma^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}},{{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}},{{\nu^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}, {{\delta ^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}},{{{\varepsilon}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}\rangle}$. The straightforward proof of the following lemma will be omitted.

\[lupstp\] If ${{\mathcal L}}$ is an auxiliary structure, then so is ${{{{\mathcal L}}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$. Furthermore, ${{\mathcal L}}$ is a substructure of ${{{{\mathcal L}}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$, and if ${{\mathcal L}}$ and $K$ are countable, then so is ${{{{\mathcal L}}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$. Moreover, if $p,q\in {{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$ such that ${\{p,q\}}\not\subseteq H$ and $p\parallel_{{{\nu^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}}q$, then ${\langle {{\delta ^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}(p), {{{\varepsilon}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}(p),{{\delta ^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}(q), {{{\varepsilon}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}(q)  \rangle}$ is a strong $N_6$-quadruple.

Since new bottom and top elements are added, we say that ${{{{\mathcal L}}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$ is obtained from ${{\mathcal L}}$ by a *vertical extension*; this motivates the triangle aiming upwards in its notation.

![The auxiliary structure ${{{{\mathcal L}}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$ \[fig3\]](czg-princl3.eps)

![Grätzer’s lattice ${L_{\textup{GG}}}$ \[fig4\]](czg-princl4.eps)

Horizontal extensions of auxiliary structures
=============================================

The key role in Grätzer [@ggprincl] is played by the lattice ${L_{\textup{GG}}}$; see Figure \[fig4\]. We also need this lattice. Assume that $$\begin{aligned}
{{\mathcal L}}&={\langle L;\gamma, H,\nu,\delta ,{\varepsilon}\rangle}\text{ is an auxiliary structure, }p,q\in H\text{, } p{\mathrel{\parallel_\nu}}q,\text{ and} \cr
&{\langle a_p,b_p,a_q,b_q\rangle}={\langle \delta (p),{\varepsilon}(p),\delta (q),{\varepsilon}(q) \rangle} \text{ is a}\cr
&\text{spanning or, equivalently, a strong }N_6\text{-quadruple}.
\end{aligned}\label{asumLpar}$$ The equivalence of “spanning” and “strong” in follows from . We define a structure ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ as follows, and it will take a lot of work to prove that it is an auxiliary structure. We call ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ a *horizontal extension* of ${{\mathcal L}}$; this explains the horizontal triangle in the notation. By changing the sublattice ${\{0_L,a_p,b_p,a_q,b_q,1_L\}}$ into an ${L_{\textup{GG}}}$ as it is depicted in Figure \[fig4\], that is, by inserting the black-filled elements of Figure \[fig4\] into $L$, we obtain an ordered set denoted by ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$; see also later for more exact details. (We will prove that ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is a lattice and $L$ is a sublattice in it.) The construction of ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ from ${{\mathcal L}}$ is illustrated in Figure \[fig5\]. Note that there can be much more elements and in a more complicated way than indicated. The solid lines represent the covering relation but the dotted lines are not necessarily edges. The new lattice ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is obtained from $L$ by inserting the black-filled elements. Note that while Grätzer [@ggprincl] constructed a lattice of length 5, here even the interval, say, $[b_p, 1_L]$ can be of infinite length.

![Obtaining ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ from ${{\mathcal L}}$ \[fig5\]](czg-princl5.eps)

Let ${{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}=H$. In ${\textup{Quord}({{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}$, we define ${{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}={\textup{quo}\bigl(\nu\cup{\{{{\langle p,q\rangle}}\}}\bigr)}$. We extend $\gamma$ to ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}\colon {{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}}\to {{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ by $${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle x,y\rangle}})=
\begin{cases}
\gamma({{\langle x,y\rangle}}),&\text{if }{{\langle x,y\rangle}}\in{{\textup{Pairs}^{\leq}(L)}},\cr
p,&\text{if }{{\langle x,y\rangle}}\in{\{{{\langle d_{pq},e_{pq}\rangle}}, {{\langle f_{pq},g_{pq}\rangle}}  \}},\cr
q,&\text{if }{{\langle x,y\rangle}}\in{\{{{\langle c_{pq},d_{pq}\rangle}}, {{\langle c_{pq},e_{pq}\rangle}}  \}},\cr
0_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}, &\text{if } x=y,\cr
1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}, &\text{otherwise.}
\end{cases}$$ The definition of ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is also illustrated in Figure \[fig5\], where the edge color $1$ stands for $1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$. Finally, after letting ${{\delta ^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}=\delta $ and ${{{\varepsilon}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}={\varepsilon}$, we define $${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}={\langle {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}};{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}, {{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}},{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}},{{\delta ^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}},{{{\varepsilon}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}\rangle}\text.\label{spaldef}$$

\[spalislat\] If ${{\mathcal L}}$ satisfies , then ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is a lattice and $L$ is a sublattice of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$.

First, we describe the ordering of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ more precisely; this description is the real definition of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. Let $$\begin{aligned}
N_6^{pq}&={{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}\setminus L={\{c_{pq},d_{pq},e_{pq},f_{pq},g_{pq}\}},\cr 
B_6^{pq}&={\{0_L, a_p,b_p,a_q,b_q,1_L \}}\text{, and}\cr
S_6^{pq}&=\{0_L, a_p,b_p,a_q,b_q,c_{pq},d_{pq},e_{pq},f_{pq},g_{pq}, 1_L\} = N_6^{pq}\cup B_6^{pq}\text{.} \cr
\end{aligned}\label{sodiHGrj}$$ Here $S_6^{pq}$ is isomorphic to the lattice ${L_{\textup{GG}}}$, and its “boundary”, $B_6^{pq}$, to $N_6$. The elements of $L$, $N_6^{pq}$, and $B_6^{pq}$ are called *old*, *new*, and *boundary* elements, respectively. For $x,y\in {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, we define $x\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} y\iff$ $$\begin{cases}
x\leq_L y ,&\text{if }x,y\in L\text{, or}\cr
x\leq_{S_6^{pq}} y ,&\text{if }x,y\in S_6^{pq}\text{, or}\cr
\exists z\in  B_6^{pq}:
x\leq_L z\text{ and }z\leq_{S_6^{pq}}y,&\text{if }x\in L\setminus S_6^{pq}\text{ and } y\in N_6^{pq}\text{, or}\cr
\exists z\in  B_6^{pq}:
x\leq_{S_6^{pq}}z\text{ and }z\leq_L y,&\text{if }x\in N_6^{pq}\text{ and } y\in L\setminus S_6^{pq}\text.
\end{cases}
\label{spaorder}$$ Observe that for $u_1,u_3\in B_6^{pq}$ and $u_2\in N_6^{pq}$, the conjunction of $u_1\leq_{S_6^{pq}}u_2$ and $u_2 \leq_{S_6^{pq}} u_3$ implies ${\{0_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}},1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}\}}\cap{\{u_1,u_3\}}\neq{\varnothing}$. Hence, it is straightforward to see that $\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ is an ordering and $\leq_L$ is the restriction of $\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ to $L$.

For $x\in N_6^{pq}$, there is a unique least element ${{x^\ast}}$ of $B_6^{pq}$ such that $x\leq_{S_6^{pq}}{{x^\ast}}$ (that is, $x\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}{{x^\ast}}$). If $x\in L$, then we let ${{x^\ast}}=x$. Similarly, for $x\in N_6^{pq}$, there is a unique largest element ${{x_\ast}}$ of $B_6^{pq}$ such that ${{x_\ast}}\leq_{S_6^{pq}} x$. Again, for $x\in L$, we let ${{x_\ast}}=x$. With this notation, is clearly equivalent to $$x\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} y\iff
\begin{cases}
x\leq_L y,&\text{if }x,y\in L\text{, or}\cr
x\leq_{S_6^{pq}} y,&\text{if }x,y\in S_6^{pq}\text{, or}\cr
x\leq_L {{y_\ast}},&\text{if }x\in L\setminus S_6^{pq}\text{ and } y\in N_6^{pq}\text{, or}\cr
{{x^\ast}}\leq_L y,&\text{if }x\in N_6^{pq}\text{ and } y\in L\setminus S_6^{pq}\text.
\end{cases}\label{spanorder}$$

Next, for $x\parallel y\in{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, we want to show that $x$ and $y$ has a join in ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. We can assume that ${\{x,y\}}$ has an upper bound $z$ in $N_6^{pq}$, because otherwise ${{x^\ast}}\vee_L {{y^\ast}}$ would clearly be the join of $x$ and $y$ in ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. If $z$ belonged to ${\{c_{pq},d_{pq},e_{pq}\}}$, then the principal ideal ${\mathord\downarrow z}$ (taken in ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$) would be a chain, and this would contradict $x\parallel y$. Hence, $z\in {\{f_{pq},g_{pq}\}}$. If both $x$ and $y$ belong to $N_6^{pq}$, then $x\parallel y$ gives ${\{x,y\}}={\{e_{pq},f_{pq}\}}$, $z$ and $1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ are the only upper bounds of ${\{x,y\}}$, and $z$ is the join of $x$ and $y$. Hence, we can assume that $x\in L$. If $y$ also belongs to $L$, then $x\leq{{z_\ast}}$ and $y\leq {{z_\ast}}$ yields $x\vee_L y\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} {{z_\ast}}\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} z$, and $x\vee_L y$ is the join of $x$ and $y$ in ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ since $z$ was an arbitrary upper bound of ${\{x,y\}}$ in $N_6^{pq}$.

Therefore, we can assume that $x\in L$ and $y\in N_6^{pq}$. It follows from $b_p\wedge_L b_q=0_L$ that, for each $u\in L$, ${\mathord\uparrow u}\cap B_6^{pq}$ has a smallest element; we denote it by $\widehat u$. For $u\in N_6^{pq}$, we let $\widehat u=u$. Note that, for every $u\in {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, $\widehat u$ is the smallest element of ${\mathord\uparrow u}\cap S_6^{pq}$. The existence of $z$, mentioned above, implies that $\widehat x\in  {\{a_p,b_p\}}$.

We assert that $\widehat x\vee_{S_6^{pq}} y= \widehat x\vee_{S_6^{pq}}\widehat y$ is the join of $x$ and $y$ in ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. (Note that $\widehat x\vee_{S_6^{pq}} y\subseteq {\{f_{pq},g_{pq}\}}$.) We can assume $y\in{\{c_{pq},d_{pq},e_{pq}\}}$ since otherwise $1_L$ is the only upper bound of $y$ in $L$ and $x\vee_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}y=\widehat x\vee_{S_6^{pq}} y$ is clear. Consider an upper bound $t\in L$ of $x$ and $y$. Since $y\in{\{c_{pq},d_{pq},e_{pq}\}}$, we have $a_q\leq t$ and $x\vee_L a_q\leq t$. From $x\parallel y\in{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ and $\widehat x\in  {\{a_p,b_p\}}$, we obtain $0_L<x\leq b_p$. Since ${\langle a_p,b_p,a_q,b_q\rangle}$ is a strong $N_6$-quadruple by , the validity of for ${{\mathcal L}}$ implies $\widehat x\vee_{S_6^{pq}} y\,\leq 1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}=1_L=x\vee_L a_q\leq t$. This shows that $\widehat x\vee_{S_6^{pq}} y$ is the join of $x$ and $y$ in ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. The case $x,y\in L$ showed that ${\langle L;\vee\rangle}$ is a subsemilattice of ${\langle {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}};\vee\rangle}$. For later reference, we summarize the description of join in a concise form as follows; note that $x\parallel y$ is not assumed here: $$x\vee_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}y=\begin{cases}
{{x^\ast}}\vee_L {{y^\ast}}, &\text{if } {\{x,y\}}\not\subseteq {\mathord\downarrow g_{pq}}\text{ or }{\{x,y\}}\subseteq L , \cr
\widehat x\vee_{S_6^{pq}} \widehat y&\text{otherwise, that is, if } {\{x,y\}}\subseteq {\mathord\downarrow g_{pq}}\text{ and }{\{x,y\}}\not\subseteq L\text.
\end{cases}\label{joindeR}$$ We have shown that any two elements of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ have a join. Although $S_6^{pq}$ and the construction of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ are not exactly selfdual, by interchanging the role of ${\{f_{pq},g_{pq}\}}$ and that of ${\{c_{pq},d_{pq},e_{pq}\}}$, we can easily dualize the argument above. Thus, we conclude that ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is a lattice and $L$ a sublattice of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$.

The following lemma is due to Dilworth [@dilworth1950a], see also Grätzer [@grglt Theorem III.1.2].

\[llajtorja\] If $L$ is a lattice and ${{\langle u_1,v_1\rangle}},{{\langle u_2,v_2\rangle}}\in{{\textup{Pairs}^{\leq}(L)}}$, then the following three conditions are equivalent.

${\textup{con}(u_1,v_1)}\leq {\textup{con}(u_2,v_2)}$;

${{\langle u_1,v_1\rangle}}\in {\textup{con}(u_2,v_2)}$;

there exists an $n\in\mathbb N$ and there are $x_{i} \in L$ for $i\in{\{0,\dots,n\}}$ and ${{\langle y_{i j},z_{i j}\rangle}} \in{{\textup{Pairs}^{\leq}(L)}}$ for ${{\langle i,j\rangle}}\in{\{1,\dots,n\}}\times{\{0,\dots,n\}}$ such that the following equalities and inequalities hold: $$\begin{aligned}
u_1&=x_{0}\leq x_{1}\leq\dots\leq x_{n-1}\leq x_{n}=v_1\cr
y_{i0} &=x_{i-1}\text{,  }y_{in}=u_2\text{,  }z_{i0}=x_i\text{, and }z_{in}=v_2\text{ for }1\leq i\leq n,\cr  
y_{i,j-1}&= z_{i,j-1}\wedge y_{ij}
\text{ and } z_{i,j-1}\leq z_{ij}
\text{ for }j \text{ odd, }  i,j\in{\{1,\dots,n\}},\cr
z_{i,j-1} & = y_{i,j-1}\vee z_{ij} \text{ and }y_{i,j-1}\geq y_{ij}\text{ for }j \text{ even, }  i,j\in{\{1,\dots,n\}}\text.
\end{aligned}\label{lajtorjaformula}$$

The situation of Lemma \[llajtorja\] is outlined in Figure \[fig6\]; note that not all elements are depicted, and the elements are not necessarily distinct. The second half of says that, in terms of Grätzer [@grglt], ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ is *weakly* up or down perspective into ${{\langle y_{ij},z_{ij}\rangle}}$; up for $j$ odd and down for $j$ even. Besides weak perspectivity, we shall also need a more specific concept; recall that ${{\langle x_1,y_1\rangle}}$ is *perspective* to ${{\langle x_2,y_2\rangle}}$ if there are $i,j\in{\{1,2\}}$ such that $i\neq j$, $x_i=y_i\wedge x_j$, and $y_j=x_j\vee y_i$.

![Illustrating Lemma \[llajtorja\] for $n=4$ \[fig6\]](czg-princl6.eps)

For a quasiordered set ${\langle H;\nu\rangle}$ and $p, q_1,\dots,q_n\in H$, we say that $p$ is a *join* of the elements $q_1,\dots,q_n$, in notation, $p=\bigvee_{i=1}^n q_i$, if $q_i{\mathrel{\leq_\nu}}p$ for all $i$ and, for every $r\in H$, the conjunction of $q_i{\mathrel{\leq_\nu}}r$ for $i=1,\dots,n$ implies $p{\mathrel{\leq_\nu}}r$. This concept is used in the next lemma. Note that even if a join exists, it need not be unique.

\[chainlemma\] If ${\langle   L; \gamma,  H,\nu\rangle}$ is a quasi-colored lattice and ${\{u_0\leq u_1\leq\dots \leq u_n\}}$ is a finite chain in $L$, then $$\gamma({{\langle u_0,u_n\rangle}})=\bigvee_{i=1}^n \gamma({{\langle u_{i-1},u_i\rangle}})\quad\text{ holds in }{\langle H;\nu\rangle}\text.\label{lancjoin}$$

Let $p=\gamma({{\langle u_0,u_n\rangle}})$ and $q_i=\gamma({{\langle u_{i-1},u_i\rangle}})$. Since ${\textup{con}(u_{i-1},u_i)}\leq {\textup{con}(u_0,u_n)}$, yields $q_i{\mathrel{\leq_\nu}}p$ for all $i$. Next, assume that $r\in H$ such that $q_i{\mathrel{\leq_\nu}}r$ for all $i$. By the surjectivity of $\gamma$, there exists a ${{\langle v,w\rangle}}\in{{\textup{Pairs}^{\leq}(L)}}$ such that $\gamma({{\langle v,w\rangle}})=r$. It follows by that ${{\langle u_{i-1},u_i\rangle}}\in {\textup{con}(u_{i-1},u_i)}\leq {\textup{con}(v,w)}$. Since ${\textup{con}(v,w)}$ is transitive and collapses the pairs ${{\langle u_{i-1},u_i\rangle}}$, it collapses ${{\langle u_{0},u_n\rangle}}$. Hence, ${\textup{con}(u_{0},u_n)}\leq {\textup{con}(v,w)}$, and implies $p{\mathrel{\leq_\nu}}r$.

Now, we are in the position to deal with the following lemma.

\[mainlemma\] The structure ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, which is defined in with assumption , is an auxiliary structure, and ${{\mathcal L}}$ is a substructure of ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. Furthermore, if ${{\mathcal L}}$ is countable, then so is ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$.

Since we work both in ${{\mathcal L}}$ and ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, relations, operations and maps are often subscripted by the relevant structure. By Lemma \[spalislat\], ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is a lattice. Obviously, and hold for ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. Since ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is an extension of $\gamma$, ${{\delta^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}= \delta$, ${{{\varepsilon}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}= {\varepsilon}$, and $L$ is a sublattice of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, we obtain that and hold in ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$.

Let $r_1,r_2\in{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. Since $\nu$ is transitive, $p{\mathrel{\parallel_\nu}}q$, and ${{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}={\textup{quo}\bigl(\nu\cup {\{{{\langle p,q\rangle}}\}}\bigr)}$, we obtain that $$\label{twopssb}
{{\langle r_1,r_2\rangle}}\in {{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}\iff
r_1{\mathrel{\leq_\nu}}p\text{ and }q{\mathrel{\leq_\nu}}r_2\text{, or }r_1{\mathrel{\leq_\nu}}r_2\text.$$ This clearly implies that holds for ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$.

It follows from that if ${{\langle x,y\rangle}}\in {{\textup{Pairs}^{\leq}(L)}}$ and $\gamma({{\langle x,y\rangle}})=1_{H}$, then we have ${\textup{con}_{L}(x,y)}={\nabla_{\kern -2pt L}}$. Combining this with , we obtain easily that for all ${{\langle x,y\rangle}}\in{{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}}$, $${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle x,y\rangle}})=1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} {\mathrel{\Longrightarrow}}{\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(x,y)}  = {\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}\text.\label{haegyakok}$$

Let $\Theta$ denote the congruence of $L$ described in . Consider the equivalence relation ${{\Theta^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ on ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ whose classes (in other words, blocks) are the $\Theta$-classes, ${\{c_{pq},d_{pq},e_{pq}\}}$ and ${\{f_{pq},f_{pq}\}}$. Based on and its dual, a straightforward argument shows that, for all $x,y\in{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, ${{\langle x\wedge y,x\rangle}}\in{{\Theta^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ if[f]{} ${{\langle y,x\vee y\rangle}}\in {{\Theta^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. Clearly, the intersection of ${{\Theta^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ and the ordering of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is transitive. Hence, we conclude that ${{\Theta^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ is a congruence on ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. Since it is distinct from ${\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}$, ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ satisfies .

Next, we prove the converse of . Assume that ${{\langle x,y\rangle}}\in{{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}}$ such that ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle x,y\rangle}})\neq 1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$; we want to show that ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(x,y)}\neq{\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}$. Since this is clear if $x=y$, we assume $x\neq y$. First, if $x,y\in L$, then let $r=\gamma({{\langle x,y\rangle}})$. Applying to $\gamma$ and to ${{\mathcal L}}$, we obtain $ {\textup{con}_{L}(x,y)} ={\textup{con}_{L}(\delta (r),\delta (r))}$. Hence $\Theta$, which we used in the previous paragraph, collapses ${{\langle x,y\rangle}}$, and ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(x,y)}\subseteq{{\Theta^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}\subset  {\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}$. Second, if ${\{x,y\}}\cap L={\varnothing}$, then ${{\langle x,y\rangle}}$ is perspective to ${{\langle a_p,b_p\rangle}}$ or ${{\langle a_q,b_q\rangle}}$, whence $ {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(x,y)} \in
{\bigl\{  {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(a_p,b_p)},  {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(a_q,b_q)}   \bigr\}}$ reduces the present case to the previous one. Finally, $|L\cap{\{x,y\}}|=1$ is excluded since then ${{\langle x,y\rangle}}$ would be $1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$-colored. Now, after verifying the converse of , we have proved that for all ${{\langle x,y\rangle}}\in{{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}}$, $${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle x,y\rangle}})=1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} \iff {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(x,y)}  = {\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}\text.\label{haiirkok}$$

Next, to prove that ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ satisfies , assume that ${{\langle u_1,v_1\rangle}},{{\langle u_2,v_2\rangle}}\in {{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}}$ such that ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_1,v_1\rangle}} ){\mathrel{\leq_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}}{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_2,v_2\rangle}} )$. Let $r_i={{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_i,v_i\rangle}} )$, for $i\in{\{1,2\}}$. We have to show ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)}\leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$. By , we can assume that $r_2\neq 1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$. Thus, by , we have $r_1\neq 1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$. We can also assume that $r_1\neq 0_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ since otherwise ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)}={\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,u_1)}=\Delta_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ would clearly imply ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)}\leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$. Thus, $r_1,r_2\in H\setminus{\{0_H,1_H\}}$. By the construction of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, ${{\langle u_i,v_i\rangle}}$ is perspective to some ${{\langle u_i',v_i'\rangle}}\in{{\textup{Pairs}^{\leq}(L)}}$ such that ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_i,v_i\rangle}})={{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_i',v_i\rangle}}')$, and perspectivity implies ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_i,v_i)}= {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_i',v_i')}$. Therefore, we can assume that ${{\langle u_1,v_1\rangle}}, {{\langle u_2,v_2\rangle}} \in {{\textup{Pairs}^{\leq}(L)}}$, because otherwise we could work with ${{\langle u_1',v_1'\rangle}}$ and ${{\langle u_2',v_2'\rangle}}$.

According to , we distinguish two cases. First, assume that $r_1{\mathrel{\leq_\nu}}r_2$. Since ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ extends $\gamma$, we have $\gamma({{\langle u_1,v_1\rangle}} ) = {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_1,v_1\rangle}} )
=r_1{\mathrel{\leq_\nu}}r_2={{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_2,v_2\rangle}} )= \gamma({{\langle u_2,v_2\rangle}} )$. Applying to $\gamma$, we obtain ${{\langle u_1,v_1\rangle}}\in {\textup{con}_{L}(u_1,v_1)}\leq {\textup{con}_{L}(u_2,v_2)}$. Using Lemma \[llajtorja\], first in $L$ and then, backwards, in ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, we obtain ${{\langle u_1,v_1\rangle}}\in{\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$, which yields ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)}\leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$.

Second, assume that $r_1{\mathrel{\leq_\nu}}p$ and $q{\mathrel{\leq_\nu}}r_2$. Since ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle a_p,b_p\rangle}})=\gamma({{\langle a_p,b_p\rangle}})=p$ and ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle a_q,b_q\rangle}})=q$ by , the argument of the previous paragraph yields that we have ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)}\leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(a_p,b_p)}$ and ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(a_q,b_q)}\leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$. Clearly (or applying Lemma \[llajtorja\] within $S_6^{pq})$, we have ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(a_p,b_p)}\leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(a_q,b_q)}$. Hence, transitivity yields ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)}\leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$. Consequently, ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ satisfies .

Next, to prove that ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ satisfies , assume that ${{\langle u_1,v_1\rangle}}, {{\langle u_2,v_2\rangle}}\in{{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}}$ such that ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)} \leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$. Our purpose is to show the inequality ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_1,v_1\rangle}} ){\mathrel{\leq_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}}{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_2,v_2\rangle}} )$. By , we can assume ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}\neq {\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}$, and we can obviously assume $u_1\neq v_1$. That is, ${\{  {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)},\, {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}  \}}\cap {\{\Delta_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}},{\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}\}}={\varnothing}$. A pair ${{\langle w_1,w_2\rangle}}\in{{\textup{Pairs}^{\leq}({{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}})}}$ is called *mixed* if $|{\{i: w_i\in L\}}|=1$. That is, if one of the components is old and the other one is new. It follows from the construction of ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ and that none of ${{\langle u_1,v_1\rangle}}$ and ${{\langle u_2,v_2\rangle}}$ is mixed. If ${{\langle u_1,v_1\rangle}}$ is a new pair, that is, if ${\{u_1,v_1\}}\cap L={\varnothing}$, then we can consider an old pair ${{\langle u'_1,v'_1\rangle}}$ such that ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_1',v_1'\rangle}} )={{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_1,v_1\rangle}} )$ and, by perspectivity, ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u'_1,v'_1)} = {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)}$. Hence, we can assume that ${{\langle u_1,v_1\rangle}}$ is an old pair, and similarly for the other pair. That is, we assume that both ${{\langle u_1,v_1\rangle}}$ and ${{\langle u_2,v_2\rangle}}$ belong to ${{\textup{Pairs}^{\leq}( L)}}$.

The starting assumption ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_1,v_1)} \leq {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$ means that ${{\langle u_1,v_1\rangle}} \in {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$. This is witnessed by Lemma \[llajtorja\]. Let $x_j, y_{ij}, z_{ij}\in {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ be elements for $i\in{\{1,\dots,n\}}$ and $j\in{\{0,\dots,n\}}$ that satisfy ; see also Figure \[fig6\]. To ease our terminology, the ordered pairs ${{\langle y_{ij},y_{ij}\rangle}}$ will be called *witness pairs* (of the containment ${{\langle u_1,v_1\rangle}} \in {\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}$). Since ${\textup{con}_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}(u_2,v_2)}\neq {\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}$, none of the witness pairs generate ${\nabla_{\kern -2pt {{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}$. Thus, by , $$\text{none of the witness pairs is mixed or }1_{{{H^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}\text{-colored.}\label{nonm1col}$$

Take two consecutive witness pairs, ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ and ${{\langle y_{ij},z_{ij}\rangle}}$. Here $i,j\in{\{1,\dots,n\}}$. Our next purpose is to show that $${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) {\mathrel{\leq_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}}{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{ij},z_{ij}\rangle}})\text. \label{winprs}$$ We assume $y_{i,j-1}<z_{i,j-1}$ since trivially holds if these two elements are equal. Hence, ${y_{ij}}<{z_{ij}}$ also holds.

If both ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ and ${{\langle y_{ij},z_{ij}\rangle}}$ are old pairs, that is, if they belong to ${{\textup{Pairs}^{\leq}(L)}}$, then yields $ {\textup{con}_{L}(y_{i,j-1},z_{i,j-1})}\leq {\textup{con}_{L}(y_{ij},z_{ij})}$. From this, we conclude the relation $\gamma({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) {\mathrel{\leq_\nu}}\gamma({{\langle y_{ij},z_{ij}\rangle}})$ by , applied for ${{\mathcal L}}$, and we obtain the validity of for old witness pairs, because ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ extends $\gamma$.

If both ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ and ${{\langle y_{ij},z_{ij}\rangle}}$ are new pairs, that is, if they belong to ${{\textup{Pairs}^{\leq}(N_6^{pq})}}$, then and allow only two possibilities: ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) = {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{ij},z_{ij}\rangle}})$, or ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) =p$ and $ {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{ij},z_{ij}\rangle}})=q$. In both cases, holds.

\[old2newcase\] Assume first that $j$ is odd, that is, ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ is weakly up-perspective into ${{\langle y_{ij},z_{ij}\rangle}}$. Since $y_{ij}$, being a new element, and $z_{i,j-1}$ are both distinct from $y_{i,j-1}$, $$z_{i,j-1}\parallel y_{ij}\text.\label{osidHn}$$ Since $0_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}\leq y_{i,j-1}<z_{i,j-1} < z_{ij} $, $z_{i,j-1}$ is an old element, and $z_{ij}$ is a new one, $z_{ij}\in{\{f_{pq}, g_{pq}\}}$. Taking $y_{ij}<z_{ij}$ and into account, we obtain $y_{ij}=f_{pq}$ and $z_{ij}=g_{pq}$. Applying the definition of $\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ for the elements of the old witness pair and using the “weak up-perspectivity relations” from , we have $y_{i,j-1}\leq a_p<f_{pq}$. Similarly, but also taking $z_{i,j-1}\parallel y_{ij}$ into account, we obtain $z_{i,j-1}\leq b_p<g_{pq}$. We claim that ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ is up-perspective to ${{\langle a_p,b_p\rangle}}$. We can assume $z_{i,j-1}<b_p$, because otherwise they would be equal, we would have $y_{i,j-1}=z_{i,j-y}\wedge f_{pq}=b_p\wedge f_{pq}=a_p$, and the two pairs would be the same. Hence, from $a_p\prec b_p$, $z_{i,j-1}<b_p$ and $z_{i,j-1}\parallel y_{ij}=f_{pq}$, we obtain $z_{i,j-1}\parallel a_p$ and $z_{i,j-1}\vee a_p=b_p$. Since $y_{i,j-1}\leq z_{i,j-1}\wedge a_p \leq z_{i,j-1}\wedge y_j=y_{i,j-1}$, the old pair ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ is up-perspective to the old pair ${{\langle a_p,b_p\rangle}}$. Hence, ${\textup{con}_{L}(y_{i,j-1},z_{i,j-1})}={\textup{con}_{L}(a_p,b_p)}$. Applying for ${{\mathcal L}}$, we obtain $$\begin{aligned}
{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) 
&=\gamma({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) \overset{{\textup{(C2)}}{}}=
\gamma({{\langle a_p,b_p\rangle}})
\overset{{\textup{(A4)}}{}}=p\cr 
&={{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle f_{pq},f_{pq}\rangle}})
= {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{ij},z_{ij}\rangle}}),\end{aligned}$$ which implies if $j$ is odd.

Second, let $j$ be even. That is, we assume that ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ is weakly down-perspective into ${{\langle y_{ij},z_{ij}\rangle}}$. The dual of the previous argument shows that $y_{ij}=c_{pq}$ and $z_{ij}\in{\{d_{pq},e_{pq}\}}$. However, $z_{ij}=d_{pq}$ or $z_{ij}=e_{pq}$ does not make any difference, and ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) 
=q= {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle a_q,b_q\rangle}})= {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{ij},z_{ij}\rangle}})$ settles for $j$ even.

Like in Case \[old2newcase\], it suffices to deal with an odd $j$, because an even $j$ could be treated dually. Since ${{\langle y_{i,j-1},z_{i,j-1}\rangle}}$ is weakly up-perspective into ${{\langle y_{ij},z_{ij}\rangle}}$ and $1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ is the only old element above $f_{pq}$, we obtain $y_{i,j-1}\in{\{c_{pq}, d_{pq},e_{pq}\}}$. We obtain as before. Taking also into account, we obtain that $y_{i,j-1}=c_{pq}$ and $z_{i,j-1}$ is one of $d_{pq}$ and $e_{pq}$. No matter which one, an argument dual to the one used in Case \[old2newcase\] yields $a_q=b_{q}\wedge y_{ij}$ and $b_q\leq z_{ij}$. Hence, ${{\langle a_q,b_q\rangle}}$ is weakly up-perspective into ${{\langle y_{ij},z_{ij}\rangle}}$, and we obtain $${\textup{con}_{L}(a_q,b_q)}\leq {\textup{con}_{L}(y_{ij},z_{ij})} \overset{{\textup{(C2)}}}{{\mathrel{\Longrightarrow}}}
q\overset{{\textup{(A4)}}}= \gamma({{\langle a_q,b_q\rangle}} ){\mathrel{\leq_\nu}}\gamma({{\langle y_{ij},z_{ij}\rangle}}),$$ which implies $${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{i,j-1},z_{i,j-1}\rangle}}) =q \leq_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{ij},z_{ij}\rangle}}),$$ and follows again.

Now that we have proved , observe that for $j=1,\dots,n$ and transitivity yield ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle x_{i-1},x_{i}\rangle}}) =
{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{i0},z_{i0}\rangle}})  {\mathrel{\leq_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}}{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle y_{in},z_{in}\rangle}}) = {{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_2,v_2\rangle}})$. Hence, Lemma \[chainlemma\] implies ${{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_1,v_1\rangle}}){\mathrel{\leq_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}}}{{\gamma^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}({{\langle u_2,v_2\rangle}})$. Therefore, ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ satisfies , and holds for ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$.

Next, to prove that ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ satisfies , assume that $r,s\in H$ such that $r\parallel_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} s$ and ${\langle \delta (r),{\varepsilon}(r), \delta (s),{\varepsilon}(s)\rangle}={\langle a_r,b_r,a_s,b_s\rangle}$ is a spanning $N_6$-quadruple. We want to show that it is a strong $N_6$-quadruple of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$. The treatment for is almost the dual of that for , whence we give the details only for . Since the role of $r$ and $s$ is symmetric, it suffices to deal with the case $0<x\leq b_r$; we want to show $x\vee_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} a_s=1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$. Since $r\parallel_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} s$ implies $r{\mathrel{\parallel_\nu}}s$, $L$ is a ${\{0,1\}}$-sublattice of ${{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$, and holds for ${{\mathcal L}}$, we obtain $x\vee_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} a_s=1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ for old elements, that is, for all $x\in L$ such that $0<x\leq b_r$.

Hence, we assume that $x$ is a new element, that is, $x\in N_6^{pq}$. Since $b_r$ is an old element and $x\leq b_r<b_r\vee_L b_s = 1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$, we obtain $x\notin{\{f_{pq},g_{pq}\}}$. Hence, $x\in  {\{c_{pq},d_{pq},e_{pq}\}}$. If we had $r\neq q$, then $x\leq b_r$ and the description of $\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ would imply $a_q\leq b_r$, which would be a contradiction since holds in ${{\mathcal L}}$. Consequently, $r=q$. Thus, we have $0<x\leq b_q$, and we know from $s\parallel_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} r=q$ and $p\leq_{{{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} q$ that $s\notin{\{p, q, 0_H\}}$ and $s{\mathrel{\parallel_\nu}}q$. We also know $p\neq 0_H$ since $p{\mathrel{\parallel_\nu}}q$.

If we had $a_s\in{\mathord\downarrow g_{pq}}$, then the description of $\leq_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$ would yield $a_s\leq b_p$, which would contradict . Hence, $a_s\notin{\mathord\downarrow g_{pq}}$, and gives $x\vee_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} a_s={{x^\ast}}\vee_L a_s$. Therefore, since the spanning $N_6$-quadruple ${\langle a_q,b_q,a_s,b_s\rangle}={\langle a_r,b_r,a_s,b_s\rangle}$ is strong in ${{\mathcal L}}$ by and $0<x<{{x^\ast}}\leq b_q$, we conclude ${{x^\ast}}\vee_L a_s=1_L$, which implies the desired $x\vee_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}} a_s=1_{{{L^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}}$. Consequently, ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ satisfies . This completes the proof of Lemma \[mainlemma\].

Approaching infinity
====================

For an ordered set $P={\langle P;\leq\rangle}$ and a subset $C$ of $P$, the restriction of the ordering of $P$ to $C$ will be denoted by ${{\leq\rceil_{C}}}$. If each element of $P$ has an upper bound in $C$, then $C$ is a *cofinal subset* of $P$. The following lemma belongs to the folklore; having no reference at hand, we will outline its easy proof.

\[cofinalitylemma\] If an ordered set $P={\langle P;\leq\rangle}$ is the union of a chain of principal ideals, then it has a cofinal subset $C$ such that ${\langle C; {{\leq\rceil_{C}}}\rangle}$ is a well-ordered set.

The top elements of these principal ideals form a cofinal chain $D$ in $P$. Let $\mathcal H(D)=\{X: X\subseteq D$ and ${\langle X;{{\leq\rceil_{X}}}\rangle}$ is a well-ordered set$\}$. For $X,Y\in \mathcal H(D)$, let $X\sqsubseteq Y$ mean that $X$ is an order ideal of ${\langle Y;{{\leq\rceil_{Y}}}\rangle}$. Zorn’s Lemma yields a maximal member $C$ in ${\langle \mathcal H(D),\sqsubseteq\rangle}$. Clearly, $C$ is well-ordered and it is a cofinal subset.

Now, we combine the vertical action of Lemma \[lupstp\] and the horizontal action of Lemma \[mainlemma\] into a single statement. Note that the order ideal $H$ of ${\langle {{H}^{\bullet}},{{\nu}^{\bullet}}\rangle}$ in the following lemma is necessarily a directed ordered set.

\[combinlemma\] Assume that ${{\mathcal L}}={\langle L;\gamma, H,\nu,\delta ,{\varepsilon}\rangle}$ is an auxiliary structure such that ${\langle H,\nu\rangle}$ is an order ideal of a bounded ordered set ${\langle {{H}^{\bullet}},{{\nu}^{\bullet}}\rangle}$. $($In particular, $\nu$ is an ordering and $\nu={{{{\nu}^{\bullet}}\rceil_{H}}}$.$)$ Then there exists an auxiliary structure ${{{{\mathcal L}}}^{\bullet}}={\langle {{L}^{\bullet}};{{\gamma}^{\bullet}}, {{H}^{\bullet}},{{\nu}^{\bullet}},{{\delta}^{\bullet}} ,{{{\varepsilon}}^{\bullet}} \rangle}$ such that ${{\mathcal L}} $ is a substructure of ${{{{\mathcal L}}}^{\bullet}}$. Furthermore, if ${{\mathcal L}}$ and ${{H}^{\bullet}}$ are countable, then so is ${{{{\mathcal L}}}^{\bullet}}$.

We can assume $H\neq {{H}^{\bullet}}$ since otherwise ${{{{\mathcal L}}}^{\bullet}}={{\mathcal L}}$ would do. Consider the set $$D={\{{{\langle p,q\rangle}}: 0_{{{H}^{\bullet}}}<_{{{\nu}^{\bullet}}}  p <_{{{\nu}^{\bullet}}} q<_{{{\nu}^{\bullet}}} 1_{{{H}^{\bullet}}}\text{ and } p\not<_\nu q \}}\text.\label{ezD}$$ Since every set can be well-ordered, we can also write $D={\{{{\langle p_\iota,q_\iota\rangle}}: \iota<\kappa\}}$, where $\kappa$ is an ordinal number. In ${\textup{Quord}({{H}^{\bullet}})}$, we define $$\nu_\lambda={\textup{quo}\bigl(\nu\cup ({\{0_{{{H}^{\bullet}}}\}}\times {{H}^{\bullet}})
\cup ({{H}^{\bullet}}\times {\{1_{{{H}^{\bullet}}}\}})
\cup {\{{{\langle p_\iota,q_\iota\rangle}}:\iota<\lambda\}}\bigr)} \label{sldiHGk}$$ for $\lambda\leq \kappa$. It is an ordering on ${{H}^{\bullet}}$, because $\nu_\lambda\subseteq {{\nu}^{\bullet}}$ implies that it is antisymmetric. Note that $\nu_\kappa={{\nu}^{\bullet}}$ and $0_{{{H}^{\bullet}}}=0_H$. For each $\lambda \leq \kappa$, we want to define an auxiliary structure ${{\mathcal L}}_\lambda={\langle L_\lambda;\gamma_\lambda, H_\lambda,\nu_\lambda,\delta_{\lambda},{\varepsilon}_{\lambda}\rangle}$ such that, for all $\lambda<\kappa$, the following properties be satisfied : $$\begin{aligned}
&\text{${{\mathcal L}}_\mu$ is a substructure of ${{\mathcal L}}_\lambda$ for all $\mu\leq \lambda$;} \label{dirun}  \\
&\text{$H_\lambda=H_0$, $0_{L_\lambda}=0_{L_0}  $, and $1_{L_\lambda}=1_{L_0}$};\label{djrun}  \\
&\begin{aligned} 
{\langle \delta_\lambda&(p),{\varepsilon}_\lambda(p),\delta_\lambda(q),{\varepsilon}_\lambda(q)\rangle}\text{ is a  spanning }N_6\text{-quadruple (equivalently, }  \cr 
&\text{a strong }N_6\text{-quadruple) for all }{{\langle p,q\rangle}}\in D\text{ such that }p\parallel_{\nu_\lambda} q\text.
\end{aligned}\label{spnnning}\end{aligned}$$ Modulo the requirement that ${{\mathcal L}}_\lambda$ should be an auxiliary structure, the equivalence mentioned in is a consequence of . We define ${{\mathcal L}}_\lambda$ by (transfinite) induction as follows.

We define ${{\mathcal L}}_0$ by a vertical extension. Let $K={{H}^{\bullet}}\setminus(H\cup{\{1_{{{H}^{\bullet}}}\}} )$, let ${{\langle {{H^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}},{{\nu^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}\rangle}}={{\langle {{H}^{\bullet}},\nu_0\rangle}}$, and let ${{\mathcal L}}_0={{{{\mathcal L}}^{\scriptscriptstyle{\mathord{\pmb{\vartriangle}}}}}}$ be the auxiliary structure what we obtain from ${{\mathcal L}}$ according to Lemma \[lupstp\]. Note that, for all ${{\langle p,q\rangle}}\in D$, ${\{p,q\}}\not\subseteq H$ since $\nu={{{{\nu}^{\bullet}}\rceil_{{{H}^{\bullet}}}}}$. Hence, by Lemma \[lupstp\], holds for $\lambda=0$.

Assume that $\lambda$ is a successor ordinal, that is, $\lambda=\eta+1$, and ${{\mathcal L}}_\eta={\langle L_\eta;\gamma_\eta, H_\eta,\nu_\eta,\delta_{\eta},{\varepsilon}_{\eta}\rangle}$ is already defined and satisfies , , and . Since $p_\eta <_{{{\nu}^{\bullet}}} q_\eta$ and $\nu_\eta\subseteq {{\nu}^{\bullet}}$, we have either $p_\eta <_{\nu_\eta} q_\eta$, or $p_\eta \parallel_{\nu_\eta} q_\eta$. These two possibilities need separate treatments. First, if $p_\eta <_{\nu_\eta} q_\eta$, then $\nu_\lambda=\nu_\eta$ and we let ${{\mathcal L}}_\lambda={{\mathcal L}}_\eta$.

Second, let $p_\eta \parallel_{\nu_\eta} q_\eta$. We define ${{\mathcal L}}_\lambda$ from ${{\mathcal L}}_\eta$ by a horizontal extension as follows. With the notation ${{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}=\nu_\lambda$, we obtain from that ${{\nu^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}={\textup{quo}({\nu_\eta\cup{\{{{\langle p_\eta,q_\eta\rangle}} \}} })}\in{\textup{Quord}({{H}^{\bullet}})}$. Furthermore, the validity of for ${{\mathcal L}}_\eta$ yields that ${{\langle p_\eta,q_\eta\rangle}}$ is a spanning $N_6$-quadruple of ${{\mathcal L}}_\eta$. Thus, letting ${{\langle p_\eta,q_\eta\rangle}}$ and ${{\mathcal L}}_\eta$ play the role of ${{\langle p,q\rangle}}$ and ${{\mathcal L}}$ in and , respectively, we define ${{{\mathcal L}}_\lambda}$ as the auxiliary structure ${{{{\mathcal L}}^{\scriptscriptstyle{{{\mathord{ \blacktriangleright  }}}}}}}$ taken from Lemma \[mainlemma\]. Since $L_\eta$ is a ${\{0,1\}}$-sublattice of $L_\lambda$, spanning $N_6$-quadruples of $L_\eta$ are also spanning in $L_\lambda$. Furthermore, it follows from $\nu_{\lambda}\supseteq \nu_\eta$ that $p\parallel_\lambda q{\mathrel{\Longrightarrow}}p\parallel_\eta q$. Hence, we conclude that is inherited by ${{{\mathcal L}}_\lambda}$ from ${{{\mathcal L}}_\eta}$.

Assume that $\lambda$ is a limit ordinal. Let $$\begin{aligned}
L_\lambda=\bigcup_{\eta<\lambda} L_\eta,{{\kern 5 pt}}  \gamma_\lambda=\bigcup_{\eta<\lambda} \gamma_\eta,{{\kern 5 pt}} 
H_\lambda={{H}^{\bullet}},{{\kern 5 pt}} 
\nu_\lambda=\bigcup_{\eta<\lambda} \nu_\eta,{{\kern 5 pt}}
\delta_{\lambda }=\bigcup_{\eta<\lambda} \delta_{\eta },
{{\kern 5 pt}}
{\varepsilon}_{\lambda}=\bigcup_{\eta<\lambda} {\varepsilon}_{\eta }\text.\end{aligned}$$ We assert that ${{\mathcal L}}_\lambda={\langle L_\lambda;\gamma_\lambda, H_\lambda,\nu_\lambda,\delta_{\lambda},{\varepsilon}_{\lambda}\rangle}$ is an auxiliary structure satisfying , , and .

Since all the unions defining ${{\mathcal L}}_\lambda$ are directed unions, $L_\lambda$ is a lattice, and ${\langle H_\lambda;\nu_\lambda\rangle}$ is a quasiordered set. Actually, it is an ordered set since $\nu_\lambda\subseteq {{\nu}^{\bullet}}$. By the same reason, $\gamma_\lambda$, $\delta_{\lambda}$, and ${\varepsilon}_{\lambda}$ are maps. It is straightforward to check that all of ,…, hold for ${{\mathcal L}}_\lambda$; we only do this for , that is, we verify and , and also for .

Assume $\gamma_\lambda({{\langle u_1,v_1\rangle}})\leq_{\nu_\lambda} \gamma_\lambda({{\langle u_2,v_2\rangle}})$. Since the unions are directed, there exists an $\eta<\lambda$ such that $u_1,v_1,u_2,v_2\in L_\nu$, and we have $\gamma_\eta({{\langle u_1,v_1\rangle}})\leq_{\nu_\eta} \gamma_\eta({{\langle u_2,v_2\rangle}})$. Using that the auxiliary structure ${{\mathcal L}}_\eta$ satisfies , we obtain ${\textup{con}_{L_\eta}(u_1,v_1)} \leq {\textup{con}_{L_\eta}(u_2,v_2)}$, that is, ${{\langle u_1,v_1\rangle}} \in {\textup{con}_{L_\eta}(u_2,v_2)}$. Using Lemma \[llajtorja\], we conclude ${{\langle u_1,v_1\rangle}} \in {\textup{con}_{L_\lambda}(u_2,v_2)}$ in the usual way. This implies ${\textup{con}_{L_\lambda}(u_1,v_1)} \leq {\textup{con}_{L_\lambda}(u_2,v_2)}$. Therefore, ${{\mathcal L}}_\lambda$ satisfies .

Similarly, if ${\textup{con}_{L_\lambda}(u_1,v_1)} \leq {\textup{con}_{L_\lambda}(u_2,v_2)}$, then Lemma \[llajtorja\] easily implies the existence of an $\eta<\lambda$ such that ${{\langle u_1,v_1\rangle}} \in {\textup{con}_{L_\eta}(u_2,v_2)}$ and ${\textup{con}_{L_\eta}(u_1,v_1)} \leq {\textup{con}_{L_\eta}(u_2,v_2)}$; for ${{\mathcal L}}_\eta$ yields $\gamma_\eta({{\langle u_1,v_1\rangle}})\leq_{\nu_\eta} \gamma_\eta({{\langle u_2,v_2\rangle}})$; and we conclude $\gamma_\lambda({{\langle u_1,v_1\rangle}})\leq_{\nu_\lambda} \gamma_\lambda({{\langle u_2,v_2\rangle}})$. Hence, ${{\mathcal L}}_\lambda$ satisfies and .

Next, for the sake of contradiction, suppose that fails in ${{\mathcal L}}_\lambda$. This implies that ${{\langle 0_{L_\lambda},1_{L_\lambda}\rangle}}$ belongs to $\bigvee{\bigl\{{\textup{con}_{L_\lambda}(a_p,b_p)}: p\in H_\lambda\setminus{\{1_{{{H}^{\bullet}}}\}}\bigr\}}$, where the join is taken in the congruence lattice of $L_\lambda$. Since principal congruences are compact, there exists a finite subset $T\subseteq  H_\lambda\setminus{\{1_{{{H}^{\bullet}}}\}}$ such that ${{\langle 0_{L_\lambda},1_{L_\lambda}\rangle}}$ belongs to $\bigvee{\{{\textup{con}_{L_\lambda}(a_p,b_p)}: p\in T\}}$. Thus, there exists a finite chain $0_{L_\lambda}=c_0<c_1<\dots<c_k=0_{L_\lambda}$ such that, for $i=1,\dots, k$, ${{\langle c_{i-1},c_i\rangle}}\in \bigcup{\{{\textup{con}_{L_\lambda}(a_p,b_p)}: p\in T\}}$. Each of these memberships are witnessed by finitely many “witness” elements according to ; see Lemma \[llajtorja\]. Taking all these memberships into account, there are only finitely many witness elements all together. Hence, there exists an $\eta<\lambda$ such that $L_\eta$ contains all these elements. Applying Lemma \[llajtorja\] in the converse direction, we obtain that ${{\langle 0_{L_\eta},1_{L_\eta}\rangle}}={{\langle 0_{L_\lambda},1_{L_\lambda}\rangle}}$ belongs to $\bigvee{\{{\textup{con}_{L_\eta}(a_p,b_p)}: p\in T\}}$, which is a contradiction since ${{\mathcal L}}_\eta$ satisfies . Consequently, ${{\mathcal L}}_\lambda$ is an auxiliary structure.

Clearly, ${{\mathcal L}}_\lambda$ satisfies and since so do the ${{\mathcal L}}_\eta$ for $\eta<\lambda$. If ${{\langle p,q\rangle}}\in D$ and $p\parallel_\lambda q$, then $p\parallel_\eta q$ for some (actually, for every) $\eta<\lambda$. Hence, the satisfaction of for ${{\mathcal L}}_\lambda$ follows the same way as in the Successor Step since $L_\eta$ is a ${\{0,1\}}$-sublattice of $L_\lambda$.

We have seen that ${{\mathcal L}}_\nu$ is an auxiliary structure for all $\lambda\leq\kappa$. Letting $\lambda$ equal $\kappa$, we obtain the existence part of the lemma. The last sentence of the lemma follows from the construction and basic cardinal arithmetics.

We are now in the position to complete the paper.

In order to prove part of the theorem, assume that $P={\langle P;\nu_P\rangle}$ is an ordered set with zero and it is the union of a chain of principal ideals. By Lemma \[cofinalitylemma\], there exist an ordinal number $\kappa$ and a cofinal chain $C={\{c_\iota: \iota<\kappa\}}$ in $P$ such that $0_P=c_0$ and, for $\iota,\mu<\kappa$ we have $\iota< \mu \iff c_\iota< c_\mu$. The cofinality of $C$ means that $P$ is the union of the principal ideals $H_\iota={\mathord\downarrow c_\iota}$, $\iota<\kappa$. We let $H_\kappa=\bigcup_{\iota<\kappa}H_ \iota$ and $\nu_\kappa=\bigcup_{\iota<\kappa}\nu_{H_i}$, where $\nu_{H_i}$ denotes the restriction ${{\nu_P\rceil_{H_i}}}$. Clearly, $P=H_\kappa$ and $\nu_P= \nu_\kappa$, that is, ${\langle P;\nu_P\rangle}={\langle H_\kappa;\nu_\kappa\rangle}$. Note that $H_\kappa$ is not a principal ideal in general since $P$ need not be bounded.

For each $\lambda \leq \kappa$, we define an auxiliary structure ${{\mathcal L}}_\lambda={\langle L_\lambda;\gamma_\lambda, H_\lambda,\nu_\lambda,\delta_{\lambda},{\varepsilon}_{\lambda}\rangle}$ such that ${{\mathcal L}}_\mu$ is a substructure of ${{\mathcal L}}_\lambda$ for every $\mu\leq \lambda$; we do this by (transfinite) induction as follows.

We start with the one-element lattice $L_0$ and $H_0={\{c_0\}}={\{0_P\}}$, and define ${{\mathcal L}}_0$ in the only possible way.

Assume that $\lambda=\eta+1$ is a successor ordinal. We apply Lemma \[combinlemma\] to obtain ${{\mathcal L}}_\lambda$ from ${{\mathcal L}}_\eta$. This is possible since $H_\eta$ is an order ideal of $H_\lambda$. Note that Lemma \[combinlemma\] does not assert the uniqueness of ${{{{\mathcal L}}}^{\bullet}}$, and, in principle, it could be a problem later that ${{\mathcal L}}_\lambda$ is not uniquely defined. However, this is not a real problem since we can easily solve it as follows.

Let $\tau_0$ be the smallest *infinite* ordinal number such that ${|P|}\leq |\tau_0|$, let $\tau=2^{\tau_0}$, and let $\pi$ be the smallest ordinal with $|P|=|\pi|$. Note that $|\tau|$ is at least the power of continuum but $|\pi|$ can be finite. Let $P={\{h_\iota: \iota<\pi\}}$ such that $h_\iota\neq h_\eta$ for $\iota<\eta<\pi$. Also, take a set $T={\{t_\iota: \iota<\tau\}}$ such that $t_\iota\neq t_\eta$ for $\iota<\eta<\tau$. The point is that, after selecting the well-ordered cofinal chain $C$ above, we can use the well-ordered index sets ${\{\iota: \iota<\pi\}}$ and ${\{\iota: \iota<\tau\}}$ to make every part of our compound construction unique. Namely, when we well-order $D$, defined in , we use the lexicographic ordering of the index set ${\{\iota: \iota<\pi\}}\times {\{\iota: \iota<\pi\}}$. When we define lattices, their base sets will be initial subsets of $T$; a subset $X$ of $T$ is *initial* if, for all $\mu<\iota<\tau$, $\,t_\iota\in X$ implies $t_\mu\in X$. If we have to add new lattice elements, like a new top or $c_{pq}$, etc., then we always add the first one of $T$ that has not been used previously. Cardinality arithmetics shows that $T$ is never exhausted. This way, we have made the definition of ${{\mathcal L}}_\lambda$ unique.

Clearly, ${{\mathcal L}}_\iota$ is a substructure of ${{\mathcal L}}_\lambda$ for $\iota< \lambda$; either by Lemma \[combinlemma\] if $\iota=\eta$, or by the induction hypothesis and transitivity if $\iota<\eta$.

If $\lambda$ is a limit ordinal, then first we form the union $${{\mathcal L}}'_\lambda={\langle L'_\lambda;\gamma'_\lambda,H'_\lambda,\nu'_\lambda,\delta'_\lambda, {\varepsilon}'_\lambda \rangle}=
{\langle \bigcup_{\eta<\lambda}L_\eta;\bigcup_{\eta<\lambda}\gamma_\eta, \bigcup_{\eta<\lambda}H_\eta,\bigcup_{\eta<\lambda}\nu_\eta,\bigcup_{\eta<\lambda}\delta_\eta, \bigcup_{\eta<\lambda}{\varepsilon}_\eta \rangle}\text.$$ Note that $\nu'_{\lambda}={{\nu_P\rceil_{H'_\lambda}}}$. The same way as in the proof of Lemma \[combinlemma\], we obtain that ${{\mathcal L}}'_\lambda$ is an auxiliary structure; the only difference is that now trivially holds in ${{\mathcal L}}_\lambda$ since $H'_\lambda$ does not have a largest element. To see this, suppose for contradiction that $u$ is the largest element of $H'_\lambda$. Then $u\in H_\eta$ for some $\eta<\lambda$. Since $\lambda$ is a limit ordinal, $\eta+1<\lambda$. Hence $c_{\eta+1}\leq u\leq c_\eta$, which contradicts $c_\eta<c_{\eta+1}$.

Clearly, ${\langle H'_\lambda;\nu'_\lambda\rangle}$ is an order ideal in ${\langle H_\lambda;\nu_\lambda\rangle}$. Thus, applying Lemma \[combinlemma\] to this situation, we obtain an auxiliary structure ${{{{\mathcal L}}}^{\bullet}}$, and we let ${{\mathcal L}}_\lambda= {{{{\mathcal L}}}^{\bullet}}$. Obviously, for all $\eta<\lambda$, ${{\mathcal L}}_\eta$ is a substructure of ${{\mathcal L}}_\lambda$.

Now, we have constructed an auxiliary structure ${{\mathcal L}}_\lambda$ for each $\lambda\leq \kappa$. In particular, ${{\mathcal L}}_\kappa={\langle L_\kappa;\gamma_\kappa, H_\kappa,\nu_\kappa,\delta_{\kappa},{\varepsilon}_{\kappa}\rangle} =
{\langle L_\kappa;\gamma_\kappa, P,\nu_P,\delta_{\kappa},{\varepsilon}_{\kappa}\rangle} 
$ is an auxiliary structure. Thus, by Lemma \[impclM\], ${\textup{Princ}(L_\kappa)}\cong{\langle P;\nu_P\rangle}$, which proves part of the theorem.

In order to prove part , assume that $L$ is a countable lattice. Obviously, we have $|{\textup{Princ}(L)}|\leq|{{\textup{Pairs}^{\leq}(L)}}|\leq\aleph_0$, and we already mentioned that ${\textup{Princ}(L)}$ is always a directed ordered set with 0, no matter what the size $|L|$ of $L$ is.

Conversely, let $P$ be a directed ordered set with 0 such that $|P|\leq\aleph_0$. Then there is an ordinal $\kappa\leq \omega$ (where $\omega$ denotes the least infinite ordinal) such that $P={\{p_i: i<\kappa\}}$. Note that ${\{i:i<\kappa\}}$ is a subset of the set of nonnegative integer numbers. For $i,j<\kappa$, there exists a smallest $k$ such that $p_i\leq p_k$ and $p_j\leq p_k$; we let $p_i\sqcup p_j=p_k$. This defines a binary operation on $P$; it need not be a semilattice operation. Let $q_0=p_0$. For $0<i<\kappa$, let $q_i=q_{i-1}\sqcup p_i$. A trivial induction shows that $q_i$ is an upper bound of ${\{p_0,p_1,\dots,p_i\}}$, for all $i<\kappa$, and $q_{i-1}\leq_P q_i$ for all $0<i<\kappa$. Hence, the principal ideals ${\mathord\downarrow q_i}$ form a chain ${\{{\mathord\downarrow q_i}: i<\kappa\}}$, and $P$ is the union of these principal ideals. Therefore, part of the Theorem yields a lattice $L$ such that $P$ is isomorphic to ${\textup{Princ}(L)}$. Since the ${\mathord\downarrow q_i}$ are countable and there are countably many of them, and since all the lemmas we used in the proof of part of the theorem preserve the property “countable”, $L$ is countable.

[99]{} Bogart, K. P., Freese, R., Kung, J. P. S. (editors): The Dilworth Theorems. Selected papers of Robert P. Dilworth. Birkhäuser Boston, Inc., Boston, MA, 1990. xxvi+465 pp. ISBN: 0-8176-3434-7

Czédli, G.: (1+1+2)-generated equivalence lattices. J. Algebra [**221**]{}, 439–462 (1999)

Czédli, G.: Representing homomorphisms of distributive lattices as restrictions of congruences of rectangular lattices. Algebra Universalis [**67**]{}, 313–345 (2012)

Dilworth, R.P.: The structure of relatively complemented lattices. Ann. of Math. (2) [**51**]{}, 348–359 (1950)

Grätzer, G.: General Lattice Theory, 2nd edn. Birkhäuser, Basel (1998)

Grätzer, G.: The Congruences of a Finite Lattice. A Proof-by-picture Approach. Birkhäuser, Boston (2006)

Grätzer, G.: The order of principal congruences of a bounded lattice. [<http://arxiv.org/pdf/1302.4163>]{}; Algebra Universalis, to appear.

Grätzer, G.: Lattice Theory: Foundation. Birkhäuser Verlag, Basel (2011)

Grätzer, G., Lakser, H., Schmidt, E.T.: Congruence lattices of finite semimodular lattices. Canad. Math. Bull. [**41**]{}, 290–297 (1998)

Huhn, A. P.: On the representation of distributive algebraic lattices. III. Acta Sci. Math. (Szeged) [**53**]{}, 11–18 (1989)

Ržička, P.: Free trees and the optimal bound in Wehrung’s theorem. Fund. Math. [**198**]{}, 217–228 (2008)

Schmidt, E.T.: The ideal lattice of a distributive lattice with 0 is the congruence lattice of a lattice. Acta Sci. Math. (Szeged) [**43**]{}, 153–168 (1981)

Wehrung, F.: A solution to Dilworth’s congruence lattice problem. Adv. Math. [**216**]{}, 610–625 (2007)

[^1]: This research was supported by the European Union and co-funded by the European Social Fund under the project “Telemedicine-focused research activities on the field of Mathematics, Informatics and Medical sciences” of project number “TÁMOP-4.2.2.A-11/1/KONV-2012-0073”, and by NFSR of Hungary (OTKA), grant number K83219
