Logic group

NOTES: unusual room.
The BSS-RAM model is a logic-based concept that provides a mathematical framework for characterizing algorithms that enable the uniform processing of all finite sequences of individuals in a domain of discourse. The model is machine-oriented and the result of a generalization of several types of abstract machines, such as real RAMs, BSS machines, and deterministic or non-deterministic Turing machines. It was developed on the basis of a concept introduced by Dana Scott and discussed by Egon Börger and others. Individual algorithms can be determined by first-order programs and suitable structures. Each program of a machine is an element of a formal language. Its semantics can be defined by a transition system derived from a suitable first-order structure. The operations of the underlying structure are used to transform objects whereby the transformations themselves can also depend on states and conditions that can be evaluated by means of the relations of the structure.

We survey how initial segments of the Medvedev degrees can be used to interpret the classical propositional calculus, the intuitionistic propositional calculus, and the logic of weak excluded middle.

Set theory has proven useful in the study of derived limits. These functors are widely studied for their applications in algebraic topology, and their behavior is to some extent independent from ZFC. As already shown by Bergfalk and Lambie-Hanson in the case of ordinals, the derived limits associated with some set-theoretic objects tend not to vanish in $𝕃$. This corresponds to some form of incompactness. Here I present a similar nonvanishing result for ${}^κ ω$ that uses diamonds and special Aronszajn trees. This is work in progress with Jeffrey Bergfalk.

One of the foundational results of voting theory is the Gibbard–Satterthwaite theorem: for finite societies, every function selecting a winner from a finite set of candidates that is immune to manipulation by the misrepresentation of preferences is either constant or dictatorial. In infinite societies, the Gibbard–Satterthwaite theorem can fail: Pazner and Wesley (1977) showed that when the set of voters is infinite, there exist social choice functions that are both non-manipulable ('strategyproof') and non-dictatorial. Their proof rests on the existence of non-principal ultrafilters, a consequence of the axiom of choice, and hence clearly has a nonconstructive aspect. In this talk I will examine the Pazner–Wesley possibility theorem in the context of reverse mathematics, and show that for countable societies it is equivalent over RCA0 to arithmetical comprehension. I will then formulate a seemingly weaker version of the Pazner–Wesley possibility theorem, using individual strategyproofness rather than coalitional strategyproofness, and raise some open questions regarding the relationship between these two statements.