The FAN principle and weak König's lemma in herbrandized second-order arithmetic

We introduce a herbrandized functional interpretation of a first-order semi-intuitionistic extension of Heyting Arithmetic and study its main properties. We then extend the interpretation to a certain system of second-order arithmetic which includes a (classically false) formulation of the FAN principle and weak König's lemma. It is shown that any first-order formula provable in this system is classically true. It is perhaps worthy of note that, in our interpretation, second-order variables are interpreted by finite sets of natural numbers.     

Classical provability of uniform versions and intuitionistic provability

Along the line of Hirst‐Mummert 9 and Dorais 4 , we analyze the relationship between the classical provability of uniform versions Uni(S) of Π₂‐statements S with respect to higher order reverse mathematics and the intuitionistic provability of S. Our main theorem states that (in particular) for every Π₂‐statement S of some syntactical form, if its uniform version derives the uniform variant of over a classical system of arithmetic in all finite types with weak extensionality, then S is not provable in strong semi‐intuitionistic systems including bar induction in all finite types but also nonconstructive principles such as K?nig's lemma and uniform weak K?nig's lemma . Our result is applicable to many mathematical principles whose sequential versions imply .     

Induced Ramsey-type theorems

We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rödl, Łuczak-Rödl, Prömel-Rödl, Erdős-Hajnal, and Nikiforov. The proofs are based on a simple lemma (generalizing one by Graham, Rödl, and Ruciński) that can be used as a replacement for Szemerédi's regularity lemma, thereby giving much better bounds. The same approach can be also used to show that pseudo-random graphs have strong induced Ramsey properties. This leads to explicit constructions for upper bounds on various induced Ramsey numbers.     

Exact categories

We survey the basics of homological algebra in exact categories in the sense of Quillen. All diagram lemmas are proved directly from the axioms, notably the five lemma, the 3×3$3\times 3$-lemma and the snake lemma. We briefly discuss exact functors, idempotent completion and weak idempotent completeness. We then show that it is possible to construct the derived category of an exact category without any embedding into abelian categories and we sketch Deligne's approach to derived functors. The construction of classical derived functors with values in an abelian category painlessly translates to exact categories, i.e., we give proofs of the comparison theorem for projective resolutions and the horseshoe lemma. After discussing some examples we elaborate on Thomason's proof of the Gabriel–Quillen embedding theorem in an appendix.     

A note on Arzela–Ascoli's lemma in almost periodic problems

This paper is concerned with a generalized Arzela–Ascoli's lemma, which has been extensively applied in almost periodic problems by the continuation theorem of degree theory. We give a counter example to show that this lemma is incorrect, and there is a gap in the proof of some existing literature, where the addressed generalized Arzela–Ascoli's lemma was used. Moreover, we make some final comments and introduce an open problem. Copyright © 2016 John Wiley & Sons, Ltd.     

Forbidden subgraphs and the Kőnig property

A graph has the Kőnig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Kőnig property by forbidden subgraphs, restricted to graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovászʼs result to a characterization of all graphs having the Kőnig property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Kőnig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Kőnig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs.     

Erhaltungssätze und schwache lösungen in der gasdynamik

The fundamental laws of Gasdynamics can be formulated very naturally as conservation laws in the form of integral relations. This formulation includes not only continuously differentiable processes but also the very important discontinuous shocks. On the other side one has the tool of weak solutions of the differential equations of Gasdynamics due to P. D. Lax and several other authors. While the conservation laws of integral type are determined by Physics in an unique way the differential equations of Gasdynamics, even if written in divergence form, are not. Hence the question arises which form of the differential equations in the weak sense is the “correct” interpretation of the physical conservation laws. This paper tries to give an answer by investigating the connections between the two formulations. At first the integral equations of Gasdynamics are written in space-time divergence form. Thus, independently from Gasdynamics, one has Haar's lemma stating that for each weak solution of a partial differential equation (in divergence form) a corresponding integral equation of conservation law type is valid for almost every family member, the family consisting of some simple domains like spheres or squares. Moreover the converse of Haar's lemma is also true. In this paper Haar's lemma is extended to a more general class of domains. This yields that both formulations of conservation laws are essentially equivalent. Additionally a divergence definition due to C. Müller is considered. As is shown by a simple example C. Müller's divergence concept leads to a more general class of solutions, not all of them being solutions of the corresponding conservation laws.     

The capacities of certain special channels with arbitrarily varying channel probability functions

In [5] Ahlswede and Wolfowitz have obtained the capacities of a.v.ch. with binary output in a number of cases, essentially with the aid of a lemma which relates the capacity of the a.v.ch. to that of a suitable (“underlying”) d.m.c. A generalization of this lemma to a special kind of a.v.ch. with output alphabet b>2, has been given by Ahlswede (Lemma 1 of [1]) and used in [1] and [2] to prove the existence of the weak capacities of various channels under different conditions. We give a detailed proof of a weakened version of Ahlswede's lemma and show, in passing, that his lemma is incorrect. We then define certain special types of a.v.ch and, on the basis of the detailed analysis given by us earlier, we prove lemmas of a similar type for these a.v.ch. We are thus able to extend certain results given for binary output a.v.ch. in [4] and [5] to these special a.v.ch. for which b>2.     

