bluuebunny/crossref_metadata_2025_split huggingface dataset:
Some consistency proofs and a characterization of inconsistency proofs in illative combinatory logic
Authors: Bunder M. W. 
Published: May 2006

It is well known that combinatory logic with unrestricted introduction and elimination rules for implication is inconsistent in the strong sense that an arbitrary term Y is provable. The simplest proof of this, now usually called Curry's paradox, involves for an arbitrary term Y, a term X defined by X = Y(CPy).The fact that X = PXY = X ⊃ Y is an essential part of the proof.The paradox can be avoided by placing restrictions on the implication introduction rule or on the axioms from which it can be proved.In this paper we determine the forms that must be taken by inconsistency proofs of systems of propositional calculus based on combinatory logic, with arbitrary restrictions on both the introduction and elimination rules for the connectives. Generally such a proof will involve terms without normal form and cut formulas, i.e. formulas formed by an introduction rule that are immediately removed by an elimination with at most some equality steps intervening. (Such a sequence of steps we call a “cut”.)The above applies not only to the strong form of inconsistency defined above, but also to the weak form of inconsistency defined by: all propositions are provable, if this can be represented in the system.Any inconsistency proof of this kind of system can be reduced to one where the major premise of the elimination rule involved in the cut and its deduction must also appear in the deduction of the minor premise involved in the cut.We can, using this characterization of inconsistency proofs, put appropriate restrictions on certain introduction rules so that the systems, including a full classical propositional one, become provably consistent.
The contributions of Alfred Tarski to general algebra
Authors: Jónsson Bjarni 
Published: May 2006

A distinctive feature of modern mathematics is the interaction between its various branches and the blurring of the boundaries between different areas. This is strikingly illustrated in the work of Alfred Tarski. He was a logician first and an algebraist second. His contributions to algebra can be divided into three (ill-defined and overlapping) categories, general algebra, the study of various algebraic structures arising from problems outside algebra, mostly in logic and set theory, and the use of concepts and techniques from logic in the study of algebraic structures. Even more roughly, these three categories could be labeled as pure algebra, applications of algebra to logic, and applications of logic to algebra.Before Tarski came to the United States in 1939, he had written a series of papers on both the axiomatic and the structural aspects of Boolean algebras, and his inclination to algebraize mathematical problems is well illustrated by his paper [38g], Algebraische Fassung des Massproblems. Many of his later investigations of various types of algebraic structures are inspired by work done in this earlier period. However, beginning around 1940 there is a much greater emphasis on the study of algebra in its various aspects.The paper [41], On the calculus of relations, is a landmark event in this respect. The object here was to find an axiomatic basis for the arithmetic of binary relations. The axioms that he chose are simple and natural (see Monk [1986]).
0# and some forcing principles
Authors: Foreman Matthew , Magidor Menachem , Shelah Saharon 
Published: May 2006

It has been considered desirable by many set theorists to find maximality properties which state that the universe has in some sense “many sets”. The properties isolated thus far have tended to be consistent with each other (as far as we know). For example it is a widely held view that the existence of a supercompact cardinal is consistent with the axiom of determinacy holding in L(R). This consistency has been held to be evidence for the truth of these properties. It is with this in mind that the first author suggested the following:Maximality Principle If P is a partial ordering and G ⊆ P is a V-generic ultrafilter then eithera) there is a real number r ∈ V [G] with r ∉ V, orb) there is an ordinal α such that α is a cardinal in V but not in V[G].This maximality principle applied to garden variety partial orderings has startling results for the structure of V.For example, if for some , then P = 〈{p: p ⊆ κ, ∣p∣ < κ}, ⊆〉 neither adds a real nor collapses a cardinal. Thus from the maximality principle we can deduce that the G. C. H. fails everywhere and there are no inaccessible cardinals. (Hence this principle contradicts large cardinals.) Similarly one can show that there are no Suslin trees on any cardinal κ. These consequences help justify the title “maximality principle”.Since the maximality principle implies that the G. C. H. fails at strong singular limit cardinals it has consistency strength at least that of “many large cardinals”. (See [M].) On the other hand it is not known to be consistent, relative to any assumptions.
Pairs without infimum in the recursively enumerable weak truth table degrees
Authors: Fischer Paul 
Published: May 2006

