#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 25.04.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Рамазан Аюпов

Название: Логика каузальной импликации Р. Сильвана — Н. да Косты

Аннотация.

Доклад посвящен логике каузальной импликации (CI) Ричарда Сильвана (Рутли) и Ньютона да Косты [1], основанной на новой связке A \ni B («А причиняет B») и временном строгом линейном порядке («быть раньше»). Логика строится на основе релевантной семантики [2].

В дискуссии о природе причинности наибольшую популярность приобрела логика контрфактуалов Д. Льюиса. Результат Сильвана и да Косты представляет собой альтернативный подход к формальному рассмотрению причинности. Каузальное условное \ni — это коннексивная строгая релевантная импликация, удовлетворяющая свойствам транзитивности, иррефлексивности, Modus Ponens, Modus Tollens, закону Аристотеля, правилу Стросона, принципам композиции и принципу усиления (Augmentation), но не соблюдающая принцип тождества, контрапозицию, упрощение, добавление, подстановку, принципы факторизации (даже в ограниченной форме); она немонотонна и не допускает принципа взрыва.

В докладе мы рассмотрим язык, семантику и аксиоматизацию логики CI, а также проанализируем и сравним ее основные свойства и принципы с логикой контрфактуалов Льюиса.

[1] R. Sylvan and N. da Costa. Cause as an implication. Studia Logica, 1988, Vol. 47, N. 4, P. 413—428.
[2] R. Routley and others. In R. Sylvan & R. Brady (Eds.), Relevant Logics and Their Rivals. Atascadero: Ridgeview, 1982.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
25 апреля (пятница) в 18.30 состоится очередное заседание исследовательского семинара "Формальная философия".

Тема доклада: Диалоги с чатами больших языковых моделей на тему "Поставь совершенно новую научную проблему в ..."

Докладчик: Александр Поддьяков.

Ждём вас в кабинете А-117 или в Zoom!

