Uncountable Homogeneous Partial Orders

A partially ordered set (P, ≤) is called k‐homogeneous if any isomorphism between k‐element subsets extends to an automorphism of (P, ≤). Assuming the set‐theoretic assumption ⋄(ϰ₁), it is shown that for each k, there exist partially ordered sets of size ϰ₁ which embed each countable partial order and are k‐homogeneous, but not (k + 1)‐homogeneous. This is impossible in the countable case for k ≥ 4.     

Epimorphisms Between Linear Orders

We study the relation on linear orders induced by order preserving surjections. In particular we show that its restriction to countable orders is a bqo.     

Cofinalities of Linear Orders

We investigate whether the existence of long linear orders can be proved without the Axiom of Choice. This question has two different answers depending on its formalization.     

Negative Dense Linear Orders

Considering dense linear orders, we establish their negative representability over every infinite negative equivalence, as well as uniformly computable separability by computable gaps and the productivity of the set of computable sections of their negative representations. We construct an infinite decreasing chain of negative representability degrees of linear orders and prove the computability of locally computable enumerations of the field of rational numbers.     

Local Spectral Theory and Surjective Spectrum of Linear Relations

Ukrainian Mathematical Journal - We initiate a study of local spectral theory for linear relations. At the beginning, we define the local spectrum and study its properties. Then we obtain results...     

Cuts of Linear Orders

We study the connection between the number of ascending and descending cuts of a linear order, its classical size, and its effective complexity (how much [how little] information can be encoded into it).     

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.     

Initial Segments of Recursive Linear Orders

We show that any -initial segment of a recursive linear order can be presented recursively.     

The Intrinsic Enumerability of Linear Orders

We study into the question of which linearly ordered sets are intrinsically enumerable. In particular, it is proved that every countable ordinal lacks this property. To do this, we state a criterion for hereditarily finite admissible sets being existentially equivalent, which is interesting in its own right. Previously, Yu. L. Ershov presented the criterion for elements h ₀ , h ₁ in HF ) to realize a same type as applied to sufficiently saturated models . Incidentally, that criterion fits with every model on the condition that we limit ourselves to 1-types.     

Antichains in Products of Linear Orders

We show that:(1) For many regular cardinals (in particular, for all successors of singular strong limit cardinals, and for all successors of singular -limits), for all n{2,3,4,...}: There is a linear order L such that L ⁿ has no (incomparability-)antichain of cardinality , while L ⁿ⁺¹ has an antichain of cardinality .(2) For any nondecreasing sequence _n :n{2,3,4,...} of infinite cardinals it is consistent that there is a linear order L such that, for all n: L ⁿ has an antichain of cardinality _n , but no antichain of cardinality _n ⁺.     

Linear Extensions of Additive Partial Orders

Addive partial orders arise naturally in theories of comparativeprobability and subset preferences. An additive partial order is a partialorder on the family of subsets of ann-element set that satisfies . This is reformulated as a subset P of {1,0,–1}ⁿ that excludes 0 and containsx+y whenever x,y P and x+y {1,0,–1}ⁿ. Additional conditions of positivity andcompleteness give rise to positive additive partial orders and additivelinear orders respectively. The paper investigates conditions under which anadditive partial order is included in, or extendable to, an additive linearorder. The additive dimension of an extendable additive partial order isdefined and computed for several classes of additive orders.     

Choiceless Ramsey Theory of Linear Orders

Motivated by work of Erd?s, Milner and Rado, we investigate symmetric and asymmetric partition relations for linear orders without the axiom of choice. The relations state the existence of a subset in one of finitely many given order types that is homogeneous for a given colouring of the finite subsets of a fixed size of a linear order. We mainly study the linear orders 〈 ^α 2,< _{l e x} 〉, where α is an infinite ordinal and < _{l e x} is the lexicographical order. We first obtain the consistency of several partition relations that are incompatible with the axiom of choice. For instance we derive partition relations for 〈 ^ω 2,< _{l e x} 〉 from the property of Baire for all subsets of ^ω 2 and show that the relation \(\langle ^{\kappa }{2}, <_{lex}\rangle \longrightarrow (\langle ^{\kappa }{2}, <_{lex}\rangle )^{2}_{2}\) is consistent for uncountable regular cardinals κ with κ ^<κ = κ. We then prove a series of negative partition relations with finite exponents for the linear orders 〈 ^α 2,< _{l e x} 〉. We combine the positive and negative results to completely classify which of the partition relations \(\langle ^{\omega }{2}, <_{lex}\rangle \longrightarrow (\bigvee _{\nu <\lambda }K_{\nu },\bigvee _{\nu <\mu }M_{\nu })^{m}\) for linear orders K _ν ,M _ν and m≤4 and 〈 ^ω 2,< _{l e x} 〉→(K,M) ⁿ for linear orders K,M and natural numbers n are consistent.     

On Initial Segments of Computable Linear Orders

We show there is a computable linear order with a initial segment that is not isomorphic to any computable linear order.     

Computable Linear Orders and the Ershov Hierarchy

We give the collection of relations on computable linear orders. For any natural number n, the degree spectrum of such relations of some computable linear orders contains exactly all n-computable enumerable degrees. We also study interconnections of these relations among themselves.     

Computable Embeddings for Pairs of Linear Orders

Algebra and Logic - We study computable embeddings for pairs of structures, i.e., for classes containing precisely two nonisomorphic structures. Surprisingly, even for some pairs of simple linear...