Ordinal arithmetic and \Sigma_{1}-elementarity

We will introduce a partial ordering on the class of ordinals which will serve as a foundation for an approach to ordinal notations for formal systems of set theory and second-order arithmetic. In this paper we use to provide a new characterization of the ubiquitous ordinal . Received: 18 August 1997     

Ordinal diagrams for recursively Mahlo universes

In this paper we introduce a recursive notation system of ordinals. An element of the notation system is called an ordinal diagram following G. Takeuti [25]. The system is designed for proof theoretic study of theories of recursively Mahlo universes. We show that for each in KPM proves that the initial segment of determined by is a well ordering. Proof theoretic study for such theories will be reported in [9]. Received: 13 January, 1998     

The path relation for directed planar graphs in rectangles, and its relation to the free diad

In this paper, we define the path relation of a directed graph to be the relation which relates two vertices if there is a path from the first to the second. We study the restriction of this relation to paths from sources to sinks, and consider the question of when two finite graphs embedded in a rectangle give the same relation. We find a set of local changes to these graphs which can be used to get between any two graphs for which this relation is the same. Furthermore, we classify the relations which can arise as this relation for a finite directed graph embedded in a rectangle as the triconvex relations between finite ordinals (defined in this paper).This work originated from some of the author’s work on category theory. It turns out that the category of finite ordinals and relations that can be the path relation of a directed graph embedded in a rectangle, is relevant to the study of diads—introduced by the author as a common generalisation of monads and comonads (note that the terms diad and dyad have been used to mean different things by other authors). More specifically, the referee of one of the author’s papers suggested that it would be useful to identify the category which plays the role for diads that the category of finite ordinals and order-preserving functions plays for monads. It turns out that the category of finite ordinals and relations that can be path relations of graphs embedded in a rectangle, is exactly the category that plays this role.     

Stationary logic of ordinals

The L(aa)-theory of ordinals—Th_aa(On)—is studied. It is shown that Th_aa(On) is primitive recursive. In a suitable language it is possible to eliminate quantifiers. L(aa)-equivalence invariants are given. Both the complete L(aa)-theories of ordinals and the complete extensions of Th_aa(On) are characterized. An ordering is L(aa)-inductive if every L(aa)-definable subset (with suitable parameters) has a least element. The models of Th_aa(On) are the L(aa)-inductive orderings. A variant of the back and forth method is introduced in order toprove primitive recursive decidability and elimination of quantifier results.     

Post’s Problem for ordinal register machines: An explicit approach

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.     

Definable Ramsey and definable Erdös ordinals

This paper studies the relation between definable Ramsey ordinals and constructible sets which have a certain set of indiscernibles. It is shown that an ordinal κ is Σ₁-Ramsey if and only if κ is ∑_ω-Ramsey. Similar results are obtained for definable Erdös ordinals.     

Register computations on ordinals

We generalize ordinary register machines on natural numbers to machines whose registers contain arbitrary ordinals. Ordinal register machines are able to compute a recursive bounded truth predicate on the ordinals. The class of sets of ordinals which can be read off the truth predicate satisfies a natural theory SO. SO is the theory of the sets of ordinals in a model of the Zermelo-Fraenkel axioms ZFC. This allows the following characterization of computable sets: a set of ordinals is ordinal register computable if and only if it is an element of Gödel’s constructible universe L.     

Towards a cost-effective ILU preconditioner with high level fill

There has been increased interest in the effect of the ordering of the unknowns on Preconditioned Conjugate Gradient (PCG) methods. A recently proposed Minimum Discarded Fill (MDF) ordering technique is effective in finding goodILU(l) preconditioners, especially for problems arising from unstructured finite element grids. This algorithm can identify anisotropy in complicated physical structures and orders the unknowns in an appropriate direction. TheMDF technique may be viewed as an analogue of the minimum deficiency algorithm in sparse matrix technology, and hence is expensive to compute for high levelILU(l) preconditioners.In this work, several less expensive variants of theMDF technique are explored to produce cost-effectiveILU preconditioners. The ThresholdMDF ordering combinesMDF ideas with drop tolerance techniques to identify the sparsity pattern in theILU preconditioners. The Minimum Update Matrix (MUM) ordering technique is a simplification of theMDF ordering and is an analogue of the minimum degree algorithm. TheMUM ordering method is especially effective for large matrices arising from Navier-Stokes problems.This work was supported by the Natural Sciences and Engineering Research Council of Canada, by the Information Technology Research Centre, which is funded by the Province of Ontario, and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc., through an appointment to the U.S. Department of Energy Postgraduate Research Program administered by Oak Ridge Associated Universities.     

Downward closure of depth in countable Boolean algebras

We study the set of depths of relative algebras of countable Boolean algebras, in particular the extent to which this set may not be downward closed within the countable ordinals for a fixed countable Boolean algebra. Doing so, we exhibit a structural difference between the class of arbitrary rank countable Boolean algebras and the class of rank one countable Boolean algebras.     

Zimmermann type cancellation in the free Faà di Bruno algebra

