<p>In this thesis we use the syntactic-semantic method of constructive type theory to give meaning to classical logic, in particular Gentzen's LK.</p><p>We interpret a derivation of a classical sequent as a derivation of a contradiction from the assumptions that the antecedent formulas are true and that the succedent formulas are false, where the concepts of truth and falsity are taken to conform to the corresponding constructive concepts, using function types to encode falsity. This representation brings LK to a manageable form that allows us to split the succedent rules into parts. In this way, every succedent rule gives rise to a natural deduction style introduction rule. These introduction rules, taken together with the antecedent rules adapted to natural deduction, yield a natural deduction calculus whose subsequent interpretation in constructive type theory gives meaning to classical logic.</p><p>The Gentzen-Prawitz inversion principle holds for the introduction and elimination rules of the natural deduction calculus and allows for a corresponding notion of convertibility. We take the introduction rules to determine the meanings of the logical constants of classical logic and use the induced type-theoretic elimination rules to interpret the elimination rules of the natural deduction calculus. This produces an interpretation injective with respect to convertibility, contrary to an analogous translation into intuitionistic predicate logic.</p><p>From the interpretation in constructive type theory and the interpretation of cut by explicit substitution, we derive a full precision contraction relation for a natural deduction version of LK. We use a term notation to formalize the contraction relation and the corresponding cut-elimination procedure.</p><p>The interpretation can be read as a Brouwer-Heyting-Kolmogorov (BHK) semantics that justifies classical logic. The BHK semantics utilizes a notion of classical proof and a corresponding notion of classical truth akin to Kolmogorov's notion of pseudotruth. We also consider a second BHK semantics, more closely connected with Kolmogorov's double-negation translation.</p><p>The first interpretation reinterprets the consequence relation while keeping the constructive interpretation of truth, whereas the second interpretation reinterprets the notion of truth while keeping the constructive interpretation of the consequence relation. The first and second interpretations act on derivations in much the same way as Plotkin's call-by-value and call-by-name continuation-passing-style translations, respectively.</p><p>We conclude that classical logic can be given a constructive semantics by laying down introduction rules for the classical logical constants. This semantics constitutes a proof interpretation of classical logic.</p>

<p>Genom att analysera domstolsmaterialet från rättegången mot fildelningssiten The Pirat Bay, i relation till en idéhistorisk diskussion om äganderätt, har uppsatsen funnit att den liberala tanketraditionen och dess juridiska institutioner står inför en betydelseglidning vad gället begreppsparet ”Egendom” och ”Stöld”. Det har visat sig att Lockes naturtillstånd, varseblivningen av ”det oändliga” på jorden, har skiftat plats; från ”naturen” ut till ”cyberspace”, vilket har resulterat i att fildelningstekniken skapat en ny matematik som omöjliggör tidigare egendomsdefinition.</p>

In this thesis we use the syntactic-semantic method of constructive type theory to give meaning to classical logic, in particular Gentzen's LK. We interpret a derivation of a classical sequent as a derivation of a contradiction from the assumptions that the antecedent formulas are true and that the succedent formulas are false, where the concepts of truth and falsity are taken to conform to the corresponding constructive concepts, using function types to encode falsity. This representation brings LK to a manageable form that allows us to split the succedent rules into parts. In this way, every succedent rule gives rise to a natural deduction style introduction rule. These introduction rules, taken together with the antecedent rules adapted to natural deduction, yield a natural deduction calculus whose subsequent interpretation in constructive type theory gives meaning to classical logic. The Gentzen-Prawitz inversion principle holds for the introduction and elimination rules of the natural deduction calculus and allows for a corresponding notion of convertibility. We take the introduction rules to determine the meanings of the logical constants of classical logic and use the induced type-theoretic elimination rules to interpret the elimination rules of the natural deduction calculus. This produces an interpretation injective with respect to convertibility, contrary to an analogous translation into intuitionistic predicate logic. From the interpretation in constructive type theory and the interpretation of cut by explicit substitution, we derive a full precision contraction relation for a natural deduction version of LK. We use a term notation to formalize the contraction relation and the corresponding cut-elimination procedure. The interpretation can be read as a Brouwer-Heyting-Kolmogorov (BHK) semantics that justifies classical logic. The BHK semantics utilizes a notion of classical proof and a corresponding notion of classical truth akin to Kolmogorov's notion of pseudotruth. We also consider a second BHK semantics, more closely connected with Kolmogorov's double-negation translation. The first interpretation reinterprets the consequence relation while keeping the constructive interpretation of truth, whereas the second interpretation reinterprets the notion of truth while keeping the constructive interpretation of the consequence relation. The first and second interpretations act on derivations in much the same way as Plotkin's call-by-value and call-by-name continuation-passing-style translations, respectively. We conclude that classical logic can be given a constructive semantics by laying down introduction rules for the classical logical constants. This semantics constitutes a proof interpretation of classical logic.

