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.

We introduce an implication-with-possible-exceptions and define validity of rules-with-possible-exceptions by means of the topological notion of a full subset. Our implication-with-possible-exceptions characterises the preferential consequence relation as axiomatized by Kraus, Lehmann and Magidor [Kraus, Lehmann, and Magidor, 1990]. The resulting inference relation is non-monotonic. On the other hand, modus ponens and the rule of monotony, as well as all other laws of classical propositional logic, are valid-up-to-possible exceptions. As a consequence, the rules of classical propositional logic do not determine the meaning of deducibility and inference as implication-without-exceptions.

Each Girard quantale (i.e., commutative quantale with a selected dualizing element) provides a support for a semantics for linear propositional formulas (but not for linear derivations). Several constructions of Girard quantales are known. We give two more constructions, one using an arbitrary partially ordered monoid and one using a partially ordered group (both commutative). In both cases the semantics can be controlled be a relation between pairs of elements of the support and formulas. This gives us a neat way of handling duality.

Let G be an infinite abelian p-group and let K be a field of characteristic ≠ p. Let K[G] be the set of all sums Σg∈Gagg where the ag are in K, and all but finitely many ag are 0. Then K[G] is a K-algebra, with multiplication induced by the group multiplication on G.

If G is countable, then the isomorphism type of K[G] has been completely described by S. D. Berman [1]. If G is a direct sum of countable groups, one can also describe K[G], as K[⊕iGi] ≃ ⊗iK[Gi]. If K contains all pn-th roots of unity, then K[G] is isomorphic to the ring of continuous functions from a Boolean space X to the field K with the discrete topology. In that case, the group UK[G] of invertible elements of K[G] is isomorphic to the direct sum of ∣G∣ copies of K×. More generally, if K is of the second kind with respect to p (see below for the definition), the group UK[G] has a simple description.

Consider the subgroup SK[G] of elements Σgagg which have order a power of p and such that Σg ag = 1. This group is of course much simpler than UK[G]. Classifying SK[G] up to isomorphism reduces to the case where G has no element of infinite height, see [7]. If G is a direct sum of cyclic groups then the isomorphism type of SK[G] has been completely determined, in [2, 3, 7, 8]. The aim of this note is to show that a similar result is in general not possible for uncountable G. We use an invariant Γ associated to abelian groups, and for any regular uncountable cardinal κ, exhibit 2κ groups G for which Γ(G) = Γ(SK[G]) are pairwise distinct. Our work is based on a construction of Shelah [9], who constructed 2κ non-isomorphic abelian p-groups of cardinality κ for κ an uncountable regular cardinal.

It is shown that axiomatic extensions of intuitionistic propositional calculus defining univocally new connectives, including those proposed by Gabbay, are strongly complete with respect to valuations in Heyting algebras with additional operations. In all cases, the double negation of such a connective is equivalent to a formula of intuitionistic calculus. Thus, under the excluded third law it collapses to a classical formula, showing that this condition in Gabbay's definition is redundant. Moreover, such connectives can not be interpreted in all Heyting algebras, unless they are already equivalent to a formula of intuitionistic calculus. These facts relativize to connectives over intermediate logics. In particular, the intermediate logic with values in the chain of length n may be “completed” conservatively by adding a single unary connective, so that the expanded system does not allow further axiomatic extensions by new connectives.

We give a proof, valid in any elementary topos, of the theorem of Zermelo that any set possessing a choice function for its set of inhabited subsets can be well-ordered. Our proof is considerably simpler than existing proofs in the literature and moreover can be seen as a direct generalization of Zermelo's own 1908 proof of his theorem.

We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within a factor of . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution. Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs.

We will study several weak axiom systems that use the Subtraction and Division primitives (rather than Addition and Multiplication) to formally encode the theorems of Arithmetic. Provided such axiom systems do not recognize Multiplication as a total function, we will show that it is feasible for them to verify their Semantic Tableaux, Herbrand, and Cut-Free consistencies. If our axiom systems additionally do not recognize Addition as a total function, they will be capable of recognizing the consistency of their Hilbert-style deductive proofs. Our axiom systems will not be strong enough to recognize their Canonical Reflection principle, but they will be capable of recognizing an approximation of it, called the “Tangibility Reflection Principle”. We will also prove some new versions of the Second Incompleteness Theorem stating essentially that it is not possible to extend our exceptions to the Incompleteness Theorem much further.

Reverse mathematics uses subsystems of second order arithmetic to determine which set existence axioms are required to prove particular theorems. Surprisingly, almost every theorem studied is either provable in RCA0 or equivalent over RCA0 to one of four other subsystems: WKL0, ACA0, ATR0 or – CA0. Of these subsystems, – CA0 has the fewest known equivalences. This article presents a new equivalence of – C0 which comes from ordered group theory.

