共查询到20条相似文献,搜索用时 15 毫秒
1.
The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172. 相似文献
2.
Michèle Giraudet 《Order》1988,5(3):275-287
Let G and H be totally ordered Abelian groups such that, for some integer k, the lexicographic powers G
k
and H
k
are isomorphic (as ordered groups). It was proved by F. Oger that G and H need not be isomorphic. We show here that they are whenever G is either divisible or 1 -saturated (and in a few more cases). Our proof relies on a general technique which we also use to prove that G and H must be elementary equivalent as ordered groups (a fact also proved by F. Delon and F. Lucas) and isomorphic as chains. The same technique applies to the question of whether G and H should be isomorphic as groups, but, in this last case, no hint about a possible negative answer seems available. 相似文献
3.
In the present paper we shall study infinite meet decompositions of an element of a complete lattice. We give here a generalization
of some results of papers [2] and [3]. 相似文献
4.
5.
There are two natural ways to extend an arbitrary map between (the carriers of) two lattices, to a map between their MacNeille
completions. In this paper we investigate which properties of lattice maps are preserved under these constructions, and for
which kind of maps the two extensions coincide.
Our perspective involves a number of topologies on lattice completions, including the Scott topologies and topologies that
are induced by the original lattice. We provide a characterization of the MacNeille completion in terms of these induced topologies.
We then turn to expansions of lattices with additional operations, and address the question of which equational properties
of such lattice expansions are preserved under various types of MacNeille completions that can be defined for these algebras.
For a number of cases, including modal algebras and residuated (ortho)lattice expansions, we provide reasonably sharp sufficient
conditions on the syntactic shape of equations that guarantee preservation. Generally, our results show that the more residuation
properties the primitive operations satisfy, the more equations are preserved.
Received August 21, 2005; accepted in final form October 17, 2006. 相似文献
6.
Martin Aigner 《Aequationes Mathematicae》1977,16(1-2):37-50
In a geometric lattice every interval can be mapped isomorphically into an upper interval (containing 1) by a strong map. A natural question thus arises as to what extent certain assumptions on the upper interval structure determine the whole lattice. We consider conditions of the following sort: that above a certain levelm any two upper intervals of the same length be isomorphic. This property, called uniformity, is studied for binary geometries. The geometries satisfying the strongest uniformity condition (m = 1) are determined (except for one open case). As is to be expected the corresponding problem for lower intervals is easier and is solved completely. 相似文献
7.
We show that the 2-crown is not coproductive, which is to say that the class of those bounded distributive lattices whose
Priestley spaces lack any copy of the 2-crown is not productive. We do this by first exhibiting a general construction to
handle questions of this sort. We then use a particular instance of this constrution, along with some of the combinatorial
features of projective planes, to show that the 2-crown is not coproductive.
This paper is dedicated to Walter Taylor.
Received November 24, 2004; accepted in final form July 16, 2005.
The first author would like to express his thanks for support by project LN 00A056 of the Ministry of Education of the Czech
Republic. The second author would like to express his thanks for support by project LN 00A056 of the Ministry of Education
of the Czech Republic, by the NSERC of Canada and by the Gudder Trust of the University of Denver. The third author would
like to express his thanks for support by the NSERC of Canada and partial support by project LN 00A056 of the Ministry of
Education of the Czech Republic. 相似文献
8.
Scott R. Sykes 《Algebra Universalis》2007,56(3-4):349-356
The purpose of this paper is to introduce the lattice of convex partitions for a lattice L. Then we will show some properties of this lattice. Finally, we will show that if the convex partition lattice of L is finite and modular if and only if L is a finite chain.
Presented by R. McKenzie.
Received December 16, 2004; accepted in final form March 7, 2006. 相似文献
9.
Manfred Droste 《Order》1985,2(3):291-319
Using combinatorial and model-theoretic means, we examine the structure of normal subgroup lattices N(A()) of 2-transitive automorphism groups A() of infinite linearly ordered sets (, ). Certain natural sublattices of N(A()) are shown to be Stone algebras, and several first order properties of their dense and dually dense elements are characterized within the Dedekind-completion
of (, ). As a consequence, A() has either precisely 5 or at least 221 (even maximal) normal subgroups, and various other group- and lattice-theoretic results follow. 相似文献
10.
Jan Florek 《Algebra Universalis》2007,56(1):57-68
In a partly ordered space the orthogonality relation is defined by incomparability. We define integrally open and integrally
semi-open ordered real vector spaces. We prove: if an ordered real vector space is integrally semi-open, then a complete lattice
of double orthoclosed sets is orthomodular. An integrally open concept is closely related to an open set in the Euclidean
topology in a finite dimensional ordered vector space. We prove: if V is an ordered Euclidean space, then V is integrally open and directed (and is also Archimedean) if and only if its positive cone, without vertex 0, is an open
set in the Euclidean topology (and also the family of all order segments
, a < b, is a base for the Euclidean topology).
Received January 7, 2005; accepted in final form November 26, 2005. 相似文献
11.
Our main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs. We conclude by exploring how some of these results over the finite field of order 2 extend to arbitrary fields and demonstrate that at least one third of the 62 are minimal forbidden subgraphs over an arbitrary field for the class of graphs having minimum rank at most 3 in that field. 相似文献
12.
If P is a directed partially ordered algebra of an appropriate sort-e.g. an upper semilattice-and has no maximal element, then P has two disjoint subalgebras each cofinal in P. In fact, if P has cofinality then there exists a family of such disjoint subalgebras. A version of this result is also proved without the directedness assumption, in which the cofinality of P is replaced by an invariant which we call its global cofinality.This work was done while the first author was partly supported by NSF contract MCS 82-02632. 相似文献
13.
Zoltán Füredi 《Order》1994,11(1):15-28
LetB
n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B
n(k, n–k))=n–2 for 3k<(1/7)n
1/3. The proof uses extremal hypergraph theory. 相似文献
14.
If V is a variety of lattices and L a free lattice in V on uncountably many generators, then any cofinal sublattice of L generates all of V. On the other hand, any modular lattice without chains of order-type +1 has a cofinal distributive sublattice. More generally, if a modular lattice L has a distributive sublattice which is cofinal modulo intervals with ACC, this may be enlarged to a cofinal distributive sublattice. Examples are given showing that these existence results are sharp in several ways. Some similar results and questions on existence of cofinal sublattices with DCC are noted.This work was done while the first author was partly supported by NSF contract MCS 82-02632, and the second author by an NSF Graduate Fellowship. 相似文献
15.
Ulrich Faigle 《Aequationes Mathematicae》1980,21(1):53-67
Morphisms and weak morphisms extend the concept of strong maps and maps of combinatorial geometry to the class of finite dimensional semimodular lattices. Each lattice which is the image of a semimodular lattice under a morphism is semimodular. In particular, each finite lattice is semimodular if and only if it is the image of a finite distributive lattice under a morphism. Regular and non-singular weak morphisms may be used to characterize modular and distributive lattices. Each morphism gives rise to a geometric closure operator which in turn determines a quotient of a semimodular lattice. A special quotient, the Higgs lift, is constructed and used to show that each morphism decomposes into elementary morphisms, and that each morphism may be factored into an injection and a contraction. 相似文献
16.
We characterize trees whose lexicographic ordering produces an order isomorphic copy of some sets of real numbers, or an order isomorphic copy of some set of ordinal numbers. We characterize trees whose lexicographic ordering is order complete, and we investigate lexicographically ordered ω-splitting trees that, under the open-interval topology of their lexicographic orders, are of the first Baire category. Finally we collect together some folklore results about the relation between Aronszajn trees and Aronszajn lines, and use earlier results of the paper to deduce some topological properties of Aronszajn lines. 相似文献
17.
It is shown that a finitely generated ordered Abelian group is generic if and only if it is superdiscrete, i.e., each homomorphic image is discretely ordered. The forcing concept uses universal sentences as forcing conditions. 相似文献
18.
Let be a product order on [n]
p
i.e. for A, B [n]
p
, 1a
1<a
2<...<a
p
º-n and 1<-b
1<b
2<...<b
p
<-n we have AB iff a
i<-b
i for all i=1, 2,..., p. For a linear extension < of (ordering [n]
p
as
) let F
<
[n],p
(m) count the number of A
i
's, i<-m such that 1A
i. Clearly,
for every m and <, where <l denotes the lexicographic order on [n]
p
. In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that
holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850. 相似文献
19.
Ž. Perović 《Algebra Universalis》1995,34(3):345-354
In this paper we show that the Comfort-Hager result on cardinalities of-complete Boolean algebras is also true for-complete OML's having a bound on the number of complements. Using the Kaplansky theorem on continuous geometries we get a result on modular ortho-lattices. We also get a result on cardinalities of saturated OML's.Presented by R. McKenzie.Supported by the NSF of Srbija through Math. Inst., Grant #401A. 相似文献
20.
Antonino Drago 《Logica Universalis》2008,2(1):127-141
Each predicate of the Aristotelian square of opposition includes the word “is”. Through a twofold interpretation of this word
the square includes both classical logic and non-classical logic. All theses embodied by the square of opposition are preserved
by the new interpretation, except for contradictories, which are substituted by incommensurabilities. Indeed, the new interpretation
of the square of opposition concerns the relationships among entire theories, each represented by means of a characteristic
predicate. A generalization of the square of opposition is achieved by not adjoining, according to two Leibniz’ suggestions
about human mind, one more choice about the kind of infinity; i.e., a choice which was unknown by Greek’s culture, but which
played a decisive role for the birth and then the development of modern science. This essential innovation of modern scientific
culture explains why in modern times the Aristotelian square of opposition was disregarded.
This work was completed with the support of our -pert. 相似文献