wtt-reducibility has become of some importance in the last years through the works of Ladner and Sasso [1975], Stob [1983] and Ambos-Spies [1984]. It differs from Turing reducibility by a recursive bound on the use of the reduction. This makes some proofs easier in the wtt degrees than in the Turing degrees. Certain proofs carry over directly from the Turing to the wtt degrees, especially those based on permitting. But the converse is also possible. There are some r.e. Turing degrees which consist of a single r.e. wtt degree (the so-called contiguous degrees; see Ladner and Sasso [1975]). Thus it suffices to prove a result about contiguous wtt degrees using an easier construction, and it carries over to the corresponding Turing degrees.In this work we prove some results on pairs of r.e. wtt degrees which have no infimum. The existence of such a pair has been shown by Ladner and Sasso. Here we use a different technique of Jockusch [1981] to prove this result (Theorem 1) together with some stronger ones. We show that a pair without infimum exists above a given incomplete wtt degree (Theorem 5) and below any promptly simple wtt degree (Theorem 12). In Theorem 17 we prove, however, that there are r.e. wtt degrees such that any pair below them has an infimum. This shows that certain initial segments of the wtt degrees are lattices. Thus there is a structural difference between the wtt and Turing degrees where the pairs without infimum are dense (Ambos-Spies [1984]).
On the number of generators of cylindric algebras
Authors: Andréka H. , Németi I. 
Published: May 2006

