<p> Propositional proof complexity is a field of theoretical computer science which concerns itself with the lengths of formal proofs in various propositional proof systems. Frege systems are an important class of propositional proof systems. Extended Frege augments them by allowing the introduction of new variables to abbreviate formulas. Perhaps the largest open question in propositional proof complexity is whether or not Extended Frege is significantly more powerful that Frege. Several proof systems, each introducing new rules or syntax to Frege, have been developed in an attempt to shed some light on this problem.</p> <p> We introduce one such system, which we call H, which allows for the quantification of transpositions of propositional variables. We show that H is sound and complete, and that H's transposition quantifiers efficiently represent any permutation.</p> <p> The most important contribution is showing that a fragment of this proof system, H*1, is equivalent in power to Extended Frege. This is a complicated and rather technical result, and is achieved by showing that H*1 can efficiently prove translations of the first-order logical theory ∀PLA, a logical theory well suited for reasoning about linear algebra and properties of graphs.</p> / Thesis / Master of Science (MSc)

[pt] A Lógica é hoje em dia vista como uma ciência matemática fundamentalmente ligada à faculdade do entendimento, e pouco relacionada com nossa capacidade de imaginar ou conceber. Desta forma, sob a alcunha de psicologismo, costuma-se descartar qualquer associação da lógica à conceptividade ou à imaginação como espúria e mal colocada. Esta tese de doutorado tem como objetivo mostrar que, contrariamente ao que se costuma crer, há na lógica, tomada como uma ciência, um inegável emprego metodológico da faculdade da conceptividade ou da imaginação. Para mostrar isto, primeiramente examinamos sobre bases autônomas o princípio da conceptividade, segundo o qual a proposição p é concebível se e semente se p é possível. Investigamos as principais posições contemporâneas contra e a favor deste princípio e chegamos a uma versão qualificada do princípio, que defendemos ser livre de contraexemplos. Terá sido mostrado, portanto, que, sob certas condições, há uma relação essencial entre conceitos modais aléticos (possibilidade, necessidade, contingência, impossibilidade) e nossa faculdade de conceber ou imaginar: o que é concebível é possível - ainda que nem sempre o que é inconcebível seja impossível. Em seguida, mostramos como o princípio da conceptividade foi um instrumento insubstituível, nas mãos dos grandes pioneiros da lógica, em uma tarefa muito bem delimitada: a codificação de novas linguagens lógicas. Defendemos, por conseguinte, que Aristóteles, quando primeiramente codificou a lógica de proposições categóricas, e Frege, quando elaborou a lógica funcional e quantificada, foram obrigados a recorrer à conceptividade como parâmetro básico para examinar a correção expressiva da linguagem que estavam codificando e para aferir a validade lógica de diversas proposições e argumentos. Com vistas a tornar claro o lugar da noção de conceptividade dentro da lógica, examinamos a lógica e a epistemologia de Aristóteles e, sobretudo, de Frege, nas quais encontramos elementos concretos que apontam para o emprego desta noção dentro do contexto primitivo de codificação lógica a que nos reportamos. Enfatizamos que, no contexto em que estes autores se encontravam, não havia opções epistemológicas para examinar e avaliar sua lógica a não ser o recurso princípio da conceptividade. / [en] Logic is seen today as a mathematical science fundamentally linked to the faculty of understanding, unrelated to our capacity of imagining or conceiving. Under the label psychologism, one usually considers any association between logic and conceivability (or imagination) as spurious and misled. This doctoral thesis has as its goal showing that, contrarily to what is ordinarily thought, there is in logic, understood as a science, an undeniable methodological employment of the faculty of conceivability or imagination. In order to show this, we firstly examine the conceivability principle (the proposition p is conceivable if and only if p is possible) on autonomous basis. We examine the main contemporary positions against and in favor of this principle and come to a qualified version of the principle, which we purport to be free of counterexamples; it will have been shown, therefore, that, under certain circumstances, there is an essential relation between modal concepts (possibility, necessity, contingency, impossibility) and our faculty of conceiving or imagining: whatever is conceivable is possible - even though it is not always true that whatever is inconceivable is impossible. Secondly, we show how the conceivability principle was an irreplaceable tool in the hands of the great pioneers of logic, in a very well delimited task: codifying new logical languages. Therefore, we hold that Aristotle, as he firstly codified the logic of categorical propositions, and Frege, as he elaborated quantified functional logic, were bound to employ conceivability as a basic parameter so as to examine the expressive correctness of the language they were codifying and determine the validity of various propositions and arguments. In order to make clear the place of conceivability in logic, we examine Aristotle´s Frege´s logic and epistemology and find concrete elements indicating the employment of this notion in the primitive context of logical codification we have mentioned. We emphasize that, in the context in which these authors were working, there were no epistemological options other than the resource to the conceivability principle.

