Poincaré-Type inequalities and reconstruction of Paley-Wiener functions on manifolds

The main goal of the article is to show that Paley-Wiener functions ƒ ∈ L ₂(M) of a fixed band width to on a Riemannian manifold of bounded geometry M completely determined and can be reconstructed from a set of numbers Φ_i (ƒ), i ∈ ℕwhere Φ_i is a countable sequence of weighted integrals over a collection of “small” and “densely” distributed compact subsets. In particular, Φ_i, i ∈ ℕ,can be a sequence of weighted Dirac measures δ_xi, x_i ∈M. It is shown that Paley-Wiener functions on M can be reconstructed as uniform limits of certain variational average spline functions. To obtain these results we establish certain inequalities which are generalizations of the Poincaré-Wirtingen and Plancherel-Polya inequalities. Our approach to the problem and most of our results are new even in the one-dimensional case.     

Bounded Scott Set Saturation

We examine the relationship between two different notions of a structure being Scott set saturated and identify sufficient conditions which guarantee that a structure is uniquely Scott set saturated. We also consider theories representing Scott sets; in particular, we identify a sufficient condition on a theory T so that for any given countable Scott set there exists a completion of T that is saturated with respect to the given Scott set. These results extend Scott's characterization of countable Scott sets via models and completions of Peano arithmetic.     

Complexity of the decidability of the unquantified set theory with a rank operator

The unquantified set theory MLSR containing the symbols ∪, ∖, ≠, ∈,R (R(x) is interpreted as a rank ofx) is considered. It is proved that there exists an algorithm which for any formulaQ of the MLSR theory decides whetherQ is true or not using the spacec|Q|³ (|Q| is the length ofQ).     

On the filter of computably enumerable supersets of an r-maximal set

We study the filter ℒ^*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ^*(A) is still Σ⁰ ₃-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ^*(A). Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001     

Robinson forcing is not absolute

Robinson (or infinite model theoretic) forcing is studied in the context of set theory. The major result is that infinite forcing, genericity, and related notions are not absolute relative to ZFC. This answers a question of G. Sacks and provides a non-trivial example of a non-absolute notion of model theory. This non-absoluteness phenomenon is shown to be intrinsic to the concept of infinite forcing in the sense that any ZFC-definable set theory, relative to which forcing is absolute, has the flavor of asserting self-inconsistency. More precisely: IfT is a ZFC-definable set theory such that the existence of a standard model ofT is consistent withT, then forcing is not absolute relative toT. For example, if it is consistent that ZFC+ “there is a measureable cardinal” has a standard model then forcing is not absolute relative to ZFC+ “there is a measureable cardinal.” Some consequences: 1) The resultants for infinite forcing may not be chosen “effectively” in general. This answers a question of A. Robinson. 2) If ZFC is consistent then it is consistent that the class of constructible division rings is disjoint from the class of generic division rings. 3) If ZFC is consistent then the generics may not be axiomatized by a single sentence ofL _w/w. In Memoriam: Abraham Robinson     

The Geometry of Standard Deontic Logic

Whereas geometrical oppositions (logical squares and hexagons) have been so far investigated in many fields of modal logic (both abstract and applied), the oppositional geometrical side of “deontic logic” (the logic of “obligatory”, “forbidden”, “permitted”, . . .) has rather been neglected. Besides the classical “deontic square” (the deontic counterpart of Aristotle’s “logical square”), some interesting attempts have nevertheless been made to deepen the geometrical investigation of the deontic oppositions: Kalinowski (La logique des normes, PUF, Paris, 1972) has proposed a “deontic hexagon” as being the geometrical representation of standard deontic logic, whereas Joerden (jointly with Hruschka, in Archiv für Rechtsund Sozialphilosophie 73:1, 1987), McNamara (Mind 105:419, 1996) and Wessels (Die gute Samariterin. Zur Struktur der Supererogation, Walter de Gruyter, Berlin, 2002) have proposed some new “deontic polygons” for dealing with conservative extensions of standard deontic logic internalising the concept of “supererogation”. Since 2004 a new formal science of the geometrical oppositions inside logic has appeared, that is “n-opposition theory”, or “NOT”, which relies on the notion of “logical bi-simplex of dimension m” (m = n − 1). This theory has received a complete mathematical foundation in 2008, and since then several extensions. In this paper, by using it, we show that in standard deontic logic there are in fact many more oppositional deontic figures than Kalinowski’s unique “hexagon of norms” (more ones, and more complex ones, geometrically speaking: “deontic squares”, “deontic hexagons”, “deontic cubes”, . . ., “deontic tetraicosahedra”, . . .): the real geometry of the oppositions between deontic modalities is composed by the aforementioned structures (squares, hexagons, cubes, . . ., tetraicosahedra and hyper-tetraicosahedra), whose complete mathematical closure happens in fact to be a “deontic 5-dimensional hyper-tetraicosahedron” (an oppositional very regular solid).      

How To Split Antichains In Infinite Posets*

