Andrew Aberdein, Combining Toulmin Layouts

Humanities and Communication
Florida Institute of Technology
Melbourne
Florida 32901-6975
USA

pdf file of abstract

Arnon Avron, Jonathan Ben-Naim & Beata Konikowska, Information Sources Logic

pdf file of abstract

Steve Awodey (joint work with Michael Warren), Predicative Algebraic Set Theory

Carnegie Mellon University

The basic results of Algebraic Set Theory are extended to the case of constructive set theories. Specifically, we identify a constructive set theory CST that is sound and complete with respect to a specified class of algebraic models. Moreover, we show how such models can be constructed in the category of "ideals" (special sheaves) over systems of constructive type theory.

I.I. Batyrshin, Quasi-reducibility and functions without fixed-points

Department of mathematics
Kazan State University

pdf file of abstract

Libor Behounek, An alternative justification of the axioms of fuzzy logics

Institute of Computer Science
Academy of Sciences of the Czech Republic
Faculty of Philosophy
Charles University in Prague

Fuzzy logics are usually introduced by imposing some reasonable constraints on the [0, 1] truth functions of logical connectives, which lead to the notion of (left-)continuous t-norm [1]. However, the Hilbert-style calculi and algebraic semantics of the resulting logics (MTL, BL, Lukasiewicz logic, Goedel logic, etc.) make no reference to the [0, 1] interval, and their completeness w.r.t. the real-valued semantics is often hard to prove. Thus it is reasonable to search for a [0, 1]-independent justification of the axioms of these logics.

The present talk gives a justification which is based on two kinds of fuzzy consequence relations, viz. the "global" (full-truth preserving) one and the "local" (partial-truth preserving) one. The account proceeds in four steps of formalizing their pre-theoretical properties: (i) the intuitive properties of full-truth preservation are those of Tarski structural consequence relations; (ii) the properties of full partial-truth preservation lead to Cintula's class of weakly implicative fuzzy logics [2]; (iii) the properties of partially valid partial-truth preservation, internalized by implication, generate the implicational fragment of MTL (possibly fine-tuned by additional assumptions); finally (iv) by adding further propositional connectives we arrive at usual fuzzy logics.

This account clarifies the position of fuzzy logics in the logical landscape: they can be characterized as intuitionistic non-contractive prelinear logics: intuitionistic and non-contractive, since the laws of double negation and contraction are often inappropriate for fuzzy propositions; and prelinear, since the property of prelinearity corresponds to "measuring" truth along linear scales, which is the distinctive feature of fuzzy logics [3].

[1] Hajek P.: Metamathematics of fuzzy logic. Kluwer, Dordrecht 1998.
[2] Cintula P.: Weakly implicative (fuzzy) logics. To appear in Arch. Math. Logic.
[3] Behounek L., Cintula P.: Fuzzy logics as the logics of chains. Fuzzy Sets Syst. 157 (2006) 604–610.

Adib Ben Jebara, About the attributes of Good and the attributes of a soul

I am using a particular case of the axiom of choice, CC(only 2 through m), the countable axiom of choice for a family of sets of n elements, n=2 through m. see web page of Andreas Blass : http://www.math.lsa.umich.edu/~ablass/dpcc.pdf

In "All things are numbers" of Logic Colloquium 2001, I wrote that the numbers of attributes of Good are Dedekind Cardinals.

Mr Andreas Blass thinks that, in the model of the above web page, the set of Dedekind cardinals is of cardinality the cardinality of the continuum.

Evil has as numbers of attributes only aleph zero and the cardinality of the continuum, see "About the strength of Evil" in ASL Winter Meeting 2004 2005. Good has more numbers of attributes than Evil. That could be one of the strengths of Good, as the numbers of attributes are related to strength, and a superiority to Evil.

One way to think of the attributes of Good is to think of the patterns of good behavior associated to most historical characters. Already so, the numbers of attributes of Good are very numerous.

In "An axiom to settle the continuum hypothesis?" in Logic Colloquium 2004, it was stated that the cardinality of the continuum could be the number of attributes of God related to the immortality of souls. It could be also the number of attributes related to immortality for the soul itself. Attributes of the soul other than immortality, like resisting Evil, make the number of attributes of the soul greater or equal than the cardinality of the continuum.

It is therefore either that that number of attributes is the cardinality of the continuum or between the cardinality of the continuum and 2 power that cardinality (negation of the generalized continuum hypothesis).

Josef Berger, A fan-theoretic equivalent to the antithesis of Specker's theorem

Department of Mathematics and Statistics
Christchurch
New Zealand

We give a classification of the statement "every sequence of real numbers bounded away from each point of [0,1] is eventually bounded away from [0,1]" in constructive reverse mathematics.

Marta Bilkova, Uniform interpolation in provability logics

Department of Logic
Faculty of Philosophy
Charles University
Prague

Institute of Computer Science
Academy of Sciences of the Czech Republic

The uniform interpolation property is a strengthening of the Craig interpolation property. It states that for every formula A and any choice of its propositional variables there exists a post-interpolant I in these variables, such that it serves as an uniform interpolant for any formula B implied by A. Symmetrically, for any B there exists a pre-interpolant. The existence of such interpolants can be seen as a simulation of certain quantifiers ranging over propositional variables.

We investigate uniform interpolation property in propositional modal logics from the proof-theoretical point of view. We prove the uniform interpolation theorem for two modal logics having arithmetical interpretation - GL and Grz. So far, only proofs based on semantics have been presented. Our proof uses terminating sequent calculi for which structural rules are admissible. It provides an explicit algorithm constructing the interpolants.

Piotr Borodulin-Nadzieja, Measures on small Boolean algebras

Institute of Mathematics
University of Wroclaw
Poland

We investigate measures on small Boolean algebras, i.e. Boolean algebras not containing an uncountable independent sequence. We prove that most well-known subclasses of small Boolean algebras (e.g. interval, superatomic) admit only separable measures. It is not the case of retractive algebras: under certain set theoretic axioms every retractive algebra carries only separable measures but it is also consistent to assume that there is a retractive Boolean algebra without this property. We exhibit some connections to topology, e.g. the existence of tree π-bases.

Andrew Brooke-Taylor, Forcing while preserving 1-extendibles

Given a universe containing a 1-extendible cardinal, one may force the global square principle while keeping the cardinal 1-extendible, whereas it is known that global square is incompatible with subcompact cardinals, which are only slightly stronger. The question arises as to whether one may force other combinatorial principles while preserving a 1-extendible cardinal. In certain cases, such as when forcing a morass or breaking GCH, there are subtleties that arise because the domain of the defining embedding for the 1-extendible is only an initial segment of V. We will present partial results regarding overcoming these difficulties.

M.W. Bunder & W.J.M. Dekkers, Are there Hilbert-style Pure Type Systems?

School of Mathematics and Applied Statistics
University of Wollongong
Wollongong, NSW 2522, Australia

Department of Computer Science
Radbout University Nijmegen
Toernooiveld 1
6525 ED Nijmegen, The Netherlands

For many a natural deduction style logic there is a Hilbert-style logic that is equivalent to it in that it has the same theorems (ie valid judgements Γ|–P where Γ=∅). For intuitionistic implicational logic, the axioms of the equivalent Hilbert-style logic can be propositions which are also known as the types of the combinators I, K and S.

Natural deduction versions of illative combinatory logics have an equivalent formulation with axioms that are actual type statements for I, K and S. As pure type systems (PTSs) are, in a sense, equivalent to systems of illative combinatory logic, it might be thought that Hilbert style PTSs (HPTSs) could be based in a similar way.