The theory of cylindric algebras (CA's) is the algebraic theory of first order logics. Several ideas about logic are easier to formulate in the frame of CA-theory. Such are e.g. some concepts of abstract model theory (cf. [1] and [10]–[12]) as well as ideas about relationships between several axiomatic theories of different similarity types (cf. [4] and [10]). In contrast with the relationship between Boolean algebras and classical propositional logic, CA's correspond not only to classical first order logic but also to several other ones. Hence CA-theoretic results contain more information than their counterparts in first order logic. For more about this see [1], [3], [5], [9], [10] and [12].Here we shall use the notation and concepts of the monographs Henkin-Monk-Tarski [7] and [8]. ω denotes the set of natural numbers. CAα denotes the class of all cylindric algebras of dimension α; by “a CAα” we shall understand an element of the class CAα. The class Dcα ⊆ CAα was defined in [7]. Note that Dcα = 0 for α ∈ ω. The classes Wsα, and Csα were defined in 1.1.1 of [8], p. 4. They are called the classes of all weak cylindric set algebras, regular cylindric set algebras and cylindric set algebras respectively. It is proved in [8] (I.7.13, I.1.9) that ⊆ CAα. (These inclusions are proper by 7.3.7, 1.4.3 and 1.5.3 of [8].)It was proved in 2.3.22 and 2.3.23 of [7] that every simple, finitely generated Dcα is generated by a single element. This is the algebraic counterpart of a property of first order logics (cf. 2.3.23 of [7]). The question arose: for which simple CAα's does “finitely generated” imply “generated by a single element” (see p. 291 and Problem 2.3 in [7]). In terms of abstract model theory this amounts to asking the question: For which logics does the property described in 2.3.23 of [7] hold? This property is roughly the following. In any maximal theory any finite set of concepts is definable in terms of a single concept. The connection with CA-theory is that maximal theories correspond to simple CA's (the elements of which are the concepts of the original logic) and definability corresponds to generation.
The ⊲-ordering on normal ultrafilters
Authors: Baldwin Stewart 
Published: May 2006

Ifκis a measurable cardinal, then it is a well-known fact that there is at least one normal ultrafilter overκ. In [K-1], Kunen showed that one cannot say more without further assumptions, for ifUis a normal ultrafilter overκ, thenL[U] is an inner model of ZFC in whichκhas exactly one normal measure. On the other hand, Kunen and Paris showed [K-P] that ifκis measurable in the ground model, then there is a forcing extension in whichκhasnormal ultrafilters, so it is consistent thatκhas the maximum possible number of normal ultrafilters. Starting with assumptions stronger than measurability, Mitchell [Mi-1] filled in the gap by constructing models of ZFC + GCH satisfying “there are exactlyλnormal ultrafilters overκ”, whereλcould beκ+orκ++(measured in the model), or anything ≤κ. Whether or not Mitchell's results can be obtained by starting only with a measurable cardinal in the ground model and defining a forcing extension is unknown.There are substantial differences between the Mitchell models and the Kunen-Paris models. In the Kunen-Paris modelsκcan be the only measurable cardinal. However, in the Mitchell model in whichκhas exactly 2 normal ultrafilters, one of them contains the set {α<κ:αis measurable} while the other does not. Thus it is natural to ask if it is possible to get a modelMof ZFC in whichκis the only measurable cardinal andκhas exactly 2 normal ultrafilters. In this paper we will show that, using appropriate large cardinal assumptions, the answer is yes.
Large cardinal structures below ℵω
Authors: Apter Arthur W. , Henle James M. 
Published: May 2006

The theory of large cardinals in the absence of the axiom of choice (AC) has been examined extensively by set theorists. A particular motivation has been the study of large cardinals and their interrelationships with the axiom of determinacy (AD). Many important and beautiful theorems have been proven in this area, especially by Woodin, who has shown how to obtain, from hypermeasurability, models for the theories “ZF + DC + ∀α < ℵ1(ℵ1 → (ℵ1)α)” and . Thus, consequences of AD whose consistency strength appeared to be beyond that of the more standard large cardinal hypotheses were shown to have suprisingly weak consistency strength.In this paper, we continue the study of large cardinals in the absence of AC and their interrelationships with AD by examining what large cardinal structures are possible on cardinals below ℵω in the absence of AC. Specifically, we prove the following theorems.Theorem 1. Con(ZFC + κ1 < κ2are supercompact cardinals) ⇒ Con(ZF + DC + The club filter on ℵ1is a normal measure + ℵ1and ℵ2are supercompact cardinals).Theorem 2. Con(ZF + AD) ⇒ Con(ZF + ℵ1, ℵ2and ℵ3are measurable cardinals which carry normal measures + μωis not a measure on any of these cardinals).
On precipitousness of the nonstationary ideal over a supercompact
Authors: Gitik Moti 
Published: May 2006

Namba [N] proved that the nonstationary ideal over a measurable (NSκ) cannot be κ+-saturated. Baumgartner, Taylor and Wagon [BTW] asked if it is possible for NSκ to be precipitous over a measurable κ. A model with this property was constructed by the author, and shortly after Foreman, Magidor and Shelah [FMS] proved a general theorem that after collapsing of a supercompact or even a superstrong to the successor of κ, NSκ became precipitous. This theorem implies that it is possible to have the nonstationary ideal precipitous over even a supercompact cardinal. Just start with a supercompact κ and a superstrong λ > κ. Make supercompactness of κ indistractible as in [L] and then collapse λ to be κ+.The aim of our paper is to show that the existence of a supercompact cardinal alone already implies the consistency of the nonstationary ideal precipitous over a supercompact. The proof gives also the following: if κ is a λ-supercompact for λ ≥ (2κ)+, then there exists a generic extension in which κ is λ-supercompact and NSκ is precipitous. Thus, for a model with NSκ precipitous over a measurable we need a (2κ)+-supercompact cardinal κ. Jech [J] proved that the precipitous of NSκ over a measurable κ implies the existence of an inner model with o(κ) = κ+ + 1. In §3 we improve this result a little by showing that the above assumption implies an inner model with a repeat point.The paper is organized as follows. In §1 some preliminary facts are proved. The model with NSκ precipitous over a supercompact is constructed in §2.
Equality and lyndon's interpolation theorem
Authors: Motohashi Nobuyoshi 
Published: May 2006

In this paper, we remark on some properties of equality that tend to be neglected and use them to give a proof of an extension of Lyndon's interpolation theorem. Let LK be a first order classical predicate calculus and LK= a first order classical predicate calculus with equality. We assume that LK and LK= have the propositional constant Τ (truth). For each formula F in LK=, let Rel+ (F), Rel− (F), Rel(F), and Fun(F) be the set of all the predicate symbols which occur in F positively, the set of all the predicate symbols which occur in F negatively, the set of all the predicate symbols which occur in F, and the set of all the function symbols which occur in F.Theorem A (Lyndon [5]). Suppose that A and B are sentences in LK such that A ⊃ B is provable in LK. Then there is a sentence C in LK such that:(i) A ⊃ C and C ⊃ B are provable in LK;(ii) and(iii) .The sentence C which satisfies (i), (ii), (iii) in Theorem A is said to be an interpolant for A ⊃ B in Theorem A. Note that condition (iii) is not included in the original form of Lyndon's interpolation theorem (cf. [5]), but we can easily add this condition. Also, there is some obscurity in the original formulation with regard to the equality symbol. For example, Lyndon writes: “The theorem takes the same form whether or not we admit a predicate denoting identity, with suitable axioms, to the predicate calculus” [5, p. 129].
Strongly compact cardinals, elementary embeddings and fixed points
Authors: Abe Yoshihiro 
Published: May 2006

J. Barbanel [1] characterized the class of cardinals fixed by an elementary embedding induced by a normal ultrafilter on Pκλ assuming that κ is supercompact. In this paper we shall prove the same results from the weaker hypothesis that κ is strongly compact and the ultrafilter is fine.We work in ZFC throughout. Our set-theoretic notation is quite standard. In particular, if X is a set, ∣X∣ denotes the cardinality of X and P(X) denotes the power set of X. Greek letters will denote ordinals. In particular γ, κ, η and γ will denote cardinals. If κ and λ are cardinals, then λ<κ is defined to be supγ<κγγ. Cardinal exponentiation is always associated from the top. Thus, for example, 2λ<κ means 2(λ<κ). V denotes the universe of all sets. If M is an inner model of ZFC, ∣X∣M and P(X)M denote the cardinality of X in M and the power set of X in M respectively.We review the basic facts on fine ultrafilters and the corresponding elementary embeddings. (For detail, see [2].)Definition. Assume κ and λ are cardinals with κ ≤ λ. Then, Pκλ = {X ⊂ λ∣∣X∣ < κ}.It is important to note that ∣Pκλ∣ = λ< κ.
Inconsistent models for relevant arithmetics
Authors: Meyer Robert K. , Mortensen Chris 
Published: May 2006

This paper develops in certain directions the work of Meyer in [3], [4], [5] and [6] (see also Routley [10] and Asenjo [11]). In those works, Peano's axioms for arithmetic were formulated with a logical base of the relevant logic R, and it was proved finitistically that the resulting arithmetic, called R#, was absolutely consistent. It was pointed out that such a result escapes incautious formulations of Gödel's second incompleteness theorem, and provides a basis for a revived Hilbert programme. The absolute consistency result used as a model arithmetic modulo two. Modulo arithmetics are not ordinarily thought of as an extension of Peano arithmetic, since some of the propositions of the latter, such as that zero is the successor of no number, fail in the former. Consequently a logical base which, unlike classical logic, tolerates contradictory theories was used for the model. The logical base for the model was the three-valued logic RM3 (see e.g. [1] or [8]), which has the advantage that while it is an extension of R, it is finite valued and so easier to handle.The resulting model-theoretic structure (called in this paper RM32) is interesting in its own right in that the set of sentences true therein constitutes a negation inconsistent but absolutely consistent arithmetic which is an extension of R#. In fact, in the light of the result of [6], it is an extension of Peano arithmetic with a base of a classical logic, P#. A generalisation of the structure is to modulo arithmetics with the same logical base RM3, but with varying moduli (called RM3i here).
Expressive power in first order topology
Authors: Bankston Paul 
Published: May 2006

AbstractAfirst order representation(f.o.r.) in topology is an assignment of finitary relational structures of the same type to topological spaces in such a way that homeomorphic spaces get sent to isomorphic structures. We first define the notions “one f.o.r. is at least as expressive as another relative to a class of spaces” and “one class of spaces is definable in another relative to an f.o.r.”, and prove some general statements. Following this we compare some well-known classes of spaces and first order representations. A principal result is that ifXandYare two Tichonov spaces whose posets of zero-sets are elementarily equivalent then their respective rings of bounded continuous real-valued functions satisfy the same positive-universal sentences. The proof of this uses the technique of constructing ultraproducts as direct limits of products in a category theoretic setting.
QE commutative nilrings
Authors: Saracino D. , Wood C. 
Published: May 2006

If L is a first-order language, then an L-structure A is called quantifier-eliminable (QE) if every L-formula is equivalent in A to a formula without quantifiers.The classification problem for QE groups and rings has received attention in work by Berline, Boffa, Cherlin, Feigner, Macintyre, Point, Rose, the present authors, and others. In [1], Berline and Cherlin reduced the problem for rings of prime characteristic p to that for nilrings, but also constructed countable QE nilrings of characteristic p. Likewise, in [3], we constructed countable QE nil-2 groups. Both results can be viewed as “nonstructure theorems”, in that they provide negative evidence for any attempt at classification. In the present paper we show that the situation is equally bad (or rich, depending on one's point of view) for commutative rings:Theorem 1. For any odd prime p, there existcountable QE commutative nilrings of characteristic p.This solves a problem posed in [1]. We remark that the examples we produce are uniformly locally finite, hence ℵ0-categorical. A more algebraic description is that each of our rings R is uniformly locally finite (in fact, R3 = 0) and homogeneous, in the sense that any isomorphism of finitely generated subrings extends to an automorphism of R.Theorem 1 does not cover the case p = 2, and we show that for commutative rings this case is in fact exceptional:Theorem 2. There exist exactly two nonisomorphic countably infinite QE commutative nilrings of characteristic 2.
3088 varieties: A solution to the Ackermann constant problem
Authors: Slaney John K. 
Published: May 2006

AbstractIt is shown that there are exactly six normal DeMorgan monoids generated by the idntity element alone. The free DeMorgan monoid with no generators but the identity is characterised and shown to have exactly three thousand and eighty-eight elements. This result solves the “Ackermann constant problem” of describing the structure of sentential constants in the logic R.
A hierarchy of families of recursively enumerable degrees
Authors: Welch Lawrence V. 
Published: May 2006

Certain investigations have been made concerning the nature of classes of recursively enumerable sets, and the relation of such classes to the recursively enumerable indices of their sets. For instance, a theorem of Rice [3, Theorem XIV(a), p. 324] states that if A is the complete set of indices for a class of recursively enumerable sets (that is, if there is a class of recursively enumerable sets such that and if A is recursive, then either A = ⌀ or A = ω. A relate theorem by Rice and Shapiro [3, Theorem XIV(b), p. 324] can be stated as follows:Let be a class of recursively enumerable sets, and let A be the complete set of indices for . Then A is r.e. if and only if there is an r.e. set D of canonical indices of finite sets Du, u ∈ D, such thatA somewhat similar theorem of Yates is the following: Let be a class of recursively enumerable sets which contains all finite sets. Let A be the complete set of indices for . Then there is a uniform recursive enumeration of the sets in if and only if A is recursively enumerable in 0(2)—that is, if and only if A is Σ3. A corollary of this is that if C is any r.e. set such that C(2)≡T⌀(2), there is a uniform recursive enumeration of all sets We such that We ≤TC [9, Theorem 9, p. 265].
Linear reasoning in modal logic
Authors: Fitting Melvin 
Published: May 2006

In [1] Craig introduced a proof procedure for first order classical logic called linear reasoning. In it, a proof of P ⊃ Q consists of a sequence of formulas, each of which implies the next, beginning with P and ending with Q. And one of the formulas in the sequence will be an interpolation formula for P ⊃ Q. Indeed, this was the first proof of the Craig interpolation theorem, some of whose important consequences were demonstrated in a companion paper [2]. In this paper we present systems of linear reasoning for several standard modal logics: K, T, K4, S4, D, D4, and GL. Similar systems can be constructed for several regular, nonnormal modal logics too, though we do not do so here. And just as in the classical case, interpolation theorems are easy consequences. Such theorems are well known for the logics considered here. There is a model theoretic argument in [6], an argument using Gentzen systems in [8], an argument using consistency properties in [4] and [5], and an argument using symmetric Gentzen systems in [5]. This paper presents what seems to be the first modal proof that follows Craig's original methods. We note that if the modal rules given here are dropped, a classical linear reasoning system results, which is related to, but not the same as those in [1] and [10].Since the basic linear reasoning ideas are fully illustrated by the propositional case, we present that first, to keep the clutter down. Later we show how the techniques can generally be extended to encompass quantifiers. We do not follow [1] in making heavy use of prenex form, since it is not generally available in modal logics. Fortunately, it plays no essential role.
The decision problem for branching time logic
Authors: Gurevich Yuri , Shelah Saharon 
Published: May 2006

AbstractThe theory of trees with additional unary predicates and quantification over nodes and branches embraces a rich branching time logic. This theory was reduced in the companion paper to the first-order theory of binary, bounded, well-founded trees with additional unary predicates. Here we prove the decidability of the latter theory.