bluuebunny/crossref_metadata_2025_split huggingface dataset:
On the computational content of the axiom of choice
Authors: Berardi Stefano , Bezem Marc , Coquand Thierry 
Published: May 2006

AbstractWe present a possible computational content of the negative translation of classical analysis with the Axiom of (countable) Choice. Interestingly, this interpretation uses a refinement of the realizability semantics of the absurdity proposition, which is not interpreted as the empty type here. We also show how to compute witnesses from proofs in classical analysis of ∃-statements and how to extract algorithms from proofs of ∀∃-statements. Our interpretation seems computationally more direct than the one based on Gödel's Dialectica interpretation.
Chang's Conjecture and the Non-Stationary Ideal
Authors: Seabold Daniel Evan 
Published: May 2006

In The Axiom of Determinacy, Forcing Axioms and the Nonstationary Ideal [W1], Woodin constructs the partial order ℙmax, which in the presence of large cardinals yields a forcing extension of L(ℝ) where ZFC holds and the non-stationary ideal on ω1 (hereafter denoted NSω1) is ω2-saturated. The basic analysis of ℙmax forcing over L(ℝ) can be carried out assuming only the Axiom of Determinacy (AD). In the central result of this paper, we show that if one increases slightly the strength of the determinacy assumptions, then Chang's Conjecture—the assertion that every finitary algebra on ω2 has a subalgebra of order type ω1—holds in this extension as well. Specifically, we obtain:Corollary 4.6. Assume AD + V = L(ℝ, μ) + μ is a normal, fine measure on. Chang's Conjecture holds in any ℙmax-generic extension of L(ℝ).This technique for obtaining Chang's Conjecture is fairly general. We [Se] have adapted it to obtain Chang's Conjecture in the model presented by Steel and Van Wesep [SVW] and Woodin [Wl] has adapted it to his ℚmax forcing notion. In each of these models, as in the ℙmax extension, one forces over L(ℝ) assuming AD to obtain ZFC and NSω1 is ω2-saturated.By unpublished results of Woodin, the assumption for Corollary 4.6 is equiconsistent with the existence of ω2 many Woodin cardinals, and hence strictly stronger than ADL(ℝ). One would like to reduce this assumption to ADL(ℝ). Curiously, this reduction is not possible in the arguments for ℚmax or the Steel and Van Wesep model, and the following argument of Woodin suggests why it may not be possible for ℙmax either.
Distance semantics for belief revision
Authors: Lehmann Daniel , Magidor Menachem , Schlechta Karl 
Published: May 2006

AbstractA vast and interesting family of natural semantics lor belief revision is defined. Suppose one is given a distance d between any two models. One may then define the revision of a theory K by a formula α as the theory defined by the set of all those models of α that are closest, by d. to the set of models of K. This family is characterized by a set of rationality postulates that extends the AGM postulates. The new postulates describe properties of iterated revisions.
Degree spectra of intrinsically c.e. relations
Authors: Hirschfeldt Denis R. 
Published: May 2006

AbstractWe show that for every c.e. degreea>0there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of setsSthere exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements ofS. Then we show that ifα∈ω∪ {ω} then for anyα-c.e. degreea>0there exists an intrinsicallyα-c.e. relation on the domain of a computable structure whose degree spectrum {0, a}. All of these results also hold for m-degree spectra of relations.
Some interesting connections between the slow growing hierarchy and the Ackermann function
Authors: Weiermann Andreas 
Published: May 2006

AbstractIt is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for Γ0. Let T be the set-theoretic ordinal notation system for Γ0 and Ttree the tree ordinal representation for Γ0. It is shown in this paper that (Gα)α∈T matches up with the class of functions which are elementary recursive in the Ackermann function as does (by folklore). By thinning out terms in which the addition function symbol occurs we single out subsystems T* ⊆ T and Ttree* ⊆ Ttree (both of order type not exceeding ε0) and prove that still matches up with but now consists of elementary recursive functions only. We discuss the relationship between these results and the Γ0-based termination proof for the standard rewrite system for the Ackermann function.
An almost deep degree
Authors: Cholak Peter , Groszek Marcia , Slaman Theodore 
Published: May 2006

AbstractWe show there is a non-recursive r.e. set A such that if W is any low r.e. set. then the join W ⊕ A is also low. That is. A is “almost deep”. This answers a question of Joekusch. The almost deep degrees form an definable ideal in the r.e. degrees (with jump.)
Admissibility of structural rules for contraction-free systems of intuitionistic logic
Authors: Dyckhoff Roy , Negri Sara 
Published: May 2006

