**ARGOMENTI:** Seminars

Seminario di Logica Permanente

VenerdÃ¬ 21 Giugno 2013, ore 14:30-17:30

Aula 2AB45

Talks:

Lorenzo Malatesta (Strathclyde)

"Initial algebra semantics of small inductive-recursive definitions"

Category theory provides for a foundational framework for data types via initial algebra semantics. At the simplest level, polynomials and containers give a theory of data types as free standing entities. At a second level of complexity, dependent polynomials and indexed containers handle more sophisticated data types in which the data has an associated index which can be used to store important computational information.The crucial and salient feature of dependent polynomials and indexed containers is that the indices are defined in advance of the data. At the most sophisticated level, induction-recursion allows us to define data with indexes where the indices are defined simultaneously with the data.In this seminar I will present the relationship between the theory of inductive recursive definitions and the theory of dependent polynomials and indexed containers. The central result is that the expressiveness of small inductive recursive definitions is exactly the same as that of dependent polynomials and indexed containers. We introduce the category of small inductive-recursive definitions and prove the equivalence of this category with the category of dependent polynomials.

This is a joint work with Peter Hancock, Conor McBride, Neil Ghani and Thorsten Altenkirch.

Umberto Grandi (Padova)

"Binary Aggregation with Integrity Constraints"

Social Choice Theory studies problems of collective decisions making, in which a set of agents is bound to take a decision on a set of common alternatives. From the seminal work of Kenneth Arrow to more recent developments in Computational Social Choice, the literature is crowded with results bounding the feasibility of such decisions (the notorious "impossibility results"), arising from paradoxical group choices obtained from individually rational agents. In this talk I will begin by introducing models of individual decision making, defining various notions of individual rationality that have been introduced in the literature, and study the paradoxes arising from the corresponding aggregation problems. We will have logic as our travel companion: I will hint at its role in the foundations of decision theory, and introduce a new approach to the study of aggregation problems based on propositional languages. In the last part of the talk I will define this in more detail, providing a general framework to express individual rationality assumptions as formulas of propositional logic, and study the corresponding aggregation problems depending on the syntactical properties of these formulas.

Emanuele Bottazzi (Trento)

"Elementary numerosities and measures"

Generalizing the notion of numerosity, first introduced by Benci and Di Nasso, we say that a function n defined on the powerset of a given set X is an elementary numerosity if

1. its range is the non-negative part of a non-archimedean field that extends the field of real numbers;

2. it is finitely additive;

3. n({x}) = 1 for every element x of X.

It turns out that the elementary numerosities are quite general: every non-atomic finitely additive or sigma-additive measure can be obtained as the ratio of an elementary numerosity by a fixed element of F. This theorem can be proved directly via an ultrapower construction or can be obtained as a consequence of a theorem of C. W. Henson about nonstandard representation of measures. Applications of the above result about elementary numerosities range from measure theory to non-archimedean probability. In the latter field, we were able to create a nonstandard model for the infinite sequence of coin tosses that agrees with the classical one and extends the range of sets for which the conditional probability makes sense, improving a result previously obtained by Benci, Horsten and Wenmackers.. We are also working on the application of elementary numerosities to the modelization of the uniform probability on bounded subsets of R^n: our goal is to obtain a nonstandard extension of the conditional probability on a very broad class of sets in a way that essentially avoids the Borel-Kolmogorov paradox.