Decidability in the Constructive Theory of Reals as an Ordered ℚ-vectorspace

We show that various fragments of the intuitionistic/constructive theory of the reals are decidable.     

EIN NEUER BEWEIS UND EINE VERSCHÄRFUNG FÜR DEN REDUKTIONSTYP ∀∃∀∞(0, 1) MIT EINER ANWENDUNG AUF DIE SPEKTRALE DARSTELLUNG VON PRÄDIKATEN

A simultaneous semantical and syntactical reduction is given for the satisfiability respectively finite satisfiability of first order formulas. We choose ???∞(0, 1) as conservative reduction class and allow only formulas out of ???∞(0, 1) having a simple set theoretical model if they are satisfiable at all. With the same method we get a spectral representation of any ?-ary enumerable respectively coenumerable predicate by a formula out of ???∞(?, 1).     

SO(∀∃*) Sentences and Their Asymptotic Probabilities

We prove a 0‐1 law for the fragment of second order logic SO(∀∃*) over parametric classes of finite structures which allow only one unary atomic type. This completes the investigation of 0‐1 laws for fragments of second order logic defined in terms of first order quantifier prefixes over, e.g., simple graphs and tournaments. We also prove a low oscillation law, and establish the 0‐1 law for Σ¹₄(∀∃*) without any restriction on the number of unary types.     

The complexity of plane hyperbolic incidence geometry is ∀∃∀∃

We show that plane hyperbolic geometry, expressed in terms of points and the ternary relation of collinearity alone, cannot be expressed by means of axioms of complexity at most ???, but that there is an axiom system, all of whose axioms are ???? sentences. This remains true for Klingenberg's generalized hyperbolic planes, with arbitrary ordered fields as coordinate fields. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Zarankiewicz problem in 3‐partite graphs

Let be a graph, be an integer, and write for the maximum number of edges in an ‐vertex graph that is ‐partite and has no subgraph isomorphic to . The function has been studied by many researchers. Finding is a special case of the Zarankiewicz problem. We prove an analog of the Kövári‐Sós‐Turán theorem for 3‐partite graphs by showing for . Using Sidon sets constructed by Bose and Chowla, we prove that this upper bound is asymptotically best possible in the case that and is odd, that is, for . In the cases of and , we use a result of Allen, Keevash, Sudakov, and Verstraëte, to show that a similar upper bound holds for all and gives a better constant when . Finally, we point out an interesting connection between difference families from design theory and .     

Decidability for ℤ2 G‐lattices when G Extends the Noncyclic Group of Order 4

Let G be the direct sum of the noncyclic groupof order four and a cyclic groupwhoseorderisthe power pⁿ of some prime p. We show that ℤ₂ G‐lattices have a decidable theory when the cyclotomic polynomia (x) is irreducible modulo 2ℤ for every j ≤ n. More generally we discuss the decision problem for ℤ₂ G‐lattices when G is a finite group whose Sylow 2‐subgroups are isomorphic to the noncyclic group of order four.     

Strong Cardinals and Sets of Reals in Lω1(ℝ)

We generalize results of [3] and [1] to hyperprojective sets of reals, viz. to more than finitely many strong cardinals being involved. We show, for example, that if every set of reals in L_ω (?) is weakly homogeneously Souslin, then there is an inner model with an inaccessible limit of strong cardinals.     

On some sets of dictionaries whose ω ‐powers have a given

A dictionary is a set of finite words over some finite alphabet X. The ω ‐power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [10] the complexity of the set of dictionaries whose associated ω ‐powers have a given complexity. In particular, he considered the sets ??( Σ ⁰k) (respectively, ??( Π ⁰_k), ??( Δ ¹₁)) of dictionaries V ? 2* whose ω ‐powers are Σ ⁰_k‐sets (respectively, Π ⁰_k‐sets, Borel sets). In this paper we first establish a new relation between the sets ??( Σ ⁰₂) and ??( Δ ¹₁), showing that the set ??( Δ ¹₁) is “more complex” than the set ??( Σ ⁰₂). As an application we improve the lower bound on the complexity of ??( Δ ¹₁) given by Lecomte, showing that ??( Δ ¹₁) is in Σ ¹ ₂(2^2*)\ Π ⁰₂. Then we prove that, for every integer k ≥ 2 (respectively, k ≥ 3), the set of dictionaries ??( Π ⁰_k+1) (respectively, ??( Σ ⁰_{k +1})) is “more complex” than the set of dictionaries ??( Π ⁰_k) (respectively, ??( Σ ⁰_k)) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Linearly Stratified Models for the Foundations of Nonstandard Mathematics

Assuming the existence of an inaccessible cardinal, transitive full models of the whole set theory, equipped with a linearly valued rank function, are constructed. Such models provide a global framework for nonstandard mathematics.     