AbstractWe give a direct proof of admissibility of cut and contraction for the contraction-free sequent calculusG4ipfor intuitionistic propositional logic and for a corresponding multi-succedent calculus: this proof extends easily in the presence of quantifiers, in contrast to other, indirect, proofs, i.e., those which use induction on sequent weight or appeal to admissibility of rules in other calculi.
Expedited Broda-Damas bracket abstraction
Authors: Bunder M. W. 
Published: May 2006

AbstractA bracket abstraction algorithm is a means of translating λ-terms into combinators. Broda and Damas, in [1], introduce a new, rather natural set of combinators and a new form of bracket abstraction which introduces at most one combinator for each λ-abstraction. This leads to particularly compact combinatory terms. A disadvantage of their abstraction process is that it includes the whole Schönfinkel [4] algorithm plus two mappings which convert the Schönfinkel abstract into the new abstract. This paper shows how the new abstraction can be done more directly, in fact, using only 2n − 1 algorithm steps if there are n occurrences of the variable to be abstracted in the term. Some properties of the Broda-Damas combinators are also considered.
Decidable fragments of first-order modal logics
Authors: Wolter Frank , Zakharyaschev Michael 
Published: May 2006

AbstractThe paper considers the setof first-order polymodal formulas the modal operators in which can be applied to subformulas of at most one free variable. Using a mosaic technique, we prove a general satisfiability criterion for formulas in, which reduces the modal satisfiability to the classical one. The criterion is then used to single out a number of new, in a sense optimal, decidable fragments of various modal predicate logics.
Sectionalism in Congress (1870 to 1890)
Authors: Roach Hannah Grace 
Published: May 2006

Sectionalism is a fundamental and persistent factor in American politics. In the shaping of congressional legislation and even in the formation of the platforms of our national parties, the influence of conflicting sectional interests is of prime importance. The precise nature of such sectional conflicts and the alignment of the various sections upon the leading policies of the time are clearly revealed by an analysis of the votes and debates in Congress on outstanding issues of national importance. Such votes, mapped by congressional districts, show that again and again party lines are broken by the force of sectional interest and that both Republicans and Democrats divide into sectional wings.A study of the period from the early 1870's to 1890 shows that sectionalism at that time was in large measure the product of the interaction of two movements in our national development,—the rapid expansion of Western settlement, particularly in the trans-Mississippi Middle West (the West North Central states) and the Mountain region, and the marked intensification of industrialism in the older sections of the country, especially in the North Atlantic states. Sectional alliances are flexible and shift with changing economic conditions. The East North Central states, for example, which at the beginning of the period usually vote in alliance with the West North Central and South, by the later eighties are found often on the side of the North Atlantic, a change which may be due to the fact that in the interval they had undergone a marked industrial development which gave them economic interests in common with the older sections. The areas of strongest radical voting move farther West with the shift in the centres of production of grain and livestock; that is, the nucleus of revolt in the Western wing of the Republican party especially is in the newer agricultural regions.
Syntactical and semantical properties of simple type theory
Authors: Schütte Kurt 
Published: May 2006

In my paper [10] I introduced the syntactical concepts “positive part” and “negative part” of logical formulas in first-order predicate calculus. These concepts make it possible to establish logical systems on inference rules similar to Gentzen's inference rules but without using the concept “sequent” and without needing Gentzen's structural inference rules. Proof-theoretical investigations of several formal systems based on positive and negative parts are published in [11]. In this paper I consider a similar formal system of simple type theory.A syntactical concept of “strict derivability” results from the formal system in [10] by generalization of the axioms and inference rules from first to higher-order predicate calculus and by addition of inference rules for set abstraction by means of a λ-symbol which allows us to form set expressions of arbitrary types from well-formed formulas.
Can the logic of indirect discourse be formalised?
Authors: Cohen L. Jonathan 
Published: May 2006

Recent attempts to analyse or explicate assertion-statements and other kinds of indirect discourse in formal terms seem to have overlooked an even greater difficulty than the familiar problems arising about equivalence, synonymy, translatability, etc. This difficulty is created by the fact that in judicial, journalistic, or historical fact-finding, as well as in everyday conversation, we frequently cite statements about a witness's truthfulness alongside the report of his testimony as the premisses from which we argue about the facts. It is then an essential part of our argument that it should appear to jump from one level of statement to another, and perhaps back again. So that the difficulty emerges: how can the formalisation of such an argument adopt any of the usual hierarchy-principles as a guarantee against semantical antinomies?Consider, for example,If the policeman testifies that anything, which the prisoner deposes, is false, and the prisoner deposes that something, which the policeman testifies, is true, then something, which the policeman testifies, is false and something, which the prisoner deposes, is true.
Disjunction and existence under implication in elementary intuitionistic formalisms
Authors: Kleene S. C. 
Published: May 2006