A maximal antichain A of poset P splits if and only if there is a set B ⊂ A such that for each p ∈ P either b ≤ p for some b ∈ B or p ≤ c for some c ∈ A\B. The poset P is cut-free if and only if there are no x < y < z in P such that [x,z]_P = [x,y]_P ∪ [y,z]_P . By [1] every maximal antichain in a finite cut-free poset splits. Although this statement for infinite posets fails (see [2])) we prove here that if a maximal antichain in a cut-free poset “resembles” to a finite set then it splits. We also show that a version of this theorem is just equivalent to Axiom of Choice. We also investigate possible strengthening of the statements that “A does not split” and we could find a maximal strengthening. * This work was supported, in part, by Hungarian NSF, under contract Nos. T37846, T34702, T37758, AT 048 826, NK 62321. The second author was also supported by Bolyai Grant.     

“Setting” n-Opposition

Our aim is to show that translating the modal graphs of Moretti’s “n-opposition theory” (2004) into set theory by a suited device, through identifying logical modal formulas with appropriate subsets of a characteristic set, one can, in a constructive and exhaustive way, by means of a simple recurring combinatory, exhibit all so-called “logical bi-simplexes of dimension n” (or n-oppositional figures, that is the logical squares, logical hexagons, logical cubes, etc.) contained in the logic produced by any given modal graph (an exhaustiveness which was not possible before). In this paper we shall handle explicitly the classical case of the so-called 3(3)-modal graph (which is, among others, the one of S5), getting to a very elegant tetraicosahedronal geometrisation of this logic.      

Turing cones and set theory of the reals

We investigate Turing cones as sets of reals, and look at the relationship between Turing cones, measures, Baire category and special sets of reals, using these methods to show that Martin's proof of Turing Determinacy (every determined Turing closed set contains a Turing cone or is disjoint from one) does not work when you replace “determined” with “Blackwell determined”. This answers a question of Tony Martin. Received: 6 December 1999 / Revised version: 28 June 2000 Published online: 3 October 2001     

Some simple Haar-type wavelets in higher dimensions

An orthonormal wavelet system in ℝ^d, d ∈ ℕ, is a countable collection of functions {ψ _j,k ^ℓ }, j ∈ ℤ, k ∈ ℤ^d, ℓ = 1,..., L, of the form that is an orthonormal basis for L² (ℝ^d), where a ∈ GL_d (ℝ) is an expanding matrix. The first such system to be discovered (almost 100 years ago) is the Haar system for which L = d = 1, ψ¹(x) = ψ(x) = κ[0,1/2)^(x) − κ_[l/2,1) ^(x), a = 2. It is a natural problem to extend these systems to higher dimensions. A simple solution is found by taking appropriate products Φ(x₁, x₂, ..., x_d) = φ₁ (x₁)φ₂(x₂) ... φ_d(x_d) of functions of one variable. The obtained wavelet system is not always convenient for applications. It is desirable to find “nonseparable” examples. One encounters certain difficulties, however, when one tries to construct such MRA wavelet systems. For example, if a = ( _1-1 ^{1 1} ) is the quincunx dilation matrix, it is well-known (see, e.g., [5]) that one can construct nonseparable Haar-type scaling functions which are characteristic functions of rather complicated fractal-like compact sets. In this work we shall construct considerably simpler Haar-type wavelets if we use the ideas arising from “composite dilation” wavelets. These were developed in [7] and involve dilations by matrices that are products of the form a^jb, j ∈ ℤ, where a ∈ GL_d(ℝ) has some “expanding” property and b belongs to a group of matrices in GL_d(ℝ) having |det b| = 1.     

Spectral representation of generalized transition kernels

Let (X, A) be a set with a countably σ-generated “Borel” field of subsets; letW be a “Borel” subset of the product of (X, A) with the real line ℝ and its Borel fieldB; and for eachx∈X let γ _x be a measure on the “slice”W _x={(w, t)∈W:w=x}. It is shown that, under reasonable conditions, the σ-field A⊗B|W can be generated by a real-valued functiong in such a way that, given any measurablef:W→ℝ,g can be chosen to be arbitrarily close tof and so that its “slice-integrals” coincide with those off. This theorem is the first step in a study of monotonic sequences of countably generated σ-fields.     

Dominating cliques in P5-free graphs

All induced connected subgraphs of a graphG contain a dominating set of pair-wise adjacent vertices if and only if there is no induced subgraph isomorphic to a path or a cycle of five vertices inG. Moreover, the problem of finding any given type of connected dominating sets in all members of a classG of graphs can be reduced to the graphsG∈G that have a cut-vertex or do not contain any cutsetS dominated by somes∈S. This research was supported in part by the “AKA” Research Fund of the Hungarian Academy of Sciences.     

Families of Graphs Closed Under Taking Powers

 This paper gives simple proofs for “G ^k ∈? implies G ^{k +1}∈?” when ? is the family of all interval graphs, all proper interval graphs, all cocomparability graphs, or all m-trapezoid graphs. Received: November 21, 1997 Final version received: October 5, 1998     