This paper shows that some PTSs have very trivial equivalent HPTSs, with only the axioms as theorems and that for many PTSs no equivalent HPTSs can exist. Most commonly used PTSs belong to these two classes.

For some PTSs however, including λ* and the PTS at the basis of the proof assistant Coq, there is a nontrivial equivalent HPTS, with axioms that are type statements for I, K and S.

Daniel Busche, AD in L(R) of a generic extension of HOD

We adapt Woodin's core model induction to a choiceless context. Starting from "ZF + all uncountable cardinals are singular" we will show, that the axiom of determinacy holds in L(R) of a generic extension of HOD.

Olivia Breysse & Michel De Glas, On boundaries and contact

CREA
CNRS – Ecole Polytechnique
Paris, France

Mereotopology, which results from the adjunction to mereology of topology, aims at providing a formal framework for the analysis of spatial and spatiotemporal entities that exhibit a topological structure.

However, one may show that most of the various mereotopologies cannot deal conjointly with the concepts of boundary, continuity and contact. Although eminently topological in nature and intimately interrelated – the discontinuous nature of boundaries presupposes continuity and contact occurs at boundaries – these three concepts are mutually incompatible in a mereotopology.

We actually prove that the so-called boundary-based mereotopological theo- ries are bound to be either paradoxical or inconsistent and that this is essentially due to the modelling of some basic intuitive notions by the means of topology. We show that substituting locology for topology leads to a satisfactory solution to the above-mentioned problems and provides the tools for an alternative to mereotopology.

Erica Calardo, A sound and complete axiomatization for the linear logic of knowledge and time LTK

pdf file of abstract

Franqui Solis Cardenas Poloche, Simplified gap 2 morasses and some applications

I am going to give a short account about my PhD thesis where it was proved the consistency of the existence of simplified gap 2 morasses using a little simpler definition of simplified gap 2 morasses due to R. Jensen, and prove some old combinatorial results which were proved with the classical morasses.

Paola Cattabriga, How to release Frege's system from Russell's antinomy

Dipartimento di Filosofia
Universita di Bologna
I-40126 Bologna
Italy

pdf file of abstract

F. Collot, Euclidean set theory

4 rue Mayet
75006 Paris
France

This theory is founded on the construction of a well-ordering on the real numbers set with a partition in an infinity of subsets. Each subset contains an identical number of figures after the virgule as 0,32 and 0,57. Its introduction in trigonometry permit to define the actual infinite of Cantor (noted omega) as a limit of convergent series, and after to show that the natural numbers and the well-ordered real numbers subsets are inscribed on the trigonometric tangent into the successive subsets with a simultaneous and indefinite manner. Then it is proved that there exists one and only one single infinite. That infinite is not a number but a limit.

Other consequences are deduced, but not explained here, as a well-ordering on the alephs, a classical manner to consider the concept of cardinal numbers and applications to a mathematical model for the time of Bergson, to the paradox of Einstein, Podolski and Rosen, and to the Big Bang.

John Corcoran, Different Counterexample Sets for Logically Equivalent Propositions

Philosophy, University at Buffalo
Buffalo, NY 14260-4150

This lecture sharpens discussions in this BULLETIN 11(2005) p. 460 and pp. 554-5.  Two propositions are [logically] equivalent if each is a consequence of the other.  A suitable first-order language is interpreted in the set N of [natural] numbers as universe of discourse.   A number n is a counterexample for a universal proposition ∀x P(x) iff n satisfies ~P(x).  Let n* be a numeral for n.  Given any false ∀x P(x) and any n, the universal proposition ∀y (y = n* → ∀x P(x)) is logically equivalent to ∀x P(x) and has n as sole counterexample – regardless of which counterexamples ∀x P(x) has.  Using disjunctive antecedents as in ∀y ((y = n* ∨ y = m*) → ∀x P(x)), the result generalizes to arbitrary non-empty finite sets of numbers.  More generally, we have the First Counterexample Theorem: given any false proposition F and any non-empty finite set S of numbers, there is a universal proposition logically equivalent to F and having S as counterexample set.  A similar result holds for N: since every proposition P is equivalent to ∀x (x = x → P), every falsehood is logically equivalent to a false universal proposition having the entire set N as counterexample set.  Corollary: given any false proposition F and any two finite sets A and B, there are two universal propositions both logically equivalent to the given falsehood, one having A as its counterexample set and the other B.  Analogous results evidently apply with other languages interpreted in other universes.  Other results will be presented if time permits. Special thanks to Mark Brown (Syracuse), Elizabeth Compton (Buffalo), and Frango Nabrasa (Tampa).

Jeroen Demeyer, Recursively enumerable sets in F_q[x] are diophantine

In 1970, Y. Matiyasevič, building on earlier work by M. Davis, H. Putnam and J. Robinson, proved that every r.e. set in Z is diophantine (i.e. definable using only existential quantifiers). As an immediate consequence, this gives a negative answer to Hilbert's Tenth Problem, namely undecidability for diophantine equations over Z.

Apart from Z, r.e. sets are known to be diophantine over Z[x] (J. Denef, 1978), and O_K[x₁, …, x_n], with O_K the ring of integers in a totally real number field (K. Zahidi, 1999).

We prove the analogous result for F_q[x]. This is done in two steps: First, we give a diophantine interpretation of the ring F_q[x, y] over F_q[x]. Second, we show that every r.e. set in F_q[x] is diophantine over F_q[x, y].

Ioanna Matilde Dimitriou (joint work with Benedikt Loewe), Inaccessibility without choice

ps file of abstract

Henrik Forssell, Ideal models of algebraic set theory

Carnegie Mellon University

We construct algebraic models of intuitionistic set theory in categories of "ideals", which are special sheaves. First, a Basic Intuitionistic Set Theory (BIST) is stated, and the categorical semantics are given. Second, a notion of an ideal over a topos is given, using which one can build a model of BIST in which a given topos occurs as the sets. Thinking of topoi as higher-order theories, this amounts to constructing, for any higher-order theory, a set theoretic universe incorporating the types of that theory as sets, in such a way that the set theory of the universe is a conservative extension of the higher-order theory we started out with. The set theory BIST is shown to be complete with respect to such universes. The approach extends the results of Awodey, Butz, Simpson, and Streicher by introducing a new and perhaps more natural notion of ideal.

Michele Friend, The Relationship Between the Practice of Mathematics and the Philosophy of Mathematics: Or, Should Mathematicians Listen to Philosophers at All?

Department of Philosophy
801 22nd. St. N.W.
George Washington University
Washington D.C. 20052
U.S.A.

As rational agents we are sometimes forced to accept a conclusion which does not agree with us, simply because this is where the argument leads us. Much to my chagrin, I have to conclude that a practicing mathematician should not heed the advice of the philosopher too much. Of course, this is not to say that the same person cannot engage in philosophical discussion, and practice mathematics.

What leads to this conclusion? Let us begin with the simplistic construal of the relationship between mathematicians and philosophers. Either philosophers dictate to mathematicians or they listen to mathematicians. In the first the philosopher prescribes mathematical practice, in the second the philosopher describes.

These simplistic ways of construing the relationship make the relationship unstable, but each relationship is unstable for different reasons. The first is unstable because it varies with the vagaries and findings of philosophy. The second is unstable because the compass of mathematical practice varies; so, we might say that the subject of description changes. The problem is that the instability of the relationship is enough to suggest to the mathematician that he, or she, not pay attention to the philosopher.

There are more complicated relationships between practicing mathematicians and philosophers of mathematics. The more complex relationship is characterised by a mix of description and prescription. The fruitful complex relationship is piecemeal and local.