Made available in DSpace on 2014-07-29T15:06:26Z (GMT). No. of bitstreams: 1 Dissertacao Mestrado Hiury Correia.pdf: 634437 bytes, checksum: cf6fd2233508dfe9b0a574d4f162b2ba (MD5) Previous issue date: 2010-11-20 / Our dissertation s theme is the Idea that, buried in Frege s unfriendly Logical notation, one finds the notion of abstraction as a key ingredient of his Begriffsschrift. This runs contrary to the ordinary appraisal, such as the one found in Van Heijenoort s introduction to that article. It runs also contrary to Frege s refusal of the possibility of referring to unsaturated entities. Still, we argue that the notion seems to be part both of Frege s philosophical positions such as the idea of quantification as second order predication and of Frege s logical practices. / O tema da nossa dissertação é a idéia de que, por trás da idiossincrática notação lógica utilizada por Frege, podemos encontrar a noção de abstração como componente fundamental de sua Begriffsschrift. Tal posição vai contra a concepção ordinária, como, por exemplo, a que encontramos na introdução de Van Heijenoort àquela obra. Ela contraria, também, a rejeição de Frege à possibilidade de se referir a entidades insaturadas. Argumentamos que a noção de abstração aparece tanto como parte das posições filosóficas de Frege como, por exemplo, a idéia de que a quantificação é uma predicação de segunda ordem como, também, de sua prática lógica.

Un important désaccord subsiste parmi les exégètes de Frege au sujet de la question suivante : quel rapport entretient l'universalisme logique de Frege avec la sémantique contemporaine ? Le premier constitue-t-il un obstacle à l'élaboration et/ou à l'exploitation de la seconde ? Face à cette interrogation deux camps s'affrontent. L'un dresse la liste considérable des passages des Grundgesetze dans lesquels Frege sembla se lancer dans de véritables raisonnements sémantiques. L'autre rétorque qu'il s'agissait à ses yeux de pures élucidations, bannies de jure de la sphère théorique. Notre objectif consiste à faire toute la lumière sur ce problème. Dans ce but, nous nous appliquons à combattre deux poncifs ancrés dans la littérature. Nous contestons (1) l'idée que Frege était toujours soucieux de signaler la moindre inflexion de sa pensée, et (2) la possibilité d'étudier ses positions philosophiques indépendamment de son symbolisme spécifique. Par conséquent, nous retraçons la genèse des idées qui ont conduit à l'élaboration de l'idéographie de 1893, avant de réaliser toutes les étapes de la construction de ce système. Ces résultats - attachés à notre rejet de (1) et (2) - jettent une lumière neuve sur le problème soulevé plus haut. Ils nous conduisent à adopter le positionnement radical selon lequel Frege faisait bel et bien droit à une sémantique dont il jeta les bases et qu'il tenta de mettre en action afin de démontrer certains théorèmes métalogiques. Nous tentons de formaliser proprement cette sémantique, puis de localiser précisément les erreurs dont il fut responsable. Cette tâche nous conduit ultimement à l'étude des célèbres §§ 29-31 des Grundgesetze. / There is still considerable disagreement among Frege's exegetes on how Frege's logical universalism relates to modem semantics; does the former obstruct the development and/or the use of the latter? Two sides exist on this issue. The first one quotes many sections of the Grundgesetze which seem to contain genuine semantic reasonings. The other one claims that Frege holds these sections to be strict elucidations excluded de jure from the realm of science. My aim is to shed light on this problem. For this purpose, I contest the following commonplaces: (1) that Frege was concerned with indicating the slightest change of his thoughts, and (2) that his philosophical theses can be studied regardless of his particular symbolism. l thus complete the two tasks of tracing back the origins of the underlying ideas in the Ideography of 1893 and of building up this very system step by step. My results, attached to my rejection of (1) and (2), shed a new light m the issue raised above. They lead us to the radical position that not only did Frege not reject semantics, but that he himself paved the way to such a semantic theory in order to prove metalogical theorems. I then try to formalize the former so as to locate his errors in the latter. This work eventually leads to a thorough study of the famous §§ 29-31 of the Grundgesetze.

