CZF does not have the existence property

Constructive theories usually have interesting metamathematical properties where explicit witnesses can be extracted from proofs of existential sentences. For relational theories, probably the most natural of these is the existence property, EP, sometimes referred to as the set existence property  . This states that whenever (∃x)?(x)$(\exists x)?(x)$ is provable, there is a formula χ(x)$\chi (x)$ such that (∃!x)?(x)∧χ(x)$(\exists !x)?(x)\wedge \chi (x)$ is provable. It has been known since the 80s that EP holds for some intuitionistic set theories and yet fails for IZF. Despite this, it has remained open until now whether EP holds for the most well known constructive set theory, CZF. In this paper we show that EP fails for CZF.     

Consistency,optimality, and incompleteness

Assume that the problem _P0$P_0$ is not solvable in polynomial time. Let T   be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T∪{_ConT}$T\cup \{{\mathit{Con}}_T\}$ as the minimal extension of T   proving for some algorithm that it decides _P0$P_0$ as fast as any algorithm B$\mathbb{B}$ with the property that T   proves that B$\mathbb{B}$ decides _P0$P_0$. Here, _ConT${\mathit{Con}}_T$ claims the consistency of T. As a byproduct, we obtain a version of Gödel?s Second Incompleteness Theorem. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories.     

The inverse inertia problem for the complements of partial k-trees

Let F$\mathbb{F}$ be an infinite field with characteristic not equal to two. For a graph G=(V,E)$G=(V,E)$ with V={1,…,n}$V=\{1,\dots ,n\}$, let S(G;F)$S(G;\mathbb{F})$ be the set of all symmetric n×n$n\times n$ matrices A=[_ai,j]$A=[a_{i,j}]$ over F$\mathbb{F}$ with _ai,j≠0$a_{i,j}\ne 0$, i≠j$i\ne j$ if and only if ij∈E$ij\in E$. We show that if G is the complement of a partial k  -tree and m?k+2$m?k+2$, then for all nonsingular symmetric m×m$m\times m$ matrices K   over F$\mathbb{F}$, there exists an m×n$m\times n$ matrix U   such that U^TKU∈S(G;F)$U^{T}KU\in S(G;\mathbb{F})$. As a corollary we obtain that, if k+2?m?n$k+2?m?n$ and G is the complement of a partial k-tree, then for any two nonnegative integers p and q   with p+q=m$p+q=m$, there exists a matrix in S(G;R)$S(G;\mathbb{R})$ with p positive and q negative eigenvalues.     

Dimension spectra of random subfractals of self-similar fractals

The dimension of a point x   in Euclidean space (meaning the constructive Hausdorff dimension of the singleton set {x}$\{x\}$) is the algorithmic information density of x  . Roughly speaking, this is the least real number dim(x)$\dim (x)$ such that r×dim(x)$r\times \dim (x)$ bits suffice to specify x   on a general-purpose computer with arbitrarily high precision 2^−r$2^{-r}$. The dimension spectrum of a set X   in Euclidean space is the subset of [0,n]$[0,n]$ consisting of the dimensions of all points in X.     

Certain strict topologies on the space of regular Borel measures on locally compact groups

Let G   denote a locally compact Hausdorff group and M(G)$M(G)$ be the space of all bounded complex-valued regular Borel measures on G  . In this paper, we define two strict topologies on M(G)$M(G)$ and study various properties of these topologies such as metrizability, barrelledness and completeness. We also determine the dual space of M(G)$M(G)$ and consider various continuity properties for the convolution product on M(G)$M(G)$ under these topologies.     

On the nonexistence of a relation between σ-left-porosity and σ-right-porosity

Given an arbitrarily weak notion of left-〈f〉$〈f〉$-porosity and an arbitrarily strong notion of right-〈g〉$〈g〉$-porosity, we construct an example of closed subset of R$\mathbb{R}$ which is not σ  -left-〈f〉$〈f〉$-porous and is right-〈g〉$〈g〉$-porous. We also briefly summarize the relations between three different definitions of porosity controlled by a function; we then observe that our construction gives the example for any combination of these definitions of left-porosity and right-porosity.     

On the conjugacy classes in the orthogonal and symplectic groups over algebraically closed fields

