Other Proofs of Old Results

We transform the proof of the second incompleteness theorem given in [3] to a proof-theoretic version, avoiding the use of the arithmetized completeness theorem. We give also new proofs of old results: The Arithmetical Hierarchy Theorem and Tarski's Theorem on undefinability of truth; the proofs in which the construction of a sentence by means of diagonalization lemma is not needed.     

A short and constructive proof of Tarski’s fixed-point theorem

I give short and constructive proofs of Tarski’s fixed-point theorem, and of Zhou’s extension of Tarski’s fixed-point theorem to set-valued maps.I thank Charles Blair, William Thomson, an associated editor and a referee for their helpful suggestions.I have taught Tarski’s Theorem with F continuous to Caltech undergraduates.     

Complex eigenvalues before the Fundamental Theorem of Algebra

We present an elementary proof of the existence of an eigenvalue for an endomorphism of a complex vector space and we derive the Fundamental Theorem of Algebra as a corollary of this existence. We also present new proofs for the corresponding results for endomorphisms of real vector spaces.     

Non-commutative extensions of the MacMahon Master Theorem

We present several non-commutative extensions of the MacMahon Master Theorem, further extending the results of Cartier-Foata and Garoufalidis-Lê-Zeilberger. The proofs are combinatorial and new even in the classical cases. We also give applications to the β-extension and Krattenthaler-Schlosser's q-analogue.     

The Hahn-Vitali-Saks and the Uniform Boundedeess Theorem in topological groups

It is shown in this paper that the Theorem of Hahn-Vitali-Saks (Theorem 4) and the Uniform Boundedness Theorem (Theorem 5) hold true for measures with values in a topological group. The proofs given here for these theorems seem to the authors to be more direct than the usual proofs for real valued measures.     

A simple and elementary proof of the Karush–Kuhn–Tucker theorem for inequality-constrained optimization

We present an elementary proof of the Karush–Kuhn–Tucker Theorem for the problem with nonlinear inequality constraints and linear equality constraints. Most proofs in the literature rely on advanced optimization concepts such as linear programming duality, the convex separation theorem, or a theorem of the alternative for systems of linear inequalities. By contrast, the proof given here uses only basic facts from linear algebra and the definition of differentiability.     

The Clique Complex and Hypergraph Matching

The width of a hypergraph is the minimal for which there exist such that for any , for some . The matching width of is the minimal such that for any matching there exist such that for any , for some . The following extension of the Aharoni-Haxell matching Theorem [3] is proved: Let be a family of hypergraphs such that for each either or , then there exists a matching such that for all . This is a consequence of a more general result on colored cliques in graphs. The proofs are topological and use the Nerve Theorem. Received June 14, 1999     

Some new results on transition probability

In this paper, we study the basic properties of stationary transition probability of Markov processes on a general measurable space （E, δ）, such as the continuity, maximum probability, zero point, positive probability set,standardization, and obtain a series of important results such as Continuity Theorem, Representation Theorem, Levy Theorem and so on. These results are very useful for us to study stationary tri-point transition probability on a general measurable space （E, δ）. Our main tools such as Egoroff＇s Theorem, Vitali-Hahn-Saks＇s Theorem and the theory of atomic set and well- posedness of measure are also very interesting and fashionable.     

Editorial

A new proof of the Katêtov-Tong Insertion Theorem for L-fuzzy topological spaces is given. All the proofs are performed in such a way that the presented results hold true in the more general case in which L-fuzzy topologies are replaced by σ-additive rings of L-fuzzy subsets.     

The full power of the half-power

We use the complex square root to define a very simple homotopic invariant over the non-vanishing functions defined on the circle. As a consequence we provide easy proofs of the plane Brouwer fixed point theorem and the Fundamental Theorem of Algebra. The relation of this new invariant with the winding number and the Brouwer degree will be fully unveiled.     

On weakening the Deduction Theorem and strengthening Modus Ponens

This paper studies, with techniques of Abstract Algebraic Logic, the effects of putting a bound on the cardinality of the set of side formulas in the Deduction Theorem, viewed as a Gentzen‐style rule, and of adding additional assumptions inside the formulas present in Modus Ponens, viewed as a Hilbert‐style rule. As a result, a denumerable collection of new Gentzen systems and two new sentential logics have been isolated. These logics are weaker than the positive implicative logic. We have determined their algebraic models and the relationships between them, and have classified them according to several standard criteria of Abstract Algebraic Logic. One of the logics is protoalgebraic but neither equivalential nor weakly algebraizable, a rare situation where very few natural examples were hitherto known. In passing we have found new, alternative presentations of positive implicative logic, both in Hilbert style and in Gentzen style, and have characterized it in terms of the restricted Deduction Theorem: it is the weakest logic satisfying Modus Ponens and the Deduction Theorem restricted to at most 2 side formulas. The algebraic part of the work has lead to the class of quasi‐Hilbert algebras, a quasi‐variety of implicative algebras introduced by Pla and Verdú in 1980, which is larger than the variety of Hilbert algebras. Its algebraic properties reflect those of the corresponding logics and Gentzen systems. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Brooks' Theorem and Beyond

