bluuebunny/crossref_metadata_2025_split huggingface dataset:
Finitely constrained classes of homogeneous directed graphs
Authors: Latka Brenda J. 
Published: May 2006

AbstractGiven a finite relational language L is there an algorithm that, given two finite sets and of structures in the language, determines how many homogeneous L structures there are omitting every structure in and embedding every structure in ?For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether Γ, the class of finite tournaments omitting every tournament in Γ. is well-quasi-order?First, we give a nonconstructive proof of the existence of an algorithm for the case in which Γ consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere.The case in which Γ consists of two tournaments is also discussed.
Semilinear cell decomposition
Authors: Liu Nianzheng 
Published: May 2006

AbstractWe obtain a p-adic semilinear cell decomposition theorem using methods developed by Denef in [Journal für die Reine und Angewandte Mathematik, vol. 369 (1986), pp. 154–166]. We also prove that any set definable with quantifiers in (0,1, +, —, λq, Pn){n∈ℕ,q∈ℚp} may be defined without quantifiers, where λq is scalar multiplication by q and Pn is a unary predicate which denotes the nonzero nth powers in the p-adic field ℚp. Such a set is called a p-adic semilinear set in this paper. Some further considerations are discussed in the last section.
Embeddability of ptykes
Authors: Girard Jean-Yves , Normann Dag 
Published: May 2006

The notion of a ptyx (plural, ptykes) is obtained by generalising the ordinals On and the dilators Dil introduced by Girard [1] into a typed hierarchy. The notion is due to Girard, and a detailed treatment will appear in Girard [2].In this Introduction we will give a summary of the theory of ptykes. It will be an advantage to be familiar with the theory of dilators as introduced in Girard [1] or as presented in Girard and Normann [3].The class On of ordinals is organised into a category ON by using strictly increasing maps f: x → y as morphisms. A dilator will be a functor F: ON → ON commuting with pullbacks and direct limits. Associated with each dilator F there is a denotation system DF, obtained as follows: For each x ∈ On and y ∈ F(x), y can be given a unique denotation (c; x0,…, xn−1;x)F, where c∈F(n) (n = {0,…, n − 1}), y = F(ϕ)(c) (where ϕ is defined by ϕ(i) = xi for i < n), and for no m < n and ψ: m → n do we have c ∈ im(ψ).We let the trace Tr(F) be the set of pairs (c, n) occurring in a denotation.
Frequency computations and the cardinality theorem
Authors: Harizanov Valentina , Kummer Martin , Owings Jim 
Published: May 2006

In 1960 G. F. Rose [R] made the following definition: A function f: ω → ω is (m, n)-computable, where 1 ≤ m ≤ n, iff there exists a recursive function R: ωn → ωn such that, for all n-tuples (x1,…, xn) of distinct natural numbers,J. Myhill (see [McN, p. 393]) asked if f had to be recursive if m was close to n; B. A. Trakhtenbrot [T] responded by showing in 1963 that f is recursive whenever 2m > n. This result is optimal, because, for example, the characteristic function of any semirecursive set is (1,2)-computable. Trakhtenbrot's work was extended by E. B. Kinber [Ki1], using similar techniques. In 1986 R. Beigel [B] made a powerful conjecture, much more general than the above results. Partial verification, falling short of a full proof, appeared in [O]. Using new techniques, M. Kummer has recently established the conjecture, which will henceforth be referred to as the cardinality theorem (CT). It is the goal of this paper to show the connections between these various theorems, to review the methods used by Trakhtenbrot, and to use them to prove a special case of CT strong enough to imply Kinber's theorem (see §3). We thus have a hierarchy of results, with CT at the top. We will also include a discussion of Kummer's methods, but not a proof of CT.
Does V equal L?
Authors: Maddy Penelope 
Published: May 2006