Let Pp, Pd, and N be the intuitionistic formal systems of prepositional calculus, predicate calculus, and elementary number theory, respectively.1 Consider the following six propositions.8(1) ├A V B only if ├A or ├B.(2) ├∋xA(x) only if ├Ã(t) for some formula Ã(x) congruent to A(x) and some term t free for x in Ã(x).
A formalization of inductive logic
Authors: Martin R. M. 
Published: May 2006

In this note we show how Carnap's theory of degree of confirmation (inductive logic) may be constructed upon a very simple and restricted semantical basis. The semantical meta-languages here may either be based upon a relation ofmultiple denotationor may even benon-translational. To these meta-languages a suitable metric for sentences may be appended. Axioms for such meta-languages are suggested, so that an especially simple formalization of Carnap's inductive logic is in effect presented in outline.For Carnap, inductive logic consists, roughly speaking, of a semantics augmented by a metric. More specifically, for a finite object-languagethe semantics consists of a theory of designation for, and to this are added numerical functions on sentences oftaking real numbers as values. (, it will be recalled, contains justNdistinct individual constants as primitive, where ‘N’ is a constant standing for some fixed finite number.contains a denumerable infinity of distinct individual constants as primitive, and will be discussed in a moment.) Were we to formalize this theory we should have, then, a translation of(or justitself), a syntax for, a primitive relation of designation, real numbers, and several different kinds of class and relational variables. The character of the underlying syntax is not clear from Carnap's account, but this can easily be supplied by a suitable adaptation of Tarski's method. For this, variables for classes of and relations between the expressions of the object-language are needed. Also in Carnap's theory of designation, variables over relations between expressions and objects are needed fundamentally. Real numbers may be handled in various ways. To simplify, let us suppose these are introduced by having a special kind of variable to range over them. Then suitable axioms for real numbers may be given, e.g., one of the axiom sets of Tarski.
On intermediate propositional logics
Authors: Umezawa Toshio 
Published: May 2006

By intermediate prepositional logics we mean prepositional logics between the intuitionistic and classical logics.K. Gödel [1] proved that there is a set of intermediate prepositional logics which possesses the order type ω. The method enables us to define intermediate logics in terms of axioms and rules of inference. We shall call it the axiomatic method.
The Economics of Transitions Democracy
Authors: Bates Robert H. 
Published: May 2006

This paper explores the relationship between economics and politics in the creation of democracy. The first section examines the shaping influence of the revenue imperative; the second, of end-game bargaining between retreating despots and insurgent democrats; and the third, of human capital. The paper is informal in argument and playful in spirit. It is designed to stimulate and provoke rather than to educate and inform.I do, however, seek to maintain a consistent set-up for the analysis: On one side stands a sovereign—in an earlier period, most likely a monarch; in the present typically a political party. The sovereign maintains a monopoly over the formulation of public policy and possesses the power to extract resources from the economy. On the other side stand the citizens. They own the factors of production: land, labor, and capital. They care about public policy, but they cannot make it. However, the decisions they do make influence the level of economic resources that can effectively be mobilized by the sovereign.
Presidential Prerogative Power: The Case of the Bush Administration and Legislative Power
Authors: Spitzer Robert J. 
Published: May 2006

Both the campaign and early administration of George Bush trumpeted a theme of a more centrist, lower-volume, less confrontational approach to politics and governing. Aspects of both the campaign and the administration seemed to belie this pledge, from the Willie Horton ads to the fight over the Tower nomination and the invasion of Panama. Still, the prevailing tone and style of the Bush administration during its first year seemed far less strident than that of the Reagan era. As Edwards (1989, 3) noted, “Bush has worked diligently to create an atmosphere of reconciliation and goodwill” and has sought to avoid “politically-charged polemics.”Yet in another respect, the Bush administration seems to have abandoned any semblance of a “kinder, gentler” politics in its dealings with Congress. Three seemingly minor aspects of Bush's recent dealings with Congress pertaining to legislative powers suggest, if anything, a singularly aggressive effort to extend the bounds of the presidency by what I will argue is a suspect invocation of prerogative powers. The actions described below have received virtually no press attention; yet they may presage a new era of presidential expansionism exceeding that which we have witnessed to date.
Liberal Democracy as a Global Phenomenon
Authors: Fukuyama Francis 
Published: May 2006