Анонс: https://llfp.hse.ru/announcements/1038494692.html

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Дорогие участники Logic Online Seminar (https://www.mathnet.ru/eng/conf876), в ближайший понедельник мы присоединяемся к Proof Society Seminar (https://www.proofsociety.org/activities-and-resources/proof-society-seminar/), где выступит Степан Кузнецов.

The Proof Society Seminar presents talks by leading researchers in proof theory and from all areas of logic related to proofs. The talks take place online via Zoom, usually on Mondays, approximately once per month. They start at 13:00 UTC and may last up to 75 minutes plus questions.

28 April 2025, 13:00 UTC

Speaker: Stepan Kuznetsov (Steklov Mathematical Institute of RAS, https://homepage.mi-ras.ru/~sk/)

Title: Circular and infinitary proofs for complexity analysis of action logic

Abstract: Action logic is the extension of the full Lambek calculus (intuitionistic-style non-commutative substructural logic) with the operation of Kleene iteration. The natural algebraic semantics for action logic is given by residuated Kleene lattices (RKLs). Action logic appears in two variants: the logic of all RKLs (action logic itself), with an inductive axiomatisation for iteration, and a stronger infinitary system, where iteration is governed by an omega-rule. The latter corresponds to the natural subclass of *-continuous RKLs. In this talk, we discuss how calculi with circular and infinitary proofs help analyse algorithmic complexity for theoremhood and entailment from hypotheses in action logic and its infinitary extension. Namely, using circular proofs we show \Sigma^0_1-completeness of action logic. The theoremhood problem in infinitary action logic is \Pi^0_1-complete. For entailment from *-free hypotheses in the latter, we get an \omega^\omega upper bound on the closure ordinal (for the system with an omega-rule) and the corresponding hyperarithmetical complexity bound, which is actually exact. Finally, entailment from arbitrary hypotheses in infinitary action logic is \Pi^1_1-complete, the closure ordinal being \omega_1^{CK}.

Partially based on joint work with Tikhon Pshenitsyn and Stanislav Speranski.

➰ ВК

#матлог #учёба #спецсеминар

Ближайший семинар «Категориальные грамматики» состоится 24 апреля 2025 года.

Начало: 18:30. Аудитория: 424.

Докладчик: Сазонова Варвара
Тема: обзор статьи "Inside-Outside Algorithm for Probabilistic Product-Free Lambek Categorial Grammar"

Будет рассмотрен inside-outside алгоритм, адаптированный под вероятностную категориальную грамматику Ламбека (Jinman Zhao and Gerald Penn), и результаты, полученные с помощью генеративной модели.

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдёт в среду 23 апреля в 14:00.
В рамках этого семинара пройдет предзащита докторской диссертации Рыбакова М.Н.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идёте на семинар ВШМ и предъявить паспорт.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Михаил Николаевич Рыбаков (ВШМ МФТИ)

Название: Моделирование логических систем средствами их фрагментов (предзащита докторской диссертации)

Аннотация:
Проведённое исследование связано с выразительностью языков, логик и теорий, и прежде всего с алгоритмической выразительностью (в том числе вычислительной сложностью) определённых их фрагментов.

Многие естественные логические системы либо алгоритмически неразрешимы (причём иногда сильно неразрешимы), либо, будучи разрешимыми, имеют высокую сложность проблемы разрешения. Известно, что определённые ограничения, накладываемые на средства языка, аксиоматику или используемую семантику, приводят к изменению алгоритмической сложности тех или иных задач. В то же время иногда это не так: например, в неклассических логиках как неразрешимость, так и высокая сложность проблемы разрешения в случае разрешимости могут получаться при очень сильных ограничениях на средства языка.

Представляется актуальным не только нахождение границ, в рамках которых подобные проблемы оказываются алгоритмически простыми или наоборот остаются алгоритмически сложными, но и разработка общих методов, позволяющих получать оценки алгоритмической сложности фрагментов не только отдельных логических систем, а всех систем тех или иных бесконечных классов. Вместе с методами хотелось бы иметь общие признаки или критерии, позволяющие относительно просто делать вывод об алгоритмической сложности тех или иных фрагментов интересующей нас системы или хотя бы о потенциальной возможности или невозможности применения этих методов.

Основная цель работы состоит в том, чтобы развить общие методы моделирования алгоритмически сложных проблем внутри логик и теорий, используя минимальные средства языка. В частности, в работе предложены методы моделирования полных языков средствами их очень бедных фрагментов. К средствам языка, которые минимизируются, в первую очередь относятся следующие: число пропозициональных переменных в пропозициональных языках, число предметных переменных, а также число и валентность предикатных букв в языках первого порядка. Рассматриваются и некоторые ограничения на использование логических связок и кванторов.

В докладе будет дан обзор результатов, которые были получены автором в этом направлении. Будут коротко описаны методы их получения, а также возможные дальнейшие продвижения.

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 22 апреля 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

Павел Соколов (НИУ ВШЭ)

Утверждения как сессии

Классическое соответствие Карри-Говарда между интуиционистской логикой и простым типизированным лямбда-исчислением наталкивает на мысль, что это соответствие продолжается как на более сложные логики, так и на более интересные диалекты лямбда-исчисления. В частности, для интуиционистской линейной логики с экспоненциалом ! нетрудно выписать соответствующий субструктурный вариант лямбда-исчисления; полученный язык наделяет линейные типы "ресурсной" семантикой. Однако более естественной "логикой ресурсов" оказывается т.н. uniqueness logic [Harrington 2006], в то время как реализации линейных систем менее эффективны.

Оказывается, что у собственно линейной логики есть совершенно другая интерпретация — утверждений как сессий, в которых утверждения описывают некоторый протокол взаимодействия (сессию); соответствующим исчислением, позволяющим описывать "процессы", удовлетворяющие протоколам, оказывается π-исчисление, формализм для описания параллельных процессов.

В предлагаемом слушателям докладе будут изложены наиболее успешные результаты по реализации программы утверждений как сессий по мотивам статей Propositions as Sessions [Wadler 2014], Better late than never и Taking Linear Logic Apart [Kokke 2019].

➰ ВК

#матлог #учёба #просеминар

💥В четверг 24 апреля на просеминаре по математической логике и информатике будет продолжение темы "P и NP" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

➰ ВК

#матлог #спецсеминар

В пятницу 25 апреля в 14:30 в Математическом институте им. В.А. Стеклова РАН состоится заседание семинара "Некоторые применения математических методов в языкознании".

Где: Математический институт им. В.А. Стеклова РАН, ул. Губкина, д. 8, ауд. 110 (см. информацию о пропусках и онлайн-подключении ниже)
Кто: Валентин Борисович Шехтман (ВШМ МФТИ)
Тема: Временные логики
Аннотация:
Временны́е логики изучают высказывания, зависящие от времени. Такие высказывания возникают в естественном языке и в различных науках: философии, физике, информатике и т.д. С формальной точки зрения, временные логики - это, как правило, модальные логики со специальным синтаксисом и семантикой. На сегодняшний день имеется большое разнообразие таких логик. В докладе будет дан краткий обзор проблематики и результатов в этой обширной области, с упоминанием некоторых приложений.
Для понимания доклада полезно иметь представление о семантике возможных миров.

Если 25 апреля вы собираетесь прийти на заседание семинара в Математический институт и у вас есть пропуск студента/аспиранта/сотрудника научной или образовательной организации (МГУ, ВШЭ, МФТИ, ...), достаточно предъявить этот пропуск и сообщить, что вы идете на семинар "Некоторые применения математических методов в языкознании". Если у вас нет такого пропуска, но вы хотите прийти очно, напишите Степану Львовичу Кузнецову на почту sk@mi-ras.ru.

Онлайн-подключение осуществляется через платформу Контур.Толк; для подключения не требуется на ней регистрироваться.
Для получения ссылки напишите Степану Львовичу Кузнецову на почту sk@mi-ras.ru.

В дальнейшем заседания будут поочередно проводиться в Институте языкознания и Математическом институте, следите за объявлениями.

➰ ВК

#матлог #наука #конференция

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
Международная конференция «Формальная философия 2025»

«Формальная философия» – ежегодная международная конференция, которую организует Международная лаборатория логики, лингвистики и формальной философии. В 2025 конференция пройдет в 8-й раз (о прошедших конференциях). Конференция посвящена обсуждению проблематики философской логики, формальной эпистемологии, эпистемической логики, формальной онтологии, аналитической метафизики, философии логики, математической логики, филоcофии математики, а также другим аспектам формальной философии. После конференции пройдет ассоциированное мероприятие – Летняя школа "Логика, лингвистика и формальная философия" (30 июня – 4 июля 2025).

Даты конференции: с 23 по 26 июня 2025

Место проведения: г. Москва, ул. Старая Басманная, д. 21/4, А-307 + Zoom

Формат: гибридный (возможно как очное, так и дистанционное участие)

Рабочие языки: русский и английский

Заявки на участие принимаются до 25 мая.
(https://llfp.hse.ru/formphil2025)

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Kontur Talk (www.mathnet.ru/eng/conf876)

21.04.2025 Anna Dmitrieva (U. of East Anglia, https://research-portal.uea.ac.uk/en/persons/anna-dmitrieva): Complex field with quasiminimal structure (online)

Zilber's Quasiminimality Conjecture states that the complex field equipped with the exponential function is quasiminimal, i.e. every definable subset is countable or co-countable. Despite remaining open, this conjecture led to multiple new concepts and results. One of the directions inspired by the conjecture is the investigation of analogous conjectures where the exponential map is replaced with another function or a function-like object. In most cases the obtained conjecture seems to stay as difficult as the exponential one; as pointed out by Koiran and Wilkie, it even remains open whether adding all entire functions to the complex field would make it quasiminimal or non-quasiminimal. In this talk we provide two quasiminimal examples of this sort: first one involves a correspondence between two elliptic curves, while the second one considers the theory of a generic function, as introduced by Zilber in 2002.

➰ ВК

#матлог #наука #семинар

Приглашаем принять участие в очередном, 9-м по счету Колмогоровском семинаре по компьютерной лингвистике, который состоится 25 апреля 2025 года.

Место проведения - Покровский бульвар, 11.

Семинар пройдет в смешанном формате.

Информация о семинаре и регистрация доступна по ссылке https://cs.hse.ru/clls/2025/

➰ ВК

#матлог #новости

В выпуске (№ 1, январь-февраль) журнала "Вестник Московского университета. Серия 1. Математика. Механика" вышла обзорная статья, посвящённая нашей кафедре!

Серия обзорных статей в "Вестнике" приурочена к 270-летию Московского университета.

Со статьёй о кафедре математической логики и теории алгоритмов можно ознакомиться по ссылке.

http://vestnik.math.msu.su/issues/2025/1/04.pdf

➰ ВК

Внимание!
Изменение аудитории семинара "Категориальные грамматики" https://m.vk.com/wall-70743963_2021

Аудитория: 424 (2 гуманитарный корпус)

➰ ВК

#матлог #спецсеминар

В пятницу 18 апреля в 14:30 на заседании семинара "Некоторые применения математических методов в языкознании" в Институте языкознания РАН состоится продолжение доклада С.Г. Татевосова и П.О. Россяйкина. Ссылка для подключения в Zoom та же. Если вы не регистрировались на первую часть доклада, но хотите прийти или подключиться онлайн, заполните форму: https://forms.gle/jFsZcNFbbx15GskT7. (Записавшиеся «очно» будут внесены в списки на проход в здание ИЯз РАН.) Уже зарегистрировавшимся это делать не нужно.

Запись первой части доклада будет разослана всем зарегистрировавшимся, а также опубликована на странице семинара в ближайшие дни http://tipl.philol.msu.ru/index.php/science/seminars/npmmvia. По всем вопросам пишите на почту npmmvia@mail.ru.

Когда: 14:30 18 апреля 2025 года
Где: Институт языкознания РАН, конференц-зал + онлайн
Кто: Сергей Георгиевич Татевосов (МГУ), Петр Олегович Россяйкин (МГУ)
Название: "Новое в семантике: о двух явлениях и всем остальном. Часть 2"
Аннотация:
В этом докладе мы рассмотрим несколько сюжетов, которые вписываются в две аналитические тенденции современной формальной семантики: (i) модальный анализ языковых выражений и явлений, традиционно не относимых к модальным; (ii) семантический анализ явлений, традиционно относимых к прагматике. А именно, преимущественно на материале русского языка, мы обсудим некоторые аргументы в пользу синтаксического представления речевых актов и модальный анализ перфектива (и, по возможности, некоторых других грамматических сущностей).

➰ ВК

#матлог #учёба #спецсеминар

Ближайший семинар «Категориальные грамматики» состоится 17 апреля (17.04.2025).

Начало: 18:30. Аудитория: 1605, кафедра математической логики и теории алгоритмов (возможно, аудитория изменится).

Докладчик: Т.Г. Пшеницын
Тема: Грамматики слияния, сохраняющие связность

Рассматриваются ориентированные гиперграфы, гиперребра которых помечены символами некоторого алфавита. У каждого символа есть комплементарный ему. На гиперграфах определена операция слияния: два гиперребра с комплементарными метками "склеиваются" и удаляются. В грамматике слияния разрешено брать неограниченное число изоморфных копий гиперграфов из фиксированного конечного набора и применять к ним слияния; грамматика порождает компоненты связности получающихся таким образом гиперграфов. Мотивация изучения такого формализма связана с моделированием взаимодействия молекул ДНК; можно смотреть на грамматики слияния и как на своеобразное логическое исчисление с "правилом сечения" (выводимые объекты такого исчисления — связные гиперграфы).

При исследовании алгоритмических и теоретико-языковых свойств грамматик слияния возникли трудности, связанные с тем, что слияние может приводить к нарушению связности: при слиянии между двумя связными гиперграфами или внутри одного связного гиперграфа может получаться несвязный гиперграф. Чтобы исключить нарушения связности, в литературе было введено понятие грамматик слияния, сохраняющих связность. Оказалось, что для них многие задачи решаются проще, чем для грамматик слияния в целом (проще — и в смысле алгоритмической сложности, и в смысле простоты доказательств). Так, Aaron Lye в 2021 году доказал, что задача непустоты для грамматик слияния, сохраняющих связность, разрешима и является NP-полной; также он получил аналогичный результат в отношении задачи принадлежности для существенных грамматик слияния, сохраняющих связность. Докладчиком также был доказан аналог теоремы Париха для грамматик слияния, сохраняющих связность (верно ли это для всех грамматик слияния, неизвестно).

В докладе будет описано свойство сохранения связности и будет дан обзор упомянутых выше результатов. Основной акцент будет сделан на сложности самого свойства сохранения связности: будет доказано, что задача проверки, сохраняет ли грамматика слияния связность, разрешима, принадлежит классу coNEXPTIME и при этом PSPACE-трудна. Доказательства иллюстрируют типичные для данной области методы.

➰ ВК

#матлог #учёба #просеминар

💥В четверг 17 апреля на просеминаре по математической логике и информатике будет тема "P и NP" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅Можно заранее порешать задачи (прикреплены к посту).
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

�� P_NP_2025

➰ ВК

#матлог #наука #спецсеминар #не_мехмат #МГУ

Научно-исследовательский семинар кафедры логики философского факультета МГУ "Современная логика"

Дата, время и аудитория: 17.04.2025 (чт) в 13.30 в г354it.
Место: Шуваловский корпус МГУ
Докладчик: С. О. Сперанский (МИАН)
Название: О кванторной версии модальной логики Белнапа–Данна
Аннотация: Речь пойдёт о кванторной версии пропозициональной модальной логики BK из статьи С.П. Одинцова и Х. Вансинга, в основе которой лежит (немодальная) четырёхзначная система Белнапа–Данна; эта версия будет обозначаться через QBK. В ходе доклада мы обсудим адаптацию метода канонических моделей для QBK и её расширений. В частности, с помощью этой адаптации получается теорема о сильной полноте для QBK относительно подходящей семантики возможных миров.

Доклад основан на совместной статье:
A.V. Grefenshtein, S.O. Speranski. On the quantified version of the Belnap–Dunn modal logic. Sbornik: Mathematics 215(3), 323–354, 2024. https://doi.org/10.4213/sm9981e

По вопросам прохода в корпус пишите на почту ivan.slusarev@mail.ru или в тг @ivanslsrv (лучше до этой среды включительно).

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдёт в среду 16 апреля.
Время проведения семинара 14:00.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, если у вас нет пропуска в МФТИ, достаточно сказать, что вы идете на семинар ВШМ и предъявить паспорт.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Дворкин Лев

Название: Финитная аппроксимируемость расширений wK4, наследуемых подшкалами (часть 1)

Подшкалой шкалы Крипке (X; R) называется подмножество S носителя X с индуцированным отношением достижимости. Логика L наследуется подшкалами Крипке, если класс её шкал Крипке замкнут относительно взятия подшкал. Файн доказал, что все полные по Крипке расширения K4, наследуемые подшкалами, финитно аппроксимируемы. Данный результат был усилен Захарьящевым на случай логик, наследуемых конфинальными подшкалами (подшкалами, носитель которых конфинален в исходной шкале). Доказательства Файна и Захарьящева основываются на семантике Крипке. Бежанишвилли, Гильярди и Джибладзе дали чисто алгебраическое доказательство результатов Файна и Захарьящева, одновременно обобщив их на расширения wK4 = K + p → p \/ p. Разбору доказательства последнего результата и посвящён доклад. В первой части мы обсудим некоторые факты, касающиеся алгебраической семантики модальных логик. В отличие от семантики Крипке, данной семантике уделяют мало времени в курсах по модальной логике, поэтому мы остановимся на ней достаточно подробно. Вторая часть посвящена непосредственно доказательству результата. От слушателей предполагается знание базовых фактов о модальных логиках и семантике Крипке.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

21 April 2025, 17.30 CET = 18.30 Moscow time

Speaker: Ivan Baburin
Title: Universality in Asynchronous Cellular Automata

Abstract:
A cellular automaton is a dynamical system consisting of an infinite array of cells, such that each cell uses a local neighborhood to perform a transition. An asynchronous cellular automaton (ACA) is a modification of cellular automata where every cell can update at is own tempo, without the need for global synchronization. In this talk we survey computational abilities of asynchronous cellular automata and show that—despite their fundamental differences—most asynchronous automata can invariantly “simulate” their synchronous counterparts [1]. To achieve that, we present two characterizations of invariance in asynchronous automata: – An algebraic approach using the notion of commutativity, as introduced by G´acs [2]. – A novel computational approach using flip automata networks, which additionally allows for simpler simulations and can be used to construct some of the smallest universal ACAs [3]. Finally, we discuss the limits of asynchronous computation by demonstrating that for certain automata neither universality nor reliable simulation can be achieved. Further Reading More details can be found in the corresponding paper [3].

References
1. T. Worsch, “Towards intrinsically universal asynchronous ca,” Natural Computing, vol. 12, no. 4, pp. 539–550, 2013.
2. P. Gacs, “Deterministic computations whose history is independent of the order of asynchronous updating,” 2001.
3. I. Baburin, M. Cook, F. Gr¨otschla, A. Plesner, and R. Wattenhofer, “Universality frontier for asynchronous cellular automata,” 2025.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Room 313 MIAN + Kontur Talk (www.mathnet.ru/eng/conf876)

14.04.2025 L. D. Beklemishev: Fragments of arithmetic and cyclic proofs (onsite, https://homepage.mi-ras.ru/~bekl/)

(jww with Daniyar Shamkanov and Ivan Smirnov)

We present an alternative cyclic proof system for Peano arithmetic that could be simpler than the existing ones and well-adapted both for proof analysis and for automatizing inductive proof search. In addition, we show how various traditional subsystems of Peano arithmetic defined by restricted forms of induction can be represented as fragments of the proposed system.

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 11.04.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Никита Лукашов

Название: Алгебраическая унификация в модальных логиках

Аннотация:

Проблема символической унификации для логики L — это достаточно естественный вопрос, имеет ли данная формула \phi унификатор в логике L. Другими словами, существует ли такая подстановка \sigma для формулы \phi, что постановочный пример \sigma(\phi) является теоремой логики L. Несмотря на простоту формулировки, проблема унификации является довольно сложной, и ещё многое предстоит сделать в этой области.

В своём докладе я предоставлю алгебраический взгляд на проблему унификации в нормальных модальных логиках. Точнее, мы посмотрим на проблему унификации в этих логиках с точки зрения алгебраической семантики. По ходу доклада мы определим модальные алгебры для произвольных нормальных модальных логик и докажем их универсальные свойства. Затем мы подробно поговорим про проективные алгебры и их эквивалентные определения (в частности, покажем их связь с проективными формулами). После чего мы определим алгебраический тип унификации через эти проективные алгебры и докажем фундаментальную теорему, утверждающую, что два типа унификации — алгебраический и символический — для произвольных нормальных модальных логик совпадают.

В заключение мы поговорим про точные формулы в нормальных модальных логиках, об условии, которое они задают для модальных алгебр, и получим новое алгебраическое доказательство известного факта, что проективные формулы всегда являются точными. Наконец, с помощью результатов С. Гильярди мы покажем, что в некоторых модальных логиках, таких как K4, S4, GL и др., верно обратное, т.е. точные и проективные формулы в этих логиках совпадают.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
11 апреля (пятница) в 18.30 состоится очередное заседание исследовательского семинара "Формальная философия".

Тема доклада: Black Boxes: The Semantics and Logic of Obliterative Modalities.

Докладчик: Элиа Дзардини.

Аннотация: If we wish to analyse knowability (and similar notions) in terms of some kind of possibility of knowledge, troubles quickly arise if the possibility in question is supposed to obey some very basic modal principles (like law 4 or the law of distribution). In this paper, I first provide an informal explanation of the notion of possibility in question. I then proceed to show how this informal explanation can be turned into a natural formal possible-world semantics with a multiplicity of accessibility relations, which gives rise to a nonregular modal logic that avoids the above-mentioned troubles. After introducing a sound and complete axiomatization of the logic, I close by mentioning some philosophically interesting directions in which the basic system can be extended or modified.

Ждём вас в кабинете А-117 или в Zoom!

Анонс: https://llfp.hse.ru/announcements/1033740295.html

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 15 апреля 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

Сергей Славнов (НИУ ВШЭ, https://www.hse.ru/org/persons/61709453/)

Индексированное исчисление Ламбека с передвижением

Исчисление Ламбека обычно интерпретируют как логику строк и конкатенации строк; именно в таком качестве оно используется в лингвистических приложениях. Однако давно замечено, что с точки зрения лингвистических приложений такой простой структуры обычно оказывается недостаточно, и требуется рассматривать более сложные объекты и операции.

Мы определяем специфическую алгебру термов, которые обозначают упорядоченные последовательности строк и могут комбинироваться между собой более сложными способами, чем простая конкатенация. Далее мы вводим систему типов для таких термов. Эта система представляет собой неассоциативное, но частично коммутативное расширение исчисления Ламбека, которое нам кажется с одной стороны достаточно простым и интересным, а с другой стороны достаточно выразительным.

➰ ВК

#матлог #новости #спецсеминар

🔥Возобновляет работу семинар "Некоторые применения математических методов в языкознании"! Это старейший семинар по математической лингвистике в России, одним из первых организаторов которого был Владимир Андреевич Успенский, в котором принимали участие Алексей Всеволодович Гладкий, Игорь Александрович Мельчук, Елена Викторовна Падучева и другие известные ученые. С 2025 года семинар проводится совместно Московским государственным университетом им. М.В. Ломоносова и Российской академией наук — Математическим институтом и Институтом языкознания.

Заседания будут проходить поочередно в ИЯз РАН и МИАН.

Когда: 11 апреля 2025 года, 14:30
Где: Институт языкознания РАН (Большой Кисловский пер., д. 1, стр. 1), конференц-зал + онлайн (ссылка отправляется зарегистрированным участникам)
Кто: Сергей Георгиевич Татевосов, Петр Олегович Россяйкин
Название: "Новое в семантике: о двух явлениях и всем остальном"
Аннотация:
В этом докладе мы рассмотрим несколько сюжетов, которые вписываются в две аналитические тенденции современной формальной семантики: (i) модальный анализ языковых выражений и явлений, традиционно не относимых к модальным; (ii) семантический анализ явлений, традиционно относимых к прагматике. А именно, преимущественно на материале русского языка, мы обсудим некоторые аргументы в пользу синтаксического представления речевых актов и модальный анализ перфектива (и, по возможности, некоторых других грамматических сущностей).

Для оформления пропуска в Институт языкознания или для получения ссылки для подключения онлайн необходимо заполнить форму до 23:59 10 апреля: https://forms.gle/jFsZcNFbbx15GskT7

Страница семинара: http://tipl.philol.msu.ru/index.php/science/seminars/npmmvia

➰ ВК

#матлог #учёба #просеминар

💥В четверг 10 апреля на просеминаре по математической логике и информатике будет продолжение темы "Наследственно конечные множества" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

➰ ВК

#матлог #не_мехмат

В ближайшие две среды, 9 и 16 апреля 2025 г., С.Л. Кузнецов прочитает две лекции в рамках курса «Coq» в Центральном университете.

Первая лекция будет посвящена вычислительным возможностям различных версий лямбда-исчисления. Будет рассказано, что в бестиповом лямбда-исчислении представимы все вычислимые функции, а также охарактеризованы подклассы всюду определённых вычислимых функций, представимых в простом типовом лямбда-исчислении и лямбда-исчислении второго порядка (система F).

На второй лекции будет рассказано о доказательстве непротиворечивости исчисления индуктивных конструкций (CIC — базовое исчисление системы Coq) в рамках теории множеств ZFC со счётным набором недостижимых кардиналов, а также обратное кодирование соответствующих расширений ZFC в Coq, по статье Б. Вернера 1997 г.

Место: учебный корпус Центрального университета, Москва, ул. Гашека, д. 7, аудитория F304 (3 этаж, из лифтов перейти по мосту и прямо)
Время: 9 и 16 апреля, 19:30

Для посещения нужно получить пропуск. Для этого нужно написать в телеграм Владу Пимкину @delamelicon, что идёте на лекцию С.Л.Кузнецова в среду. Желательно сделать это не позднее вторника.

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 9 апреля.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Иван Смирнов

Тема: Фрагменты арифметики и циклические выводы.

Аннотация:
Циклический вывод отличается от классического возможностью наличия циклов в "графе вывода", который для классического вывода является деревом. А. Симпсон [1] (и независимо С. Берарди и М. Татсута) доказал эквивалентность некоторой формальной системы арифметики 1-го порядка, основанной на циклических выводах, и арифметики Пеано.

В докладе мы расскажем о новой системе циклических выводов для арифметики 1-го порядка, предложенной в работе [2]. Глобальные ограничения корректности на выводы в этой системе выглядят проще, чем в предшествующих: задача проверки корректности вывода в ней лежит в классе P, а не только в PSPACE. Мы также определим некоторые фрагменты этой системы, основанные на ограничении сложности формул, входящих в вывод, эквивалентные известным фрагментам арифметики Пеано: $I \Sigma_n$ и $I \Sigma_n^R$.

Список литературы:
[1] A. Simpson. “Cyclic arithmetic is equivalent to Peano arithmetic”. In: FOSSACS 2017, Proceedings. pp. 283--300.
[2] L. Beklemishev, D. Shamkanov and I. Smirnov. "Fragments of arithmetic and cyclic proofs". arxiv.org/abs/2502.06639

➰ ВК

#матлог #учёба #спецсеминар

На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ

"Модальная и алгебраическая логика" и "Логические методы в информатике"

в ближайший вторник 8 апреля, начало в 18:30, состоится доклад

Докладчик:
Слюсарев Владислав Владимирович

Тема:
Критерии локальной табличности произведений модальных логик

Аннотация:
Для заданной модальной логики L формулы φ и ψ называются L-эквивалентными, если φ-ψ∈L. Модальная логика L называется локально табличной, если для любого n∈ω число классов L-эквивалентности модальных формул на n пропозициональных переменных конечно.

Критерий Сегерберга-Максимовой утверждает, что для одномодальных логик, расширяющих K4, локальная табличность эквивалентна конечной высоте. В общем случае этот критерий не выполнен, а аналоги неизвестны.

В этом докладе будут рассмотрены новые критерии, характеризующие локальную табличность произведений модальных логик. Произведение шкал Крипке F=(X,R) и G=(Y,S) определяется как шкала F*G=(X*Y,Rh,Rv), где
(a,b) Rh (c,d) ⟺ aRc и b=d;
(a,b) Rv (c,d) ⟺ a=c и bSd.
Произведением двух модальных логик называется логика класса шкал, состоящего из произведений шкал этих логик. Легко видеть, что локальная табличность обеих логик необходима, но не достаточна для локальной табличности их произведения. Для получения критерия мы описываем несколько синтаксических и семантических свойств, такие как: равномерная ограниченность сгустков одной из логик; свойство сокращения путей; конечность однопеременного фрагмента одной из логик.

Новые критерии позволяют найти ранее неизвестные семейства локально табличных бимодальных логик.

Доклад основан на совместной работе с И. Б. Шапировским. Препринт доступен по ссылке: http://arxiv.org/abs/2404.01670.

Видеозаписи предыдущих докладов:

https://www.youtube.com/playlist?list=PLEBNQnjHceeVxr2o766qqr993dyaKWRCX

Веб-страница с аннотациями и слайдами:

http://logic.math.msu.ru/sem/ml/

Для получения ссылки Zoom пишите на почту kudinov.andrey@gmail.com.
Убедительно просим всех подключающихся указывать в Zoom свои настоящие имя и фамилию!

➰ ВК

#матлог #новости

С прискорбием сообщаем, что 4 апреля 2025 года на 82-м году жизни скончалась Лариса Львовна Максимова — выдающийся математик, доктор физико-математических наук, главный научный сотрудник Института математики им. С. Л. Соболева СО РАН, ученица выдающегося алгебраиста и логика Анатолия Ивановича Мальцева.

Лариса Львовна вошла в историю как один из ведущих специалистов по неклассическим логикам. Её работы по модальным и суперинтуиционистским логикам стали классикой математической логики и получили международное признание. В 2018 году была награждена медалью института математики СО РАН «За выдающийся вклад в математику».

До последних дней Лариса Львовна сохраняла ясность мысли — её последняя статья увидела свет в начале 2024 года.

Для многих поколений математиков Лариса Львовна навсегда останется в памяти как соавтор легендарного задачника (Лавров, Максимова, "Задачи по теории множеств, математической логике и теории алгоритмов"; первое издание вышло в 1975 году), по которому и сегодня учатся студенты.

Светлая память.

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 8 апреля 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

К.А. Ковалёв (МФТИ)

Об интерпретациях полей в о-минимальных расширения вещественно замкнутых полей — 2

На предыдущем докладе мы сделали небольшой обзор результатов, связанных с понятием о-минимальности, и начали доказывать основной результат об интерпретируемости областей целостности в о-минимальных обогащениях вещественно замкнутых полей. Настоящий доклад начнётся с повторения схемы доказательства результатов, которые обсуждались ранее, в том числе мы остановимся подробнее на местах, которые «заметались под ковёр». Далее, мы завершим доказательство основного результата, идея которого кратко обсуждалась в конце предыдущего доклада. Кроме того, мы обсудим схему доказательства результатов, на которые мы ссылались (в частности, о введении структуры определимого многообразия на определимых группах).

Ссылка на предыдущий доклад: https://www.mathnet.ru/rus/present45786

➰ ВК

#матлог #наука #конференция

В среду 16 апреля 2025 г. в 18:30 в аудитории 1402 состоится научная конференция студентов, аспирантов и молодых ученых "Ломоносов - 2025".

Будут представлены доклады:

18:30-18:50 Аллеманд Аллан Олегович
"Топологическая теория разрешимости некоторых уравнений в элементарных функциях методом Арнольда"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1476634/181905/uid494087_report.pdf

18:50-19:10 Вишникин Максим Евгеньевич
"Базовые категориальные грамматики с ограничением на количество присваиваемых категорий"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1485934/186601/uid563464_report.pdf

19:10-19:30 Хайруллин Артур Миннахматович
"Вычисления с частичным оракулом"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1486507/186915/uid567073_report.pdf

19:30-19:50 Холодилов Филипп Дмитриевич
"О множествах натуральных чисел, замощающих натуральный ряд"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1476552/181859/uid683528_report.pdf

19:50-20:10 Deng Zhibo
"On the equivalence checking problem for deterministic top-down tree automata"
Тезисы: https://lomonosov-msu.ru/file/uploaded/10000/report/request_1476139/181592/uid952894_report.pdf

➰ ВК

#матлог #конференция

Journées sur les Arithmétiques Faibles
Weak Arithmetics Days 44

https://workshop.math.cas.cz/JAF44/

8-10 September 2025, Prague, Czech Republic
Aim. Weak arithmetics play a fundamental role in several areas of philosophy, mathematics, and computer science, by studying the nature and properties of natural numbers from a logical point of view. The aim of the conference is to provide a forum for researchers to present their results to members of communities who study or apply weak arithmetics in various fields and formalisms. Previous JAFs.

Topics. Proofs in arithmetic with restricted system of axioms; non-standard models of such systems; decidability, undecidability, and complexity of arithmetical theories; definability in arithmetic structures; machines, automata and words, related to arithmetic; finite model theory, word structures.

Location. Institute of Mathematics, Czech Academy of Sciences. The institute is in the centre of Prague, a few minutes walk from Wenceslas Square.

Programme. TBA; confirmed speakers

Albert Atserias, Technical University of Catalonia
Leszek Kołodziejczyk, University of Warsaw
Jan Krajíček, Charles University
Contributed papers. Authors are invited to send an abstract not exceeding three pages as an electronic submission in the form of a pdf file, to be sent both to cegielski@u-pec.fr and to thapen@math.cas.cz. Submissions are to be received before 2 June 2025. Authors will be notified of acceptance before 5 July 2025.

Registration. To register, send your details (full name, affiliation, planned dates of arrival and departure) to thapen@math.cas.cz. There is no conference fee.

Financial support. We have some funds to support students coming to Prague to attend the conference. Please contact Neil Thapen, thapen@math.cas.cz, to apply.

Contact. For any enquires contact Patrick Cégielski, cegielski@u-pec.fr or Neil Thapen, thapen@math.cas.cz.

JAF steering committee. Patrick Cégielski (Paris XII), Julien Cervelle (Paris XII), Andrés Córdon-Franco (Seville), Ali Enayat (Göteborg), Costas Dimitracopoulos (Athens), Alex Esbelin (Clermont-Ferrand), Neil Thapen (CAS)

Local organizing committee. Neil Thapen (CAS), Pavel Hrubeš (CAS), Ondřej Ježil (Charles University)

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

3 April 2025, 16.30 CET = 18.30 Moscow time

Speaker: Matthew Cook
Title: The Understanding Machine

Abstract:
One of the still-distant goals of AI is to generate understanding out of raw data. After all, a brain is a machine that can do this. Inspired by how the visual cortex appears to operate, combined with a simple algebra for manipulating an abstraction of the structures that arise, we look at what happens when we apply this to trying to understand the one-dimensional world of binary addition problems. Starting with raw data, and then mechanically applying the simplifying rules of the algebra, we indeed reach a new understanding, yielding a new binary addition algorithm.

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 04.04.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Павел Разумный

Название: Об алгоритмической сложности множества теорем логики QGL, расширенной нефундированными выводами

Аннотация.

Будет рассмотрена модальная логика предикатов QGL (предикатный аналог логики Гёделя-Лёба), расширенная нефундированными выводами. Нефундированный вывод - это дерево формул, построенное по правилам вывода (в нашем случае MP, Nec и правила Бернайса), в корне которого стоит выводимая формула, листья помечены аксиомами и гипотезами, а все бесконечные ветви содержат бесконечно много применений правила Nec. Эта система корректна и слабо полна относительно топологической семантики.
В докладе будет доказан результат о сложности множества теорем данной логической системы: множество теорем QGL, расширенной нефундированными выводами, является полным в классе Sigma^1_1 аналитической иерархии.

➰ ВК

#матлог #конференция

FPMW-ESPM Conference 2025
Joint Seventeenth French Philosophy of Mathematics Workshop and Second Conference of the European Society for the Philosophy of Mathematics

https://fpmwespm2025.sciencesconf.org/

The seventeenth edition of the French Philosophy of Mathematics Workshop (FPMW 17) and the second conference of the European Society for the Philosophy of Mathematics will be held from the 15th to the 17th of October 2025 in Paris, at Université Paris Cité and Université Paris 1 Panthéon-Sorbonne.

The workshop program consists of five talks by invited speakers and five contributed talks (see the programs of previous editions of the workshop at the following address: https://philmath.hypotheses.org/fpmw).

The invited speakers are:
• Timothy Gowers (Collège de France)
• Elaine Landry (UC Davis)
• Georg Schiemer (University of Vienna)
• David Rabouin (CNRS, SPHERE, Paris)
• Andrea Sereni (IUSS Pavia)

For the five contributed talks, all topics and approaches in the philosophy of mathematics are welcome.
The workshop is also open to philosophical talks about mathematics which do not fall under the philosophy of mathematics in a strict sense.

Submission window: April 15th, 2025 - May 15th, 2025.
Notification of acceptance (by email): July 1st, 2025.

Length of talks: 1-hour talk followed by 30 minutes of discussion.

The languages of the workshop will be French and English. Talks in French should be supported by slides in English.

Proposals (between 10,000 and 15,000 characters), prepared for anonymous review, should be sent in PDF format to fpmw-espm2025@sciencesconf.org copying in Brice Halimi brice.halimi@u-paris.fr in an email entitled “FPMW-ESPM2025”.

The workshop is supported financially by the Research Network PHILMATH, the European Society for the Philosophy of Mathematics, and the CNRS research units SPHERE (Université Paris Cité & CNRS) and IHPST (Université Paris 1 Panthéon-Sorbonne & CNRS).

Scientific committee:
• Andrew Arana (Université de Lorraine)
• Silvia De Toffoli (IUSS Pavia)
• Mirna Džamonja (Université Paris Cité)
• Emmylou Haffner (CNRS, ENS)
• Brice Halimi (Université Paris Cité)
• Mary Leng (University of York)
• Øystein Linnebo (University of Oslo)
• Jean-Pierre Marquis (Université de Montréal)
• Carlo Nicolai (King's College London)
• Alexander Paseau (University of Oxford)
• Frédéric Patras (CNRS, Université Côte d’Azur)
• Jean-Jacques Szczeciniarz (Université Paris Cité)

➰ ВК

#матлог #наука

Представляем вашему вниманию презентацию профессора нашей кафедры Шехтмана Валентина Борисовича, которая демонстрировалась сегодня на встрече кафедры со студентами второго курса!

В этой короткой презентации сформулированы целых две интереснейшие открытые проблемы 😱

�� present25n.pdf

➰ ВК

#матлог #учёба #просеминар

💥В четверг 3 апреля на просеминаре по математической логике и информатике будет тема "Наследственно конечные множества" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://vk.com/away.php?to=https%3A%2F%2Ft.me%2F%2B8lzSUf8ghLAzMjRi&utf=1
✅Можно заранее порешать задачи (прикреплены к посту).

✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

�� HF_ZFC2025.pdf

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 2 апреля.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Антон Кащенко

Тема: Топологический квадрат логики S4.1

Аннотация.

Существует много способов комбинирования модальных логик. Помимо соединений и произведений, основанных на семантике Крипке, рассматриваются также и топологические произведения. Они были впервые введены Й. ван Бентемом с соавторами в 2006 году и представляют собой естественный способ комбинирования логик, основанный на топологической интерпретации модальностей. Известно, что топологическое произведение двух модальных логик находится между их соединением и произведением. В работе А.В. Кудинова приводится пример топологического произведения (а именно произведение логик S4 и S4.1), находящегося строго между соединением и расширяющимся произведением. Топологический квадрат логики S4.1 (это логика S4 с аксиомой Маккинси) также оказался нетривиальным произведением. Кроме того, эти топологические произведения оказались финитно аппроксимируемыми и разрешимыми, в отличии от Крипке-произведений этих логик, которые являются неразрешимыми. В этом докладе будут рассмотрены оба этих произведения.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия

4 апреля (пятница) в 18.30 состоится очередное заседание исследовательского семинара "From the Logical Point of View".

Тема доклада: Эпистемология математики между прагматизмом и эмпиризмом.

Докладчик: Арсен Вольский.

Аннотация: Традиционные исследования в области эпистемологии математики часто предполагают, что математические утверждения обладают априорной природой и абсолютной достоверностью, доказательства в математике не вызывают сомнений, а их критерии остаются неизменными, исторический контекст математических практик при этом игнорируется как не имеющий отношения к, собственно, эпистемологическому анализу. В своём докладе я предлагаю альтернативный взгляд на эпистемологию математики, который сближает её с эпистемологией естественных наук, представляющий собой промежуточную позицию между эмпиризмом и прагматизмом.

Ждём вас в кабинете А-117 или в Zoom!

Анонс: https://llfp.hse.ru/announcements/1030074442.h

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), only Kontur Talk (www.mathnet.ru/eng/conf876)

07.04.2025 Yanjing Wang (Peking University, https://wangyanjing.com/): Knowing how to understand intuitionistic logic (and its relatives) (online)

In this talk, we provide an intuitive understanding of intuitionistic logic by interpreting it as a logic of knowing how (to prove). The approach is inspired by scattered but related ideas hidden in the vast literature of math, philosophy, CS, and linguistics about intuitionistic logic, which also echoes Heyting's largely forgotten conception of intuitionistic logic as "a logic of knowing". The key technique is to combine the bundled modality we developed in the past decade with the BHK-style interpretation. If time permits, I will demonstrate the use of this epistemic interpretation with applications in inquisitive logic, dependence logic, and deontic logic.

➰ ВК

#матлог #конференция

CCR 2025: CALL FOR ABSTRACTS

========
18th International Conference on Computability, Complexity and Randomness (CCR 2025)
https://ccr2025.sciencesconf.org/

June 16-20, 2025, LaBRI, University of Bordeaux, France

========

TOPICS:
* Algorithmic randomness
* Computability theory
* Kolmogorov complexity
* Computational complexity
* Reverse mathematics and logic

========

SUBMISSION INFORMATION:

Authors are invited to submit an extended abstract of 1-2 pages on the conference website. Submissions can be done at any time and notification of acceptance or rejection will be sent shortly after submission. The deadline for submitting an abstract is April 30, 2025.

========

INVITED SPEAKERS:

* Elvira Mayordomo (Universidad de Zaragoza, Spain)
* Joseph Miller (University of Wisconsin–Madison, USA)
* Kenshi Miyabe (Meiji University, Japan)
* Raul Santhanam (Oxford University, UK)
* Andrea Sorbi (Università degli Studi di Siena, Italy)

========

SCIENTIFIC PROGRAM COMMITTEE:

* Laurent Bienvenu (CNRS & Université de Bordeaux, France), co-chair
* Satyadev Nandakumar (IIT Kanpur, India)
* Takako Nemoto (Tohoku University, Japan)
* Cristobal Rojas (Universidad Católica de Chile, Chile)
* Andrei Romashchenko (CNRS & Université de Montpellier, France)
* Paul Shafer (University of Leeds, UK), co-chair
* Sebastiaan Terwijn (Radboud University, Netherlands)
* Francesca Zaffora-Blando (Carnegie-Mellon University, USA)

========

LOCAL ORGANIZERS:

* Laurent Bienvenu
* Subin Pulari
* Ivan Titov

========

ABOUT THE CONFERENCE:

CCR 2025 is the 18th edition of the International Conference on Computability, Complexity and Randomness, a series of conferences devoted generally to the mathematics of computation and complexity but that tends to primarily focus on algorithmic randomness/algorithmic information theory and its impact on mathematics. Previous editions of the conference have been held at Cordoba (Argentina), Buenos Aires (Argentina), Nanjing (China), Luminy (France), Notre Dame (USA), Cape Town (South Africa), Cambridge (UK), Moscow (Russia), Singapore, Heidelberg (Germany), Honolulu (USA), Mysore (India), Santiago de Chile (Chile), Astana (Kazakhstan), Cambridge (UK), Lake Kochel (Germany) and Nagoya (Japan).

This year's edition will be colocated with the annual meeting of the French community in computability and related topics (`Journées Calculabilités').

========

FUNDING:

Funding opportunities for student members of the Association for Symbolic Logic (ASL) are available. Applications should be directed to the Association for Symbolic Logic three months prior to the meeting, following the instructions here: https://aslonline.org/student-travel-awards/

➰ ВК

#матлог #конференция

19-21 июня 2025 года в Московском университете состоится международная научная конференция

«Четырнадцатые Смирновские чтения по логике»,

посвященная памяти выдающихся исследователей в области логики, методологии и философии науки Владимира Александровича и Елены Дмитриевны Смирновых.

Организаторы конференции: философский факультет МГУ имени М.В. Ломоносова, Институт философии РАН, Фонд логико-философских исследований.

В рамках конференции планируется проведение двух пленарных заседаний и работа секций:
- Символическая логика,
- Философская логика,
- История логики,
- Логика научного познания.

Основные мероприятия конференции планируется проводить в очном формате, отдельные заседания возможны в формате он-лайн.

Информация о конференции будет размещена на официальном сайте мероприятия http://www.smirnovreadings.ru

Материалы конференции будут опубликованы. Участники конференции предоставляют свои научные результаты в формате небольших статей в размере от 2 до 4 страниц выходного PDF файла (5000-10000 знаков стандартного неформульного текста). Статьи принимаются до 30 апреля 2025 года. Формат принимаемых файлов:
1) Тексты статей, содержащих формульные выражения, должны быть подготовлены только с помощью системы набора текста LaTeX (необходим исходный файл с расширением .tex), с использованием стилевого файла и инструкции для правильного оформления текста, размещенных на сайте конференции в разделе подача тезисов.
2) Текст без формульных выражений можно подготовить в формате MS Word. Авторы могут представить свои работы как на английском языке, так и на русском языке. Русскоязычный текст сопровождается также названием и аннотацией на английском языке (см. инструкцию). Обращаем ваше внимание на особенности в порядке проведения конференции.
Планируется выделение специальной подсекции, в рамках которой все выступающие будут делать доклады на английском языке.

После получения авторских статей вопрос о Вашем участии будет рассмотрен Программным комитетом. Программный комитет оставляет за собой право отклонять заявки, не соответствующие тематике конференции, а также редактировать присланные материалы при их подготовке к публикации. Участникам, чьи заявки прошли отбор, будет выслано официальное приглашение.

Подача статей. Статьи подаются через электронную почту smirnovreadings@philos.msu.ru

Персональные данные. Участники предоставляют в оргкомитет более детальные персональные данные, заполнив анкету участника, форму которой можно скачать на сайте конференции в разделе подача тезисов.

Контактная информация:
Адрес электронной почты Оргкомитета: smirnovreadings@philos.msu.ru
Телефон оргкомитета: +7 (495) 939-18-46

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 1 апреля 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

К.А. Ковалёв (МФТИ)

Об интерпретациях полей в о-минимальных расширениях вещественно замкнутых полей

Напомним, что структура (M, , ...) с линейным порядком называется o-минимальной, если любое определимое с параметрами подмножество M является конечным объединением интервалов и точек (например, любое вещественно замкнутое поле является таковым). Наш доклад будет посвящён интерпретациям полей в о-минимальных структурах, а именно, мы разберём следующий результат, который был получен в [1]: любое поле, интерпретируемое в о-минимальном расширении (обогащении) вещественно замкнутого поля, определимо изоморфно самому этому полю или его алгебраическому замыканию. Планируется провести два семинара. На первом семинаре мы дадим некоторый обзор известных результатов и начнём доказательство основного результата, а именно, мы докажем определимые аналоги теоремы о единственности решений дифференциальных уравнений и вложимости некоторых определимых групп в полную линейную группу.

[1] M. Otero, Y. Peterzil, A. Pillay. On groups and rings definable in o-minimal expansions of real closed fields. Bulletin of the London Mathematical Society 28(1), 7–14, 1996.

➰ ВК

#матлог #новости

⚡Встреча кафедры математической логики и теории алгоритмов со студентами 2 курса состоится 1 апреля в 18:30 в аудитории 1408 (это не шутка, а чистая правда...)

На встрече вы можете больше узнать о научных направлениях кафедры и выбрать своего будущего научного руководителя.

Видеозапись встречи с кафедрой 2022 года можно посмотреть по ссылке vk.com/wall-70743963_1238.

Подробнее о кафедре вы можете узнать по следующим ссылкам.
📎Презентация зав.кафедрой А.Л.Семёнова: https://prezi.com/view/t0oiMzfyh0FkG3UcDz5N/
📎Деятельность кафедры logic.math.msu.ru/about/
📎Направления исследований кафедры logic.math.msu.ru/research/
📎Примеры задач, которые вы можете решать на кафедре logic.math.msu.ru/problems/

➰ ВК

#матлог #новости

⚡Встреча кафедры математической логики и теории алгоритмов со студентами 2 курса состоится 1 апреля в 18:30 в аудитории 1408 (это не шутка, а чистая правда...)

На встрече вы можете больше узнать о научных направлениях кафедры и выбрать своего будущего научного руководителя.

Видеозапись встречи с кафедрой 2022 года можно посмотреть по ссылке vk.com/wall-70743963_1238.

Подробнее о кафедре вы можете узнать по следующим ссылкам.
📎Презентация зав.кафедрой А.Л.Семёнова: https://prezi.com/view/t0oiMzfyh0FkG3UcDz5N/
📎Деятельность кафедры logic.math.msu.ru/about/
📎Направления исследований кафедры logic.math.msu.ru/research/
📎Примеры задач, которые вы можете решать на кафедре logic.math.msu.ru/problems/

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 26 марта.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Константин Ковалев

Тема: Аналоги теоремы Шепердсона для языка с экспонентой (продолжение доклада предыдущей недели)

➰ ВК

#матлог #учёба #просеминар

💥В четверг 27 марта на просеминаре по математической логике и информатике будет продолжение темы "Игры Эренфойхта" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

➰ ВК

#матлог #не_мехмат #МИАН

Научный семинар кафедры методов современной математики (базовая кафедра МИАН в МФТИ),
25 марта, вторник, 18.00, только онлайн (для получения ссылки пишите учёному секретарю кафедры Оноприенко А.А.)

К. А. Ковалёв. Об аксиоматизации арифметики Бюхи

Аннотация: Арифметикой Бюхи (с основанием p = 2) называется теория натуральных чисел в языке с нулем, функцией последователя, сложением и специальной функцией, обозначаемой V_p, которая число n отображает в наибольшую степень p, делящую n. Хорошо известно, что данная теория является разрешимой, однако неизвестно никакой явной аксиоматизации этой теории (есть некоторые отрицательные результаты, полученные А. Запрягаевым). Цель данной работы состоит в отыскании такой аксиоматизации. Наша аксиоматизация состоит из некоторого конечного числа простых аксиом (похожих на арифметику Робинсона) и схемы аксиом вида ∃x φ(x) → ∃x ≤ n_φ φ(x), где натуральное число n_φ подбирается так, чтобы данная формула была истинна в стандартной модели. Выбор такого числа n_φ опирается на важное свойство арифметики Бюхи, а именно, что любое определимое в рассматриваемом языке множество A является p-автоматным (т. е., множество p-ичных записей элементов A распознаваемо некоторым конечным автоматом).

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 25 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

А.В. Грефенштейн (МИАН)

Инфинитарные исчисления для первопорядковой логики вероятности с распределением на носителе и её фрагментов — 2

На прошлом докладе было представлено инфинитарное исчисление для (односортной версии) первопорядковой логики вероятности с распределением на носителе и изложена схема доказательства соответствующей теоремы о сильной полноте. Настоящий доклад будет посвящён завершению этого доказательства и построению исчислений для естественных фрагментов рассматриваемой логики. В частности, нас будут интересовать линейный и базовый сублинейный фрагменты, а также «чисто вероятностный» фрагмент, в котором всякая классическая формула находится под \mu. В каждом из случаев мы обсудим, как нужно модифицировать исходное исчисление и как при этом меняется конструкция канонической модели и доказательство основной семантической леммы.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

24 March 2025, 16.30 CET = 18.30 Moscow time

Andrei Romashchenko
On the reduction of Kolmogorov complexity by relativization

Alexander Shen asked the following question: let us have a tuple of strings x_1,...,x_n and their Kolmogorov complexities v=(C(x_1),...,C(x_n)). For every string y we get the values of conditional complexities w=(C(x_1|y),...,C(x_n|y)). Which values w of conditional complexities can we obtain? Can we, for example, find a y such that each value C(x_i|y) is (approximately) a half of C(x_i)?

We show that the answer to the last question is positive for n=1 (trivial) and for n=2 (can be proven with Muchnik's theorem on condtional descriptions or with Shen's topological argument).

For n=3, the answer is negative: there exists a triple (x_1, x_2, x_3) such that C(x_1)=2n, C(x_2)=2n, C(x_3)=3n, and there is no y such that C(x_1|y)=n, C(x_2|y)=n, C(x_3|y)=1.5n. This negative result follows from combinatorial properties of discrete projective planes over prime fields (Bourgain, Katz, Tao).

➰ ВК

#матлог #наука #конференция

Ломоносовские чтения 2025, кафедра математической логики и теории алгоритмов

Научно-исследовательский семинар по математической логике
под руководством академика РАН Л. Д. Беклемишева и академика РАН А. Л. Семёнова

2 апреля 2025 г., среда, 18:30

Главное здание, сектор "А", ауд. 16-04

✅О теореме Гудман-Штрауса. Доклад профессора Верещагина Н. К.
✅О конструктивном исчислении предикатов. Доклад доцента Плиско В. Е.
✅Предикатные модальные логики ограниченной альтернативы. Доклад профессора Шехтмана В. Б.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия

21 марта (пятница) в 18.30 состоится очередное заседание исследовательского семинара "Формальная философия".

Тема доклада: Метафизика в философии математики и эпистемологические последствия для доказательства.

Докладчик: Илья Гущин (УрФУ).

Аннотация: В докладе будут рассмотрены две альтернативные классическому вариации платонизма в философии математики. В качестве аргумента в пользу классического платонизма часто указывается, что принятие его как метафизики обеспечивает уникальный эпистемологический статус для математического доказательства, чем обеспечивает преимущество математики над другими системами знания. В докладе будет показано, что в действительности классический платонизм создаёт серьезные трудности для доказательства, а его альтернативные версии позволяют от этих проблем избавиться.

Ждём вас в кабинете А-117 или в Zoom!

Анонс: https://llfp.hse.ru/announcements/1025647859.html

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 21.03.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Дудаков С.М. (ТвГУ, ВШЭ)

Название: О теориях алгебр подмножеств и решёток подалгебр

Аннотация.
Одним из способов построения новых алгебр является конструкция алгебры всех или некоторых подмножеств уже имеющейся. Например, для произвольной полугруппы S можно можно построить новую полугруппу exp S, элементами которой будут подмножества S, а операция определена поточечно. В докладе будут рассмотрены теории таких подалгебр exp A, когда исходная алгебра A снабжена бинарной операцией (то есть A — группоид). Будет показано, что при определённых условиях теория exp A позволяет интерпретировать элементарную арифметику (и даже - арифметику второго порядка) или, как минимум, арифметические операции для начального фрагмента натурального ряда. Аналогичный результат будет показан для теории решётки lat A подалгебр алгебры A. Далее, для любого класса K алгебр можно рассмотреть классы exp K и lat K. Первый из них состоит из всех алгебр вида exp A, а второй - из всех решёток вида lat A, когда A берётся из K. Будет показано, что для широко распространённых классов K теории классов exp K и lat K тоже допускают интерпретацию элементарной арифметики. В частности, они неразрешимы и не имеют рекурсивной аксиоматизации.

➰ ВК

#матлог #учёба #просеминар

💥В четверг 20 марта на просеминаре по математической логике и информатике будет тема "Игры Эренфойхта" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi
✅Можно заранее порешать задачи (прикреплены к посту).

✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

�� Ehrenfeucht25.pdf

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 19 марта.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Константин Ковалев

Тема: Аналоги теоремы Шепердсона для языка с экспонентой

Аннотация: В 1964 году Дж. Шепердсон получил результат, который полностью характеризует модели теории IOpen (фрагмент арифметики Пеано с бескванторной индукцией), а именно, дискретно упорядоченное полукольцо M является моделью IOpen тогда и только тогда, когда соответствующее кольцо является целой частью вещественного замыкания R своего поля частных (то есть, для любого r из R найдется m из M, такое что m = r m + 1). На основе этого результата он построил рекурсивную нестандартную модель IOpen и получил явные результаты о недоказуемости некоторых простых утверждений (например, иррациональности корня из 2). Цель нашей работы – получить аналогичные результаты для расширения арифметического языка экспонентой или функцией возведения в степень. Мы получим результаты, устанавливающие аналогичные соответствия между моделями арифметических теорий IOpen(exp) (бескванторная индукция в языке с экспонентой), IOpen(x^y) (бескванторная индукция в языке с функцией возведения в степень) и IOpen + T_{x^y} (T_{x^y} – некоторые естественные арифметические аксиомы для x^y и неравенство Бернулли) и моделями некоторых фрагментов теории Th(\R, exp) (элементарная теория вещественных чисел со стандартной экспонентой). Основываясь на этих результатах, мы явно построим нестандартные модели (к сожалению, не рекурсивные) IOpen(exp) и IOpen(x^y) и получим аналогичные результаты о недоказуемости. В конце доклада, если останется время, сделаем обзор некоторых дальнейших результатов по этой теме.

➰ ВК

#матлог #не_мехмат #ВШЭ

В пятницу 21 марта 2025 г. в 18:10 на Математическом семинаре ФКН ВШЭ состоится доклад Павла Соколова на тему "Теория типов и альтернативные основания математики".

Аннотация:

Теория типов — сравнительно молодая область на стыке математической логики, теории категорий и компьютерных наук. Появившись как один из вариантов разрешения парадоксов наивной теории множеств, системы типов нашли неожиданное применение в языках программирования как средство легковесной верификации как пользовательского кода, так и программных оптимизаций. Кроме этого, системы типов естественным образом обеспечивают конструктивный и, более того, синтетический подход к математике (синтетическая (дифференциальная) геометрия, синтетическая топология, синтетическая теория гомотопий и т.д.) В особенности, гомотопическая теория типов (HoTT) претендует на статус альтернативного основания (конструктивной) математики.

В рамках данного доклада будет изложена история становления теории типов как самостоятельной дисциплины с изложением основных математических результатов, начиная с Principia Mathematica Бертрана Рассела и заканчивая сегодняшними наиболее активными направлениями исследований.

Место проведения: Покровский бульвар 11, аудитория R305.

Объявление и ссылку для регистрации см. на странице семинара:
https://cs.hse.ru/seminatfkn/

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 18 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

А.В. Грефенштейн (МИАН)

Инфинитарные исчисления для первопорядковой логики вероятности с распределением на носителе и её фрагментов

Первопорядковая логика вероятности с распределением на носителе — весьма известный формальный язык для рассуждения о вероятностях в теоретической информатике. В односортной версии этой логики имеются кванторы по элементам носителя, а в двухсортной добавляются кванторы по вещественным числам. Как было показано М. Абади и Дж. Хальперном, при почти всех сигнатурах двухсортная версия имеет как минимум ту же сложность, что и полная арифметика второго порядка, а потому для неё невозможно построить адекватное инфинитарное исчисление; см. также доклад С.О. Сперанского (https://www.mathnet.ru/php/seminars.phtml?presentid=45377&option_lang=rus).

Нас будет интересовать аксиоматизируемость односортной версии вышеупомянутой логики. Первый доклад будет посвящён построению сильно полного инфинитарного исчисления для неё. Здесь «инфинитарность» означает, что наше исчисление будет содержать омега-правила, т.е. правила со счётным числом посылок; однако сами формулы будут конечными. На втором докладе мы рассмотрим различные естественные фрагменты данной логики.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), only Kontur Talk (www.mathnet.ru/eng/conf876)

17.03.2025 семинара не будет

24.03.2025 В.Л. Селиванов, И.В. Смирнов (СПбГУ): Ординальные инварианты гомоморфных предпорядков к-размеченных лесов

В докладе обсуждается комбинаторная сложность хороших частичных порядков (ХЧП). Название является калькой английского термина WPO (Well Partial Order)-theory (часто встречается также название WQO-theory). К сожалению, в русскоязычной литературе нет общепринятого наименования этой теории, в которой изучаются частичные порядки, не имеющие бесконечно убывающих цепей и бесконечных антицепей; такие порядки и называются хорошими. Теория ХЧП имеет богатую историю и приложения к различным разделам математики и информатики.

К числу инструментов теории ХЧП относятся так называемые ординальные инварианты, т.е. ординалы, измеряющие те или иные аспекты комбинаторной сложности ХЧП. Вычисление ординальных инвариантов конкретных ХЧП (высоты, ширины и максимального ординала) часто оказывается нетривиальной задачей, которая к настоящему времени решена лишь для небольшого числа важных ХЧП.

В данной работе вычислены (в терминах ординалов Веблена) ординальные инварианты для конкретных указанных в заглавии ХЧП, введенных П. Хертлингом и нашедших приложения в дескриптивной теории множеств и теории автоматов на бесконечных словах.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

17 March 2025, 16.30 CET = 18.30 Moscow time

Ivan Baburin
Universality in Asynchronous Cellular Automata

Abstract. Universality in Asynchronous Cellular Automata Ivan Baburin Kolmogorov Seminar Talk description A cellular automaton is a dynamical system consisting of an infinite array of cells, such that each cell uses a local neighborhood to perform a transition. An asynchronous cellular automaton (ACA) is a modification of cellular automata where every cell can update at is own tempo, without the need for global synchronization. In this talk we survey computational abilities of asynchronous cellular automata and show that—despite their fundamental differences—most asynchronous automata can invariantly “simulate” their synchronous counterparts [1]. To achieve that, we present two characterizations of invariance in asynchronous automata: – An algebraic approach using the notion of commutativity, as introduced by G´acs [2]. – A novel computational approach using flip automata networks, which additionally allows for simpler simulations and can be used to construct some of the smallest universal ACAs [3]. Finally, we discuss the limits of asynchronous computation by demonstrating that for certain automata neither universality nor reliable simulation can be achieved. Further Reading More details can be found in the corresponding paper [3].

References
1. T. Worsch, “Towards intrinsically universal asynchronous ca,” Natural Computing, vol. 12, no. 4, pp. 539–550, 2013.
2. P. Gacs, “Deterministic computations whose history is independent of the order of asynchronous updating,” 2001.
3. I. Baburin, M. Cook, F. Gr¨otschla, A. Plesner, and R. Wattenhofer, “Universality frontier for asynchronous cellular automata,” 2025.

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 14.03.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Анна Задаля

Название: Темпоральные логики LTL и CTL.

Аннотация.
Доклад будет посвящён темпоральным логикам LTL и CTL. Мы познакомимся с базовыми определениями, касающимися этой темы. Данные логики являются расширениями классической логики высказываний, полученными путём добавления специальных модальностей. Эти модальности (темпоральные операторы) позволяют формулировать утверждения про факты, истинность которых может меняться с течением времени.
Предварительных знаний не требуется, все определения будут даны в процессе доклада.

➰ ВК

#матлог #учёба #просеминар

💥В четверг 13 марта на просеминаре по математической логике и информатике будет продолжение темы: "Колмогоровская сложность" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi

✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале!

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 12 марта.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Иван Слюсарев

Тема: Модальное расширение двойственной классической паранепротиворечивой логики

Аннотация
Паранепротиворечивые логики - направление неклассических логик, возникшее в 30-40е годы XX века, относительно которых верно, что существуют такие формулы A, B (в языке данных логик), что из {A,¬A} невыводима формула B (минимальный критерий паранепротиворечивости по Г. Присту) Паранепротиворечивыми логиками являются, например, дискуссивные логики (discussive logic) С. Яськовского, минимальная логика И. Йоханссона, бесконечная иерархия логик Н. да Косты, релевантные логики E и R, а также трехзначная логика Г. Приста.

В [1], [2] были введены две паранепротиворечивые логики с унарной логической связкой, двойная итерация которой совпадает по своим дедуктивным свойствам с классическим отрицанием. Данные логики были обозначены как CP (classical paraconsistent logic) и dCP (dual classical paraconsistent logic). Относительно данных логик доказаны основные металогические свойства (полнота и корректность относительно некоторых четырёхзначных семантик, построены секвенциальные исчисления с устранимым сечением и т. д.). Модальные и кванторные расширения данных логик ранее не рассматривались. В докладе будет начато рассмотрение данных расширений путем представления модальной версии логики dCP , будет описана семантика данной логики, аналогичная семантике модальной версии логики BK из [3]; будет доказана полнота и корректность данной логики (модальной версии логики dCP ) относительно этой семантики. Кроме того, предварительно будет дано некоторое историко-логическое введение, связанное с историей развития паранепротиворечивых логик.

Список литературы
[1] Belikov A., Grigoriev O., Zaitsev D. On connegation // Relevance Logics and other Tools for Reasoning. Essays in Honor of J. Michael Dunn. Vol. 46 of Tributes. United States: United States, 2022. P. 73 88.
[2] Kamide, N.(2017). Paraconsistent double negations as classical and intuitionistic negations, Studia Logica 105(6): 1167 1191.
[3] Odintsov, S. P., and H. Wansing, Modal logics with Belnapian truth values, Journal of Applied Non Classical Logics 20(3): 279 301, 2010.

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (https://www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (https://homepage.mi-ras.ru/~sk/) и С.О. Сперанского (https://homepage.mi-ras.ru/~speranski/)

Время: 11 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

Н.В. Лукашов (НИУ ВШЭ)

Сюрреальные числа Конвея

В своём докладе я совместной трансфинитной индукцией дам определение сюрреальных чисел и отношения порядка на них, как это делает Джон Конвей в своей книге «On Numbers and Games». Дальше мы покажем, что этот порядок является отношением предпорядка, и опишем все «конечные» сюрреальные числа, т.е. такие, которые получаются на конечных шагах. Затем мы обсудим, как вводятся операции сложения и умножения на сюрреальных числах, относительно которых они формируют упорядоченное Поле (Поле с большой буквы, поскольку сюрреальные числа образуют не множество, а собственный класс). В заключение мы подробно поговорим о шаге \omega в конструкции сюрреальных чисел, а также о том, как в них вкладываются вещественные числа, каким образом там представлены инфинитезимали, и, если останется время, о нормальных формах сюрреальных чисел.

❗Просьба ко всем потенциальным участникам зарегистрироваться на странице семинара. Ссылка для Контур.Толк будет отправлена зарегистрированным участникам накануне заседания.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

10 March 2025, 16.30 CET = 18.30 Moscow time

Existence of key-agreement, a Kolmogorov complexity characterization.

Bruno Bauwens

In a key-agreement protocol, Alice and Bob have a natural number n, exchange messages, and obtain with high probability the same string x. A time bounded adversery listen to the messages and guesses the key x. A common conjecture in cryptography is that there exist protocols in which the adversary fails to guess the key with probability 1 - 1/n^c for all c. In 2023, Ball, Liu, Mazor and Pass gave an equivalent formulation of this conjecture using Kolmogorov complexity ("Kolmogorov goes to cryptomania"). We present a simple proof this equivalence.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Room 313 MIAN + Kontur Talk (https://www.mathnet.ru/eng/conf876)

10 марта 2025 года

Тихон Пшеницын (МИАН, аспирант)
Интуиционистская линейная логика первого порядка и гиперграфовые языки (очный доклад)

Некоммутативные субструктурные логики имеют несколько точек соприкосновения с теорией формальных языков. С одной стороны, такие логики, например, исчисление Ламбека, используются как механизм задания формальных языков в категориальных грамматиках. С другой стороны, формальные языки возникают как модели субструктурных логик; основной результат в этом направлении, доказанный М.Р. Пентусом, гласит, что исчисление Ламбека корректно и полно относительно языковой семантики.

В докладе предполагается обсудить аналогичные взаимосвязи между субструктурными логиками первого порядка и гиперграфовыми языками. В первой части доклада будет предложено определение гиперграфовых L-грамматик, основанных на произвольной первопорядковой логике L (в секвенциальном формате). Оно обобщает понятие MILL1-грамматик — категориальных грамматик, основанных на мультипликативной интуиционистской линейной логике первого порядка MILL1. Последние рассматривались в работах [Μοοt, 2014], [Slavnov, 2023]. Будет показана связь гиперграфовых MILL1-грамматик, а также грамматик над интуиционистской линейной логикой первого порядка ILL1 с порождающими гиперграфовыми грамматиками. В качестве следствия будет дан ответ на открытый вопрос из [Moot, 2014] о классе языков, задаваемых строковыми MILL1-грамматиками; в частности, будет показано, что этот класс содержит NP-полный язык.

Во второй части доклада будет дано определение языковой семантики для логики MILL1, в рамках которой формулы интерпретируются гиперграфовыми языками, а мультипликативная конъюнкция (тензор) линейной логики интерпретируется операцией параллельной композиции. Эта операция хорошо известна в теории графовых грамматик в контексте HR-алгебр [Courcelle, 1990]. Будет установлена теорема о корректности и полноте для негативного фрагмента MILL1 (с помощью аналога конструкции [Buszkowski, 1982]). Вопрос полноты всей логики MILL1 относительно гиперграфово-языковой семантики остается открытым.

Доклад основан на препринте https://arxiv.org/abs/2502.05816.

🔗 Seminars "Proof Theory" and "Logic Online Seminar"


➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 07.03.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Анастасия Оноприенко

Название: Таблицы Лейвера

Аннотация.
Таблицы Лейвера - конечные комбинаторные объекты с очень простым определением. Они были введены в рассмотрение Ричардом Лейвером в 1990-х годах в процессе исследования им теории множеств. Тем не менее, изучение свойств таблиц Лейвера требует очень сильных методов, выходящих далеко за "стандартную" математику, лежащую в рамках теории множеств ZFC.
В докладе будет дано введение в эту любопытную и, к сожалению, малоизвестную тему. Предварительных знаний для понимания доклада не требуется, все определения будут даны.

🔗 Логика в Москве


➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия

7 марта (пятница) в 19.30 состоится очередное заседание исследовательского семинара "Формальная философия".

Тема доклада: Эпистемология математики между прагматизмом и эмпиризмом.

Докладчик: Арсен Вольский.

Аннотация: Традиционные исследования в области эпистемологии математики часто предполагают, что математические утверждения обладают априорной природой и абсолютной достоверностью, доказательства в математике не вызывают сомнений, а их критерии остаются неизменными, исторический контекст математических практик при этом игнорируется как не имеющий отношения к, собственно, эпистемологическому анализу. В своём докладе я предлагаю альтернативный взгляд на эпистемологию математики, который сближает её с эпистемологией естественных наук, представляющий из себя промежуточную позицию между эмпиризмом и прагматизмом.

Ждём вас в кабинете А-117 или в Zoom!

Анонс: https://llfp.hse.ru/announcements/1021417749.html

➰ ВК

#матлог #учёба #просеминар

💥В четверг 6 марта возобновляется работа просеминара по математической логике и информатике!
✨Тема: "Колмогоровская сложность" (А.А.Оноприенко).
✨Аннотация. Понятие колмогоровской сложности позволяет измерять количество информации, заключённой в индивидуальных конечных объектах и тем самым отличать простые объекты от сложных. На просеминаре мы обсудим вводные задачи, касающиеся понятия колмогоровской сложности.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус). (Обратите внимание, что аудитория поменялась по сравнению с 1 семестром!)
✅По просьбам участников создан чат просеминара в телеграме: https://t.me/+8lzSUf8ghLAzMjRi

✅Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале!

�� Просеминар по математической логике и информатике


📝 kolm_complexity2025.pdf

➰ ВК

#матлог #наука #конференция

First Annual Paris-Chicago Joint Conference in the Philosophy of Logic and Mathematics (https://philevents.org/event/show/132186)
Paris, France, 12th and 13th June, 2025, at the John W. Boyer Paris Center.

The first annual Paris-Chicago Joint Conference in the Philosophy of Logic and Mathematics will take place in the University of Chicago Paris Center on the 12th and 13th of June, 2025.

This is the first a recurring series of events hosted at the new University of Chicago campus in Paris, aiming to bring together American and European researchers working at the intersection of logic, philosophy, and mathematics. Accordingly, we welcome papers from a wide range of areas, including but not limited to:

- Philosophy of mathematics
- Philosophy of logic
- Developments in the foundations of mathematics
- Interactions between proofs and programs
- History of logic and mathematics
- AI and mathematics

This event is supported by a grant from the University of Chicago International Institute for Research in Paris. The conference will be held in English.

INVITED SPEAKERS: TBA

PARTICIPATION

Those interesting in presenting should send an abstract of their talk (approximately 150-300 words) along with a coversheet containing their name, institutional affiliation and title of the paper to stefanosjones@uchicago.edu by no later than March 15th.

Notifications of acceptance are expected to be provided by the end of March.

Conference attendance is free.

ORGANIZERS

Kevin Davey (University of Chicago), Brice Halimi (Université Paris Cité), Stefanos Jones (University of Chicago)

CONTACT

Questions can be addressed to Kevin Davey at kjdavey@uchicago.edu or Stefanos Jones at stefanosjones@uchicago.edu

🔗 Paris-Chicago Joint Conference in the Philosophy of Logic and Mathematics


➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (https://www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (https://homepage.mi-ras.ru/~sk/) и С.О. Сперанского (https://homepage.mi-ras.ru/~speranski/)

❗Замена

Доклад А.В. Грефенштейна откладывается в связи с болезнью. Вместо этого будет доклад С.О. Сперанского — см. подробности ниже.

Время: 4 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

С.О. Сперанский (МИАН)

О сложности первопорядковой логики вероятности с распределением на носителе

Первопорядковая логика вероятности с распределением на носителе — известный формальный язык для рассуждения о вероятностях в теоретической информатике, предложенный Дж. Хальперном. В односортной версии этой логики имеются кванторы по элементам носителя, а в двухсортной добавляются кванторы по вещественным числам.

Сложность вышеупомянутой логики была изучена М. Абади и Дж. Хальперном (1994). Основной интерес здесь представляют нижние сложностные оценки. Для их получения в статье М. Абади и Дж. Хальперна существенно использовались сложение и умножение между вероятностями. В настоящем докладе будет показано, как получить те же самые сложностные оценки для малых «качественных» (англ. qualitative) фрагментов, в которых нет ни сложения, ни умножения. В частности, в односортном случае будет достаточно равенств между вероятностями от бескванторных первопорядковых формул.

🔗 Семинар С. Л. Кузнецова и С. О. Сперанского "Вероятностные и субструктурные логические системы&


➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

Tuesday, March 4, 2025, 17:00 (Moscow time)

Speaker: Robert Sedgewick, Princeton University.

Title: Cardinality estimation.

Abstract: This talk surveys decades of research on algorithms for estimating the number of different items in a DataStream, from early algorithms of Flajolet and Martin to the recent algorithms of Lumbroso, Janson and Sedgewick. The story is a poster child for the use of probabilistic methods in algorithm science.

➰ ВК

#матлог #наука #конференция

--------------------------------------------------------------
↪ Международный молодежный научный форум ЛОМОНОСОВ

🔥 ОТКРЫТА РЕГИСТРАЦИЯ на Международную конференцию «ЛОМОНОСОВ – 2025»

Дорогие коллеги, уже открыта регистрация на некоторые секции XXXII Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов»!

✅ Дедлайн подачи заявок: до 3 марта (включительно).
✅ Подробная информация и регистрация на портале: lomonosov-msu.ru/rus/event/10000/

В этом году Международный молодёжный научный форум «Ломоносов» будет проходить с 11 по 25 апреля 2025 💫

Что Вас ждёт:
💠 Более 40 секций, отражающих все основные направления современной фундаментальной и прикладной науки;
💠 Работа региональных площадок научно-образовательных консорциумов «Вернадский» и на базе зарубежных и российских филиалов МГУ для всех заинтересованных.
💠 Дискуссионные площадки, лекторий и многое другое!

Присоединяйтесь к самому масштабному сообществу талантливых молодых исследователей, делайте первые шаги в науке и находите единомышленников!

Ваше будущее в науке начинается здесь! 🚀

#МГУ #270летМГУ #MSU #Ломоносов2025 #Lomonosov
#Lomonosov2025 #ФорумЛомоносов
#СтудсоюзМГУ #СНО_МГУ #ВСК_Вернадский
#наука #образование

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 28.02.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Федор Пахомов

Название: Инфинитарная логика доказуемости

В данном докладе я расскажу об аналогах и обобщениях некоторых результатов об обычной логике доказуемости на инфинитарный случай. С одной стороны, будет дана полная по Крипке нефундированная система доказательств на основе глубокого вывода. С другой стороны, будет дана интерпретация связки бокс как некоторых предикатов доказуемости в допустимых фрагментах инфинитарной первопорядковой логики.

🔗 Логика в Москве


➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (https://www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (https://homepage.mi-ras.ru/~sk/) и С.О. Сперанского (https://homepage.mi-ras.ru/~speranski/)

Время: 4 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

А.В. Грефенштейн (МИАН)

Инфинитарные исчисления для первопорядковой логики вероятности с распределением на носителе и её фрагментов

Первопорядковая логика вероятности с распределением на носителе — известный формальный язык для рассуждения о вероятностях в теоретической информатике, предложенный Дж. Хальперном. В односортной версии этой логики имеются кванторы по элементам носителя, а в двухсортной добавляются кванторы по вещественным числам. Известно, что при почти всех сигнатурах двухсортная версия имеет как минимум ту же сложность, что и полная арифметика второго порядка, а потому для неё невозможность построить адекватное (даже слабо) полное инфинитарное исчисление.

Нас будет интересовать односортная версия вышеупомянутой логики. Первый доклад будет посвящён построению сильно полного инфинитарного исчисления для неё. Здесь «инфинитарность» означает, что наше исчисление будет содержать омега-правила, т.е. правила со счётным числом посылок; однако сами формулы будут конечными. На втором докладе мы рассмотрим различные естественные фрагменты данной логики.

❗Просьба ко всем потенциальным участникам зарегистрироваться на странице семинара. Ссылка для Контур.Толк будет отправлена зарегистрированным участникам накануне заседания.

🔗 Семинар С. Л. Кузнецова и С. О. Сперанского "Вероятностные и субструктурные логические системы&


➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 26 февраля.
‼ВНИМАНИЕ Время поменялось.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик:
В.Б. Шехтман (ВШМ МФТИ)

Тема: Полупроизведения модальных логик

Аннотация:
Наряду с соединением (fusion) и произведением, полупроизведение представляет собой операцию над модальными логиками, которая объединяет их модальности и добавляет новые аксиомы. Соответствующая операция над шкалами Крипке - взятие подмножеств произведений, устойчивых по первой координате. Полупроизведения также связаны с модальными логиками предикатов и топологическими модальными логиками.

Свойства полупроизведений еще недостаточно изучены. В докладе будет дан обзор известных результатов, в том числе полученных в последние годы совместно с Д. Шкатовым.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Room 313 MIAN + Kontur Talk (https://www.mathnet.ru/eng/conf876)

03 March 2025, 13:00 UTC, the Proof Society Seminar

Speaker: Henry Towsner (University of Pennsylvania, https://www.sas.upenn.edu/~htowsner/)

Title: Proofs that Modify Proofs

Abstract: In this talk, we outline an approach to cut-elimination for full second order arithmetic using a modified form of the Buchholz Omega-rule. The usual Buchholz Omega-rule is a rule branching over ("small") deductions; this method works for systems around the strength of Pi11-comprehension, but breaks down approaching Pi12-comprehension.

We describe an extended sequent calculus in which the cut-elimination functions can themselves be represented by non-well-founded deductions. The Omega-rule can then be reinterpreted as a rule which takes a function as a premise. The extension to Pi12-comprehension then requires us to work with functionals---that is, functions on functions---and iterating through the finite types extends the method to full second order arithmetic. We will also briefly describe how to assign "ordinals" to non-well-founded deductions to extract an ordinal analysis from the cut-elimination algorithm.

🔗 Seminars "Proof Theory" and "Logic Online Seminar"


➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Room 313 MIAN + Kontur Talk (https://www.mathnet.ru/eng/conf876)

24.02.2025 Об отношениях между предпорядками Рудин – Кейслера и Комфорта, часть I

Н. Л. Поляков, Д. И. Савельев (докладчик)

При рассмотрении канонических ультрарасширений многоместных операций естественно возникают отношения на ультрафильтрах, обобщающие классический предпорядок Рудин – Кейслера (задающийся одноместными операциями). Возрастающую цепь этих отношений можно продолжить трансфинитно. Оказывается, что объединение всех полученных отношений даёт другое хорошо известное отношение на ультрафильтрах – предпорядок Комфорта. Будет показано, как вычисляется композиция этих отношений; как следствие, будет установлено, что отношение является предпорядком тогда, и только тогда, когда его индекс является мультипликативно неразложимым ординалом. Также будут представлены некоторые теоретико-модельные приложения, значительно обобщающие ранее известные результаты.

🔗 Seminars "Proof Theory" and "Logic Online Seminar"


➰ ВК

#матлог #учёба #спецсеминар

Семинар "Вычислимость и неклассические логики" работает по пятницам с 16.45 в аудитории 425.

21 февраля 2025 г.
Г. Г. Черевиченко
Трудности с определением подстановки.
Подстановку мы обычно не пишем явно и поэтому не замечаем. При попытке же что-то о ней строго доказать неожиданно оказывается, что это мучительно трудно. В большинстве случаев трудности замалчивают (например, почти никто не проверяет кванторные правила при определении моделей Крипке). На примере моделей Крипке докладчик опишет трудности и предложит свой подход к их решению.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия

21 февраля (пятница) в 19.30 состоится очередное заседание исследовательского семинара "From the Logical Point of View"

Тема доклада: Applying the theory of quasi-truth for clarification of cognitive distortions

Докладчики: Ricardo Peraça Cavassane (University of Campinas), Виктория Денисова (НИУ ВШЭ)

Аннотация: We begin by examining Beck's cognitive model, focusing on its three key components: the cognitive triad, schemas, and cognitive errors. Our analysis emphasizes cognitive errors, particularly cognitive distortions, as a subset of these errors. The presentation then delves into a systematic review of Beck's identified thinking errors. We argue that many cognitive distortions can be understood as errors in deductive reasoning, often stemming from invalid premises or flawed logical forms. By applying principles of the theory of quasi-truth, we demonstrate how cognitive distortions can be reframed as instances of reasoning with inconsistent or incomplete information and negative assumptions. That is, by adding negative assumptions to the set of primary sentences P of a simple pragmatic structure A, the individual can only construct the A-normal structures which are consistent with those assumptions and, therefore, can only come to negative quasi-true conclusions. This approach provides a more nuanced understanding of how individuals with depression process information and make inferences about themselves, their experiences, and their future

Ждём вас в кабинете А-117 или в Zoom!

Анонс: https://llfp.hse.ru/announcements/1016973796.html

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 19 февраля.
Время проведения семинара 14:30.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

‼ВНИМАНИЕ Место поменялось.
Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

Докладчик: М.Н.Рыбаков (ВШМ МФТИ, НИУ ВШЭ, ТвГУ)
Тема: Погружение интуиционистской и близких логик в их фрагменты от одной-двух переменных

Аннотация:

Известно, что интуиционистская пропозициональная логика Int PSPACE-полна, причём PSPACE-полным является даже её импликативный фрагмент (R.Statman, 1979). Чуть ранее А.В.Кузнецов высказывал предположение, что Int полиномиально финитно аппроксимируема шкалами Крипке (и, как следствие, полиномиально погружается в классическую логику Cl). Это оказалось не так, что следует как из доказательства PSPACE-трудности Int, так и из результатов М.В.Захарьящева о сложности аппроксимации Int шкалами Крипке, полученных примерно в то же время. Тем не менее, фрагмент Int от одной переменной полиномиально финитно аппроксимируем и полиномиально разрешим (благодаря т.н. лестнице Ригера--Нишимуры). А.В.Чагров высказывал гипотезу о том, что полиномиально разрешимым будет любой фрагмент Int от конечного множества переменных (заметим, что для Cl это именно так и есть). В монографии [A.Chagrov, M.Zakharyaschev. Modal Logic. 1997] сформулирована соответствующая проблема (Problem 18.4), где вопросы о полиномиальной финитной аппроксимируемости и полиномиальной разрешимости ставятся для фрагмента Int от двух переменных и фрагментов S4, Grz и других стандартных модальных логик от одной переменной. На момент публикации этой монографии сложность фрагментов от одной переменной логик K, T, S4 была установлена (E.Spaan, 1993; J.Halpern, 1995), а в отношении Int долгое время ответа не было. Ответ для Int был получен докладчиком в 2004 году. В доказательстве возникла конструкция, позволившая обосновать PSPACE-трудность фрагментов от двух переменных всех логик между Int и логикой слабого закона исключённого третьего. Много позже эта конструкция была использована в решении алгоритмических вопросов для суперинтуиционистских предикатных логик, а недавно — для модальных интуиционистских логик, таких как MIPC (известна как IK — интуиционистская K), FS (известна как IS5) и других. Некоторые из полученных результатов опубликованы в совместных работах с Д.П.Шкатовым, в частности, касающиеся модальных интуиционистских логик.

В докладе предполагается (а) представить и обсудить используемую в доказательствах конструкцию, позволяющую полиномиально погрузить всю логику в её фрагмент от одной-двух переменных, (б) представить недавно полученные совместно с Д.П.Шкатовым результаты, а также (в) рассказать о некоторых следствиях, в т.ч. полученных совместно с А.А.Оноприенко (касаются логики HC, 2024г.) и М.И.Щербаковым (касаются логики GL.2, 2025г.).

➰ ВК

#матлог #не_мехмат #ВШЭ

В пятницу 21 февраля 2025 г. в 18:10 на Математическом семинаре ФКН ВШЭ состоится доклад Л.Д. Беклемишева на тему "Циклические доказательства".

Объявление и ссылку для регистрации см. на странице семинара:
https://cs.hse.ru/seminatfkn/

Место проведения: Покровский бульвар 11, аудитория R205.

🔗 Математический семинар


➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Room 313 MIAN + Kontur Talk (https://www.mathnet.ru/eng/conf876)

17.02.2025, jointly with S.I. Adian seminar

Alexei Miasnikov (Stevens Institute of Technology): First-order classification, non-standard models, and interpretations (online)

In this talk I will focus on three things:

1. First-order classification: in particular, how one can describe ALL groups which are first-order equivalent to a given one.

2. Non-standard models of groups: in particular, I will describe non-standard models of the finitely generated groups with decidable or recursively enumerable (or arithmetic) word problems and explain how they naturally appear as non-standard Z-points of the general algebraic schemes.

3. Theory of interpretations: it seems a new rich theory is emerging right now. I will show several interesting results based on interpretations.

🔗 Seminars "Proof Theory" and "Logic Online Seminar"


➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 14.02.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Кирилл Александров

Название: Сложность линейно аппроксимируемых расширений базисной пропозициональной логики

Аннотация:
Изучение алгоритмических свойств логик исторически было связано с оцениванием размера наименьших шкал Крипке, отделяющих формулы от логик. Для логики L, полной относительно некоторого класса конечных шкал Крипке, оценка размера наименьших шкал Крипке логики L, опровергающих формулы определенной длины, проводится с помощью функции сложности, которая по длине формулы говорит, какого размера шкалы Крипке логики L достаточно использовать , чтобы опровергнуть формулы не из L данной длины.
Интерес к функции сложности логики связан с долгим убеждением, что ее характер (полиномиальный, экспоненциальный и др.) напрямую связан со сложностью логики, однако Хемаспаандра установила существование нормальных модальных логик с линейной функцией сложности и неразрешимым унарным фрагментом. М.Н. Рыбаков и Д.П. Шкатов расширили её результаты, а именно показали, что для любой степени неразрешимости существуют нормальные расширения модальных логик KTB, K4, GL, Grz с линейными функциями сложности и константными или унарными фрагментами с данной степенью неразрешимости, а также доказали существование суперинтуиционистских пропозициональных логик с похожими свойствами. Мы расширим данный результат на случай базисной пропозициональной логики BPL, которая представляет собой логику класса шкал Крипке с транзитивным и антисимметричным отношением достижимости, а именно покажем, что для любой степени неразрешимости существует линейно аппроксимируемая логика, расширяющая BPL, константный фрагмент которой имеет данную степень неразрешимости.

🔗 Логика в Москве


➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

On Monday February 17, Time: 18:30 (MSK), 16:30 (CET) we have a talk of Sasha Kozachinskiy on computable online learning.

In the online learning setting, a learner receives an input x_1 to an unknown function f from a known hypothesis class H. The learner has to guess f(x_1). Then the learner receives the real value f(x_1), and the process repeats for x_2, x_3, and so on. The minimal number of mistakes that one can achieve on a hypothesis class H is known to be equal to the so-called Littlestone dimension of H.

What if the learner has to be computable? Or if the Littlestone dimension ''effective''? We will establish relationships between different versions of online learning when we impose computability conditions. Joint with Valentino Delle Rose and Tomasz Steifer.

➰ ВК

#матлог #учёба #спецсеминар

Семинар "Вычислимость и неклассические логики" работает по пятницам с 16.45 в аудитории 425.

14 февраля 2025 г.
Г. Г. Черевиченко
Интерпретация Гёделя.
Гёдель предложил некий способ устранения кванторов, похожий на введение скулемовских функций, но пригодный для интуиционистской арифметики. Арифметика при этом "погружается" в некоторую теорию без кванторов, но содержащую гораздо больше функциональных символов (в частности, для всех примитивно рекурсивных функций, но не только для них). Это даёт очень ясное описание, о каких вычислимых функциях можно говорить в арифметике (какие функции доказуемо общерекурсивны). Кроме того, Гёдель рассматривал эту интерпретацию как некоторое доказательство непротиворечивости арифметики.

➰ ВК

#матлог #учёба #спецкурс

В этом семестре В.Б.Шехтман прочитает спецкурс "Временные логики”".

Первая лекция: 13 февраля

Место проведения: МГУ, 2 гум. корп., ауд. 424

Время проведения: четверг, 16:45 - 18:05

Страница спецкурса в базе мехмата: https://scs.math.msu.ru/ru/node/6979

Аннотация.
Временные логики составляют класс модальных логик, в которых модальности интерпретируются как временные связки (“всегда будет”, “было вчера” и др.). Эти логики часто оказываются разрешимыми и успешно применяются в компьютерных науках. В курсе дается введение в эту обширную область. Рассматриваются различные логики дискретного, непрерывного и ветвящегося времени. Доказываются результаты об аксиоматизируемости, разрешимости и определимости.

Пререквизиты: основной курс "Введение в математическую логику и теорию алгоритмов".

🔗 Временные логики | Спецкурсы и спецсеминары механико-математического факультета МГУ


➰ ВК

#матлог #учёба #спецкурс

В этом семестре В.А.Любецкий продолжит чтение годового спецкурса "Современные методы обработки данных".

Первая лекция: 24 февраля

Место проведения: удалённо

Время проведения: понедельник, 16:45 - 18:30

Страница спецкурса в базе мехмата: https://scs.math.msu.ru/ru/node/6467

Можно сдавать как годовой спецкурс, так и полугодовую "половинку".
Название полугодовой "половинки": "Компьютерный анализ клеточных типов"
Страница в базе мехмата: https://scs.math.msu.ru/ru/node/6471

Аннотация.
Будет рассмотрен весьма сложный эвристический алгоритм, который ставит много математических проблем и также широко применяется в прикладных задачах из многих предметных областей (желательно программирование и счёт реальных прикладных задач, которые будут предложены).
Предварительных знаний не требуется.

❗До начала курса каждому слушателю записаться у Михаила Саблина mikhail.sablin@math.msu.ru, сообщив ФИО, группу, почту, мобильный.
Студенты, работающие с Любецким В.А. (курсовая, дипломная, аспирантура), обязательно посещают курс!

🔗 Современные методы обработки данных | Спецкурсы и спецсеминары механико-математического факультета М


➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 12 февраля.
Время проведения семинара 14:30.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный

Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16

Заседание пройдет очно без трансляции.

Докладчик: Александр Колпащиков

Название: Введение в логику норм: проблемы и примеры.

Доклад представляет собой изложение наиболее известных вопросов деонтической логики - раздела логики, исследующего формализацию таких нормативных концепций, как моральный долг, обязательства, правовые нормы и т.д. Также будут рассмотрены основные системы аксиом, некоторые их модификации и соответствующие семантические структуры.

➰ ВК

#матлог #учёба #спецкурс

В этом семестре В.Е.Плиско прочитает спецкурс "Конструктивная логика".

Первая лекция: 14 февраля

Место проведения: МГУ, ауд. 425

Время проведения: пятница, 18:30 - 20:05

Страница спецкурса в базе мехмата: https://scs.math.msu.ru/ru/node/7193

🔗 Конструктивная логика | Спецкурсы и спецсеминары механико-математического факультета МГУ


➰ ВК

#матлог #учёба #спецсеминар

11 и 18 февраля 2025 г., в 16:00 на семинаре НОЦ МИАН «Вероятностные и субструктурные логические системы» (https://www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова и С.О. Сперанского будет следующий доклад (в двух частях):

С.Л. Кузнецов, Т.Г. Пшеницын (МИАН)

Исчисление Ламбека с операцией круллева пересечения

Исчисление Ламбека — это субструктурная логика, т. е. логика без правил сокращения, ослабления и перестановки. Одним из естественных классов моделей для исчисления Ламбека являются модели на алгебрах бинарных отношений (R-модели). В рамках доклада будет рассмотрено расширение исчисления Ламбека с помощью операции круллева пересечения, т. е. пересечения степеней данного элемента (начиная с первой). Эта операция в некотором смысле двойственна операции взятия транзитивного замыкания (положительной итерации Клини). В первой части доклада будут доказаны теоремы об устранении сечения, о полноте относительно R-моделей, а также верхняя оценка алгоритмической сложности для исчисления Ламбека с операцией круллева пересечения. Вторая часть будет посвящена доказательству нижней оценки сложности.

Семинар проходит очно в МИАН (ул. Губкина 8), ауд. 303. Возможно также подключение через Контур Толк. Всем желающим участвовать в семинаре просьба зарегистрироваться на странице семинара (https://www.mathnet.ru/conf2533). Ссылка на Контур Толк будет выслана зарегистрировавшимся участникам накануне семинара.

🔗 Семинар С. Л. Кузнецова и С. О. Сперанского "Вероятностные и субструктурные логические системы&


➰ ВК

#матлог #учёба #спецкурс

В этом семестре Н.К.Верещагин прочитает спецкурс "Сложность вычислений".

Первая лекция: 11 февраля

Место проведения: МГУ, ауд. 424

Время проведения: вторник, 18:30 - 20:05

Страница спецкурса в базе мехмата: https://scs.math.msu.ru/ru/node/7137

Аннотация. Это - базовый спецкурс по теории сложности вычислений (включая доказательства трудности задач, основные сложностные классы, теорию NP полноты, PSPACE полноты). Предварительных знаний не требуется.

🔗 Сложность вычислений | Спецкурсы и спецсеминары механико-математического факультета МГУ


➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

UPD: The forthcoming talk on February 10th (Monday) will be given by Prof. Aleksandar Perović (University of Belgrade, https://www.scopus.com/authid/detail.uri?authorId=23987185400), who is another co-author of the work.

Logic Online Seminar, Monday 16:00 MSK (UTC+3), Room 313 MIAN + Kontur Talk (https://www.mathnet.ru/eng/conf876)
10.02.2025 Angelina Ilić-Stepić (Matematički institut SANU, Beograd, Srbija, https://www.mi.sanu.ac.rs/novi_sajt/members/fulltime/angelina.php): Beyond the class of locally finite height Kripke models for provability logic (online)

The paper [K. Sasaki & Y. Tanaka 2024: An omega-rule for the logic of provability and its models, Studia Logica 112] presents the propositional logic NGL, an extension of the provability logic GL with an infinitary inference rule, and proves simple completeness theorem w.r.t. the class LF of locally finite height Kripke models. We provide a strongly complete modification of NGL and a family of Barwise-complete infinitary logics that correspond to specific subclasses of the class of all conversely well-founded strict posets that are proper superclasses of LF.

The talk is based on joint work with Zoran Ognjanović and Aleksandar Perović.

🔗 Seminars "Proof Theory" and "Logic Online Seminar"


➰ ВК

#матлог #учёба #спецкурс

В этом семестре в МГУ (при поддержке Фонда «БАЗИС») будет читаться курс С.О. Сперанского «Проблемы алгоритмической разрешимости теорий для алгебры и анализа».

Первая лекция: 14 февраля

Место проведения: МГУ, ауд. 1414

Время проведения: пятница, 16:45-18:20

Страница курса (где можно найти расширенную аннотацию и предварительный план лекций):

https://homepage.mi-ras.ru/~speranski/courses/theories.html

Аннотация:

Теории классов структур в языке логики первого порядка традиционно называют «элементарными»; они являются одним из основных объектов изучения в математической логике и теории алгоритмов. Элементарная теория данного класса — это совокупность свойств, выразимых в соответствующем языке и присущих всем структурам из класса; её алгоритмическая разрешимость означает возможность эффективной проверки «элементарных» свойств над рассматриваемым классом. Многие известные результаты, а также открытые проблемы в математической логике связаны с изучением вычислительных аспектов элементарных теорий различных классов групп, колец и т.п. и их естественных фрагментов. Это классическое и не теряющее актуальности направление исследований, восходящее к фундаментальным работам А. Тарского и А.И. Мальцева.

Кроме того, в настоящее время большое внимание уделяется изучению двухсортных структур, возникающих в функциональном анализе. Элементарные теории классов такого рода структур оказываются тесно связаны с арифметикой второго порядка, чей язык активно используется в основаниях математики. С точки зрения теоретической информатики особый интерес здесь представляют вероятностные пространства, поскольку они лежат в основе семантики многочисленных вероятностных логических систем.

Основная цель настоящего курса — познакомить слушателей с методами, которые активно применяются в изучении вычислительных аспектов элементарных теорий, и сопутствующими результатами о разрешимости и неразрешимости, связанными со структурами из алгебры и анализа.

❗ Просьба ко всем участникам зарегистрироваться через Google-форму, ссылка на которую есть в верхней части страницы курса — см. кнопку «Регистрация».

🔗 Станислав Сперанский


➰ ВК