Γ‐convergence: a tool to investigate physical phenomena across scales

De Giorgi's Γ‐convergence is a variational theory modelled upon the convergence of families of (perturbed) minimum problems and of the corresponding minimizers. In these notes, after reviewing briefly the basic theory and accounting for some recent new insights, we discuss three examples of static mechanical models, which can be analysed by means of Γ‐convergence arguments. Copyright © 2012 John Wiley & Sons, Ltd.     

A small generating set for the 3‐BD closed set of block sizes ≥ 6

Let v, k be positive integers and k ≥ 3, then K_k = : {v: v ≥ k} is a 3‐BD closed set. Two finite generating sets of 3‐BD closed sets K₄ and K₅ are obtained by H. Hanani [5] and Qiurong Wu [12] respectively. In this article we show that if v ≥ 6, then v ∈ B₃(K,1), where K = {6,7,…,41,45,46,47,51,52,53,83,84}\{22,26}; that is, we show that K is a generating set for K₆. Finally we show that v ∈ B₃(6,20) for all v ∈ K\{35,39,40,45}. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 128–136, 2008     

Decidability for ℤ[G]-Modules when G is Cyclic of Prime Order

We consider the decision problem for modules over a group ring ?[G], where G is a cyclic group of prime order. We show that it reduces to the same problem for a class of certain abelian structures, and we obtain some partial decidability results for this class. Mathematics Subject Classification: 03C60, 03B25.     

A theory of sets with the negation of the axiom of infinity

In this paper we introduce a theory of finite sets FST with a strong negation of the axiom of infinity asserting that every set is provably bijective with a natural number. We study in detail the role of the axioms of Power Set, Choice, Regularity in FST, pointing out the relative dependences or independences among them. FST is shown to be provably equivalent to a fragment of Alternative Set Theory. Furthermore, the introduction of FST is motivated in view of a non-standard development. MSC: 03E30, 03E35.     

Joint Consistency of Fuzzy Theories

This paper is a contribution to the development of fuzzy logic in narrow sense with evaluated syntax and connectives interpreted in Łukasiewicz algebra. The main results concern model theory of fuzzy logic (various kinds of submodels, chains of models) and generalization of the Craig‐Robinson's theorem on joint consistency of fuzzy theories as well as Craig's interpolation theorem.     

Definable predicates of standardness in internal set theory

It is shown that Nelson’s internal set theory IST has no definable predicate that is a proper extension of the standardness predicate and satisfies the carry-over, idealization, and standardization principles. Translated fromMatematicheskie Zametki, Vol. 66, No. 6, pp. 803–809, December, 1999.     

Some Decidability Results for ℤ[G]-Modules when G is Cyclic of Squarefree Order

We extend the analysis of the decision problem for modules over a group ring ?[G] to the case when G is a cyclic group of squarefree order. We show that separated ?[G]-modules have a decidable theory, and we discuss the model theoretic role of these modules within the class of all ?[G]-modules. The paper includes a short analysis of the decision problem for the theories of (finitely generated) modules over ?[ζ_m], where m is a positive integer and ζ_m is a primitive mth root of 1. Mathematics Subject Classification: 03C60, 03B25.     

On κ‐hereditary Sets and Consequences of the Axiom of Choice

We will prove that some so‐called union theorems (see [2]) are equivalent in ZF⁰ to statements about the transitive closure of relations. The special case of “bounded” union theorems dealing with κ‐hereditary sets yields equivalents to statements about the transitive closure of κ‐narrow relations. The instance κ = ω₁ (i. e., hereditarily countable sets) yields an equivalent to Howard‐Rubin's Form 172 (the transitive closure Tc(x) of every hereditarily countable set x is countable). In particular, the countable union theorem (Howard‐Rubin's Form 31) and, a fortiori, the axiom of countable choice imply Form 172.     

An Operator Theoretical Approach to Enveloping ϕ* – and C* – Algebras of Melrose Algebras of Totally Characteristic Pseudodifferential Operators

Let X be a compact manifold with boundary. It will be shown (Theorem 3.4) that the small Melrose algebra A? ?_b,cl (χ,^bΩ^1/2) (cf. [22], [23]) of classical, totally characteristic pseudodifferential operators carries no topology such that it is a topological algebra with an open group of invertible elements, in particular, the algebra A cannot be spectrally invariant in any C* – algebra. On the other hand, the symbolic structure of A can be extended continuously to the C* – algebra B generated by A as a subalgebra of ζ(σ^bL²(χ, ^bΩ^1/2)) by a generalization of a method of Gohberg and Krupnik. Furthermore, A is densely embedded in a Fréchet algebra A ? B which is a ?* – algebra in the sense of Gramsch [9, Definition 5.1], reflecting also smooth properties of the original algebra A.