One of the fundamental problems about ordered groups is to classify all possible orders for various classes of orderable groups. In general, this problem is extremely difficult to solve. Mal'tsev [1949] solved a related problem by showing that the order type of a countable ordered group is ℤαℚε where ℤ is the order type of the integers, ℚ is the order type of the rationals, α is a countable ordinal, and ε is either 0 or 1. The goal of this article is to prove that this theorem is equivalent over RCA0 to – CA0.

In Section 2, we give the basic definitions and notation for RCA0, ACA0 and CA0 as well as for ordered groups. For more information on reverse mathematics, see Friedman, Simpson, and Smith [1983] or Simpson [1999] and for ordered groups, see Kokorin and Kopytov [1974] or Fuchs [1963]. Our notation will follow these sources. In Section 3, we show that – CA0 suffices to prove Mal'tsev's Theorem and the reversal is done over RCA0 in Section 4.

In this paper, constructions of free ordered algebras on one generator are given that correspond to some one-variable fragments of affine propositional classical logic and their extensions with n-contraction (n ≥ 2). Moreover, embeddings of the already known infinite free structures into the algebras introduced below are furnished with; thus, solving along the respective cardinality problems.

Let M be an L-structure and A be an infinite subset of M. Two structures can be defined from A:

• The induced structure on A has a name Rφ for every ∅-definable relation φ(M) ∩ An on A. Its language is

A with its Lind-structure will be denoted by Aind.

• The pair (M, A) is an L(P)-structure, where P is a unary predicate for A and L(P) = L ∪{P}.

We call A small if there is a pair (N, B) elementarily equivalent to (M, A) and such that for every finite subset b of N every L–type over Bb is realized in N.

A formula φ(x, y) has the finite cover property (f.c.p) in M if for all natural numbers k there is a set of φ–formulas

which is k–consistent but not consistent in M. M has the f.c.p if some formula has the f.c.p in M. It is well known that unstable structures have the f.c.p. (see [6].) We will prove the following two theorems.

Theorem A. Let A be a small subset of M. If M does not have the finite cover property then, for every λ ≥ ∣L∣, if both M andAindare λ–stable then (M, A) is λ–stable.

Corollary 1.1 (Poizat [5]). If M does not have the finite cover property and N ≺ M is a small elementary substructure, then (M, N) is stable.

Corollary 1.2 (Zilber [7]). If U is the group of wots of unity in the field ℂ of complex numbers the pair (ℂ, U) isω–stable.

Proof. (See [4].) As a strongly minimal set ℂ is ω–stable and does not have the f.c.p. By the subspace theorem of Schmidt [3] every algebraic set intersects U in a finite union of translates of subgroups definable in the group structure of U alone. Whence Uind is nothing more than a (divisible) abelian group, which is ω–stable.

With each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L(G) of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras.

It 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.

This paper looks at the concept of neighborhood canonicity introduced by Brian Chellas [2]. We follow the lead of the author's paper [9] where it was shown that every non-iterative logic is neighborhood canonical and here we will show that all logics whose axioms have a simple syntactic form—no intensional operator is in boolean combination with a propositional letter—and which have the finite model property are neighborhood canonical. One consequence of this is that KMcK, the McKinsey logic, is neighborhood canonical, an interesting counterpoint to the results of Robert Goldblatt and Xiaoping Wang who showed, respectively, that KMcK is not relational canonical [5] and that KMcK is not relationally strongly complete [11].

We introduce a notion of syntactical truth predicate (s.t.p.) for the second order arithmetic PA2. An s.t.p. is a set T of closed formulas such that:

(i) T(t = u) if and only if the closed first order terms t and u are convertible, i.e., have the same value in the standard interpretation

(ii) T(A → B) if and only if (T(A) ⇒ T(B))

(iii) T(∀xA) if and only if (T(A[x ← t]) for any closed first order term t)

(iv) T(∀X A) if and only if (T(A[X ← ∆]) for any closed set definition ∆ = {x ∣ D(x)}).

S.t.p.'s can be seen as a counterpart to Tarski's notion of (model-theoretical) validity and have main model properties. In particular, their existence is equivalent to the existence of an ω-model of PA2, this fact being provable in PA2 with arithmetical comprehension only.

We generalize the result of Mekler and Shelah [3] that the existence of a canary tree is independent of ZFC + GCH to uncountable regular cardinals. We also correct an error from the original proof.

In this paper, two theorems concerning measurable limits of strong cardinals and supercompactness are proven. This generalizes earlier work, both individual and joint with Shelah.

In examples like the total recursive functions or the computable real numbers the canonical indexings are only partial maps. It is even impossible in these cases to find an equivalent total numbering. We consider effectively given topological T0-spaces and study the problem in which cases the canonical numberings of such spaces can be totalized, i.e., have an equivalent total indexing. Moreover, we show under very natural assumptions that such spaces can effectively and effectively homeomorphically be embedded into a totally indexed algebraic partial order that is closed under the operation of taking least upper bounds of enumerable directed subsets.