Genom att analysera domstolsmaterialet från rättegången mot fildelningssiten The Pirat Bay, i relation till en idéhistorisk diskussion om äganderätt, har uppsatsen funnit att den liberala tanketraditionen och dess juridiska institutioner står inför en betydelseglidning vad gället begreppsparet ”Egendom” och ”Stöld”. Det har visat sig att Lockes naturtillstånd, varseblivningen av ”det oändliga” på jorden, har skiftat plats; från ”naturen” ut till ”cyberspace”, vilket har resulterat i att fildelningstekniken skapat en ny matematik som omöjliggör tidigare egendomsdefinition.

Aquesta tesi té tres objectius. En primer lloc, estudiem generalitzacions de la jerarquia no ample relatives a una família de tipus parcials. Aquestes jerarquies en permeten classificar la complexitat del “forking” respecte a una família de tipus parcials. Si considerem la família de tipus algebraics, aquestes generalitzacions corresponen a la jerarquia ordinària, on el primer i el segon nivell corresponen a one-basedness i a CM-trivialitat, respectivament. Fixada la família de tipus regulars “no one-based”, el primer nivell d'una d'aquestes possibles jerarquies no ample ens diu que el tipus de la base canònica sobre una realització és analitzable en la família. Demostrem que tota teoria simple amb suficients tipus regulars pertany al primer nivell de la jerarquia dèbil relativa a la família de tipus regulars no one-based. Aquest resultat generalitza una versió dèbil de la “Canonical Base Property” estudiada per Chatzidakis i Pillay. En segon lloc, discutim problemes d'eliminació de hiperimaginaris assumint que la teoria és CM-trivial, en tal cas la independència del “forking” té un bon comportament. Més concretament, demostrem que tota teoria simple CM-trivial elimina els hiperimaginaris si elimina els hiperimaginaris finitaris. En particular, tota teoria petita simple CM-trivial elimina els hiperimaginaris. Cal remarcar que totes les teories omega-categòriques simples que es coneixen són CM-trivials; en particular, aquelles teories obtingudes mitjançant una construcció de Hrushovski. Finalment, tractem problemes de classificació en les teories simples. Estudiem la classe de les teories simples baixes; classe que inclou les teories estables i les teories supersimples de D-rang finit. Demostrem que les teories simples amb pes finit acotat també pertanyen a aquesta classe. A més, provem que tota teoria omega-categòrica simple CM-trivial és baixa. Aquest darrer fet resol parcialment una pregunta formulada per Casanovas i Wagner. / The development of first-order stable theories required two crucial abstract notions: forking independence, and the related notion of canonical base. Forking independence generalizes the linear independence in vector spaces and the algebraic independence in algebraically closed fields. On the other hand, the concept of canonical base generalizes the field of definition of an algebraic variety. The general theory of independence adapted to simple theories, a class of first-order theories which includes all stable theories and other interesting examples such as algebraically closed fields with an automorphism and the random graph. Nevertheless, in order to obtain canonical bases for simple theories, the model-theoretic development of hyperimaginaries --equivalence classes of arbitrary tuple modulo a type-definable (without parameters) equivalence relation-- was required. In the present thesis we deal with topics around the geometry of forking in simple theories. Our first goal is to study generalizations of the non ample hierarchy which will code the complexity of forking with respect to a family of partial types. We introduce two hierarchies: the non (weak) ample hierarchy with respect to a fixed family of partial types. If we work with respect to the family of bounded types, these generalizations correspond to the ordinary non ample hierarchy. Recall that in the ordinary non ample hierarchy the first and the second level correspond to one-basedness and CM-triviality, respectively. The first level of the non weak ample hierarchy with respect to some fixed family of partial types states that the type of the canonical base over a realization is analysable in the family. Considering the family of regular non one-based types, the first level of the non weak ample hierarchy corresponds to the weak version of the Canonical Base Property studied by Chatzidakis and Pillay. We generalize Chatzidakis' result showing that in any simple theory with enough regular types, the canonical base of a type over a realization is analysable in the family of regular non one-based types. We hope that this result can be useful for the applications; for instance, the Canonical Base Property plays an essential role in the proof of Mordell-Lang for function fields in characteristic zero and Manin-Mumford due to Hrushovski. Our second aim is to use combinatorial properties of forking independence to solve elimination of hyperimaginaries problems. For this we assume the theory to be simple and CM-trivial. This implies that the forking independence is well-behaved. Our goal is to prove that any simple CM-trivial theory which eliminates finitary hyperimaginaries --hyperimaginaries which are definable over a finite tuple-- eliminates all hyperimaginaries. Using a result due to Kim, small simple CM-trivial theories eliminate hyperimaginaries. It is worth mentioning that all currently known omega-categorical simple theories are CM-trivial, even those obtained by an ab initio Hrushovski construction. To conclude, we study a classification problem inside simple theories. We study the class of simple low theories, which includes all stable theories and supersimple theories of finite D-rank. In addition, we prove that it also includes the class of simple theories of bounded finite weight. Moreover, we partially solve a question posed by Casanovas and Wagner: Are all omega-categorical simple theories low? We solve affirmatively this question under the assumption of CM-triviality. In fact, our proof exemplifies that the geometry of forking independence in a possible counterexample cannot come from finite sets.

