Topological completeness of the provability logic GLP

Provability logic GLP is well-known to be incomplete w.r.t. Kripke semantics. A natural topological semantics of GLP interprets modalities as derivative operators of a polytopological space. Such spaces are called GLP-spaces whenever they satisfy all the axioms of GLP. We develop some constructions to build nontrivial GLP-spaces and show that GLP is complete w.r.t. the class of all GLP-spaces.     

Canonical subbase-compactness of topological products

For topological products the concept of canonical subbase-compactness is introduced, and the question analyzed under what conditions such products are canonically subbase-compact in ZF-set theory.Results: (1) Products of finite spaces are canonically subbase-compact iff AC(fin), the axiom of choice for finite sets, holds.(2) Products of n-element spaces are canonically subbase-compact iff AC(<n), the axiom of choice for sets with less than n elements, holds.(3) Products of compact spaces are canonically subbase-compact iff AC, the axiom of choice, holds.(4) All powers XI of a compact space X are canonically subbase compact iff X is a Loeb-space.These results imply that in ZF the implications

     

The oscillation stability problem for the Urysohn sphere: A combinatorial approach

We study the oscillation stability problem for the Urysohn sphere, an analog of the distortion problem for ?₂ in the context of the Urysohn space U. In particular, we show that this problem reduces to a purely combinatorial problem involving a family of countable ultrahomogeneous metric spaces with finitely many distances.     

Invariance properties of a triple matrix product involving generalized inverses

Given complex-valued matrices A, B and C of appropriate dimensions, this paper investigates certain invariance properties of the product AXC with respect to the choice of X, where X is a generalized inverse of B. Different types of generalized inverses are taken into account. The purpose of the paper is three-fold: First, to review known results scattered in the literature, second, to demonstrate the connection between invariance properties and the concept of extremal ranks of matrices, and third, to add new results related to the topic.     

On extensions of countable filterbases to ultrafilters and ultrafilter compactness

We show in the Zermelo-Fraenkel set theory ZF without the axiom of choice:

1. Given an infinite set X, the Stone space S(X) is ultrafilter compact.

2. For every infinite set X, every countable filterbase of X extends to an ultra-filter i? for every infinite set X, S(X) is countably compact.

3. ω has a free ultrafilter i? every countable, ultrafilter compact space is countably compact.

   We also show the following:

4. There are a permutation model 𝒩 and a set X ∈ 𝒩 such that X has no free ultrafilters and S(X) is not compact but S(X) is countably compact and every countable filterbase of X extends to an ultrafilter.

5. It is relatively consistent with ZF that every countable filterbase of ω extends to an ultrafilter but there exists a countable filterbase of ? which does not extend to an ultrafilter. Hence, it is relatively consistent with ZF that ? has free ultrafilters but there exists a countable filterbase of ? which does not extend to an ultrafilter.

     

Countable partition ordinals

The structure of ordinals of the form ω^ωβ for countable β is studied. The main result is:

Theorem 1. Ifβ<ω₁is the sum of one or two indecomposable ordinals, then

ω^ωβ→(ω^ωβ,3)².     

A homeomorphism between strong measure zero sets whose graph is not of strong measure zero

Assuming Martin's axiom MA, we define a homeomorphism between two strong measure zero sets in the real line whose graph in not of strong measure zero in the plane. Using Michael's concentrated sets, we give also some refinements of this result, and we describe some singular subgroups of the group ZN.     

The γ-borel conjecture

In this paper we prove that it is consistent that every -set is countable while not every strong measure zero set is countable. We also show that it is consistent that every strong -set is countable while not every -set is countable. On the other hand we show that every strong measure zero set is countable iff every set with the Rothberger property is countable.Thanks to Boise State University for support during the time this paper was written and to Alan Dow for some helpful discussions and to Boaz Tsaban for some suggestions to improve an earlier version.     

Polynomials satisfied by two linked matrices

Polynomials in two variables, evaluated at A and with A being a square complex matrix and being its transform belonging to the set {A⁼, A^†, A^∗}, in which A⁼, A^†, and A^∗ denote, respectively, any reflexive generalized inverse, the Moore-Penrose inverse, and the conjugate transpose of A, are considered. An essential role, in characterizing when such polynomials are satisfied by two matrices linked as above, is played by the condition that the column space of A is the column space of . The results given unify a number of prior, isolated results.     

Some explicit solutions of the additive Deligne-Simpson problem and their applications

In this paper we construct three infinite series and two extra triples (E₈ and ) of complex matrices B, C, and A=B+C of special spectral types associated to Simpson's classification in Amer. Math. Soc. Proc. 1 (1992) 157 and Magyar et al. classification in Adv. Math. 141 (1999) 97. This enables us to construct Fuchsian systems of differential equations which generalize the hypergeometric equation of Gauss-Riemann. In a sense, they are the closest relatives of the famous equation, because their triples of spectral flags have finitely many orbits for the diagonal action of the general linear group in the space of solutions. In all the cases except for E₈, we also explicitly construct scalar products such that A, B, and C are self-adjoint with respect to them. In the context of Fuchsian systems, these scalar products become monodromy invariant complex symmetric bilinear forms in the spaces of solutions.When the eigenvalues of A, B, and C are real, the matrices and the scalar products become real as well. We find inequalities on the eigenvalues of A, B, and C which make the scalar products positive-definite.As proved by Klyachko, spectra of three hermitian (or real symmetric) matrices B, C, and A=B+C form a polyhedral convex cone in the space of triple spectra. He also gave a recursive algorithm to generate inequalities describing the cone. The inequalities we obtain describe non-recursively some faces of the Klyachko cone.     

