#матлог #учёба #спецсеминар Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com) 2 November, 18:30 MSK Nikolay Vereshchagin — Arithmetical and set-theoretic semantics for a logic of problems and propositions. Kolmogorov (1932) suggested that intuitionistic logic is a calculus of problems, as opposed to classical logic, which deals with propositions, and that a complete account should treat both sorts at once. Melikhov's logic HC is such a two-sorted system: classical propositions, intuitionistic problems, and two modalities connecting them, !A = "find a proof of A" and ?p = "problem p has a solution". However, no semantics supporting this reading of the modalities has been proposed so far. We go in the opposite direction: we start with semantics and only then look for calculi. A propositional variable is interpreted by a closed arithmetical formula, a problem variable by an arithmetical formula with one free variable, the set of its solutions. Connectives on problems act as in Kleene realizability, !A is the set of PA-proofs of A, and ?p says that the set of solutions of p is nonempty. A problem is valid if a solution can be computed uniformly from the (code of the) interpretation, and this is provable in PA (or, in a second variant, true in N). A third, set-theoretic variant interprets problem variables by arbitrary subsets of omega, "black boxes", and uses ZF-proofs; it also allows a quantifier over problems. We present sound calculi for all three semantics. On the propositional side the picture is complete: the valid propositions are exactly the theorems of Solovay's logics GL and GLS; the Lob axiom is derived from the other axioms via the fixed-point lemma rather than postulated. On the problem side the logic is much less understood: the valid modality-free problems form a superintuitionistic logic strictly between Int and the logic of the weak excluded middle, with an intuitionistic positive fragment (the separating examples are Rose's formula and Scott's axiom), and our calculi are incomplete there. We will also discuss how HC itself relates to the semantics (its co-reflection axiom p -> !?p fails, and HC is inconsistent with the Lob scheme). Joint work with Anastasia Onoprienko.

31 октября в 9:00 и 3 ноября в 15:00 состоятся заседания теоретического семинара «Формальная философия» Докладчик: Марко Руффино (Университет Кампинаса) Тема доклада (31 октября): How to Frege a Perry-Kaplan or How to do Words with Things — Анонс и регистрация: https://llfp.hse.ru/announcements/1213286527.html Тема доклада (3 ноября): Frege on What Negation Should Not Be — Анонс и регистрация: https://llfp.hse.ru/announcements/1213286726.html ______________________ Ждём вас в кабинете А-117 или в Zoom!

#матлог #учёба #просеминар 💥 В пятницу 30 октября состоится очередное занятие просеминара по математической логике и информатике! ✨ Тема: "Кубики сома, продолжение" (Александр Калинин, студент кафедры). ✨ Аннотация. «Примет сому человек — время прекращает бег, сладко человек забудет и что было, и что будет». — из романа "О дивный новый мир" Олдоса Хаксли. На прошлом семинаре мы познакомились с фигурами сома и их классическими задачами. Однако ими потенциал головоломки не исчерпывается. В этот раз мы обсудим нестандартные модификации деталей, правила и стратегии настольной игры на основе фигур сома, а также выясним, что же такое супружеская пара. ✨ Можно заранее порешать задачи. ✅ Просеминар проходит по пятницам в 16:45-18:20 в аудитории 426 (2 гуманитарный корпус). ✅ По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi ✅ Информацию о просеминаре можно найти в группе кафедры ВК или в телеграм-канале по хештегу #просеминар