Made available in DSpace on 2014-07-29T15:06:23Z (GMT). No. of bitstreams: 1 Vinicius Rodrigues.pdf: 924953 bytes, checksum: a900dd6bc1f4e6f711ca14de37b7507d (MD5) Previous issue date: 2009-10-02 / The objective of this dissertation is to present Gottlob Frege s criticism of psychologism in Mathematics and Logic. Our working hypothesis is that Frege s criticism is based on his notion of an "abstract object". In order to investigate this hypothesis we will contrast the pre and post paradox phases of Fregean s philosophy. We will try to show that there is a continuity between these two periods, and that this continuity depends on Frege s insistence in maintaining the notion of an "abstract object", even if in a somewhat weakened version. Our dissertation will be divided into three chapters. In the first chapter, we will make a brief characterization of psychologism in order to circumscribe the exact focus of Frege s criticism. In the second chapter we will discuss the notion of an "abstract object" in the pre-paradox period of Frege s philosophy and its connection to Frege s main concern: that of defining number upon a pure logical basis. Eventually, in the third chapter, we will show how, even without a logically unassailable method of introducing logical objects, due to Russell s paradox, the philosopher does not give up his main theses concerning the nature of logic and mathematics. They are still grounded on the notion of an "abstract object", even thought in a somewhat feebler form. / O objetivo dessa dissertação é expor a critica de Gottlob Frege ao psicologismo na lógica e na matemática. Nossa hipótese de trabalho é a de que a crítica de Frege está fundamentada na sua noção de &#8213;objeto abstrato&#8214;. Para investigar essa hipótese, contrastaremos as fases pré e pós-paradoxo da filosofia fregiana. Tentaremos mostrar que há uma continuidade entre esses dois períodos e que essa continuidade se dá através da insistência, por parte de Frege, em manter uma noção de &#8213;o bjeto abstrato&#8214;, mesmo que numa versão enfraquecida. Nossa dissertação será dividida em três capítulos. No primeiro capítulo, faremos uma caracterização breve do psicologismo, com a finalidade de circunscrever o foco exato das críticas de Frege. No segundo capítulo, discutiremos a noção de &#8213;objeto abstrato&#8214; na fase pré-paradoxo da filosofia fregiana e sua conexão com o que foi o principal projeto filosófico de Frege: definir número em bases puramente lógicas. Finalmente, no terceiro capítulo, mostraremos como, mesmo sem possuir um método logicamente inatacável para introdução dos objetos lógicos em virtude do paradoxo de Russell, o filósofo não abandona suas teses principais em relação à natureza da lógica e da matemática. Essas teses continuarão baseadas na noção de &#8213;objeto abstrato&#8214;, embora em uma versão um tanto enfraquecida.