Order Extensions and the Fixed Point Property

The purpose of this paper is to investigate how the fixed point property and its negation behave when a covering relation is added to the order. We prove that every finite ordered set which is not totally ordered and which is dismantlable by retractables, respectively by irreducibles, has an upper cover (in its extension lattice) which is also dismantlable by retractables, respectively by irreducibles. We also provide examples of finite ordered sets having the fixed point property so that none of their upper covers has the fixed point property. Part of this work was done while the author was visiting Brandon University. The author thanks M. Roddy for his hospitality and financial support.     

Varieties with decidable finite algebras I: Linearity

The aim of this paper is to prove that every congruence distributive variety containing a finite subdirectly irreducible algebra whose congruences are not linearly ordered has an undecidable first order theory of its finite members. This fills a gap which kept us from the full characterization of the finitely generated, arithmetical varieties (of finite type) having a decidable first order theory of their finite members. Progress on finding this characterization was made in the papers [14] and [15].Presented by Stanley Burris.     

Dimension two,fixed points and dismantlable ordered sets

When does the fixed point property of a finite ordered set imply its dismantlability by irreducible elements? For instance, if it has width two. Although every finite ordered set is dismantlable by retractible (not necessarily irreducible) elements, surprisingly, a finite, dimension two ordered set, need not be dismantlable by irreducible elements. If, however, a finite ordered set with the fixed point property is N-free and of dimension two, then it is dismantlable by irreducibles. A curious consequence is that every finite, dimension two ordered set has a complete endomorphism spectrum.     

Automorphism group and dimension of ordered sets

It is shown that a finite groupG is isomorphic to the automorphism group of a two-dimensional ordered set if and only if it is a generalized wreath product of symmetric groups over an ordered index set that is a dual tree. Furthermore, every finite abelian group is isomorphic to the full automorphism group of a three-dimensional ordered set. Also every finite group is isomorphic to the automorphism group of an ordered set that does not contain an induced crown with more than four elements.     

A combinatorial proof of a fixed point property

A class of finite simplicial complexes, called pseudo cones, is developed that has a number of useful combinatorial properties. A partially ordered set is a pseudo cone if its order complex is a pseudo cone. Pseudo cones can be constructed from other pseudo cones in a number of ways. Pseudo cone ordered sets include finite dismantlable ordered sets and finite truncated noncomplemented lattices. The main result of the paper is a combinatorial proof of the fixed simplex property for finite pseudo cones in which a combinatorial structure is constructed that relates fixed simplices to one another. This gives combinatorial proofs of some well known non-constructive results in the fixed point theory of finite partially ordered sets.     

The structure of lattice-ordered commutative topological groups of compact origin

It is shown that every lattice-ordered commutative separable topological group of compact origin can be obtained from a finite number of its linearly ordered subgroups, each of which is isomorphic either to the additive group of real numbers with the natural topology and the usual order or to a subgroup of the additive group of real numbers with the discrete topology and the usual order, admitting a finite system of linearly independent generators, by forming in turn the direct and the lexicographic products.Translated from Matematicheskie Zametki, Vol. 21, No. 6, pp. 855–860, June, 1977.     

有限个GO-空间乘积的遗传集体Hausdorff性(英文)

本文证明了最小线性序紧化中点的共尾数不超过ω₁的有限个GO-空间的乘积是遗传集体Hausdorff空间。     

Linear Orders on General Algebras

We answer the question, when a partial order in a partially ordered algebraic structure has a compatible linear extension. The finite extension property enables us to show, that if there is no such extension, then it is caused by a certain finite subset in the direct square of the base set. As a consequence, we prove that a partial order can be linearly extended if and only if it can be linearly extended on every finitely generated subalgebra. Using a special equivalence relation on the above direct square, we obtain a further property of linearly extendible partial orders. Imposing conditions on the lattice of compatible quasi orders, the number of linear orders can be determined. Our general approach yields new results even in the case of semi-groups and groups.     

An extension of a theorem of Jeroslow and Kortanek

Given a semi-infinite system of linear inequalities, including strict inequalities, it is shown that if every finite subsystem has a solution inR, then the entire system has a solution in the ordered fieldR(M) obtained by adjoining a transcendental greater than every real number.     

Structure of Partially Ordered Cyclic Semigroups

This paper recalls some properties of a cyclic semigroup and examines cyclic subsemigroups in a finite ordered semigroup. We prove that a partially ordered cyclic semigroup has a spiral structure which leads to a separation of three classes of such semigroups. The cardinality of the order relation is also estimated. Some results concern semigroups with a lattice order.     