In conclusion, the best we might say is that the relationship between the mathematician and the philosopher does exist, and can locally lead to changes and modifications in both mathematics and philosophy. However, unfortunately, a wide-spread and stable relationship is not in the offing. In general, the mathematician should not pay too much attention to the philosopher.

Gunter Fuchs (joint work with Joel Hamkins), Degrees of Rigidity for Souslin Trees and Changing the Heights of Automorphism Towers

Various strong notions of rigidity for Souslin trees are investigated and separated, assuming the diamond principle, into a hierarchy. Most of these rigidity properties state that a tree has a certain rigidity property in any model obtained by forcing with the tree itself.

An application to the automorphism tower problem is given, showing that, again assuming diamond, there is a group the height of the automorphism tower of which is highly malleable by forcing with certain Souslin trees. Carrying out the construction at higher cardinality levels gives the full statement on changing the heights of automorphism towers, that was realized by Hamkins and Thomas using proper class forcing, but this time in L, the minimal inner model of set theory: For any cardinal κ, and any ordinal α<κ, there is a centreless group G such that its automorphism tower has height α, but for any β with 1≤β<κ, there is a notion of forcing P, preserving cofinalities and cardinalities, such that in any forcing extension by P, the height of the automorphism tower of the very same group is β.

Murdoch James Gabbay, Nominal Algebra

The Gabbay-Pitts model of alpha-equivalence was followed by Urban et al's Nominal Terms, which are a syntax and semantics for reasoning about syntax-with-binding. Nominal Algebra generalises nominal terms to an algebraic framework, that is, to a framework within which systems with binding, such as lambda-calculi and logics, can be investigated (in new ways) as denotational objects in the style of universal algebra.

The logics and lambda-calculi obtained from nominal algebra specifications are richer than we might think, because they contain meta-variables as first-class elements of their syntax. So for example in "lambda a.t", "t" becomes a first-class piece of syntax representing, not an unknown term, but an unknown denotational object which may mention a!

Similarly, in forall a.phi, phi becomes a first-class piece of syntax representing an unknown truth-value which may mention a, and this in spite of the fact that we have bound a in that unknown predicate --- this is the so-called "one-and-a-halfth-order logic", which has an interesting sequent presentation and proof-theory in its own right.

We will discuss the uses of nominal algebra to axiomatise capture-avoiding substitution, the lambda-calculus, and first-order logic, and describe the resulting systems and their mathematics.

Nikolaos Galatos, Glivenko theorems for substructural logics

pdf file of abstract

Georgi Georgiev (joint work with Tinko Tinchev), Monadic second order logic on equivalence relations

pdf file of abstract

Nina Gierasimczuk & Jakub Szymanik, Hintikka's Thesis Revisited

pdf file of abstract

S.S. Goncharov, Some New Spectrum of Computable Models

pdf file of abstract

Christoph Heinatsch, About the Ramsey-strength of Π¹₂-CA₀

We show that a system of autonomous iterated Ramseyness is prooftheoretically equivalent to Π¹₂-CA₀.

Alex Hellsten, Saturation of the weakly compact ideal

Department of Mathematics
00014 University of Helsinki
Finland

The weakly compact ideal on a weakly compact cardinal is a normal ideal that extends NS_κ|Reg, the non-stationary ideal of κ restricted to regular cardinals. In [1] results on the saturation of NS_κ|Reg for Mahlo cardinals κ are obtained. We use similar methods for investigating the saturation of the weakly compact ideal.

References
[1] Thomas Jech and W. Hugh Woodin, Saturation of the closed unbounded filter on the set of regular cardinals, Transactions of the American Mathematical Society, vol. 292 (1985), no. 1, pp. 345-356.

Brian Hill, A proof semantics for classical logic

Université Paris 1
IHPST
17 rue Racine
75006 Paris
France

The non-deterministic character of proof reduction in classical logic poses a difficulty regarding the identity of proofs: under pain of triviality, one can no longer consider proof reduction as conserving identity of proof, as in the case of intuitionnistic logic. Since it has not been decided what counts as identity between classical proofs, proposing a proof semantics for classical proof becomes a particularly interesting exercise: in fact, one may consider it as the exercise of proposing a notion of identity of (classical) proof.

We shall propose just such a proof semantics, which is motivated by natural intuitions, and in which proofs of sequents are interpreted by Boolean algebras equipped with sets of their elements. Different proofs of the same sequent are interpreted as different algebras. Reduction between proofs is represented by a particular type of order between the algebras. We will prove the soundness of this semantics.

It respects the non-deterministic character of classical proof reduction (in a similar way to, for example, Fuhrmann & Pym, 2005, 2006). It provides two equivalence relations on proofs, which we shall call equality of proof (the proofs have the same interpretation) and equivalence of proofs (their interpretations are equivalent relative the order representing proof reduction). This difference is important: it allows the semantics to satisfy many of the equations proposed by Bellin et al, 2005 for classical proof when understood as equivalences but not when understood as equalities, and inversely to invalidate several of the equations that Bellin et al reject as equalities, whilst satisfying them as equivalences. Finally, it has the rather unique property that eta-redexes and eta-reducts are not necessarily equivalent.

G. Bellin, J. Hyland, E. Robinson, C. Urban, Proof theory of classical propositional classical, Theoretical Computer Science, 2005.
C. Fuhrmann, D. Pym, Order-enriched categorical models of the classical sequent calculus, Journal of Pure Applied Algebra, 204, 2006
C. Fuhrmann, D. Pym, On Categorical Models of Classical Logic and the Geometry of Interaction, http://www.cs.bath.ac.uk/~cf/, 2005.

Daisuke Ikegami, Projective absoluteness under Sacks forcing

University of Amsterdam

It is known that the Sacks measurability of every Delta¹₂ set of reals, that of every Sigma¹₂ set of reals, and the statement that V has more reals than L[r] for any real r, are all equivalent. It is showed that the Sigma¹₃ absoluteness under Sacks forcing is also equivalent to each of them. Also, Sigma¹₃ absoluteness under Sacks forcing is the weakest of all the non-trivial Sigma¹₃ absoluteness. We will see these results and their generalization.

Aleksander Ivanov & Krzysztof Majcher, Nice enumerations of ω-categorical groups

University of Wroclaw

ps file of abstract

Tom Johnstone, Weakly Compact Cardinals Made Indestructible

Department of Mathematics
CUNY Graduate Center
365 Fifth Avenue
New York, NY 10016, US

Large Cardinals may get destroyed or stay preserved after forcing with a particular poset. Determining which cardinals can be made indestructible by various classes of forcing has been of major interest in modern set theory, in part, because such theorems often provide a way of obtaining new independence results. In 1978 Richard Laver proved that given a supercompact cardinal, it can be made indestructible by a very large class of forcings. While lots of indestructibility research has dealt with cardinals stronger than measurable cardinals, in this talk I will address the issue for weakly compact cardinals and for strongly unfoldable cardinals. Both are consistent with V=L. Weakly compact cardinals resemble miniature measurable cardinals, and strongly unfoldable cardinals resemble miniature supercompact cardinals. Given a strongly unfoldable cardinal kappa, I will provide a forcing extension in which the cardinal is indestructible by all kappa-closed, kappa-proper forcing. In particular, the weak compactness of kappa is indestructible. This result sheds light on the major open question of the consistency strength of a fully indestructible weakly compact cardinal.

Pawel Kawa, Extending Baire property and Lebesgue measure by ω₁ sets

Polish Academy of Sciences

We prove that if ZFC is consistent so is ZFC + "for any σ-algebra A, where A ⊆ P(2^ω) is generated by at most ω₁-sets and contains all Borel sets, the Baire property can be extended to A". This is a category analogue of the problem of extending Lebesgue measure to any collection of ω₁ sets.