Does V = L? Is the Axiom of Constructibility true? Most people with an opinion would answer no. But on what grounds? Despite the near unanimity with which V = L is declared false, the literature reveals no clear consensus on what counts as evidence against the hypothesis and no detailed analysis of why the facts of the sort cited constitute evidence one way or another. Unable to produce a well-developed argument one way or the other, some observers despair, retreating to unattractive fall-back positions, e.g., that the decision on whether or not V = L is a matter of personal aesthetics. I would prefer to avoid such conclusions, if possible. If we are to believe that L is not V, as so many would urge, then there ought to be good reasons for this belief, reasons that can be stated clearly and subjected to rational evaluation. Though no complete argument has been presented, the literature does contain a number of varied argument fragments, and it is worth asking whether some of these might be developed into a persuasive case.One particularly simple approach would be to note that the existence of a measurable cardinal (MC) implies that V ≠ L,1and to argue that there is a measurable cardinal. The drawback to this approach is that its implying V ≠ L cannot then be counted as evidence in favor of MC, as it often is. Indeed, there seems to have been considerable sentiment against V = L even before the proof of its negation from MC,2and this sentiment must either be accounted for as reasonable or explained away as an aberration of some kind.
Combinatorial properties of the ideal ℬ2
Authors: Cichoń J. , Rosłanowski A. , Steprans J. , Wȩglorz B. 
Published: May 2006

AbstractBy ℬ2 we denote the σ-ideal of all subsets A of the Cantor set {0, 1}ω such that for every infinite subset T of ω the restriction A∣{0, 1}T is a proper subset of {0, 1}T. In this paper we investigate set theoretical properties of this and similar ideals.
μ-definable sets of integers
Authors: Lubarsky Robert S. 
Published: May 2006

Inductive definability has been studied for some time already. Nonetheless, there are some simple questions that seem to have been overlooked. In particular, there is the problem of the expressibility of the μ-calculus.The μ-calculus originated with Scott and DeBakker [SD] and was developed by Hitchcock and Park [HP], Park [Pa], Kozen [K], and others. It is a language for including inductive definitions with first-order logic. One can think of a formula in first-order logic (with one free variable) as defining a subset of the universe, the set of elements that make it true. Then “and” corresponds to intersection, “or” to union, and “not” to complementation. Viewing the standard connectives as operations on sets, there is no reason not to include one more: least fixed point.There are certain features of the μ-calculus coming from its being a language that make it interesting. A natural class of inductive definitions are those that are monotone: if X ⊃ Y then Γ (X) ⊃ Γ (Y) (where Γ (X) is the result of one application of the operator Γ to the set X). When studying monotonic operations in the context of a language, one would need a syntactic guarantor of monotonicity. This is provided by the notion of positivity. An occurrence of a set variable S is positive if that occurrence is in the scopes of exactly an even number of negations (the antecedent of a conditional counting as a negation). S is positive in a formula ϕ if each occurrence of S is positive. Intuitively, the formula can ask whether x ∊ S, but not whether x ∉ S. Such a ϕ can be considered an inductive definition: Γ (X) = {x ∣ ϕ(x), where the variable S is interpreted as X}. Moreover, this induction is monotone: as X gets bigger, ϕ can become only more true, by the positivity of S in ϕ. So in the μ-calculus, a formula is well formed by definition only if all of its inductive definitions are positive, in order to guarantee that all inductive definitions are monotone.
Natural language, sortal reducibility and generalized quantifiers
Authors: Keenan Edward L. 
Published: May 2006