We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and extensions of each. The proofs illustrate some of the major techniques in graph coloring, such as greedy coloring, Kempe chains, hitting sets, and the Kernel Lemma. We also discuss standard strengthenings of vertex coloring, such as list coloring, online list coloring, and Alon–Tarsi orientations, since analogs of Brooks' Theorem hold in each context. We conclude with two conjectures along the lines of Brooks' Theorem that are much stronger, the Borodin–Kostochka Conjecture and Reed's Conjecture.     

An observation on realcompact spaces

We give a characterization of realcompact spaces in terms of nets. By using the technique of this characterization we give easy proofs of the Tychonoff Theorem and the Alaoglu Theorem.

     

On fundamental theorems of algebraic K-theory

In this work we present proofs of basic theorems in Quillen's algebraic K-theory of exact categories. The proofs given here are simpler and more straight-forward than the originals.     

Stability and other limit laws for exit times of random walks from a strip or a halfplane

We show that the passage time, T^*(r), of a random walk S_n above a horizontal boundary at r (r≥0) is stable (in probability) in the sense that as r→∞ for a deterministic function C(r)>0, if and only if the random walk is relatively stable in the sense that as n→∞ for a deterministic sequence B_n>0. The stability of a passage time is an important ingredient in some proofs in sequential analysis, where it arises during applications of Anscombe's Theorem. We also prove a counterpart for the almost sure stability of T^*(r), which we show is equivalent to E|X|<∞, EX>0. Similarly, counterparts for the exit of the random walk from the strip {|y|≤r} are proved. The conditions arefurther related to the relative stability of the maximal sum and the maximum modulus of the sums. Another result shows that the exit position of the random walk outside the boundaries at ±r drifts to ∞ as r→∞ if and only if the random walk drifts to ∞.     

Note on residually finite rings

This paper is on the subject of residually finite (= RF) modules and rings introduced by Varadarajan [93] and [98/99]. Specifically there are several theorems that simplify proofs and generalize some results of Varadarajan, namely.

Theorem 1. An RF right R-module is finitely bedded (= has finite essential socle iff M is finite.

Corollay. If T is a right RF woth just finitely many simple ringht R-modules, them R is fimite.

Theorem 2. A commutative ring R is residually finite iff every local ring R_m at a maximal ideal m is finite.     

A desarguesian theorem for algebraic combinatorial geometries

The points of an algebraic combinatorial geometry are equivalence classes of transcendentals over a fieldk; two transcendentals represent the same point when they are algebraically dependent overk. The points of an algebraically closed field of transcendence degree two (three) overk are the lines (resp. planes) of the geometry. We give a necessary and sufficient condition for two coplanar lines to meet in a point (Theorem 1) and prove the converse of Desargues’ theorem for these geometries (Theorem 2). A corollary: the “non-Desargues” matroid is non-algebraic. The proofs depend on five properties (or postulates). The fifth of these is a deep property first proved by Ingleton and Main [3] in their paper showing that the Vámos matroid is non-algebraic.     

The translation theorem

Summary We state and prove the Translation Theorem. Then we apply the Translation Theorem to Soare's Extension Theorem, weakening slightly the hypothesis to yield a theorem we call the Modified Extension Theorem. We use this theorem to reprove several of the known results about orbits in the lattice of recursively enumerable sets. It is hoped that these proofs are easier to understand than the old proofs.Mathematics subject classification (1991): 03D25The author was partially supported by a NSF Postdoctoral Fellowship and by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University and wishes to thank Michael Stob and Rodney Downey for their help     

Quasi-periodic Solutions of Completely Resonant Wave Equations with Quasi-periodically forced Vibrations

In this paper, we provide the existence of quasi-periodic solutions with two frequencies for a class of completely resonant nonlinear wave equations with quasi-periodically forced vibrations under the spatial periodic boundary conditions. We consider the frequencies vector (ω ₁,ω ₂) near the linear system. The proofs are based on the Variational Lyapunov-Schmidt reduction and Linking Theorem.     

A proof of the homotopy push-out and pull-back lemma

The homotopy push-out and pull-back lemma of Iwase (1998) is a generalized version of Theorem 1.1 of Ganea (1965) and the Theorem of Rutter (1971) whose proofs were given under the simply-connectivity condition. The purpose of this paper is to give a proof in the general case.