Decidability of the AE-theory of the lattice of $${\varPi }_1^0$$ classes

An AE-sentence is a sentence in prenex normal form with all universal quantifiers preceding all existential quantifiers, and the AE-theory of a structure is the set of all AE-sentences true in the structure. We show that the AE-theory of \((\mathscr {L}({\varPi }_1^0), \cap , \cup , 0, 1)\) is decidable by giving a procedure which, for any AE-sentence in the language, determines the truth or falsity of the sentence in our structure.     

On Shattering,Splitting and Reaping Partitions

In this article we investigate the dual-shattering cardinal ?, the dual-splitting cardinal ?? and the dual-reaping cardinal ??, which are dualizations of the well-known cardinals ?? (the shattering cardinal, also known as the distributivity number of P(ω)/fin), s (the splitting number) and ?? (the reaping number). Using some properties of the ideal ?? of nowhere dual-Ramsey sets, which is an ideal over the set of partitions of ω, we show that add(??) = cov(??) = ?. With this result we can show that ? > ω₁ is consistent with ZFC and as a corollary we get the relative consistency of ? > ?? t, where t is the tower number. Concerning ?? we show that cov(M) ? ?? ?? (where M is the ideal of the meager sets). For the dual-reaping cardinal ?? we get p ?? ? ?? ? ?? (where ?? is the pseudo-intersection number) and for a modified dual-reaping number ??′ we get ??′ ? ?? (where ?? is the dominating number). As a consistency result we get ?? < cov(??).     

The Ultrafilter Closure in ZF