AbstractRecent work in natural language semantics leads to some new observations on generalized quantifiers. In §1 we show that English quantifiers of type 〈1, 1〉 are booleanly generated by theirgeneralized universalandgeneralized existentialmembers. These two classes also constitute thesortally reduciblemembers of this type.Section 2 presents our main result — the Generalized Prefix Theorem (GPT). This theorem characterizes the conditions under which formulas of the form (Q1x1…QnxnRx1…xnandq1x1…qnxnRx1…xnare logically equivalent for arbitrary generalized quantifiersQi,qi. GPT generalizes, perhaps in an unexpectedly strong form, the Linear Prefix Theorem (appropriately modified) of Keisler & Walkoe (1973).
Games and full completeness for multiplicative linear logic
Authors: Abramsky Samson , Jagadeesan Radha 
Published: May 2006

AbstractWe present a game semantics for Linear Logic, in which formulas denote games and proofs denote winning strategies. We show that our semantics yields a categorical model of Linear Logic and prove full completeness for Multiplicative Linear Logic with the MIX rule: every winning strategy is the denotation of a unique cut-free proof net. A key role is played by the notion of history-free strategy; strong connections are made between history-free strategies and the Geometry of Interaction. Our semantics incorporates a natural notion of polarity, leading to a refined treatment of the additives. We make comparisons with related work by Joyal, Blass, et al.
A constructive proof of McNaughton's theorem in infinite-valued logic
Authors: Mundici Daniele 
Published: May 2006

AbstractWe give a constructive proof of McNaughton's theorem stating that every piecewise linear function with integral coefficients is representable by some sentence in the infinite-valued calculus of Lukasiewicz. For the proof we only use Minkowski's convex body theorem and the rudiments of piecewise linear topology.
Ideals of nowhere Ramsey sets are isomorphic
Authors: Plewik Szymon 
Published: May 2006

AbstractWe introduce a notion of ideal type such that any two ideals with the same ideal type are isomorphic. From this we infer, under the axiom t = h, that each ideal which consists of all nowhere Ramsey sets contained in some family of infinite subsets of natural numbers is isomorphic with the ideal of all nowhere Ramsey sets.
Recursion theory in a lower semilattice
Authors: Feldman Alex 
Published: May 2006

In §3 we construct a universal, ℵ0-categorical recursively presented partial order with greatest lower bound operator. This gives us the unique structure which embeds every countable lower semilattice. In §§5 and 6 we investigate the recursive and recursively enumerable substructures of this structure, in particular finding a suitable definition for the simple-maximal hierarchy and giving an example of an infinite recursively enumerable substructure which does not contain any infinite recursive substructure.The idea of looking at the lattice of recursively enumerable substructures of some recursive algebraic structure was introduced by Metakides and Nerode in [5], and since then many different kinds of algebraic structures have been studied in this way, including vector spaces, Boolean algebras, groups, algebraically closed fields, and equivalence relations. Since different algebraic structures have different recursion theoretic properties, one natural question is whether an algebraic structure with relatively little structure (such as a partial order or an equivalence relation) exhibits behavior more like classical recursion theory than one with more structure (such as vector spaces or algebraically closed fields).In [6] and [7], Metakides and Remmel studied recursion theory on orderings, and, as they point out in [6], orderings differ from most other algebraic structures in that the algebraic closure operation on orderings is trivial; but this does not present a problem for them, given the questions they explore. Moreover, they take an approach of proving general theorems which can then be applied to specific orderings. Our tack is different, although also well-established (see, for example, [3]), in which a “largest” structure is defined (in §3) which corresponds to the natural numbers in classical recursion theory. In order to distinguish substructures from subsets, a function symbol is added, namely greatest lower bound. The greatest lower bound function is fundamental to the study of orderings and occurs naturally in many of them, and thus is an appropriate addition to the theory of orderings. In §4 we redefine the concepts of simple and maximal in a manner appropriate to this structure, and prove several existence theorems.
Baire numbers, uncountable Cohen sets and perfect-set forcing
Authors: Landver Avner 
Published: May 2006

The Baire number of the real line (see 1.1(c)) has uncountable cofinality [Mi]. This number is equal to the Baire number of the space 2ω and also to the Baire number (1.1(d)) of every countable partial order. Our research is motivated by the following open question (1.13) (see also [BPS] and [Mi]): can the cofinality of nκ, the Baire number of the space (2κ)κ (1.1(b)), be less than or equal to κ? This question is nontrivial when κ is regular and 2κ = κ (1.3). A. Miller proved that the answer is “no” if κ is strongly inaccessible (see [Mi] and 1.11). Assuming CH, is equal to the Baire number of the Stone space of ℘(ω)/Fin.In §1 we discuss , the Baire number of the space (2λ)κ. If κ is regular, then , and using 1.3 and 1.5, we may rule out the easy cases and restrict ourselves to cases where κ is regular with 2<κ = κ, and κ ≤ λ 2κ. If λ > κ, then it is consistent to have cof()=κ ([Mi] and 1.7). We do not know whether is consistent (1.9). Next, the cardinal number eκ is defined (1.10). It is easy to see that nκ ≤ eκ and that cof(eκ) > κ. If κ is strongly inaccessible (s.i.), then nκ = eκ ([Mil], [Bar], [MF] and 1.11). For κ accessible, the question of whether nκ = eκ is open.Another open question (Fremlin) is stated as follows: assume W ⊇ V and f ∈ ωω ∩ W is such that, for every g ∈ ω ω ∩ V, ∣(f = g)∣ = ℵ0, does this imply that W contains sets which are ω-Cohen (1.1(a)) over V? If κ is accessible regular with 2<κ = κ, then the answer to the analog of Fremlin's question for κ is “no”. In fact, any κ-closed forcing that adds new subsets of κ, also adds a new function f ∈ κκ such that, for every g ∈ κκ ∩V, (f = g) is stationary (4.1(a)). On the other hand, perfect-set forcing on κ (see [Ka] and §5) adds a new subset of κ but produces a minimal extension (5.4(b)), and hence adds no sets which are κ-Cohen over V.
Decomposing Baire functions
Authors: Cichoń J. , Morayne M. , Pawlikowski J. , Solecki S. 
Published: May 2006

AbstractWe discuss in the paper the following problem: Given a function in a given Baire class, into “how many” (in terms of cardinal numbers) functions of lower classes can it be decomposed? The decomposition is understood here in the sense of the set-theoretical union.
Continuity and nondiscontinuity in constructive mathematics
Authors: Ishihara Hajime 
Published: May 2006

AbstractThe purpose of this paper is an axiomatic study of the interrelations between certain continuity properties. We show that every mapping is sequentially continuous if and only if it is sequentially nondiscontinuous and strongly extensional, and that “every mapping is strongly extensional”, “every sequentially nondiscontinuous mapping is sequentially continuous”, and a weak version of Markov's principle are equivalent. Also, assuming a consequence of Church's thesis, we prove a version of the Kreisel-Lacombe-Shoenfield-Tseĭtin theorem.
On the weak Kleene scheme in Kripke's theory of truth
Authors: Cain James , Damnjanovic Zlatan 
Published: May 2006

AbstractIt is well known that the following features hold of AR + T under the strong Kleene scheme, regardless of the way the language is Gödel numbered:1. There exist sentences that are neither paradoxical nor grounded.2. There are fixed points.3. In the minimal fixed point the weakly definable sets (i.e., sets definable as {n ∣ A(n) is true in the minimal fixed point}, where A(x) is a formula of AR + T) are precisely the sets.4. In the minimal fixed point the totally defined sets (sets weakly defined by formulae all of whose instances are true or false) are precisely the sets.5. The closure ordinal for Kripke's construction of the minimal fixed point is .In contrast, we show that under the weak Kleene scheme, depending on the way the Gödel numbering is chosen:1. There may or may not exist nonparadoxical, ungrounded sentences.2. The number of fixed points may be any positive finite number, ℵ0, or .3. In the minimal fixed point, the sets that are weakly definable may range from a subclass of the sets 1-1 reducible to the truth set of AR to the sets, including intermediate cases.4. Similarly, the totally definable sets in the minimal fixed point range from precisely the arithmetical sets up to precisely the sets.5. The closure ordinal for the construction of the minimal fixed point may be ω, , or any successor limit ordinal in between.In addition we suggest how one may supplement AR + T with a function symbol interpreted by a certain primitive recursive function so that, irrespective of the choice of the Gödel numbering, the resulting language based on the weak Kleene scheme has the five features noted above for the strong Kleene language.
New set-theoretic axioms derived from a lean metamathematics
Authors: Mycielski Jan 
Published: May 2006

I will formulate in this paper three set-theoretic axioms, (A1), (A2), and (A3), which appear natural and settle some well-known questions, and I will give some metamathematical evidence supporting these axioms. I build upon a distinction between pure mathematics and applied metamathematics which views the first as an art dealing with imaginary objects, where following Poincaré we can say to exist is to be free of contradiction, and the second as a science describing the phenomenon of mathematics, where science means a description of some physical reality (in this case the reality of thoughts in our brains which underlie spoken or written mathematics). Of course this distinction is not new, but it has been disregarded by many mathematicians and philosophers who wrote about the nature of mathematics, e.g. by the Platonists, and even by some empiricists who thought that mathematics is a science. Since applied metamathematics is a science, unlike pure mathematics it has to be lean, i.e., to obey Ockham's principle of economy of concepts (entia non sunt multiplicanda praeter necessitatem).In this lean metamathematics we describe pure mathematics as a finite structure of thoughts in our brains, and we think that written or spoken mathematics is an abstract description of this structure. (I think that this is the view which Poincaré expressed informally in his discussions with the logicians and set theorists of his times, although his idea has to be modified to some extent; see Remark 4 at the end of this paper.) We claim that all mathematical objects which are imagined when we develop a (first-order) theory T can be represented by means of terms of the language of a Skolemization of the set of sentences consisting of the axioms of T and of all theorems of logic.
Fine hierarchies and Boolean terms
Authors: Selivanov V. L. 
Published: May 2006

AbstractWe consider fine hierarchies in recursion theory, descriptive set theory, logic and complexity theory. The main results state that the sets of values of different Boolean terms coincide with the levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating the usefulness of fine hierarchies.
A semantics of evidence for classical arithmetic
Authors: Coquand Thierry 
Published: May 2006

If it is difficult to give the exact significance of consistency proofs from a classical point of view, in particular the proofs of Gentzen [2, 6], and Novikoff [14], the motivations of these proofs are quite clear intuitionistically. Their significance is then less to give a mere consistency proof than to present an intuitionistic explanation of the notion of classical truth. Gentzen for instance summarizes his proof as follows [6]: “Thus propositions of actualist mathematics seem to have a certain utility, but no sense. The major part of my consistency proof, however, consists precisely in ascribing a finitist sense to actualist propositions.” From this point of view, the main part of both Gentzen's and Novikoff's arguments can be stated as establishing that modus ponens is valid w.r.t. this interpretation ascribing a “finitist sense” to classical propositions.In this paper, we reformulate Gentzen's and Novikoff's “finitist sense” of an arithmetic proposition as a winning strategy for a game associated to it. (To see a proof as a winning strategy has been considered by Lorenzen [10] for intuitionistic logic.) In the light of concurrency theory [7], it is tempting to consider a strategy as an interactive program (which represents thus the “finitist sense” of an arithmetic proposition). We shall show that the validity of modus ponens then gets a quite natural formulation, showing that “internal chatters” between two programs end eventually.We first present Novikoff's notion of regular formulae, that can be seen as an intuitionistic truth definition for classical infinitary propositional calculus. We use this in order to motivate the second part, which presents a game-theoretic interpretation of the notion of regular formulae, and a proof of the admissibility of modus ponens which is based on this interpretation.
Relativized logspace and generalized quantifiers over finite ordered structures
Authors: Gottlob Georg 
Published: May 2006

AbstractWe here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a familyQof generalized quantifiers expressing a complexity classC, what is the expressive power of first order logic FO(Q) extended by the quantifiers inQ? From previously studied examples, one would expect that FO(Q) capturesLC, i.e., logarithmic space relativized to an oracle inC. We show that this is not always true. However, after studying the problem from a general point of view, we derive sufficient conditions onCsuch that FO(Q) capturesLC. These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, byNP. As an application of this result, it follows that first order logic extended by Henkin quantifiers capturesLNP. This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many familiesQof generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform, vol. 18, 1993].