The results of this paper are a continuation of a work of Carlson and Zakrzewski. We study extensions of Baire Property and Lebesgue Measure in Cohen and Solovay models.

We also sketch how to generalize this result to other cardinals in place of ω₁.

Ruaan Kellerman, Logical Theories of Orthogonality Structures

School of Mathematics
University of Witwatersrand
Johannesburg
Private Bag 3
Wits 2050
South Africa

The geometric relation of line orthogonality in Euclidean space has a rich and interesting elementary theory that captures a substantial and non-trivial fragment of Euclidean geometry. This talk will investigate elementary theories of classes of line orthogonality structures for dimension n ≥ 2. In particular, we will prove that the elementary theory of orthogonality structures for dimension n ≥ 3 is not countably categorical.

Juliette Kennedy (joint work with Saharon Shelah), Square-like Principles and Model Theory

Department of Mathematics and Statistics
University of Helsinki
Helsinki
Finland

In this talk we discuss the consistency of the failure of conjecture 19 of Chang and Keisler's Model Theory: if D is a regular ultrafilter over λ, then for all infinite M, the power M^λ/D is λ⁺⁺-universal, using square- like principles.

Vincent Kieftenbeld (joint work with David de Kloet & Benedikt Loewe), Solovay objects from Blackwell determinacy

Solovay's work of the late 70's showed that the consistency strength of the axiom of real determinacy is considerably higher than that of the axiom of determinacy. We follow the lines of Solovay's analysis and present analoguous theorems for the axiom of (real) Blackwell determinacy. This is joint work with David de Kloet (Vrije Universiteit) and Benedikt Loewe (Universiteit van Amsterdam).

Byunghan Kim (joint work with R. Moosa), Stable definability and generic relations

Criteria for stable definability/determinability and relationship with CM-triviality are given. Those are used to verify structures equipped with generic relations (over stable structures), pseudo-finite fields, and ACFA are neither stably definable nor determinable.

Byunghan Kim (joint work with N. Shi), On weak dividing

We study the notion of weak dividing introduced by S. Shelah. In particular we prove that weak dividing is symmetric if and only if the theory is stable.

Alexei Kolesnikov (joint work with A. Tsuboi & B. Kim), Generalized types and heir bases in simple theories

Department of Mathematics
University of Michigan
Ann Arbor, MI 48109
USA

The study of multi-dimensional amalgamation properties in simple theories is motivated by the question of whether or not a model of a theory fails to interpret a cycle-free hypergraph. More generally, the question can be restated as whether any finite Morley sequence can be extended to an infinite one.

The notions of generalized types and generalized Morley sequences arise naturally in the study of such amalgamation properties. The notion of an "heir base" model for a finite Morley sequence is an important tool in the study of amalgamation properties.

Anton V. Kulakov, Some results on Medvedev degrees of separability

Department of mathematics
Kazan State University

pdf file of abstract

Oliver Kullmann, Finding the error in propositional translations

Computer Science Department
University of Wales Swansea
Swansea, SA2 8PP
UK

Consider checking the consistency of some specification, for example whether a specification of some component produced by some manufacturing process can actually be realised. There are interesting (and successful) applications where+the increasing power of SAT solvers is utilised for this purpose, using some form of propositional translation. If now we find a "bug", that is the propositional translation is inconsistent, then we need to translate this back into the original problem domain, which is problematic, since the translation maps the high level specification into a low level propositional formula, and the inconsistency found will use bits and pieces of different aspects of the original formulation.

In my talk I want to report about the joint work [1], where we studied the algorithmic problems related to the fundamental task of computing for an inconsistent propositional formula in conjunctive normal form (a clause-set) a "good" sub-clause-set explaining the inconsistency.

References
Oliver Kullmann, Inês Lynce, and João Marques-Silva. Categorisation of clauses in conjunctive normal forms: Minimally unsatisfiable sub-clause-sets and the lean kernel. Technical Report CSR 3-2006, University of Wales Swansea, Computer Science Report Series, March 2006.

Robert S. Lubarsky, On the Cauchy Completeness of the Constructive Cauchy Reals

Dept. of Mathematical Sciences
Florida Atlantic University
777 Glades Rd.
Boca Raton, FL 33431 USA

Classically it can be shown that, if the reals are taken to be equivalence classes of Cauchy sequences, then they are Cauchy complete (that is, every Cauchy sequence of reals has a limit). However, the same is not necessarily true in intuitionistic mathematics. In fact, the question itself splits into several variants. In this talk, some of these variants are shown to be independent of standard intuitionistic set theories.

Kerkko Luosto, Graphs and finitely many variables

Department of Mathematics and Statistics
P.O.Box 68 (Gustaf Hällströmin katu 2b)
FIN–00014 University of Helsinki
Finland

Consider the k-equivalence of structures, i.e., the equivalence of structures with respect to sentences (either in first order logic or infinitary finite variable logic) with at most k variables. Given a finite structure A which is k-equivalent to another, nonisomorphic structure, B. Poizat (1982) asked if it is true that A is k-equivalent also to an infinite structure. S. Thomas (1986) showed this is not necessarily the case. Call a structure A like this dubious.

We analyze the properties of dubious graphs with the aim of finding the dubious graph that is smallest in the size. We show that there is a dubious graph with 16 vertices, and all dubious graphs have at least 10 vertices.

Ondrej Majer (joint work with Petr Cintula) Game semantics for Gödel and Product logic

Institute of Philosophy
Academy of Sciences of the Czech Republic
Prague
Czech Republic

Both the areas of mathematical fuzzy logics and game-theoretical semantics have been extensively studied for quite a long time, but their intersection received an attention quite recently. The literature on games in fuzzy logics concentrates on the proof-theoretical features of fuzzy logics and uses the framework of the Lorenzen-style dialogue games (e.g. Fermuller [Fermuller, 2003]). The research on evaluation games reflecting the model theory of fuzzy logics started with the article (Cintula, Majer 2006), providing two kinds of game semantics for Lukasiewicz logic - one of the three most basic fuzzy logics. The aim of this article is to complete the picture and provide a game-theoretic semantics for the remaining two: Gödel and Product logic.

Lukasiewicz logic has nice properties e.g. interdefinability of connectives and prenex normal forms, which allow to give the corresponding games intuitive form. The first game is a generalization of classical evaluation game - it is a zero sum game of two players traditionally called Eloise and Abelard. In the course of the game they take up the roles of Verifier and Falsifier. The game is played over a fixed model M and its positions are given by a formula, an evaluation (over M) and by a degree of validity of the formula (for simplicity we restrict here the set of truth degrees to be the standard interval [0, 1]). The goal of Eloise (the initial Verifier) is to defend the initial degree of validity of the initial formula in the initial evaluation.

The second kind of game ("bargaining game") captures more adequately the idea of fuzzy logic(s) as a logic of degrees of truth. Unlike in the previous game no value of the initial formula is given in advance. It consists of playing only the quantifier prefix of a formula (which consist in choosing a witness for the bounded variable in question). The remaining quantifier-free part of the formula is supposed to be played automatically. This game can be seen as a "bargaining truth" between Verifier and Falsifier as the first one choose the witness to push the degree of validity of the formula up, while the goal of the second one is exactly opposite. It was proven that the Lukasiewicz logic is complete with respect to the both games. (There is a one-one correspondence between the standard Tarskian validity in a model and the existence of a winning strategy for Eloise in the corresponding game).