Haiman and Schmitt showed that one can use the antipode SF of the colored Faà di Bruno Hopf algebra F to compute the (compositional) inverse of a multivariable formal power series. It is shown that the antipode SH of an algebraically free analogue H of F may be used to invert non-commutative power series. Whereas F is the incidence Hopf algebra of the colored partitions of finite colored sets, H is the incidence Hopf algebra of the colored interval partitions of finite totally ordered colored sets. Haiman and Schmitt showed that the monomials in the geometric series for SF are labeled by trees. By contrast, the non-commuting monomials of SH are labeled by colored planar trees. The order of the factors in each summand is determined by the breadth first ordering on the vertices of the planar tree. Finally there is a parallel to Haiman and Schmitt's reduced tree formula for the antipode, in which one uses reduced planar trees and the depth first ordering on the vertices. The reduced planar tree formula is proved by recursion, and again by an unusual cancellation technique. The one variable case of H has also been considered by Brouder, Frabetti, and Krattenthaler, who point out its relation to Foissy's free analogue of the Connes-Kreimer Hopf algebra.     

Algorithms for improving efficiency of discrete Markov chains

Sampling from an intractable probability distribution is a common and important problem in scientific computing. A popular approach to solve this problem is to construct a Markov chain which converges to the desired probability distribution, and run this Markov chain to obtain an approximate sample. In this paper, we provide two methods to improve the performance of a given discrete reversible Markov chain. These methods require the knowledge of the stationary distribution only up to a normalizing constant. Each of these methods produces a reversible Markov chain which has the same stationary distribution as the original chain, and dominates the original chain in the ordering introduced by Peskun [11]. We illustrate these methods on two Markov chains, one connected to hidden Markov models and one connected to card shuffling. We also prove a result which shows that the Metropolis-Hastings algorithm preserves the Peskun ordering for Markov transition matrices.     

Infinite Time Turing Machines With Only One Tape

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi‐tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one‐tape computable, and so the two models of infinitary computation are not equivalent. Surprisingly, the class of one‐tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal that is clockable by an infinite time Turing machine is clockable by a one‐tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.     

A periodic flow with infinite Epstein hierarchy

In 1975 D. Sullivan gave an example of a periodic flow on a compact 5-manifold with Epstein hierarchy of length one, and he asked whether the Epstein hierarchy of a compact foliation could have infinite length. We show that the answer is yes by constructing a periodic flow with this property on a compact 8-manifold. By modifying the example one can see that any countable ordinal can occur as the length of the Epstein hierarchy. It is known that only countable ordinals can occur [1].     

EPIREFLECTIVE HULLS OF SPACES OF ORDINALS IN To

Abstract

A particular class of epireflective subcategories of To is investigated, exactly the epireflective hulls g(S(a) of the spaces S(a) of the ordinals with the “open half lines” topology. The topological structure of the objects of these hulls is studied, also in relation with their sobrification. Furthermore, a bijective correspondence between hulls and classes of cofinality of ordinals is found.     

Metaheuristics for the linear ordering problem with cumulative costs

The linear ordering problem with cumulative costs (LOPCC) is a variant of the well-known linear ordering problem, in which a cumulative propagation makes the objective function highly non-linear. The LOPCC has been recently introduced in the context of mobile-phone telecommunications. In this paper we propose two metaheuristic methods for this NP-hard problem. The first one is based on the GRASP methodology, while the second one implements an Iterated Greedy-Strategic Oscillation procedure. We also propose a post-processing based on Path Relinking to obtain improved outcomes. We compare our methods with the state-of-the-art procedures on a set of 218 previously reported instances. The comparison favors the Iterated Greedy - Strategic Oscillation with the Path Relinking post-processing, which is able to identify 87 new best objective function values.     

GO-空间乘积的子空间仿紧性的充分必要条件

我们知道,GO-空间乘积的子空间不一定仿紧.在2000年,数学家N.Kemoto,K.Tamano和Y.Yajima证明了两个特殊的GO-空间-序数乘积子空间的仿紧性的一个充分必要条件.把这个定理进行了推广,到了两个一般的GO-空间乘积的任意子空间仿紧性的一个充分必要条件.     

Operating on the universe

Summary In spite of the fact that the Z.F. universe is not well-ordered, it behaves in some respects like the ordinals. It is possible to define on it the usual operations of addition, multiplication and exponentiation, which enjoy similar properties to those on the ordinals. Further when restricted to the ordinals, the operations coincide, so that ordinal arithmetic can be regarded as a restriction of the universe arithmetic. But more than that, rank which retracts the universe of sets onto the ordinals is a homomorphism between the universe arithmetical structure V,+,·,exp and the ordinal arithmetical structure Ord, +, ·,exp.     

A note on the Σ1 spectrum of a theory

Let T be a suitable system of classical set theory. We will show, that the Σ₁ spectrum of T, i.e. the set of ordinals having good Σ₁ definition in T is an initial segment of the ordinals. Received: 11 October 1999 / Published online: 12 December 2001     

Successors of singular cardinals and coloring theorems I

We investigate the existence of strong colorings on successors of singular cardinals. This work continues Section 2 of [1], but now our emphasis is on finding colorings of pairs of ordinals, rather than colorings of finite sets of ordinals.This is publication number 535 of the second author.