Brouwer’s Fan Theorem as an axiom and as a contrast to Kleene’s alternative

The paper is a contribution to intuitionistic reverse mathematics. We introduce a formal system called Basic Intuitionistic Mathematics BIM, and then search for statements that are, over BIM, equivalent to Brouwer’s Fan Theorem or to its positive denial, Kleene’s Alternative to the Fan Theorem. The Fan Theorem is true under the intended intuitionistic interpretation and Kleene’s Alternative is true in the model of BIM consisting of the Turing-computable functions. The task of finding equivalents of Kleene’s Alternative is, intuitionistically, a nontrivial extension of the task of finding equivalents of the Fan Theorem, although there is a certain symmetry in the arguments that we shall try to make transparent. We introduce closed-and-separable subsets of Baire space \({\mathcal{N}}\) and of the set \({\mathcal{R}}\) of the real numbers. Such sets may be compact and also positively noncompact. The Fan Theorem is the statement that Cantor space \({\mathcal{C}}\) , or, equivalently, the unit interval [0, 1], is compact and Kleene’s Alternative is the statement that \({\mathcal{C}}\) , or, equivalently, [0, 1], is positively noncompact. The class of the compact closed-and-separable sets and also the class of the closed-and-separable sets that are positively noncompact are characterized in many different ways and a host of equivalents of both the Fan Theorem and Kleene’s Alternative is found.     

A Theory of Stationary Trees and the Balanced Baumgartner–Hajnal–Todorcevic Theorem for Trees

Building on early work by Stevo Todorcevic, we develop a theory of stationary subtrees of trees of successor-cardinal height. We define the diagonal union of subsets of a tree, as well as normal ideals on a tree, and we characterize arbitrary subsets of a non-special tree as being either stationary or non-stationary. We then use this theory to prove the following partition relation for trees: Main Theorem. Let \({\kappa}\) be any infinite regular cardinal, let ξ be any ordinal such that \({2^{|\xi|} < \kappa}\) , and let k be any natural number. Then $$non-(2^{<\kappa})-special\, tree \rightarrow (\kappa + \xi)^{2}_k.$$ This is a generalization to trees of the Balanced Baumgartner–Hajnal–Todorcevic Theorem, which we recover by applying the above to the cardinal \({(2^{< \kappa})^{+}}\) , the simplest example of a non- \({(2^{< \kappa})}\) -special tree. As a corollary, we obtain a general result for partially ordered sets: Theorem. Let \({\kappa}\) be any infinite regular cardinal, let ξ be any ordinal such that \({2^{|\xi|} < \kappa}\) , and let k be any natural number. Let P be a partially ordered set such that \({P \rightarrow (2^{< \kappa})^{1}_{2^{< \kappa}} }\) . Then $$P \rightarrow (\kappa + \xi)^{2}_{k}.$$      

Doeblin's and Harris' theory of Markov processes

Our notation and definitions are taken from (Chung, K. L.: The general theory of Markov processes according to Doeblin. Z. Wahrscheinlichkeitstheorie und verw. Gebiete 2, 230–254 (1964)). A closed set H is called recurrent in the sense of Harris if there exists a σ-finite measure ? such that for E=H, ?(E) >0 implies Q(x, E)=1 for all tx?H. Theorem 1. Let X be absolutely essential and indecomposable. Then there exists a closed set B?X. such that B contains no acountable disjoint collection of perpetuable sets if and only if X=H+1 where H is recurrent in the sense of Harris and I is either inessential or improperly essential. Theorem 2. If there exists no uncountable disjoint collection of closed sets, then there exists a countable disjoint collection {D_n} _n=1 ^∞ of absolutely essential and indecomposable closed sets such that \(I = X - \sum\nolimits_{n = 1}^\infty {D_n } \) . Under the additional assumption that Suslin's Conjecture holds, Theorem 2 was proved by Jamison (Jamison, B.: A Result in Doeblin's Theory of Markov Chains implied by Suslin's Conjecture. Z. Wahrscheinlichkeitstheorie verw. Gebiete 24, 287–293 (1972)).     

Another proof of a result of Jech and Shelah

Shelah’s pcf theory describes a certain structure which must exist if ${\aleph _\omega }$ is strong limit and $2^{\aleph _\omega } > \aleph _{\omega 1} $ holds. Jech and Shelah proved the surprising result that this structure exists in ZFC. They first give a forcing extension in which the structure exists then argue that by some absoluteness results it must exist anyway. We reformulate the statement to the existence of a certain partially ordered set, and then we show by a straightforward, elementary (i.e., non-metamathematical) argument that such partially ordered sets exist.     

Multifractal analysis of the divergence of Fourier series: The extreme cases