As Product and Godel logics have different properties than Lukasiewicz logic (eg. non involutive negation), the extension of the proposed games is not straightforward. It has to give rules for a broader set of basic connectives (e.g. there has to be a special move for implication) and due the fact that no prenex normal forms are available, the bargaining game has to be defined in a parameterized form.

References
Fermüller, Christian Georg (2003). Parallel dialogue games and hypersequents for intermediate logics. In Mayer, Marta Cialdea and Pirri, Fiora, editors, Proceedings of TABLEAUX 2003, pages 48-64.
Cintula, Petr and Majer, Ondrej (2006 to appear): Towards Evaluation Games For Fuzzy Logics, in: Logic, Games, Philosophy, Majer, O., Pietarinen, A. , Tulenheimo, T. (eds.), Springer, to appear in 2006.
Hájek, Petr (1998). Metamathematics of Fuzzy Logic, volume 4 of Trends in Logic. Kluwer, Dordercht.
Hintikka, Jaakko and Sandu, Gabriel (1997). Game-theoretical semantics. In van Benthem, Johan and ter Meulen, Alice, editors, Handbook of Logic and Language, pages 361-410. Elsevier Science B.V. / The MIT Press, Oxford/Shannon/Tokio/Cambridge (Massachusetts).

Larisa Maksimova, Weak interpolation in equational logic

Institute of Mathematics
Siberian Branch of Russian Acad. Sci.
630090, Novosibirsk
Russia

pdf file of abstract

Maciej Malicki, A characterization of locally compact Polish subgroups of S_∞

Department of Mathematics
University of Illinois at Urbana-Champaign

Consider the following question: Is it true that if some nonempty open subset of a Polish group G can be covered by a finite union of two-sided translates of any other nonempty open set, then G is locally compact? This is by no means immediate since it does not hold in general that Polish groups admit a compatible metric with respect to which all two-sided translates of sets with small diameter have small diameter.

The answer turns out to be in the positive in the realm of Polish subgroups of S_∞. This result has consequences for the structure of left Haar null sets and, possibly, actions of non-locally compact groups.

I also study from this perspective certain particular examples of other groups, among them the group of isometries of the Urysohn space and the unitary group of the separable Hilbert space.

Gianarturo Marco, The Dynamics of Reference: Orbits and Points

Turin
Italy

Aim of this paper is to outline a mathematical foundation of the notion of reference, ubiquitous to various areas of mathematics, logic, philosophy of language and natural language semantics.

In particular, we introduce the notion of"orbital reference": this rises in the realm of automorphism group actions on the space of interpretations for a given countable language.