Szemerédi’s Lemma for the Analyst

Szemerédi’s regularity lemma is a fundamental tool in graph theory: it has many applications to extremal graph theory, graph property testing, combinatorial number theory, etc. The goal of this paper is to point out that Szemerédi’s lemma can be thought of as a result in analysis. We show three different analytic interpretations. Received: February 2006 Revision: April 2006 Accepted: April 2006     

Independence over arbitrary sets in NSOP1 theories

We study Kim-independence over arbitrary sets. Assuming that forking satisfies existence, we establish Kim's lemma for Kim-dividing over arbitrary sets in an NSOP₁ theory. We deduce symmetry of Kim-independence and the independence theorem for Lascar strong types.     

Microlocal defect measures

In order to study weak continuity of quadratic forms on spaces of L² solutions of systems of partial differential equations, we define defect measures on the space of positions and frequencies.A systematic use of these measures leads in particular to a compensated compactness theorem, generalizing MURAT"TARTAR's compensated compactness to variable coefficients and GOLSE"LIONS"PERTHAME"SENTIS's averaging lemma. We also obtain results on homogenization for differential operators of order I with oscillating coefficients.     

A De Giorgi Type Result to Divergence Degenerate Elliptic Equation with Bounded Coefficients Related To Hörmander's Vector Fields

In this paper, we consider the divergence degenerate elliptic equation with bounded coefficients constructed by Hörmander's vector fields. We prove a De Giorgi type result, i.e., the local Hölder continuity for the weak solutions to the equation by providing a De Giorgi type lemma and extending the Moser iteration to the setting here. As a consequence, the Harnack inequality of weak solutions is also given.     

Weak Hopf lemma for the invariant Laplacian and related elliptic operators

We obtain a weak version of the Hopf lemma for the invariant Laplacian on the unit ball of the complex n$n$-space. We also show that our result is sharp in some sense. Motivated by this result, we also consider a class of degenerate elliptic operators with the degeneracy depending on the distance to the boundary of the domain. We study the dependence of the validity of Hopf lemma on the degree of degeneracy of the operator. We show that Hopf lemma holds if the degeneracy is small and fails in general if the degeneracy is large. What is more interesting is the critical case for which we show that certain weak version of Hopf lemma holds.     

Complex analysis in subsystems of second order arithmetic

This research is motivated by the program of Reverse Mathematics. We investigate basic part of complex analysis within some weak subsystems of second order arithmetic, in order to determine what kind of set existence axioms are needed to prove theorems of basic analysis. We are especially concerned with Cauchy’s integral theorem. We show that a weak version of Cauchy’s integral theorem is proved in RCAo. Using this, we can prove that holomorphic functions are analytic in RCAo. On the other hand, we show that a full version of Cauchy’s integral theorem cannot be proved in RCAo but is equivalent to weak König’s lemma over RCAo.     

Pullback attractors of 2D Navier–Stokes equations with weak damping,distributed delay,and continuous delay

In this present paper, the existence of pullback attractors for the 2D Navier–Stokes equation with weak damping, distributed delay, and continuous delay has been considered, by virtue of classical Galerkin's method, we derived the existence and uniqueness of global weak and strong solutions. Using the Aubin–Lions lemma and some energy estimate in the Banach space with delay, we obtained the uniform bounded and existence of uniform pullback absorbing ball for the solution semi‐processes; we concluded the pullback attractors via verifying the pullback asymptotical compactness by the generalized Arzelà–Ascoli theorem. Copyright © 2016 John Wiley & Sons, Ltd.     

Coding of real-valued continuous functions under WKL$\mathsf {WKL}$

In the context of constructive reverse mathematics, we show that weak Kőnig's lemma ($\mathsf{WKL}$) implies that every pointwise continuous function $f:[0,1]\to \mathbb{R}$ is induced by a code in the sense of reverse mathematics. This, combined with the fact that $\mathsf{WKL}$ implies the Fan theorem, shows that $\mathsf{WKL}$ implies the uniform continuity theorem: every pointwise continuous function $f:[0,1]\to \mathbb{R}$ has a modulus of uniform continuity. Our results are obtained in Heyting arithmetic in all finite types with quantifier-free axiom of choice.     

Extremal results in sparse pseudorandom graphs

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.     

Operator trigonometry of preconditioning,domain decomposition,sparse approximate inverses,successive overrelaxation,minimum residual schemes

This paper extends the relationship between the author's operator trigonometry and convergence rates and other properties of important iterative methods. A new interesting trigonometric preconditioning lemma is given. The general relationship between domain decomposition methods and the operator trigonometry is established. A new basic conceptual link between sparse approximate inverse algorithms and the operator trigonometry is observed. A new underlying fundamental inherent trigonometry of the classical successive over‐relaxation scheme is exposed. Some improved trigonometric interpretations of minimum residual schemes are mentioned. Copyright © 2002 John Wiley & Sons, Ltd.     

Existence of nontrivial homoclinic orbits for fourth-order difference equations

We obtain a sufficient condition for the existence of nontrivial homoclinic orbits for fourth-order difference equations by using Mountain Pass Theorem, a weak convergence argument and a discrete version of Lieb’s lemma.