We study the size, in terms of the Hausdorff dimension, of the subsets of T such that the Fourier series of a generic function in L ¹(T), L ^p (T), or C(T) may behave badly. Genericity is related to the Baire Category Theorem or the notion of prevalence. This paper is a continuation of [3].     

Cores,cutsets and the fixed point property

The purpose of this paper is the analysis and application of the concepts of a core (a pair of chains) and cutset in the fixed point theory for posets. The main results are:

1. (Theorem 3) If P is chain-complete and (*), it contains a cutset S such that every nonempty subset of S has a join or a meet in P, then P has the fixed point property (FPP),
2. (Theorem 5) If P or Q is chain-complete, Q satisfies (*) and both P and Q have the FPP, then P x Q has the FPP.
3. (Theorem 6) Let P or Q be chain-complete and there exist p∈P and a finite sequence f ₁, f ₂, ..., f _n of order-preserving mappings of P into P such that $$\left( {\forall x\varepsilon P} \right)x \leqslant f_1 \left( x \right) \geqslant f_2 \left( x \right) \leqslant \cdots \geqslant f_n \left( x \right) \leqslant p$$ If P and Q have the FPP then P x Q has the FPP.
4. (Theorem 7) If T is an ordered set with the FPP and {P _t :t∈T} is a disjoint family of ordered sets with the FPP then its ordered sum ∪{P _t :t∈T} has the FPP.

     

Directional Lipschitzness of Minimal Time Functions in Hausdorff Topological Vector Spaces

In a general Hausdorff topological vector space E, we associate to a given nonempty closed set S???E and a bounded closed set Ω???E, the minimal time function T _S,Ω defined by $T_{S,\Omega}(x):= \inf \{ t> 0: S\cap (x+t\Omega)\not = \emptyset\}$ . The study of this function has been the subject of various recent works (see Bounkhel (2012, submitted, 2013, accepted); Colombo and Wolenski (J Global Optim 28:269–282, 2004, J Convex Anal 11:335–361, 2004); He and Ng (J Math Anal Appl 321:896–910, 2006); Jiang and He (J Math Anal Appl 358:410–418, 2009); Mordukhovich and Nam (J Global Optim 46(4):615–633, 2010) and the references therein). The main objective of this work is in this vein. We characterize, for a given Ω, the class of all closed sets S in E for which T _S,Ω is directionally Lipschitz in the sense of Rockafellar (Proc Lond Math Soc 39:331–355, 1979). Those sets S are called Ω-epi-Lipschitz. This class of sets covers three important classes of sets: epi-Lipschitz sets introduced in Rockafellar (Proc Lond Math Soc 39:331–355, 1979), compactly epi-Lipschitz sets introduced in Borwein and Strojwas (Part I: Theory, Canad J Math No. 2:431–452, 1986), and K-directional Lipschitz sets introduced recently in Correa et al. (SIAM J Optim 20(4):1766–1785, 2010). Various characterizations of this class have been established. In particular, we characterize the Ω-epi-Lipschitz sets by the nonemptiness of a new tangent cone, called Ω-hypertangent cone. As for epi-Lipschitz sets in Rockafellar (Canad J Math 39:257–280, 1980) we characterize the new class of Ω-epi-Lipschitz sets with the help of other cones. The spacial case of closed convex sets is also studied. Our main results extend various existing results proved in Borwein et al. (J Convex Anal 7:375–393, 2000), Correa et al. (SIAM J Optim 20(4):1766–1785, 2010) from Banach spaces and normed spaces to Hausdorff topological vector spaces.     

On Two Equivalent Dilation Theorems in VH-Spaces

We prove that a generalized version, essentially obtained by R.M. Loynes, of the B. Sz.-Nagy??s Dilation Theorem for ${\mathcal{B}^*(\mathcal{H})}$ -valued (here ${\mathcal{H}}$ is a VH-space in the sense of Loynes) positive semidefinite maps on *-semigroups is equivalent with a generalized version of the W.F. Stinespring??s Dilation Theorem for ${\mathcal{B}^*(\mathcal{H})}$ -valued completely positive linear maps on B ^*-algebras. This equivalence result is a generalization of a theorem of F.H. Szafraniec, originally proved for the case of operator valued maps (that is, when ${\mathcal{H}}$ is a Hilbert space).     

Smooth Stable Planes