Exponentially closed fields and the conjecture on intersections with tori

We give an axiomatization of the class ECF of exponentially closed fields, which includes the pseudo-exponential fields previously introduced by the second author, and show that it is superstable over its interpretation of arithmetic. Furthermore, ECF is exactly the elementary class of the pseudo-exponential fields if and only if the Diophantine conjecture CIT on atypical intersections of tori with subvarieties is true.     

Glivenko theorems revisited

Glivenko-type theorems for substructural logics (over FL) are comprehensively studied in the paper [N. Galatos, H. Ono, Glivenko theorems for substructural logics over FL, Journal of Symbolic Logic 71 (2006) 1353-1384]. Arguments used there are fully algebraic, and based on the fact that all substructural logics are algebraizable (see [N. Galatos, H. Ono, Algebraization, parametrized local deduction theorem and interpolation for substructural logics over FL, Studia Logica 83 (2006) 279-308] and also [N. Galatos, P. Jipsen, T. Kowalski, H. Ono, Residuated Lattices: An Algebraic Glimpse at Substructural Logics, in: Studies in Logic and the Foundations of Mathematics, vol. 151, Elsevier, 2007] for the details).As a complementary work to the algebraic approach developed in [N. Galatos, H. Ono, Glivenko theorems for substructural logics over FL, Journal of Symbolic Logic 71 (2006) 1353-1384], we present here a concise, proof-theoretic approach to Glivenko theorems for substructural logics. This will show different features of these two approaches.     

Two local operators and the BLUE

For a given matrix A, a matrix P such that PA = A is said to be a local identity, and such that P²A = PA is said to be a local idempotent. In the paper, some simple properties of such operators are presented. Their relation to the best linear unbiased estimation in the general Gauss-Markov model is also demonstrated.     

On commutativity of projectors

The purpose of this paper is to revisit two problems discussed previously in the literature, both related to the commutativity property P₁P₂ = P₂P₁, where P₁ and P₂ denote projectors (i.e., idempotent matrices). The first problem was considered by Baksalary et al. [J.K. Baksalary, O.M. Baksalary, T. Szulc, A property of orthogonal projectors, Linear Algebra Appl. 354 (2002) 35-39], who have shown that if P₁ and P₂ are orthogonal projectors (i.e., Hermitian idempotent matrices), then in all nontrivial cases a product of any length having P₁ and P₂ as its factors occurring alternately is equal to another such product if and only if P₁ and P₂ commute. In the present paper a generalization of this result is proposed and validity of the equivalence between commutativity property and any equality involving two linear combinations of two any length products having orthogonal projectors P₁ and P₂ as their factors occurring alternately is investigated. The second problem discussed in this paper concerns specific generalized inverses of the sum P₁ + P₂ and the difference P₁ − P₂ of (not necessary orthogonal) commuting projectors P₁ and P₂. The results obtained supplement those provided in Section 4 of Baksalary and Baksalary [J.K. Baksalary, O.M. Baksalary, Commutativity of projectors, Linear Algebra Appl. 341 (2002) 129-142].     

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.     

Function spaces and one point extensions for the construct of metered spaces

The construct M of metered spaces and contractions is known to be a superconstruct in which all metrically generated constructs can be fully embedded. We show that M has one point extensions and that quotients in M are productive. We construct a Cartesian closed topological extension of M and characterize the canonical function spaces with underlying sets Hom(X,Y) for metered spaces X and Y. Finally we obtain an internal characterization of the objects in the Cartesian closed topological hull of M.     

On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them

A full-rank under-determined linear system of equations Ax = b has in general infinitely many possible solutions. In recent years there is a growing interest in the sparsest solution of this equation—the one with the fewest non-zero entries, measured by ∥x∥₀. Such solutions find applications in signal and image processing, where the topic is typically referred to as “sparse representation”. Considering the columns of A as atoms of a dictionary, it is assumed that a given signal b is a linear composition of few such atoms. Recent work established that if the desired solution x is sparse enough, uniqueness of such a result is guaranteed. Also, pursuit algorithms, approximation solvers for the above problem, are guaranteed to succeed in finding this solution.Armed with these recent results, the problem can be reversed, and formed as an implied matrix factorization problem: Given a set of vectors {b_i}, known to emerge from such sparse constructions, Ax_i = b_i, with sufficiently sparse representations x_i, we seek the matrix A. In this paper we present both theoretical and algorithmic studies of this problem. We establish the uniqueness of the dictionary A, depending on the quantity and nature of the set {b_i}, and the sparsity of {x_i}. We also describe a recently developed algorithm, the K-SVD, that practically find the matrix A, in a manner similar to the K-Means algorithm. Finally, we demonstrate this algorithm on several stylized applications in image processing.