On a class of isometric subgraphs of a graph

In a graphG, which has a loop at every vertex, a connected subgraphH=(V(H),E(H)) is a retract if, for anya, b ∈V(H) and for any pathsP, Q inG, both joininga tob, and satisfying |Q|≧ ≧|P|, thenP ⫅V(H) wheneverQ ⫅V(H). As such subgraphs can be described by a closure operator we are led to the investigation of the corresponding complete lattice of “closed” subgraphs. For example, in this complete lattice every element is the infimum of an irredundant family of infimum irreducible elements. The work presented here was supported in part by N.S.E.R.C. Operating Grant No. A4077.     

Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements

An arrangement of oriented pseudohyperplanes in affined-space defines on its setX of pseudohyperplanes a set system (or range space) (X, ℛ), ℛ ⊑ 2 ^x of VC-dimensiond in a natural way: to every cellc in the arrangement assign the subset of pseudohyperplanes havingc on their positive side, and let ℛ be the collection of all these subsets. We investigate and characterize the range spaces corresponding tosimple arrangements of pseudohyperplanes in this way; such range spaces are calledpseudogeometric, and they have the property that the cardinality of ℛ is maximum for the given VC-dimension. In general, such range spaces are calledmaximum, and we show that the number of rangesR∈ℛ for whichX - R∈ℛ also, determines whether a maximum range space is pseudogeometric. Two other characterizations go via a simple duality concept and “small” subspaces. The correspondence to arrangements is obtained indirectly via a new characterization of uniforom oriented matroids: a range space (X, ℛ) naturally corresponds to a uniform oriented matroid of rank |X|—d if and only if its VC-dimension isd,R∈ℛ impliesX - R∈ℛ, and |ℛ| is maximum under these conditions. Part of this work was done while the first author was a member of the Graduiertenkolleg “Algorithmische Diskrete Mathematik,” supported by the Deutsche Forschungsgemeinschaft, Grant We 1265/2-1. Part of this work has been supported by the German-Israeli Foundation for Scientific Research and Development (G.I.F.).     

Weakly least integer closed groups

An archimedean lattice-ordered groupA with distinguished weak unit has the canonical Yosida representation as an ℓ-group of extended real-valued functions on a certain compact Hausdorff spaceY A. Such an ℓ-groupA is calledleast integer closed, orLIC (resp.,weakly least integer closed, orwLIC) if, in the representation,a ∈A implies [a] ∈A (resp., there isa′ ∈A witha′=[a] on a dense set inY A), where [r] ≡ the least integer greater than or equal tor. Earlier, we have studiedLIC groups, with an emphasis on their a-extensions. Here, we turn towLIC groups: we give an intrinsic (though awk-ward) characterization in terms of existence of certain countable suprema. This results also in an intrinsic characterization ofLIC, previously lacking. Also,wLIC is a hull class (whichLIC is not), and the hullwlA is “somewhere near” the projectable hullpA. The best comparison comes from a (somewhat novel) factoringpA=loc(wpA), wherewpA is the “weakly projectable” hull (defined here), andlocB is the “local monoreflection”; then,wpA≤wlA≤loc(wpA), andpA≤loc(wlA), while with a strong unit, all these coincide. Numerous examples and special cases are examined.     

Block separation in solvable groups

If π is a set of primes, a finite group G is block π-separated if for every two distinct irreducible complex characters α, β ∈ Irr(G) there exists a prime p ∈ π such that α and β lie in different Brauer p-blocks. A group G is block separated if it is separated by the set of prime divisors of |G|. Given a set π with n different primes, we construct an example of a solvable π-group G which is block separated but it is not separated by every proper subset of π. Received: 22 December 2004     

Ploucquet’s “Refutation” of the Traditional Square of Opposition

In the 18th century, Gottfried Ploucquet developed a new syllogistic logic where the categorical forms are interpreted as set-theoretical identities, or diversities, between the full extension, or a non-empty part of the extension, of the subject and the predicate. With the help of two operators ‘O’ (for “Omne”) and ‘Q’ (for “Quoddam”), the UA and PA are represented as ‘O(S) – Q(P)’ and ‘Q(S) – Q(P)’, respectively, while UN and PN take the form ‘O(S) > O(P)’ and ‘Q(S) > O(P)’, where ‘>’ denotes set-theoretical disjointness. The use of the symmetric operators ‘–’ and ‘>’ gave rise to a new conception of conversion which in turn lead Ploucquet to consider also the unorthodox propositions O(S) – O(P), Q(S) – O(P), O(S) > Q(P), and Q(S) > Q(P). Although Ploucquet’s critique of the traditional theory of opposition turns out to be mistaken, his theory of the “Quantification of the Predicate” is basically sound and involves an interesting “Double Square of Opposition”. My thanks are due to Hanno von Wulfen for helpful discussions and for transforming the word-document into a Latex-file.