Derived sequences and reverse mathematics

One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR₀. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR₀. In actuality, the full strength of ATR₀ is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR₀, using only RCA₀ and the assertion that every countable closed set has a derived sequence. We will use three of the subsystems of second order arithmetic defined by H. Friedman ([3], [4]), which can be roughly characterized by the strength of their set comprehension axioms. RCA₀ includes comprehension for Δ definable sets, ACA₀ includes comprehension for arithmetical sets, and ATR₀ appends to ACA₀ a comprehension scheme for sets defined by transfinite recursion on arithmetical formulas. MSC: 03F35, 54B99.     

Reverse mathematics and initial intervals

In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We show that the left to right directions of these theorems are equivalent to _ACA0${\mathsf{ACA}}_0$ and _ATR0${\mathsf{ATR}}_0$, respectively. On the other hand, the opposite directions are both provable in _WKL0${\mathsf{WKL}}_0$, but not in _RCA0${\mathsf{RCA}}_0$. We also prove the equivalence with _ACA0${\mathsf{ACA}}_0$ of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains.     

Effectiveness for infinite variable words and the Dual Ramsey Theorem

We examine the Dual Ramsey Theorem and two related combinatorial principles VW(k,l) and OVW(k,l) from the perspectives of reverse mathematics and effective mathematics. We give a statement of the Dual Ramsey Theorem for open colorings in second order arithmetic and formalize work of Carlson and Simpson [1] to show that this statement implies ACA₀ over RCA₀. We show that neither VW(2,2) nor OVW(2,2) is provable in WKL₀. These results give partial answers to questions posed by Friedman and Simpson [3].The first authors research is partially supported by an NSF VIGRE Grant at Indiana University. The second authors research is partially supported by an NSF Postdoctoral Fellowship.     

On the absence of eigenvalues of Maxwell and Lamé systems in exterior domains

The arguments showing non‐existence of eigensolutions to exterior‐boundary value problems associated with systems—such as the Maxwell and Lamé system—rely on showing that such solutions would have to have compact support and therefore—by a unique continuation property—cannot be non‐trivial. Here we will focus on the first part of the argument. For a class of second order elliptic systems it will be shown that L²‐solutions in exterior domains must have compact support. Both the asymptotically isotropic Maxwell system and the Lamé system with asymptotically decaying perturbations can be reduced to this class of elliptic systems. Copyright © 2004 John Wiley & Sons, Ltd.     

Trading crossings for handles and crosscaps