A definition of abstract logic is presented. This is used to explore and compare some abstract logics, such as logics with generalised quantifiers and infinitary logics, and their properties. Special focus is given to the properties of completeness, compactness, and the Löwenheim-Skolem property. A method of comparing different logics is presented and the concept of equivalent logics introduced. Lastly a proof is given for Lindström's theorem, which provides a characterization of elementary logic, also known as first-order logic, as the strongest logic for which both the compactness property and the Löwenheim-Skolem property, holds.

Diese Arbeit untersucht ordnungsinvariante Formeln der Logik erster Stufe (FO) und einiger ihrer Erweiterungen, sowie andere eng verwandte Konzepte der endlichen Modelltheorie. Viele Resultate der endlichen Modelltheorie nehmen an, dass Strukturen mit einer Einbettung ihres Universums in ein Anfangsstück der natürlichen Zahlen ausgestattet sind. Dies erlaubt es, beliebige Relationen (z.B. die lineare Ordnung) und Operationen (z.B. Addition, Multiplikation) von den natürlichen Zahlen auf solche Strukturen zu übertragen. Die resultierenden Relationen auf den endlichen Strukturen werden als numerische Prädikate bezeichnet. Werden numerische Prädikate in Formeln verwendet, beschränkt man sich dabei häufig auf solche Formeln, deren Wahrheitswert auf endlichen Strukturen invariant unter Änderungen der Einbettung der Strukturen ist. Wenn das einzige verwendete numerische Prädikat eine lineare Ordnung ist, spricht man beispielsweise von ordnungsinvarianten Formeln. Die Resultate dieser Arbeit können in drei Teile unterteilt werden. Der erste Teil betrachtet die Lokalitätseigenschaften von FO-Formeln mit Modulo-Zählquantoren, die beliebige numerische Prädikate invariant nutzen. Der zweite Teil betrachtet FO-Sätze, die eine lineare Ordnung samt der zugehörigen Addition auf invariante Weise nutzen, auf endlichen Bäumen. Es wird gezeigt, dass diese dieselben regulären Baumsprachen definieren, wie FO-Sätze ohne numerische Prädikate mit bestimmten Kardinalitätsprädikaten. Für den Beweis wird eine algebraische Charakterisierung der in dieser Logik definierbaren Baumsprachen durch Operationen auf Bäumen entwickelt. Der dritte Teil der Arbeit beschäftigt sich mit der Ausdrucksstärke und der Prägnanz von FO und Erweiterungen von FO auf Klassen von Strukturen beschränkter Baumtiefe. / This thesis studies the concept of order-invariance of formulae of first-order logic (FO) and some of its extensions as well as other closely related concepts from finite model theory. Many results in finite model theory assume that structures are equipped with an embedding of their universe into an initial segment of the natural numbers. This allows to transfer arbitrary relations (e.g. linear order) and operations (e.g. addition, multiplication) on the natural numbers to structures. The arising relations on the structures are called numerical predicates. If formulae use these numerical predicates, it is often desirable to consider only such formulae whose truth value in finite structures is invariant under changes to the embeddings of the structures. If the numerical predicates include only a linear order, such formulae are called order-invariant. We study the effect of the invariant use of different kinds of numerical predicates on the expressive power of FO and extensions thereof. The results of this thesis can be divided into three parts. The first part considers the locality and non-locality properties of formulae of FO with modulo-counting quantifiers which may use arbitrary numerical predicates in an invariant way. The second part considers sentences of FO which may use a linear order and the corresponding addition in an invariant way and obtains a characterisation of the regular finite tree languages which can be defined by such sentences: these are the same tree languages which are definable by FO-sentences without numerical predicates with certain cardinality predicates. For the proof, we obtain a characterisation of the tree languages definable in this logic in terms of algebraic operations on trees. The third part compares the expressive power and the succinctness of different ex- tensions of FO on structures of bounded tree-depth.