1,720,983 research outputs found
La logica del convincimento
No full textIn questo articolo si analizzano alcune strategie di persuasione di massa utilizzate durante la gestione della recente emergenza pandemica per indurre la popolazione ad uniformarsi alle disposizioni governative. Tali strategie vengono confrontate con i principi logici fondamentali della Logica Classica, in particolare il principio del Terzo Escluso e quello di Non Contraddizione. Viene tracciato un confronto tra le strategie dialettiche riportate da Jacopo da Varazze nel capitolo su Santa Caterina d'Alessandria nella Legenda Aurea e quelle presentatesi nella recente emergenza sanitaria
Introduzione alla Teoria dei Modelli
No full textScopo di questo manuale è quello di tracciare alcuni argomenti di base per un'agile introduzione allo studio della Teoria dei Modelli. Il testo è pensato primariamente come introduzione alla materia a beneficio degli studenti, ma è anche concepito per essere adatto allo studio individuale da parte di chiunque possa essere interessato alla disciplina, essendo richieste unicamente nozioni matematiche di livello scolastico
An Analysis of the Lemmas of Urysohn and Urysohn-Tietze According to Effective Borel Measurability
No full textInternal Computability
No full textWe extend the notion of (TTE-)computability to nonstandard
universes by the traditional method of enlarging universes through
ultrafilters. In this way a nonstandard notion of effectivity is obtained
Weihrauch goes Brouwerian
Full text linkWe prove that the Weihrauch lattice can be transformed into a
Brouwer algebra by the consecutive application of two closure operators in
the appropriate order: rst completion and then parallelization. The closure
operator of completion is a new closure operator that we introduce. It transforms
any problem into a total problem on the completion of the respective
types, where we allow any value outside of the original domain of the problem.
This closure operator is of interest by itself, as it generates a total version
of Weihrauch reducibility that is dened like the usual version of Weihrauch
reducibility, but in terms of total realizers. From a logical perspective completion
can be seen as a way to make problems independent of their premises.
Alongside with the completion operator and total Weihrauch reducibility we
need to study precomplete representations that are required to describe these
concepts. In order to show that the parallelized total Weihrauch lattice forms
a Brouwer algebra, we introduce a new multiplicative version of an implication.
While the parallelized total Weihrauch lattice forms a Brouwer algebra with
this implication, the total Weihrauch lattice fails to be a model of intuitionistic
linear logic in two dierent ways. In order to pinpoint the algebraic reasons
for this failure, we introduce the concept of a Weihrauch algebra that allows
us to formulate the failure in precise and neat terms. Finally, we show that
the Medvedev Brouwer algebra can be embedded into our Brouwer algebra,
which also implies that the theory of our Brouwer algebra is Jankov logic
Completion of choice
Full text linkWe systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete
Effective choice and boundedness principles in computable analysis
No full textIn this paper we study a new approach to classify mathematical theorems ac-
cording to their computational content. Basically, we are asking the question which theorems
can be continuously or computably transferred into each other? For this purpose theorems
are considered via their realizers which are operations with certain input and output data.
The technical tool to express continuous or computable relations between such operations
is Weihrauch reducibility and the partially ordered degree structure induced by it. We have
identified certain choice principles such as co-finite choice, discrete choice, interval choice,
compact choice and closed choice, which are cornerstones among Weihrauch degrees and it
turns out that certain core theorems in analysis can be classified naturally in this structure.
In particular, we study theorems such as the Intermediate Value Theorem, the Baire Cate-
gory Theorem, the Banach Inverse Mapping Theorem, the Closed Graph Theorem and the
Uniform Boundedness Theorem. We also explore how existing classifications of the Hahn–
Banach Theorem and Weak König’s Lemma fit into this picture. Well-known omniscience
principles from constructive mathematics such as LPO and LLPO can also naturally be con-
sidered as Weihrauch degrees and they play an important role in our classification. Based on
thiswe compare the results of our classificationwith existing classifications in constructive and
reverse mathematics and we claim that in a certain sense our classification is finer and sheds
some new light on the computational content of the respective theorems. Our classification
scheme does not require any particular logical framework or axiomatic setting, but it can be
carried out in the framework of classical mathematics using tools of topology, computability
theory and computable analysis. We develop a number of separation techniques based on a
new parallelization principle, on certain invariance properties of Weihrauch reducibility, on
the Low Basis Theorem of Jockusch and Soare and based on the Baire Category Theorem.
Finally, we present a number of metatheorems that allow to derive upper bounds for the
classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed
Point Theorem as an example
Le direzioni della logica in Italia: la reverse mathematics e l'analisi computazionale
Full text linkNelle conversazioni tra matematici non è infrequente sentire affermazioni del tipo “i teoremi Φ e Ψ sono equivalenti”, oppure “il teorema Φ è più forte del teorema Ψ”. Dato che Φ e Ψ (essendo teoremi) sono entrambi dimostrabili, prendendo alla lettera le due affermazioni abbiamo che la prima è banalmente vera e la seconda banalmente falsa. Sappiamo tutti però che queste affermazioni hanno un altro significato, molto meno banale, e c’è quindi una ragione per cui vengono fatte. Negli ultimi decenni la logica matematica ha sviluppato alcuni strumenti in grado di rendere precise, e suscettibili di dimostrazione o refutazione, affermazioni come le precedenti. In particolare ci riferiamo alla reverse mathematics e all’analisi computazionale. Questi sono due programmi di ricerca di origine diverse che nell’ultimo decennio, anche grazie al contributo di alcuni ricercatori italiani, hanno trovato significativi punti di contatto. In questo lavoro presenteremo i due programmi, con particolare riferimento alle loro aree di contatto. Evidenzieremo in particolare i contributi dei ricercatori italiani attivi in queste aree, e concluderemo indicando alcune prospettive di sviluppo su cui anche in Italia si sta cercando di lavorare
La calculabilité
No full textLa calculabilité est la théorie mathématique des fonctions calculables en droit par un algorithme. Fondée durant les années 1930 pour résoudre des problèmes de logique et fondements des mathématiques, elle s’est révélée a posteriori féconde pour théoriser les limites ultimes des ordinateurs, en ce que ceux-ci exécutent des algorithmes rédigés dans un langage formel de programmation.
La calculabilité s’abstrait à dessein des limites concrètes pesant sur les ressources nécessaires au calcul, comme le temps et l’espace mémoire. Mais on peut enrichir les objets créés par cette théorie pour prendre en compte ces limitations, et formuler une théorie de la complexité intrinsèque des problèmes algorithmiques. Une telle théorie est nommée « théorie de la complexité computationnelle ». Elle vient compléter la calculabilité pour former la théorie du calcul.
Ce chapitre du Précis vise à une présentation succinte de cette théorie du calcul, et de certains de ses enjeux philosophiques. Il se veut accessible aux philosophes versés dans la logique, comme aux mathématiciens et informaticiens intéressés par les fondements du calcul.
Dans un premier temps, nous présentons les concepts de base de la calculabilité. Dans un deuxième temps, nous exposons l’expansion de cette théorie au calcul sur les réels. Enfin, nous introduisons les fondements de la théorie de la complexité computationnelle
- …