Let c_k = cr_k (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence c_o, c₁,c₂…encodes the trade‐off between adding handles and decreasing crossings. We focus on sequences of the type c_o > c₁ > c₂ = 0; equivalently, we study the planar and toroidal crossing number of doubly‐toroidal graphs. For every ? > 0 we construct graphs whose orientable crossing sequence satisfies c₁/c_o > 5/6??. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non‐orientable crossing sequence ?₀,?₁,?₂, ··· for drawings on non‐orientable surfaces. We show that for every ?₀ > ?₁ > 0 there exists a graph with non‐orientable crossing sequence ?₀, ?₁, 0. We conjecture that every strictly‐decreasing sequence of non‐negative integers can be both an orientable crossing sequence and a non‐orientable crossing sequence (with different graphs). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001     

Asymptotic analysis and boundary homogenization in linear elasticity

We describe the asymptotic behaviour of the solution of a linear elastic problem posed in a domain of ℝ³, with homogeneous Dirichlet boundary conditions imposed on small zones of size less than ϵ distributed on the boundary of this domain, when the parameter ϵ goes to 0. We use epi‐convergence arguments in order to establish this asymptotic behaviour. We then specialize this general situation to the case of identical strips of size r_ϵ ϵ‐periodically distributed on the lateral surface of an axisymmetric body. We exhibit a critical size of the strips through the limit of the non‐negative quantity −1/(ϵ ln r_ϵ) and we identify the different limit problems according to the values of this limit. Copyright © 2000 John Wiley & Sons, Ltd.     

Second order theories with ordinals and elementary comprehension

We study elementary second order extensions of the theoryID ₁ of non-iterated inductive definitions and the theoryPA _Ω of Peano arithmetic with ordinals. We determine the exact proof-theoretic strength of those extensions and their natural subsystems, and we relate them to subsystems of analysis with arithmetic comprehension plusΠ ₁ ¹ comprehension and bar induction without set parameters. Research supported by the Swiss National Science Foundation     

Stability and convergence of the mark and cell finite difference scheme for Darcy‐Stokes‐Brinkman equations on non‐uniform grids

In this paper, we consider the mark and cell (MAC) method for Darcy‐Stokes‐Brinkman equations and analyze the stability and convergence of the method on nonuniform grids. Firstly, to obtain the stability for both velocity and pressure, we establish the discrete inf‐sup condition. Then we introduce an auxiliary function depending on the velocity and discretizing parameters to analyze the super‐convergence. Finally, we obtain the second‐order convergence in L2 norm for both velocity and pressure for the MAC scheme, when the perturbation parameter ? is not approaching 0. We also obtain the second‐order convergence for some terms of ∥·∥_? norm of the velocity, and the other terms of ∥·∥_? norm are second‐order convergence on uniform grid. Numerical experiments are carried out to verify the theoretical results.     

Homogenization of the Signorini boundary‐value problem in a thick junction and boundary integral equations for the homogenized problem

We consider a mixed boundary‐value problem for the Poisson equation in a thick junction Ω_ε which is the union of a domain Ω₀ and a large number of ε—periodically situated thin cylinders. The non‐uniform Signorini conditions are given on the lateral surfaces of the cylinders. The asymptotic analysis of this problem is done as ε→0, i.e. when the number of the thin cylinders infinitely increases and their thickness tends to zero. We prove a convergence theorem and show that the non‐uniform Signorini boundary conditions are transformed in the limiting variational inequalities in the region that is filled up by the thin cylinders as ε→0. The convergence of the energy integrals is proved as well. The existence and uniqueness of the solution to this non‐standard limit problem is established. This solution can be constructed by using a penalty formulation and successive iteration. For some subclass, these problems can be reduced to an obstacle problem in Ω₀ and an appropriate postprocessing. The equations in Ω₀ finally are also treated with boundary integral equations. Copyright © 2010 John Wiley & Sons, Ltd.     

Trace Formulas for Some Singular Differential Operators and Applications

We characterize the convergence of the series ∑ λ^–1_n, where λⁿ are the non‐zero eigenvalues of some boundary value problems for degenerate second order ordinary differential operators and we prove a formula for the above sum when the coefficient of the zero‐order term vanishes. We study these operators both in weighted Hilbert spaces and in spaces of continuous functions. After investigating the boundary behaviour of the eigenfunctions, we give applications to the regularity of the generated semigroups.     

Determinacy of Wadge classes and subsystems of second order arithmetic

In this paper we study the logical strength of the determinacy of infinite binary games in terms of second order arithmetic. We define new determinacy schemata inspired by the Wadge classes of Polish spaces and show the following equivalences over the system RCA₀*, which consists of the axioms of discrete ordered semi‐rings with exponentiation, Δ₁⁰ comprehension and Π₀⁰ induction, and which is known as a weaker system than the popularbase theory RCA₀: 1. Bisep(Δ₁⁰, Σ₁⁰)‐Det* ? WKL₀, (1) 2. Bisep(Δ₁⁰, Σ₂⁰)‐Det* ? ATR₀ + Σ₁¹ induction, (2) 3. Bisep(Σ₁⁰, Σ₂⁰)‐Det* ? Sep(Σ₁⁰, Σ₂⁰)‐Det* ? Π₁¹‐CA₀, (3) 4. Bisep(Δ₂⁰, Σ₂⁰)‐Det* ? Π₁¹‐TR₀, (4) where Det* stands for the determinacy of infinite games in the Cantor space (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Independence Result on Weak Second Order Bounded Arithmetic

We show that length initial submodels of S¹₂ can be extended to a model of weak second order arithmetic. As a corollary we show that the theory of length induction for polynomially bounded second order existential formulae cannot define the function division.     

Second‐order finite‐volume schemes for a non‐linear hyperbolic equation: error estimate

We study second‐order finite‐volume schemes for the non‐linear hyperbolic equation u_t(x, t) + div F(x, t, u(x, t)) = 0 with initial condition u₀. The main result is the error estimate between the approximate solution given by the scheme and the entropy solution. It is based on some stability properties verified by the scheme and on a discrete entropy inequality. If u₀ ∈ L^∞ ∩ BV_loc(ℝ^N), we get an error estimate of order h^1/4, where h defines the size of the mesh. Copyright © 2000 John Wiley & Sons, Ltd.     

Model theory of a Hilbert space expanded with an unbounded closed selfadjoint operator

We study a closed unbounded self‐adjoint operator Q acting on a Hilbert space H in the framework of Metric Abstract Elementary Classes (MAECs). We build a suitable MAEC for such a structure, prove it is ?₀‐categorical and ?₀‐stable up to a system of perturbations. We give an explicit continuous axiomatization for the class. We also characterize non‐splitting and show it has the same properties as non‐forking in superstable first order theories. Finally, we characterize equality, orthogonality and domination of (Galois) types in that MAEC.     

Fragments of Arithmetic and true sentences

By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Π_n+1‐sentences true in the standard model is the only (up to deductive equivalence) consistent Π_n+1‐theory which extends the scheme of induction for parameter free Π_n+1‐formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first‐order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, we obtain results on the quantifier complexity, (non)finite axiomatizability and relative strength of schemes for Δ_n+1‐formulas. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Lebesgue measure of the algebraic difference of two random Cantor sets

In this paper we consider a family of random Cantor sets on the line. We give some sufficient conditions when the Lebesgue measure of the arithmetic difference is positive. Combining this with the main result of a recent joint paper of the second author with M. Dekking we construct random Cantor sets F₁, F₂ such that the arithmetic difference set F₂ − F₁ does not contain any intervals but ?eb(F₂ − F₁)> 0 almost surely, conditioned on non-extinction.     

Abelian groups and quadratic residues in weak arithmetic

We investigate the provability of some properties of abelian groups and quadratic residues in variants of bounded arithmetic. Specifically, we show that the structure theorem for finite abelian groups is provable in S₂² + iWPHP(Σ₁^b), and use it to derive Fermat's little theorem and Euler's criterion for the Legendre symbol in S₂² + iWPHP(PV) extended by the pigeonhole principle PHP(PV). We prove the quadratic reciprocity theorem (including the supplementary laws) in the arithmetic theories T₂⁰ + Count₂(PV) and I Δ₀ + Count₂(Δ₀) with modulo‐2 counting principles (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A new highly accurate discretization for three‐dimensional singularly perturbed nonlinear elliptic partial differential equations

We employ a new fourth‐order compact finite difference formula based on arithmetic average discretization to solve the three‐dimensional nonlinear singularly perturbed elliptic partial differential equation ε(u_xx + u_yy + u_zz) = f(x, y, z, u, u_x, u_y, u_z), 0 < x, y, z < 1, subject to appropriate Dirichlet boundary conditions prescribed on the boundary, where ε > 0 is a small parameter. We also describe new fourth‐order methods for the estimates of (?u/?x), (?u/?y), and (?u/?z), which are quite often of interest in many physical problems. In all cases, we require only a single computational cell with 19 grid points. The proposed methods are directly applicable to solve singular problems without any modification. We solve three test problems numerically to validate the proposed derived fourth‐order methods. We compare the advantages and implementation of the proposed methods with the standard central difference approximations in the context of basic iterative methods. Numerical examples are given to verify the fourth‐order convergence rate of the methods. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

Relative arithmetic

In nonstandard mathematics, the predicate ‘x is standard’ is fundamental. Recently, ‘relative’ or ‘stratified’ nonstandard theories have been developed in which this predicate is replaced with ‘x is y ‐standard’. Thus, objects are not (non)standard in an absolute sense, but (non)standard relative to other objects and there is a whole stratified universe of ‘levels’ or ‘degrees’ of standardness. Here, we study stratified nonstandard arithmetic and the related transfer principle. Using the latter, we obtain the ‘reduction theorem’ which states that arithmetical formulas can be reduced to equivalent bounded formulas. Surprisingly, the reduction theorem is also equivalent to the transfer principle. As applications, we obtain a truth definition for arithmetical sentences and we formalize Nelson's notion of impredicativity (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)