Projective mad families

Using almost disjoint coding we prove the consistency of the existence of a definable ω-mad family of infinite subsets of ω (resp. functions from ω to ω) together with b=2^ω=ω₂.     

Club-guessing, stationary reflection, and coloring theorems

We obtain very strong coloring theorems at successors of singular cardinals from failures of certain instances of simultaneous reflection of stationary sets. In particular, the simplest of our results establishes that if μ is singular and , then there is a regular cardinal θ<μ such that any fewer than cf(μ) stationary subsets of must reflect simultaneously.     

Generic embeddings associated to an indestructibly weakly compact cardinal

I use generic embeddings induced by generic normal measures on P_κ(λ) that can be forced to exist if κ is an indestructibly weakly compact cardinal. These embeddings can be applied in order to obtain the forcing axioms in forcing extensions. This has consequences in : The Singular Cardinal Hypothesis holds above κ, and κ has a useful Jónsson-like property. This in turn implies that the countable tower Q_<κ works much like it does when κ is a Woodin limit of Woodin cardinals. One consequence is that every set of reals in the Chang model is Lebesgue measurable and has the Baire Property, the Perfect Set Property and the Ramsey Property. So indestructible weak compactness has effects on cardinal arithmetic high up and also on the structure of sets of real numbers, down low, similar to supercompactness.     

A quadratic Bolza-type problem in a Riemannian manifold

A classical nonlinear equation on a complete Riemannian manifold is considered. The existence of solutions connecting any two points is studied, i.e., for T>0 the critical points of the functional with x(0)=x₀,x(T)=x₁. When the potential V has a subquadratic growth with respect to x, J_T admits a minimum critical point for any T>0 (infinitely many critical points if the topology of is not trivial). When V has an at most quadratic growth, i.e., , this property does not hold, but an optimal arrival time T(λ)>0 exists such that, if 0<T<T(λ), any pair of points in can be joined by a critical point of the corresponding functional. For the existence and multiplicity results, variational methods and Ljusternik-Schnirelman theory are used. The optimal value is fulfilled by the harmonic oscillator. These ideas work for other related problems.     

A non-implication between fragments of Martin’s Axiom related to a property which comes from Aronszajn trees

We introduce a property of forcing notions, called the anti-, which comes from Aronszajn trees. This property canonically defines a new chain condition stronger than the countable chain condition, which is called the property .In this paper, we investigate the property . For example, we show that a forcing notion with the property does not add random reals. We prove that it is consistent that every forcing notion with the property has precaliber ℵ₁ and for forcing notions with the property fails. This negatively answers a part of one of the classical problems about implications between fragments of .     

Elementary differences between the degrees of unsolvability and degrees of compressibility

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies (2005) [14] and denoted by A≤_LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes induced by ≤_LK are called LK degrees (or degrees of compressibility) and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies (2005) [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity.We show that with respect to ≤_LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications.     

Some relations between rank of a graph and its complement

Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that .     

The Chase radical and reduced products

Let κ be a regular uncountable cardinal. We shall give a criterion for certain reduced products of torsion-free abelian groups to be ℵ₁-free. As an application we shall show that the norm of the Chase radical is ℵ₁ in ZFC, a result which was previously known only under the assumption of the continuum hypothesis 2^ℵ₀=ℵ₁.     

Malliavin calculus in abstract Wiener space using infinitesimals

Using infinitesimals, we develop Malliavin calculus on spaces which result from the classical Wiener space by replacing with any abstract Wiener space .We start from a Brownian motion b on a Loeb probability space Ω with values in the Banach space is the standard part of a ∗finite-dimensional Brownian motion B. Then we define iterated Itô integrals as standard parts of internal iterated Itô integrals. The integrator of the internal integrals is B and the values of the integrands are multilinear forms on , where is a ∗finite-dimensional linear space over between the Hilbert space and its ∗-extension .In the first part we prove a chaos decomposition theorem for L²-functionals on Ω that are measurable with respect to the σ-algebra generated by b. This result yields a chaos decomposition of L²-functionals with respect to the Wiener measure on the standard space of -valued continuous functions on [0,1]. In the second part we define the Malliavin derivative and the Skorohod integral as standard parts of internal operators defined on ∗finite-dimensional spaces. In an application we use the transformation rule for finite-dimensional Euclidean spaces to study time anticipating and non-anticipating shifts of Brownian motion by Bochner integrals (Girsanov transformations).     

A minimal classical sequent calculus free of structural rules

Gentzen’s classical sequent calculus has explicit structural rules for contraction and weakening. They can be absorbed (in a right-sided formulation) by replacing the axiom P,¬P by Γ,P,¬P for any context Γ, and replacing the original disjunction rule with Γ,A,B implies Γ,A∨B.This paper presents a classical sequent calculus which is also free of contraction and weakening, but more symmetrically: both contraction and weakening are absorbed into conjunction, leaving the axiom rule intact. It uses a blended conjunction rule, combining the standard context-sharing and context-splitting rules: Γ,Δ,A and Γ,Σ,B implies Γ,Δ,Σ,A∧B. We refer to this system as minimal sequent calculus.We prove a minimality theorem for the propositional fragment : any propositional sequent calculus S (within a standard class of right-sided calculi) is complete if and only ifS contains (that is, each rule of is derivable in S). Thus one can view as a minimal complete core of Gentzen’s .     

The double negation of the intermediate value theorem

In the context of intuitionistic analysis, we consider the set F consisting of all continuous functions ? from [0,1] to R such that ?(0)=0 and ?(1)=1, and the set I₀ consisting of ?’s in F where there exists x∈[0,1] such that . It is well-known that there are weak counterexamples to the intermediate value theorem, and with Brouwer’s continuity principle we have I₀≠F. However, there exists no satisfying answer to . We try to answer to this question by reducing it to a schema (which we call ) about intuitionistic decidability that asserts “there exists an intuitionistically enumerable set that is not intuitionistically decidable”. We also introduce the notion of strong Specker double sequence, and prove that the existence of such a double sequence is equivalent to the existence of a function ?∈F_mon where .     

Completeness for flat modal fixpoint logics

This paper exhibits a general and uniform method to prove axiomatic completeness for certain modal fixpoint logics. Given a set Γ of modal formulas of the form γ(x,p₁,…,p_n), where x occurs only positively in γ, we obtain the flat modal fixpoint language L_?(Γ) by adding to the language of polymodal logic a connective ?_γ for each γ∈Γ. The term ?_γ(φ₁,…,φ_n) is meant to be interpreted as the least fixed point of the functional interpretation of the term γ(x,φ₁,…,φ_n). We consider the following problem: given Γ, construct an axiom system which is sound and complete with respect to the concrete interpretation of the language L_?(Γ) on Kripke structures. We prove two results that solve this problem.First, let be the logic obtained from the basic polymodal by adding a Kozen-Park style fixpoint axiom and a least fixpoint rule, for each fixpoint connective ?_γ. Provided that each indexing formula γ satisfies a certain syntactic criterion, we prove this axiom system to be complete.Second, addressing the general case, we prove the soundness and completeness of an extension of . This extension is obtained via an effective procedure that, given an indexing formula γ as input, returns a finite set of axioms and derivation rules for ?_γ, of size bounded by the length of γ. Thus the axiom system is finite whenever Γ is finite.