Lattice betweenness relation and a generalization of König’s lemma. (English) Zbl 0890.06001

Hedlíková, Jarmila; Katriňák, Tibor

Math. Slovaca 46, No. 4, 343-354 (1996).

A tree is a partially ordered set \((T,\leq )\) such that for every \(x\in T\), the set \(\{y\in T: y<x\}\) is well-ordered. Equivalently, a tree is a transitive \(\alpha\)-partite König graph \(G\) for some ordinal \(\alpha \). König’s lemma states that every transitive \(\omega \)-partite König graph \(G\) with finite parts contains an \(\omega\)-frame. An extension of König’s lemma which has the origin in a characterization of lattices by a ternary relation (the lattice betweenness relation) given by M. Kolibiar is presented in the paper. This generalization of König’s lemma states that for every up-directed partially ordered set \(S\), each transitive \(S\)-partite König graph \(G\) with sufficiently many finite parts contains an \(S\)-frame. As an example, this result is applied in lattice theory.

MSC:

06A06	Partial orders, general
05C20	Directed graphs (digraphs), tournaments
06B05	Structure theory of lattices
08A02	Relational systems, laws of composition

Keywords:

tree; König’s lemma; partially ordered set; transitive \(S\)-partite König graph; \(J\)-frame; lattice betweenness relation; ternary relation

References:

[1]	BALCAR B.-ŠTĚPÁNEK P.: Set Theory. Academia, Praha, 1986. · Zbl 0635.03039
[2]	BIRKHOFF G.: Lattice Theory. (3rd. Amer. Math. Soc. Colloq. Publ. 25. Providence, R.I.-1967. · Zbl 0153.02501
[3]	HEDLÍKOVÁ J.-KATRIŇÁK T.: On a characterization of lattices by the betweenness relation - on a problem of M. Kolibiar. Algebra Universalis 28 (1991), 389-400. · Zbl 0757.06003
[4]	KOLIBIAR M.: Charakterisierung der Verbände durch die Relation zwischen. Z. Math. Logik Grundlag. Math. 4 (1958), 89-100. · Zbl 0087.26002
[5]	KONIG D.: Sur les correspondences multivoques des ensembles. Fund. Math. 8 (1926). 114-134. · JFM 52.0195.02
[6]	MILNER E. C.-SAUER N.: Remarks on the cofinality of a partrally ordered set, and ageneralization of König’s lemma. Discrete Math. 35 (1981), 165-171. · Zbl 0465.05041
[7]	WECHLER W.: Universal Algebra for Computer Scientists. Monographs on Theoretical Computer Science, Vol. 25, Springer-Verlag, Berlin, Heidelberg, 1992. · Zbl 0748.68002