Let F$\mathbb{F}$ be an algebraically closed field. Let V$\mathbb{V}$ be a vector space equipped with a non-degenerate symmetric or symplectic bilinear form B   over F$\mathbb{F}$. Suppose the characteristic of F$\mathbb{F}$ is sufficiently large  , i.e. either zero or greater than the dimension of V$\mathbb{V}$. Let I(V,B)$I(\mathbb{V},\mathbb{B})$ denote the group of isometries. Using the Jacobson–Morozov lemma we give a new and simple proof of the fact that two elements in I(V,B)$I(\mathbb{V},\mathbb{B})$ are conjugate if and only if they have the same elementary divisors.     

Relativization makes contradictions harder for Resolution

We provide a number of simplified and improved separations between pairs of Resolution-with-bounded-conjunction refutation systems, Res(d)$\mathrm{Res}(d)$, as well as their tree-like versions, Res^?(d)${\mathrm{Res}}^{?}(d)$. The contradictions we use are natural combinatorial principles: the Least number principle  , _LNPn${\mathrm{LNP}}_n$ and an ordered variant thereof, the Induction principle  , _IPn${\mathrm{IP}}_n$.     

Diagonals and numerical ranges of direct sums of matrices

For any n-by-n matrix A  , we consider the maximum number k=k(A)$k=k(A)$ for which there is a k-by-k compression of A   with all its diagonal entries in the boundary ∂W(A)$\partial W(A)$ of the numerical range W(A)$W(A)$ of A. If A   is a normal or a quadratic matrix, then the exact value of k(A)$k(A)$ can be computed. For a matrix A   of the form B⊕C$B\oplus C$, we show that k(A)=2$k(A)=2$ if and only if the numerical range of one summand, say, B is contained in the interior of the numerical range of the other summand C   and k(C)=2$k(C)=2$. For an irreducible matrix A  , we can determine exactly when the value of k(A)$k(A)$ equals the size of A  . These are then applied to determine k(A)$k(A)$ for a reducible matrix A   of size 4 in terms of the shape of W(A)$W(A)$.     

Regularity of Hölder continuous solutions of the supercritical quasi-geostrophic equation

We present a regularity result for weak solutions of the 2D quasi-geostrophic equation with supercritical (α<1/2$\alpha <1/2$) dissipation α(−Δ)${(-\mathrm{\Delta })}^{\alpha }$: If a Leray–Hopf weak solution is Hölder continuous θ∈Cδ(R²)$\theta \in C^{\delta }({\mathbb{R}}^2)$ with δ>1−2α$\delta >1-2\alpha$ on the time interval [t₀,t]$[t_0,t]$, then it is actually a classical solution on (t₀,t]$(t_0,t]$.     

The topological structure of fuzzy sets with sendograph metric

For a non-degenerate convex subset Y of the n  -dimensional Euclidean space Rⁿ${\mathbb{R}}^n$, let F(Y)$\mathbb{F}(Y)$ be the family of all fuzzy sets of Rⁿ${\mathbb{R}}^n$ which are upper semicontinuous, fuzzy convex and normal with compact supports contained in Y  . We show that the space F(Y)$\mathbb{F}(Y)$ with the topology of sendograph metric is homeomorphic to the separable Hilbert space ?²${?}^2$ if Y   is compact; and the space F(Rⁿ)$\mathbb{F}({\mathbb{R}}^n)$ is also homeomorphic to ?²${?}^2$.     

A converse of Loewner–Heinz inequality and applications to operator means

Let f(t)$f(t)$ be an operator monotone function. Then A?B$A?B$ implies f(A)?f(B)$f(A)?f(B)$, but the converse implication is not true. Let A?B$A?B$ be the geometric mean of A,B?0$A,B?0$. If A?B$A?B$, then B⁻¹?A?I$B^{-1}?A?I$; the converse implication is not true either. We will show that if f(λB+I)⁻¹?f(λA+I)?I$f{(\lambda B+I)}^{-1}?f(\lambda A+I)?I$ for all sufficiently small λ>0$\lambda >0$, then f(λA+I)?f(λB+I)$f(\lambda A+I)?f(\lambda B+I)$ and A?B$A?B$. Moreover, we extend it to multi-variable matrices means.