This paper deals with smooth stable planes which generalize the notion of differentiable (affine or projective) planes [7]. It is intended to be the first one of a series of papers on smooth incidence geometry based on the Habilitationsschrift of the author. It contains the basic definitions and results which are needed to build up a foundation for a systematic study of smooth planes. We define smooth stable planes, and we prove that point rows and line pencils are closed submanifolds of the point set and line set, respectively (Theorem (1.6)). Moreover, the flag space is a closed submanifold of the product manifold $P\times {\cal L}$ (Theorem (1.14)), and the smooth structure on the set P of points and on the set ${\cal L}$ of lines is uniquely determined by the smooth structure of one single line pencil. In the second section it is shown that for any point p \te P the tangent space T_pP carries the structure of a locally compact affine translation plane ${\cal A}_p$ , see Theorem (2.5). Dually, we prove in Section 3 that for any line $L \in {\cal L}$ the tangent space ${\rm T}_L{\cal L}$ together with the set ${\cal \rm S}_L=\lbrace {\rm T}_{L}{\cal L}_p\mid p \in L\rbrace$ gives rise to some shear plane. It turned out that the translation planes ${\cal A}_p$ are one of the most important tools in the investigation of smooth incidence geometries. The linearization theorems (3.9), (3.11), and (4.4) can be viewed as the main results of this paper. In the closing section we investigate some homogeneity properties of smooth projective planes.     

On the sharpness of Bruen’s bound for intersection sets in Desarguesian affine spaces

In this note we investigate the sharpness of Bruen’s bound on the size of a t-fold blocking set in \(AG(n,q)\) with respect to the hyperplanes. We give a construction for t-fold blocking sets meeting Bruen’s bound with \(t=q-n+2\) . This construction is used further to find the minimal size of a t-fold affine blocking set with \(t=q-n+1\) . We prove that for blocking sets in the geometries \(AG(n,2)\) the difference between the size of an optimal t-fold blocking set and tn exceeds any given number. In particular, we deviate infinitely from Bruen’s bound as n goes to infinity. We conclude with a construction that gives t-fold blocking sets with \(t=q-n+3\) whose size is close to the lower bounds known so far.     

Interpolation with lagrange polynomials a simple proof of Markov inequality and some of its generalizations

The following theorem is provedTheorem 1.Let q be a polynomial of degree n(qP_n)with n distinct zeroes lying inthe interval[-1,1] and△'_q={-1}∪{τ_i:q'(τ_i)=0,i=1,n-1}∪{1}.If polynomial pP_n satisfies the inequalitythen for each k=1,n and any x[-1,1]its k-th derivative satisfies the inequality丨p~(k)(x)丨≤max{丨q~((k))(x)丨,丨1/k(x~2-1)q~(k+1)(x)+xq~((k))(x)丨}.This estimate leads to the Markov inequality for the higher order derivatives ofpolynomials if we set q=T_n,where Tn is Chebyshev polynomial least deviated from zero.Some other results are established which gives evidence to the conjecture that under theconditions of Theorem 1 the inequality ‖p~((k))‖≤‖q~(k)‖holds.     

Forbidden Triples Containing a Complete Graph and a Complete Bipartite Graph of Small Order

For a graph G and a set \({\mathcal{F}}\) of connected graphs, G is said be \({\mathcal{F}}\) -free if G does not contain any member of \({\mathcal{F}}\) as an induced subgraph. We let \({\mathcal{G} _{3}(\mathcal{F})}\) denote the set of all 3-connected \({\mathcal{F}}\) -free graphs. This paper is concerned with sets \({\mathcal{F}}\) of connected graphs such that \({\mathcal{F}}\) contains no star, \({|\mathcal{F}|=3}\) and \({\mathcal{G}_{3}(\mathcal{F})}\) is finite. Among other results, we show that for a connected graph T( ≠ K ₁) which is not a star, \({\mathcal{G}_{3}(\{K_{4},K_{2,2},T\})}\) is finite if and only if T is a path of order at most 6.     

Immunity properties and strong positive reducibilities

We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has ${\overline{K}\not\le_{\rm ss} B}$ (respectively, ${\overline{K}\not\le_{\overline{\rm s}} B}$ ): here ${\le_{\overline{\rm s}}}$ is the finite-branch version of s-reducibility, ??_ss is the computably bounded version of ${\le_{\overline{\rm s}}}$ , and ${\overline{K}}$ is the complement of the halting set. Restriction to ${\Sigma^0_2}$ sets provides a similar characterization of the ${\Sigma^0_2}$ hyperhyperimmune sets in terms of s-reducibility. We also show that no ${A \geq_{\overline{\rm s}}\overline{K}}$ is hyperhyperimmune. As a consequence, ${\deg_{\rm s}(\overline{K})}$ is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed.     

Necessary and sufficient conditions for the validity of Jensen’s inequality