It is well known that, in a topological space, the open sets can be characterized using ?lter convergence. In ZF (Zermelo‐Fraenkel set theory without the Axiom of Choice), we cannot replace filters by ultrafilters. It is proven that the ultra?lter convergence determines the open sets for every topological space if and only if the Ultrafilter Theorem holds. More, we can also prove that the Ultra?lter Theorem is equivalent to the fact that u_X = k_X for every topological space X, where k is the usual Kuratowski closure operator and u is the Ultra?lter Closure with u_X (A):= {x ∈ X: (? U ultrafilter in X)[U converges to x and A ∈ U ]}. However, it is possible to built a topological space X for which u_X ≠ k_X, but the open sets are characterized by the ultra?lter convergence. To do so, it is proved that if every set has a free ultra?lter, then the Axiom of Countable Choice holds for families of non‐empty finite sets. It is also investigated under which set theoretic conditions the equality u = k is true in some subclasses of topological spaces, such as metric spaces, second countable T0‐spaces or {?} (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Alternative Definition of Quantifiers on Four-Valued Łukasiewicz Algebras

An alternative notion of an existential quantifier on four-valued ?ukasiewicz algebras is introduced. The class of four-valued ?ukasiewicz algebras endowed with this existential quantifier determines a variety which is denoted by \(\mathbb {M}_{\frac{2}{3}}\mathbb {L}_4\). It is shown that the alternative existential quantifier is interdefinable with the standard existential quantifier on a four-valued ?ukasiewicz algebra. Some connections between the new existential quantifier and the existential quantifiers defined on bounded distributive lattices and Boolean algebras are given. Finally, a completeness theorem for the monadic four-valued ?ukasiewicz predicate calculus corresponding to the dual of the alternative existential quantifier is proven.     

The logical consequence relation of propositional tense logic

This work concerns the model theory of propositional tense logic with the Kripke relational semantics. It is shown (i) that there is a formula y whose logical consequences form a complete II set, and (ii) that for 0 ≦ m < ω+ ω there are formulas γ_m such that all models of γ_m are isomorphic and have cardinality x_m, where x₀ = χ₀, x_m+1 = 2^xm, and x_ω = lim{x_m < | m ω}. Familiarity with the relational semantics for modal and tense logic ([1] or [3], for example) will be presumed. A knowledge of recursion theory would be helpful, although some background material will be provided.     

Homogenization of Hamilton‐Jacobi‐Bellman equations with respect to time‐space shifts in a stationary ergodic medium

We consider a family {u_? (t, x, ω)}, ? < 0, of solutions to the equation ?u_?/?t + ?Δu_?/2 + H (t/?, x/?, ?u_?, ω) = 0 with the terminal data u_?(T, x, ω) = U(x). Assuming that the dependence of the Hamiltonian H(t, x, p, ω) on time and space is realized through shifts in a stationary ergodic random medium, and that H is convex in p and satisfies certain growth and regularity conditions, we show the almost sure locally uniform convergence, in time and space, of u_?(t, x, ω) as ? → 0 to the solution u(t, x) of a deterministic averaged equation ?u/?t + H?(?u) = 0, u(T, x) = U(x). The “effective” Hamiltonian H? is given by a variational formula. © 2007 Wiley Periodicals, Inc.     

On coding uncountable sets by reals

If A ? ω₁, then there exists a cardinal preserving generic extension ??[A ][x ] of ??[A ] by a real x such that 1) A ∈ ??[x ] and A is Δ₁^HC (x) in ??[x ]; 2) x is minimal over ??[A ], that is, if a set Y belongs to ??[x ], then either x ∈ ??[A, Y ] or Y ∈ ??[A ]. The forcing we use implicitly provides reshaping of the given set A (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Controllability of stochastic systems with random delay

The object of the present paper is to study the stability behavior of a nonlinear stochastic differential system with random delay of the form ?(t; ω), ω; u(t)) + ?? (t, ω) ?(z(t — y(t; ω); ω) where ω ω, the supporting set of a probability measure space (ω, A, P), x(t, ω) in an n-dimensional random function; u(t) is an m-dimensional control vector, A(t, ω) in an n X p matrix function and ø in a p-dimensional random function defined on R^p X ω and y(t, ω) is a random delay with z(t, ω) being a p-dimensional observation vector defined a specific way. Conditions are given that guarantee the existence of an admissible control u, under the influence of which the sample paths of the stochastic system can be guided arbitrarily close to the origin with an assigned probability.     

Models and quantifier elimination for quantified Horn formulas

In this paper, quantified Horn formulas (QHORN) are investigated. We prove that the behavior of the existential quantifiers depends only on the cases where at most one of the universally quantified variables is zero. Accordingly, we give a detailed characterization of QHORN satisfiability models which describe the set of satisfying truth assignments to the existential variables. We also consider quantified Horn formulas with free variables (QHORN^*) and show that they have monotone equivalence models.The main application of these findings is that any quantified Horn formula Φ of length |Φ| with free variables, |∀| universal quantifiers and an arbitrary number of existential quantifiers can be transformed into an equivalent quantified Horn formula of length O(|∀|·|Φ|) which contains only existential quantifiers.We also obtain a new algorithm for solving the satisfiability problem for quantified Horn formulas with or without free variables in time O(|∀|·|Φ|) by transforming the input formula into a satisfiability-equivalent propositional formula. Moreover, we show that QHORN satisfiability models can be found with the same complexity.     

An improvement of fraisse's sufficient condition for hamiltonian graphs

Let G be a k-connected graph of order n. For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S. We prove that if there exists some s, 1 ≤ s ≤ k, such that Σ_xiEX d(X\{X_i}) > s(n?1) – k[s/2] – i(X)[(s?1)/2] holds for every independetn set X ={x₀, x₁ ?x_s} of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries.     

Substandard models of finite set theory

A survey of the isomorphic submodels of V_ω, the set of hereditarily finite sets. In the usual language of set theory, V_ω has 2^?0 isomorphic submodels. But other set‐theoretic languages give different systems of submodels. For example, the language of adjunction allows only countably many isomorphic submodels of V_ω (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A local normal form theorem for infinitary logic with unary quantifiers

We prove a local normal form theorem of the Gaifman type for the infinitary logic L_∞ω( Q _u)^ω whose formulas involve arbitrary unary quantifiers but finite quantifier rank. We use a local Ehrenfeucht‐Fraïssé type game similar to the one in [9]. A consequence is that every sentence of L_∞ω( Q _u)^ω of quantifier rank n is equivalent to an infinite Boolean combination of sentences of the form (?^≥iy)ψ(y), where ψ(y) has counting quantifiers restricted to the (2^n–1 – 1)‐neighborhood of y. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Infinitary calculus for a restricted first-order linear temporal logic without contraction on quantified formulas

An infinitary calculus for a restricted fragment of the first-order linear temporal logic is considered. We prove that for this fragment one can construct the infinitary calculusG _Lω ^* without contraction on predicate formulas. The calculusG _Lω ^* possesses the following properties: (1) the succedent rule for the existential quantifier is included into the corresponding axiom; (2) the premise of the antecedent rule for the universal quantifier does not contain a duplicate of the main formula. The soundness and completness ofG _Lω ^* are also proved. Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 3, pp. 378–397, July–September, 1999. Translated by R. Lapinskas     

A Characterization of a Certain Class of Compact Metric Spaces

Compact metric spaces χ of such a kind, that ??_f =??(X), are characterized, ??(X) is the σ-field of BOREL sets and ??_f(X) is the field generated by all open subset of X. Our main result is Theorem 5: If χ is a compact metric space, then the following conditions are equivalent:

• 1 ??_f(X) =??(X).
• 2 card (X) ≦x₀ and there are k, m?N such that card (X^(k)) = m.
• 3 There are k, m?N such that χ is homeomorphic to ω^k · m + 1.

     

Approximation properties of zonal function networks using scattered data on the sphere

A zonal function (ZF) network is a function of the form x↦∑ _k=1 ⁿ c _k (x · y _k), where x and the y _k's are on the unit sphere in q+1 dimensional Euclidean space, and where the y _k's are scattered points. In this paper, we study the degree of approximation by ZF networks. In particular, we compare this degree of approximation with that obtained with the classical spherical harmonics. In many cases of interest, this is the best possible for a given amount of information regarding the target function. We also discuss the construction of ZF networks using scattered data. Our networks require no training in the traditional sense, and provide theoretically predictable rates of approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stable signal recovery from incomplete and inaccurate measurements

Suppose we wish to recover a vector x₀ ∈ ?^?? (e.g., a digital signal or image) from incomplete and contaminated observations y = A x₀ + e; A is an ?? × ?? matrix with far fewer rows than columns (?? ? ??) and e is an error term. Is it possible to recover x₀ accurately based on the data y? To recover x₀, we consider the solution x^# to the ??₁‐regularization problem where ? is the size of the error term e. We show that if A obeys a uniform uncertainty principle (with unit‐normed columns) and if the vector x₀ is sufficiently sparse, then the solution is within the noise level As a first example, suppose that A is a Gaussian random matrix; then stable recovery occurs for almost all such A's provided that the number of nonzeros of x₀ is of about the same order as the number of observations. As a second instance, suppose one observes few Fourier samples of x₀; then stable recovery occurs for almost any set of ?? coefficients provided that the number of nonzeros is of the order of ??/(log ??)⁶. In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals. © 2006 Wiley Periodicals, Inc.     

Odd‐sized partitions of Russell‐sets

In the setting of ZF, i.e., Zermelo–Fraenkel set theory without the Axiom of Choice (AC), we study partitions of Russell‐sets into sets each with exactly n elements (called n ‐ary partitions), for some integer n. We show that if n is odd, then a Russell‐set X has an n ‐ary partition if and only if |X | is divisible by n. Furthermore, we establish that it is relative consistent with ZF that there exists a Russell‐set X such that |X | is not divisible by any finite cardinal n > 1 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

HEREDITARY SOBRIETY AND THE CARDINALITY OF T 1 TOPOLOGIES ON COUNTABLE SETS

Abstract

A T ₀ space is called sober provided the only irreducibly closed sets are the closures of singletons; a closed set is irreducibly closed if it cannot be written as a union of two of its proper closed subsets. The relationship between hereditarily sober spaces and the lower separation axioms is examined; e.g., every hereditarily sober space satisfies axiom T _D (the derived set of every set is closed). For T ₁ spaces, hereditary sobriety is much weaker than Hausdorff, however an hereditarily sober T ₁ topology on a countably infinite set has cardinality of the continumn.     

Existence and continuity of an implicit function in the neighborhood of an abnormal point

Solutions to the equation F(x, ??) = 0 with unknown x and the parameter ?? in the neighborhood of the solution (x _*, ??_*) under the additional constraint x ?? U, where U is a closed convex set, are studied. The sufficient conditions for existence of an implicit function without prior assumption of the normalcy of point x _* are given. The obtained result is used to investigate the local solvability of controlled systems with mixed constraints.