In this setting the classical notion of reference unravels its functional structure: namely, it appears as a variety of definable point-re-identification maps within a suitable space of recognition (i.e.: a Polish G-space X, where X is Polish space and G is a closed group of transformations acting continuosly on X (1). The complexity of the orbital reference for a given referring term t heavely depends on the algebraic and topological properies of the group stabilizer of the term t. One of the main consequences of our approach is that the Fregean notion of compositionality, accordingly with the referential variety, spreads out into a variety of patterns of compositionality. Such a variety of patterns rests upon the complexity spectrum of the invariant complete codes reducing the orbital spaces induced by the group actions.

Examples from Model Theory, like coordinatization for relively categorical theories over a predicate, give evidence for the independence of our notion of oprbital reference from the Russellian notion of ostensive denotation.It is just on its going beyond the denotational character that our concept of orbital reference turns out to be of crucial interest in the determinacy of semantic games for anaphoric co-reference: as pointed out by G. Sandu (2), the demonstrative, deictic notion of reference is unfit for semantic games on anaphoric co-reference whenever the anaphoric link occurs within the scope of a negation, We define a point-reidentification game that settles the problem of determinacy of coreference anaphoric link in negative contexts.

Last, but not least, we give evidence also for the fact that "rigidity" is not a property intrinsic to the pure denotational "nature" of reference: rather it belongs to the automorphism group of a given structure.

References
H. Becker/H.S. Kechris: The Descriptive Set Theory of Polish Group Actions. Cambridge University Press, 1996.
G. Sandu: On The Theory of Anaphora: Dynamic Predicate Logic vs. Game-Theoretical Semantics. In: Linguistics and Philosophy 20, 1997.

Alberto Marcone, Interval orders and reverse mathematics

Università di Udine
Italy

A partial order (P, ≤_P) is an interval order if the elements of P can be mapped to intervals of a linear order so that p ≤_P q holds iff every element of the interval associated to p precedes every element of the interval associated to q. Interval orders occur quite naturally in many different areas.

We study interval orders from the viewpoint of reverse mathematics, establishing the logical strength of the equivalences of various formalizations in second order arithmetic of the notion of interval order. We also establish the proof-theoretic strength of the basic characterization theorem for interval orders: a partial order is an interval order if and only if it does not contain a copy of the partial order 2⊕2.

Our proofs yield also results that can be viewed as examples of computable mathematics.

Alexander G. Melnikov, Lempp's question for torsion free abelian groups of finite rank

Novosibirsk State University
Novosibirsk
Russia

Steffen Lempp asked (unpublished): Does a structure with representations in all non-recursive degrees have a recursive representation? T. Slaman and S. Wehner independently built a structure, that has all non-recursive entations, but has no recursive one. In the other hand, R. Downey and C. Jockusch showed that every low boolean algebra is isomorphic to recursive one (J. Knight and M. Stob generalized this for low₄). In this context the wish to get such results for torsion free abelian groups (TFAG) is rather natural. In we showed that the result of R. Downey and C. Jockusch does not hold for TFAG: there exists low non-recursive TFAG. Our present result is:

Theorem 1. If TFAG of finite rank has all non-recursive copies, then it must have a recursive copy.

Russell Miller, Computable Categoricity and Fields

We present work in progress on the question of which fields are computably categorical. A computable structure A is computably categorical if, for every computable structure B isomorphic to A, there exists a computable isomorphism from B onto A. Algebraic characterizations of this property have been found for such theories as linear orders, Boolean algebras, trees, and ordered Abelian groups, by researchers including Dzgoev, Goncharov, Lempp, McCoy, Miller, Remmel, and Solomon. Fields have proven to be more challenging in this regard, but we will offer partial results relating the computable categoricity of a field (and also its ∅'-computable catgoricity) to its normality and its transcendence degree as an extension of its prime filed.

Portions of this work are joint with Hans Schoutens.

Sheila Miller, A Division Algorithm for the Free Algebra on Many Generators

University of Colorado at Boulder
Department of Mathematics
Boulder
Colorado 80309
USA

The left distirbutive algebras (algebras satisfying the LD-law a(bc) = (ab)(ac)) which occur in classical math are idempotent, hence not free. The free left distributive algebra A on one generatotr is representable as the span of an elementary embedding j : V_λ → V_λ (Laver) and is a subset of the braid group under a certain operation (Dehornoy). Ways in which A—and more generally the free algebra A_κ on κ-many generators—are known or conjectured to be "well-founded" will be discussed. We wil present a division algorithm theorem for the elements of A_κ. The algorithm, improving one of Laver for the one generator case, takes place not in A_κ but in P_κ—the result of enlarging A_κ to freely add a composition operation. It is hopped that this will be useful in solving a conjecture of J. Moody on A_κ.

Grigori Mints, A simplified cut elimination for ID1ε

Dept. of Mathematics
Stanford University
Stanford
Ca 94305
USA

ps file of abstract

Ryszard Mirek, Algebraization of non-classical logics

Institute of Logic
Pedagogical University of Krakow
Poland

ps file of abstract

Wojciech Moczydlowski, Normalizing Curry-Howard isomorphism for intuitionistic set theory

We define a lambda calculus corresponding to proofs in a non-extensional version of intuitionistic set theory IZF. We show weak normalization of the calculus and use it to prove the disjunction, numerical existence and term existence properties of the theory.

Marcin Mostowski & Jakub Szymanik, Computational complexity of some Ramsey quantifiers in finite models

pdf file of abstract

Raja Natarajan, First-order frameworks of mobility

School of Technology & Computer Science
Tata Institute of Fundamental Research
Mumbai 400 005
India

In the design space of models for concurrency, there are two paradigms that are known to possess a wide ranging expressive power, namely the "concurrent constraint paradigm" and the "pi-calculus." The expressive power of these paradigms essentially derives from their ability to model the key notion of "mobility" elegantly, within a first-order framework. These two paradigms appear to be completely divergent from each other, since they evolved from distinct sub-disciplines of computer science. The differences in the primitives of the two paradigms gives them their distinct flavour, but also makes the task of relating them a non-trivial one. We relate these two models of mobile computation, by defining a minimal calculus which contains the core features of the concurrent constraint paradigm, and by constructing a semantic-preserving embedding from it to the pi-calculus.

Cyrus F. Nourani, Functorial Models, Generic Sets, and Recursion Urlements

Computability with functorial, generic, and admissible sets are presented. Urlements and fragment consistent models are applied to computable KPU recursion and Peano models towards specific computability questions. Specifc genericity concepts are presented as example applications.

pdf file of abstract

David Pierce, Vector-spaces over unspecified fields

Mathematics Department
Middle East Technical University
Ankara 06531
Turkey

In the Elements, Euclid of Alexandria gives a geometric formulation of certain field-theoretic identities; for example, the identity

x²−y²=(x+y)(x−y)

is Euclid's Proposition II.5, but Euclid expresses in terms of the squares and rectangles bounded by certain lines. At the beginning of the Geometry, René Descartes shows how lines can be multiplied to produce lines rather than rectangles, if one line is chosen as unit. The construction justifies Descartes's algebraic treatment of geometry.

A model-theoretic version of Descartes's construction is that the theory of vector-spaces (as one-sorted structures, but over unspecified fields) can be axiomatized in the signature of abelian groups with a predicate for parallelism (binary linear dependence). The existentially closed models of this theory are two-dimensional spaces (over algebraically closed fields). If a predicate for n-ary linear dependence is introduced to the language, then the existentially closed models of the expanded theory are n-dimensional. In particular, a vector-space of dimension greater than n embeds in a space of dimension n so as to preserve independence in all n-element sets of vectors. This might be compared with the observation that existentially closed field-extensions have transcendence-degree one.

S. Yu. Podzorov, Distributive upper semilattices with Σ⁰₃-representations

pdf file of abstract

Francesca Poggiolesi, Sequent Calculus for Modal Logic

University of Paris 1

University of Florence
Department of Philosophy
52, via Bolognese
50132, Florence
Italy

In my talk, I will present a new sequent calculus for the principal systems of modal logic: K, KT, KB, K4, S4 and S5. This calculus is the first modular, analitic, general, and completely synyactic calculus to satisfy the subformula property and the Dosen principle. Furthermore, it is extremely natural. I will prove validity, completenes and cut elimination theorems for this calculus.

Tomasz Polacik, Partially-elementary extension Kripke models and subtheories of Heyting Arithmetic

Institute of Mathematics
University of Silesia
Katowice, Poland

A Kripke model for a first order language can be viewed as a family of classical structures for that language, called the worlds of the model, partially ordered by the (weak) submodel relation. However, in case of certain intuitionistic theories the relationship between the worlds of their models can be stronger. We study partially-elementary extension Kripke models that is the models whose usual ordering relation is replaced by a stronger relation of being an elementary submodel with respect to some class of formulae. We offer characterizations of partially-elementary extension Kripke models both in terms of forcing certain intuitionistically meaningfull schemata and the relationship of forcing and classical satisfiability at the worlds of a model. We also present some applications of partially-elementary Kripke models in case of subtheories of Heyting Arithmetic and show that the properties of their models differ much from the properties of models of the full theory.

Giuseppe Primiero, A constructive type-theoretical Interpretation of the philosophical Methods of Abstraction and Instantiation

pdf file of abstract

Dieter Probst, Fixed points in non-standard models of subsystems of second order arithmetic

pdf file of abstract

Vadim Puzarenko, One reducibility on Admissibles

IM SD RAS
Novosibirsk

pdf file of abstract

Gemma Robles, José M. Méndez & Francisco Salto, Relevance logics, paradoxes of consistency and the K rule

ps file of abstract

Wim Ruitenburg, Ways to build intuitionistic theories that admit quantifier elimination

Department of Mathematics
Marquette University
P.O. Box 1881
Milwaukee, WI 53201
USA

We present methods by which to construct new intuitionistic theories that admit quantifier elimination, from known ones. These methods involve the construction of special Kripke models for these new theories, from Kripke models of known ones. The intuitionistic theories can be made so that they are in some sense very intuitionistic.

Literature
Ruitenburg, W. Very intuitionistic theories and quantifier elimination. The Review of Modern Logic, Vol. 10 Nos. 1 & 2.

V.V. Rybakov, Decidability Variants of Linear Temporal Logic LTL w.r.t. Logical Consecutions

Department of Computing and Mathematics
Manchester Metropolitan University
Chester Street, Manchester M1 5GD
UK

pdf file of abstract

Pavel Schreiner, Recognition of the Craig Interpolation Property and Projective Beth Property in the local tabular positive calculus

Institute of Mathematics
Siberian Branch of Russian Academy of Science

ps file of abstract

Peter Schuster (joint work with Bernhard Banaschewski), The Shrinking Principle and the Axiom of Choice

The axiom of choice is equivalent to the principle that every indexed cover of a set has a refinement with the same index set which is a partition.

Marina Semenova, Embedding lattices into subsemigroup lattices

pdf file of abstract

Tamara Servi, Effective methods for the real exponential field: some remarks

A. Macintyre and A. Wilkie have shown in their paper [On the decidability of the real exponential field (1996)] that Schanuel's Conjecture implies the decidability of the real exponential field. They have also shown that the Last Root Conjecture (which says that there is a recursive bound on the norm of all regular solutions of systems of n exponential polynomials in n variables) is actually equivalent to the decidability problem. We propose two new conjectures, which we prove to be equivalent to the decidability problem. We rephrase the problem in terms of recursive axiomatizations and er discuss the axioms proposed. We exhibit some fragments of the theory of the real exponential field which can be proved to be R.E. without assuming any conjecture

Ian Sharpe, A Strong Chang Conjecture

ps file of abstract

Alexandra Sirokofski (joint work with C. Dimitracopoulos), On a problem of J. Paris

pdf file of abstract

Alexandra Soskova, Properties of Relative Spectra

Sofia University

pdf file of abstract

Bas Spitters, Applying pointfree topology to Riesz spaces

I will show how to mechanically remove the axiom of choice from a proof in Riesz space (vector lattice) theory. Thus obtaining an elementary proof and a more general result. This is part of a general theme to develop mathematics observationally, connecting ideas by Kolmogorov, von Neumann and Segal on the one hand and point-free (aka formal) topology on the other. This provides a nice illustration how ideas from logic (proof theory) can be used to obtain mathematical results.

Jack Stecher (joint work with Mark van Atten), Using Brouwer's continuity principle to pick stocks

Department of Accounting, Auditing and Law
Norwegian School of Economics and Business Administration
Helleveien 30
N-5045 Bergen
Norway

IHPST (Paris 1/CNRS/ENS)
13 rue du Four
F-75006 Paris
France

The purpose of this talk is to show that intuitionistic reasoning in general, and Brouwer's continuity principle in particular, can provide insights into the behavioral sciences that are classically unattainable. Our setting is an economic application.

In financial economics, many formulae have been proposed for estimating the intrinsic worth of a share of stock. These formulae all involve the present value an infinte series, such as expected future dividends (favored by researchers in finance or economics) or expected future earnings (favored by those in accounting). It has been argued since at least the 1930s that these formulae are logically equivalent, and therefore that researchers should get the same estimated value for every company at every date, irrespective of which approach they choose. In practice, empirical researchers invariably report different results, with the earnings-based approach generally outperforming the dividends-based approach (measured by closeness to observed market prices).

One explanation for this empirical finding is that the logical equivalence depends critically on reasoning about infinite sequences: for arbitrarily large finite sequences, the dividends-based valuation need not be even remotely close to the earnings-based valuation. Thus the equivalence argument depends on a stronger than intuitionistic logic.

We show that these two approaches to valuation are intuitionistically quite different, and that only the earnings approach satisfies Brouwer's continuity principle. Thus the better observed performance of the earnings-based approach reflects the fact that estimated values are insensitive to assumptions about an infinitely remote future.

Lastly, we show how the continuity principle can address additional puzzles concerning dividends. We view the omission of a promised dividend as the lifting of a provisional restriction; this enables us to explain the market's reaction to dividend omissions, which has previously been seen as anomalous.

Alexey Stukachev, Presentations of structures in admissible sets and on natural numbers

Sobolev Institute of Mathematics
Acad. Koptyuga Avenue 4
Novosibirsk
630090, Russia

pdf file of abstract

Giuseppina Terzo, Solutions of exponential polynomials

Dipartimento di Matematica
Università di Napoli "Federico II"

We consider solutions of polynomials in the complex exponential field and in a Zilber's field (see [Z]).

In particular we look for solutions of the type (z₁,...,z_n,E(z₁),...,E(z_n)) in the above fields. Moreover we want to describe those exponential polynomials which do not have any zeros in a Zilber's field.

References
[Z] B. Zilber: Pseudo-exponentiation on algebraically closed fields of characteristic zero, Annals of Pure and Applied Logic, Vol 132, No 1, 2004.

Katie Thompson, Global universality results and internal consistency

Kurt Goedel Research Center for Mathematical Logic
Vienna
Austria

When no universal model exists for a set of structures, it is natural to consider the complexity (or covering number) - that is, the minimal cardinality of a family of structures which together embed the rest. It has been shown that is consistent that the complexity for posets which omit large chains can be any cardinality with cofinality greater than the size of the poset (for posets of regular, uncountable size). In joint work with Sy-David Friedman, we have taken this a step farther and globalised this result. That is, one can simultaneously fix the complexity of such posets for all regular uncountable cardinals. It is also shown that this class forcing extension is internally consistent.

Carlo Toffalori (joint work with Gena Puninski & Vera Puninskaya), Decidability of the theory of modules over commutative valuation domains

University of Camerino
Department of Mathematics and Computer Science
Via Madonna delle Carceri 9
62032 Camerino
Italy

We consider modules over an "effectively given" commutative valuation domain V. It is well known that, if the value group of V is isomorphic to the ordered group of integers, then V-modules have a decidable theory. We deal with an opposite case, when the value group is dense and archimedea. We show that the theory of V-modules is decidable even under this assumption.

Joel Uckelman, Two Reactive Modal Logics

Institute for Logic, Language, and Computation
University of Amsterdam
Amsterdam
The Netherlands

Dov Gabbay proposed (in an unpublished draft) a relational modal logic in which the relational structure may change as formulas are evaluated on it. We explore the properties of two such relational logics, and provide axiomatizations for them.

Sara L. Uckelman, Paraconsistent Logic in the Middle Ages

Institute for Logic, Language, and Computation
University of Amsterdam
Amsterdam
The Netherlands

A paraconsistent logic is one which denies the ex contradictione quodlibet rule, i.e., the rule that from a contradiction, anything can be derived. Traditionally, paraconsistent logic is held to have been first developed at the turn of the 20th century. However, there are examples of medieval logicians who reject the validity of the ECQ rule, in particular William of Ockham in his Summa totius logicae. We investigate the arguments these medieval logicians give against the ECQ rule, and consider whether or not the resulting systems can plausibly be considered paraconsistent.

Geert Vernaeve & Albert Hoogewijs, A tale of two substitutions

Ghent University
Galglaan 2
B-9000 Gent
Belgium

ps file of abstract

Andreas Weiermann, Renormalization and Universality for Gödel incompleteness

The talk is about phase transition phenomena for first order Peano Arithmetic. The idea is to study true assertions which are provable for small values of the order parameter and unprovable for large values. In this situation there will be a natural phase transition threshold which locates the jump from provability to unprovability. Inspired from ideas stemming from theoretical physics we investigate renormalization and universality phenomena in this context. We present a selection of corresponding results which have been obtained so far. It will turn out, for example, that the phase transition thresholds in various examples have quite often the same form.

Roman Wencel, On the property of strong cell decomposition for weakly o-minimal structures

Wroclaw University
Poland

A totally ordered structure M=(M,≤,...) is said to be weakly o-minimal iff all subsets of M definable in M are finite unions of convex sets. As weak o-minimlity is not preserved under elementary equivalence, we cannot hope for a reasonable cell decomposition theorem in the weakly o-minimal setting.

Strong cell decomposition is a property of weakly o-minimal structures generalizing the cell decomposition for o-minimal structures (i.e. by definition every o-minimal structure has the strong cell decomposition). If M=(M,≤,+,...) is a weakly o-minimal expansion of an ordered group such that the only subgroups of (M,+) definable in M are {0} and M, then M has the strong cell decomposition property. During my talk I am going to discuss some consequences of the strong cell decomposition property related to the structure of definable sets and definable groups.

M.M. Yamaleev, n-c.e. sets CEA in c.e. degrees

Kazan State University
Kazan
Russia

pdf file of abstract

Anna Zalewska, Formalized system of algorithmic logic and procedures

A certain formalized system of algorithmic logic (AL) with procedures is presented. In the system algorithmic properties of programs with procedures can be proved.

The system is an extension of a certain Gentzen-like system for AL with program variables.It uses the notion of a tree of sequents as a basis tool. Algorithmic language is extended by new constructs: block and procedures. A procedure text is treated as a text constant. The declaration of procedure is treated as an assignment of the text constant to the name of the procedure. New Gentzen-like inference rules for the language are proposed.

Soundness and completeness of the system (extended in this way) are discussed from the point of view of procedure complexity.

Xunwei Zhou, Second level hypothetical inference is better than deduction theorem

Institute of Information Technology
Beijing Union University
97 Beisihuandong Road
Beijing
China

In classical logic, we cannot prove a theorem directly. Deduction theorem transforms theorem proving into fact proving. For example, if we we want to prove int(x)→real(x) from in(x)→rat(x) and rat(x)→real(x), then we regard int(x) as additional premise and prove real(x). This is done as follows (to simplify the inference, we do not consider quantifiers):

(1)	int(x)	additional premise
(2)	int(x)→rat(x)	P
(3)	rat(x)	T, (1), (2), MP
(4)	rat(x)→real(x)	P
(5)	real(x)	T, (3), (4), MP
(6)	int(x)→real(x)	CP rule

In mutually-inversistic logic, however, we have as inference rule the second level hypotheitcal inference (SLMP), which takes logical theorem, say, {P≤^-1Q} ∧ {Q≤^-1R} ≤^-1 {P≤^-1Q} ( ≤^-1means sufficient condition) as the major premis, takes mathematical theorems, say, {int(x)≤^-1rat(x)} ∧ {rat(x)≤^-1real(x)} as the minor premise, infers mathematical theorem, say, int(x)≤^-1real(x). The inference mentioned above is done as follows:

(7)	int(x)≤-1rat(x)	P
(8)	rat(x)≤-1real(x)	P
(9)	{int(x)≤-1rat(x)} ∧ {rat(x)≤-1real(x)}	T, (7), (8), Conjunction rule
(10)	{P≤-1Q} ∧ {Q≤-1R} ≤-1 {P≤-1Q}	P
(11)	int(x)≤-1real(x)	T, (9), (10), SLMP

From this example we observe that in mutually-inversistic logic, a theorem can be proved directly. So, mutually-inversistic logic is better than classical logic in this respect.

Maxim Zubkov, Strongly η-representable sets

Kazan
Russia

I will talk about a classification of strongly η-representable Δ₃ degrees. In particular, I'll construct a Δ₃ set A such that any noncomputable set B≤TA is not strongly η-representable. In another way, I'll show that a set-theoretical difference of two Σ₂ sets is a strongly η-representable.

A infinite set A={a₀<a₁<...} is called a strongly η-representable, if there is a computable linear ordering of order type η+a₀+η+a₁+... A degree a is called a strongly η-representable, if a contains a strongly η-representable set.

Norma B. Goethe (chair/introduction), Danielle Macbeth, Philippe de Rouilhan & Sanford Shieh, Panel on Frege's Begriffsschrift

Panelists
Sanford Shieh, Department of Philosophy, Wesleyan University, CT, U.S.A.
Philippe de Rouilhan, IHPST, Paris, France
Danielle Macbeth, Department of Philosophy, Haverford College, PA, U.S.A.

Chair/Introduction
Norma B. Goethe
University of Cordoba
Argentina

Presentation
The Panel on Frege's "Begriffsschrift" proposes to discuss Macbeth's recent book Frege's Logic (Harvard University Press 2005) on Frege's bidimensional notation. In this panel discussion the author will meet two critics of this work. Two critics will offer their assessment of the new book on Frege's conception of logic. The author will then reply to the papers by Sanford Shieh ("Quantification and the Nature of Frege's Logic") and Philippe de Rouilhan ("What characterization of a logic does one have in mind when speaking of a 'standard reading' of Frege's logic?")

Reply to Sanford Shieh and Philippe de Rouilhan by Danielle Macbeth
There is a familiar drawing that regarded one way looks like a drawing of the head of a duck and regarded another way like the head of a rabbit. Frege's Begriffsschrift notation is like such a drawing: there are two quite different ways of regarding it. One way, due ultimately to Russell, is very familiar; in my book I aim to teach my reader the other. The difference between them can be illustrated by way of a simple example from arithmetic that Frege discusses in Grundlagen: 1 + 1 + 1 = 3. On the standard model-theoretic conception of language, such a sentence is taken to be composed of antecedently meaningful parts. In particular, each tokening of the numeral '1' designates the number one, and the sentence itself expresses the fact that the number one and the number one and the number one together equal three. Frege argues that this cannot be right because there is only one one and no amount of putting one together with itself will produce anything other than one. Frege's own view is that we should understand the primitive signs of arithmetic as only expressing a sense prior to their use. The signs are then put together to form a sentence that expresses a thought, and that thought can then be analyzed into function and argument in various ways, none of which are privileged. The sentence '1 + 1 + 1 = 3' can be taken to involve, for instance, the function ξ + 1 + 1 = 3 with the number one as argument. Alternatively, we can take the object names '1 + 1 + 1' and '3', both of which designate the number three (though they do so under different modes of presentation), to designate the arguments for the two-place relation ξ = ζ. And so on. So read the sentence does not present objects as thus and so. Instead it expresses a sense. Only relative to an analysis into function and argument are objects and concepts designated by the subsentential expressions of the language so conceived. I argue in my book that Frege's Begriffsschrift notation functions in just the same way.

Shieh argues that my reading is implausible; and he does so, I will argue, because he sees only the Russellian duck. Seeing only the Russellean duck, he tries to assess various claims I make piecemeal, independent of the picture within which they are embedded, and then, understandably enough, cannot appreciate the motivation for them. If what you see is the Russellian duck, no amount of argument will convince you that the duck's bill is really a pair of rabbit ears. You need to get the rabbit into view.

De Rouilhan argues that there is nothing that could be called the standard reading of Frege's logic against which to set my reading. In one sense this is correct. There are many readings of Frege available. It is what they all share that I wish to take issue with, and that is the underlying conception of language as functioning in a certain way, namely, by way of meaningful primitives that are then combined to form sentences the meanings of which are to be understood by appeal to truth-conditions. In Begriffsschrift, signs, whether simple or complex, designate only relative to an analysis of a sentence that expresses a thought and designates a truth-value.

Philippe de Rouilhan, What characterization of a logic does one have in mind when speaking of a "standard reading" of Frege's logic?

IHPST
Paris
France

In her book Macbeth argues that Frege's Begriffsschrift notation, i.e. his two dimensional way of writing is like a drawing in the sense that there may be different ways of looking at it. In particular, she thinks that there are two quite different ways of reading Frege's notation. One way, is the "standard way of reading" Frege's logic which, she claims, is ultimately due to Bertrand Russell.

According to the author, this is the most common way of reading Begriffsschrift sentences. She thinks that this is indeed a very familiar way to read Frege's script we were all brought up with but once we overcome this sense of "the familiar", we can conceive of another "novel way" of understanding it and we can learn to read it differently. To teach her readers this novel way of reading Begriffsschrift is the aim of her book.

But it is far from clear what the "standard reading" of Frege's logic is supposed to look like. We are told that on this standard reading Frege's logic is "quantificational logic". This would seem to include the assumption that "quantificational logic" is well known and sharply defined. However, what exactly is the so-called quantificational logic that Frege's logic is apparently not?

In my paper I shall argue that in the context of Macbeth's book the very idea of a "standard reading" of Frege's logic remains too vague and undetermined for this notion to be able to play the role that the author would like it to play.

Sanford Shieh, Quantification and the Nature of Frege's Logic

Department of Philosophy
Wesleyan University
CT
USA

In Frege's Logic, Danielle Macbeth argues against the widespread assumption that Frege is one of the discoverers of modern polyadic quantificational logic, and in favor of taking Frege's logical language to subserve an expressivist and inferentialist project similar in spirit to that of Robert Brandom.

In this paper I examine some of the evidence in Frege's writings for Macbeth's interpretation, focusing on her claims about the non-quantificational status of Frege's "Begriffsschrift" symbols, and on her account of the subject matter of logic for Frege. I raise some difficulties for Macbeth's interpretive arguments based on Frege's explanations of "Begriffsschrift" and his mathematical practice in Grundgesetze der Arithmetik. Specifically, I argue that attempts to interpret Frege's explanations of his symbols as non-quantificational are implausible, and that some of Frege's derivations are difficult to account for non-quantificationally. I conclude that Frege's writings fail to support Macbeth's interpretation unequivocally.

However, I also argue that there is an aspect of Frege's thought about logic that might provide motivation for Macbeth's attempt to account for his logic in non-quantificational terms. This is Frege's repeated characterization of the laws of logic as the most general standards of correctness for judgment. There are difficulties for explaining such a characterization quantificationally, which supports the attempt to find a non-quantificational explanation. But on my reading these difficulties may simply indicate tensions in Frege's commitments on the nature of logic.