We consider the d-dimensional Jensen inequality $$ T[\varphi(f_1, \dots, f_d)]\, \ge \, \varphi(T[f_1], \dots, T[f_d])\quad\quad(\ast)$$ T [ φ ( f 1 , … , f d ) ] ≥ φ ( T [ f 1 ] , … , T [ f d ] ) ( * ) as it was established by McShane in 1937r. Here T is a functional, φ is a convex function defined on a closed convex set ${K\subset \mathbb{R}^d}$ K ? R d , and f ₁, . . . , f _d are from some linear space of functions. Our aim is to find necessary and sufficient conditions for the validity of (*). In particular, we show that if we exclude three types of convex sets K, then Jensen’s inequality holds for a sublinear functional T if and only if T is linear, positive, and satisfies T[1] = 1. Furthermore, for each of the excluded types of convex sets, we present nonlinear, sublinear functionals T for which Jensen’s inequality holds. Thus the conditions on K are optimal. Our contributions generalize or complete several known results.     

The ∀∃-theory of the effectively closed Medvedev degrees is decidable

We show that there is a computable procedure which, given an ??-sentence ${\varphi}$ in the language of the partially ordered sets with a top element 1 and a bottom element 0, computes whether ${\varphi}$ is true in the Medvedev degrees of ${\Pi^0_1}$ classes in Cantor space, sometimes denoted by ${\mathcal{P}_s}$ .     

Laplacian Spectral Radius and Maximum Degree of Trees with Perfect Matchings

Let μ(T) and Δ(T) denote the Laplacian spectral radius and the maximum degree of a tree T, respectively. Denote by ${\mathcal{T}_{2m}}$ the set of trees with perfect matchings on 2m vertices. In this paper, we show that for any ${T_1, T_2\in\mathcal{T}_{2m}}$ , if Δ(T ₁) > Δ(T ₂) and ${\Delta(T_1)\geq \lceil\frac{m}{2}\rceil+2}$ , then μ(T ₁) > μ(T ₂). By using this result, the first 20th largest trees in ${\mathcal{T}_{2m}}$ according to their Laplacian spectral radius are ordered. We also characterize the tree which alone minimizes (resp., maximizes) the Laplacian spectral radius among all the trees in ${\mathcal{T}_{2m}}$ with an arbitrary fixed maximum degree c (resp., when ${c \geq \lceil\frac{m}{2}\rceil + 1}$ ).     

Convex equipartitions: the spicy chicken theorem

We show that, for any prime power $n$ and any convex body $K$ (i.e., a compact convex set with interior) in $\mathbb{R }^d$ , there exists a partition of $K$ into $n$ convex sets with equal volumes and equal surface areas. Similar results regarding equipartitions with respect to continuous functionals and absolutely continuous measures on convex bodies are also proven. These include a generalization of the ham-sandwich theorem to arbitrary number of convex pieces confirming a conjecture of Kaneko and Kano, a similar generalization of perfect partitions of a cake and its icing, and a generalization of the Gromov–Borsuk–Ulam theorem for convex sets in the model spaces of constant curvature.     

An example related to Gregory’s Theorem

In this paper, we give an example of a complete computable infinitary theory T with countable models ${\mathcal{M}}$ and ${\mathcal{N}}$ , where ${\mathcal{N}}$ is a proper computable infinitary extension of ${\mathcal{M}}$ and T has no uncountable model. In fact, ${\mathcal{M}}$ and ${\mathcal{N}}$ are (up to isomorphism) the only models of T. Moreover, for all computable ordinals α, the computable ${\Sigma_\alpha}$ part of T is hyperarithmetical. It follows from a theorem of Gregory (JSL 38:460–470, 1972; Not Am Math Soc 17:967–968, 1970) that if T is a Π ₁ ¹ set of computable infinitary sentences and T has a pair of models ${\mathcal{M}}$ and ${\mathcal{N}}$ , where ${\mathcal{N}}$ is a proper computable infinitary extension of ${\mathcal{M}}$ , then T would have an uncountable model.     

Antimatroids and Balanced Pairs

We generalize the $\frac{1}{3}$ – $\frac{2}{3}$ conjecture from partially ordered sets to antimatroids: we conjecture that any antimatroid has a pair of elements x,y such that x has probability between $\frac{1}{3}$ and $\frac{2}{3}$ of appearing earlier than y in a uniformly random basic word of the antimatroid. We prove the conjecture for antimatroids of convex dimension two (the antimatroid-theoretic analogue of partial orders of width two), for antimatroids of height two, for antimatroids with an independent element, and for the perfect elimination antimatroids and node search antimatroids of several classes of graphs. A computer search shows that the conjecture is true for all antimatroids with at most six elements.     

Martin representation and Relative Fatou Theorem for fractional Laplacian with a gradient perturbation

Let $L=\Delta ^{\alpha /2}+ b\cdot \nabla $ with $\alpha \in (1,2)$ . We prove the Martin representation and the Relative Fatou Theorem for non-negative singular L-harmonic functions on $\mathcal{C }^{1,1}$ bounded open sets.