I. The Worldwide Democratic Revolution and Its CausesIt being less than ten days after the collapse of the attempted coup by communist hardliners in the Soviet Union, the coup's outcome serves as a useful reminder of the vitality that the democratic dea has for people still living under authoritarianism. The anti-communist revolution in the USSR is of course not an isolated event. The single most remarkable macropolitical phenomenon of the past generation has been the global crisis of authoritarianism, and the spread of liberal democracy in its wake, as noted by Lucian Pye in his presidential addressto this convention two years ago. By my count, there were three democracies in 1790; 13 in 1900, 27 in 1919, and 62 today.This progress has not been linear or continuous, of course: there were 14 fewer democracies in 1940 than in 1919; democracies were overthrown throughout Latin America in the 60s and 70s. Many of the countries thathave become democracies in the past few years are very unstable or of uncertain commitment to liberal values, and it would not be surprising to see a number of them lapse back into some kind of authoritarian rule in the nearfuture, as Thailand has already done this past year. Nonetheless, th trend is there. The 62 countries I countas democracies have a combined population of 2.24 billion people, or approximately 44 percent of the world's population. Moreover, neither the Soviet Union nor China are counted among the 62, and if parts or all of either country democratizes successfully, half to two-thirds of the world's population could be said to enjoy democratic rights and liberties.
America as a Model for the World? A Foreign Policy Perspective
Authors: Waltz Kenneth N. 
Published: May 2006

I. How the Placement of States Affects Their PoliciesBecause throughout most of the years since the second World War the United States and the Soviet Union were similarly placed by their power, their external behaviors should have shown striking similarities. Did they? Yes, more than has usually been realized. The behavior of states can be compared on many counts. Their armament policies and their interventions abroad are two of the most revealing. On the former count, the United States in the early 1960s undertook the largest strategic and conventional peace-time military build-up the world has yet seen. We did so even as Khrushchev was trying at once to carry through a major reduction in the conventional forces and to follow a strategy of minimum deterrence, and we did so even though the balance of strategic weapons greatly favored the United States. As one should have expected, the Soviet Union soon followed in America's footsteps, thus restoring the symmetry of great-power behavior. And so it was through most of the years of the Cold War. Advances made by one were quickly followed by the other, with the United States almost always leading the way. Allowing for geographic differences, the overall similarity of their forces was apparent. The ground forces of the Soviet Union were stronger than those of the United States, but in naval forces the balance of advantage was reversed. The Soviet Union's largely coastal navy gradually became more of a blue-water fleet, but one of limited reach. Its navy never had more than half the tonnage of ours.
Political Economy and Militarism
Authors: Kinnucan Michael J. 
Published: May 2006

Shortly after the demolition of the Berlin Wall, PS: Political Science & Politics published an article, “Socialism and Militarism,” which purported to demonstrate a positive causal relationship between socialism and militarism. Authors Thomas R. Dye and Harmon Zeigler (1989, 801) presented data and analysis leading them to conclude that “militarism is a much more pervasive characteristic of socialist nations than capitalist nations.” This finding is supportive of Payne (1989, 110) who, in Why Nations Arm stated, “the Marxist regimes are considerably more militaristic [than non-Marxist countries].”For their examination Dye and Zeigler employed the resource allocation measures of military spending as a percentage of gross national product and the number of military personnel per 1000 population as indicators of militarism, and the classification system of Gastil (cited in Dye and Zeigler 1989) in defining national political economy types. Using this information Dye and Zeigler generated four tables that ostensibly demonstrate that socialist countries are more militaristic than capitalist countries. It is arguable, however, that Dye and Zeigler's conclusions are dubious because of the definitions and measures they have chosen to use for both socialism and militarism.
Tracking Changes in the U.S. Senate
Authors: Polsby Nelson W. 
Published: May 2006

The character of the U.S. Senate has changed markedly over the last 30 years. The Senate can no longer be characterized as a well-bounded entity ruled by an “inner club” of insular grandees. Increasingly, rather, the Senate is a great forum, an echo chamber, a theater, where dramas—comedies and tragedies, soap operas and horse operas—are staged to enhance the careers of its members and to influence public policy by means of debate and public investigation.Its special role today in the contemporary American political system is as an incubator of policy ideas and political innovations (Polsby 1984). This stands in dramatic contrast with the Senate as late as the 1950s, which was far more a body that had positioned itself as a critic and a respondent—frequently an inhospitable one—to the political innovations hatched in the executive branch and by activist presidents and forwarded to it by the House of Representatives. Thus over the last three decades the Senate has evolved from a rather negative repository of states-rights thinking, dominated by a mostly southern-led “inner club,” and hence an explicit agent of the devolved aspect of the federal system, into a predominantly nationally-oriented body.The principal agent of this transformation has been the very great change in the life chances and therefore in the political ambitions of a large number of U.S. senators. Earlier, not so many of them entertained presidential ambitions. Today, the Senate is the main institutional source of presidential hopefuls, and for a large fraction of senators such hopes play a significant part in guiding their behavior in the Senate.