Definability in substructure orderings, I: finite semilattices

We investigate definability in the set of isomorphism types of finite semilattices ordered by embeddability; we prove, among other things, that every finite semilattice is a definable element in this ordered set. Then we apply these results to investigate definability in the closely related lattice of universal classes of semilattices; we prove that the lattice has no non-identical automorphisms, the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets and each element of the two subsets is a definable element in the lattice.     

On circle containment orders

A partially ordered set is called acircle containment order provided one can assign to each element of the poset a circle in the plane so thatxy iff the circle assigned tox is contained in the circle assigned toy. It has been conjectured that every finite three-dimensional partially ordered set is a circle containment order. We show that the infinite three dimensional posetZ ³ isnot a circle containment order.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.Research supported in part by National Science Foundation, grant number DMS-8403646.     

Shellability of Interval Orders

An finite interval order is a partially ordered set whose elements are in correspondence with a finite set of intervals in the line, with disjoint intervals being ordered by their relative position. We show that any such order is shellable in the sense that its (not necessarily pure) order complex is shellable.     

Completion and finite embeddability property for residuated ordered algebras.

A residuated ordered algebra is a partially ordered set with additional ‘residuated’ operations. A construction is presented that, from any partial subalgebra of a residuated ordered algebra, constructs a complete algebra into which the partial subalgebra embeds. Conditions are given under which the constructed algebra is finite whenever a finite partial subalgebra is chosen. This implies the ‘finite embeddability property’ for the given class of residuated ordered algebras. In the case that the whole algebra is chosen as the partial subalgebra, the construction is a completion of the underlying order of the algebra. A scheme of inequalities is described that are shown to have the property of being preserved by the above construction. These preservation results thus extend the results on the finite embeddability property and completion.     

Every poset has a central element

It is proved that there exists a constant , such that in every finite partially ordered set there is an element such that the fraction of order ideals containing that element is between δ and 1−δ. It is shown that δ can be taken to be at least (3−log₂ 5)/40.17. This settles a question asked independently by Colburn and Rival, and Rosenthal. The result implies that the information-theoretic lower bound for a certain class of search problems on partially ordered sets is tight up to a multiplicative constant.     

On a New Idiom in the Study of Entailment

This paper is an experiment in Leibnizian analysis. The reader will recall that Leibniz considered all true sentences to be analytically so. The difference, on his account, between necessary and contingent truths is that sentences reporting the former are finitely analytic; those reporting the latter require infinite analysis of which God alone is capable. On such a view at least two competing conceptions of entailment emerge. According to one, a sentence entails another when the set of atomic requirements for the first is included in the corresponding set for the other; according to the other conception, every atomic requirement of the entailed sentence is underwritten by an atomic constituent of the entailing one. The former conception is classical on the twentieth century understanding of the term; the latter is the one we explore here. Now if we restrict ourselves to the formal language of the propositional calculus, every sentence has a finite analysis into its conjunctive normal form. Semantically, then, every sentence of that language can be represented as a simple hypergraph, H, on the powerset of a universe of states. Entailment of the sort we wish to study can be represented as a known relation, subsumption between hypergraphs. Since the lattice of hypergraphs thus ordered is a DeMorgan lattice, the logic of entailment thus understood is the familiar system, FDE of first-degree entailment. We observe that, extensionalized, the relation of subsumption is itself a DeMorgan Lattice ordered by higher-order subsumption. Thus the semantic idiom that hypergraph-theory affords reveals a hierarchy of lattices capable of representing entailments of every finite degree.     

On a fixed point theorem for partially ordered sets

An elementary combinatorial proof is presented of the following fixed point theorem: Let P be a finite partially ordered set with a cut-set X. If every subset of X has either a meet or a join, then P has the fixed point property. This theorem is strengthened to include a certain class of infinite partially ordered sets, as well.     

On partial ordering of chief factors in solvable groups

The isomorphism classes of chief factors in a finite solvable group are partially ordered by taking one class higher than the other if a member of the first class appears as a chief factor of the action of the group on a member of the second class. Together with this partial ordering the characteristics of the chief factors are considered. It is shown that the two conditions found by G. Pazderski are not only necessary but also sufficient for a partially ordered set and a function to be representable as the poset of isomorphism classes of chief factors in a finite solvable group with the chief factors having the prescribed characteristics. In addition, the construction yields that every finite distributive lattice is the lattice of normal subgroups of some finite solvable group.