#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
19 ноября в 18:10 состоится заседание научно-исследовательского семинара «From the Logical Point of View».

Тема доклада: Abstract Model Structures and Compactness Theorems.

Докладчик: Саянтан Рой (научный сотрудник МЛ ЛогЛинФФ).

Аннотация: The compactness theorem for a logic states, roughly, that the satisfiability of a set of well-formed formulas can be determined from the satisfiability of its finite subsets, and vice versa. Usually, proofs of this theorem depend on the syntactic/semantic particularities of the corresponding logic. In this talk, using the notion of abstract model structures, we show that one can develop a generalized notion of compactness that is independent of these. Several characterization theorems for a particular class of compact abstract model structures are also proved.
_____________________

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

Анонс и регистрация: https://llfp.hse.ru/announcements/1101848996.html

➰ ВК

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

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

17 November, 18:30 MSK

Tomorrow on the seminar there will be the final part of the presentation by Fyodor Kiselyov. We will discuss the definition of randomized reductions between search problems and some sort of "derandomization" result: any randomized reduction from PPP to some class may be transformed to a usual deterministic reduction.

➰ ВК

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

💥В среду 19 ноября состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Модальная логика, продолжение 2" (Лев Дворкин).
✨Аннотация. Модальная логика - неклассическая логика, в которой к стандартным классическим связкам (конъюнкция, дизъюнкция, импликация, отрицание) добавляется "модальность", которую в зависимости от контекста можно понимать по-разному: "необходимо", "доказуемо", "известно" и др. Мы обсудим модальное исчисление, семантику Крипке для модальных логик, разные примеры модальных логик, взаимосвязь модальных формул и свойств шкал Крипке, которые они задают.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 modal2025.pdf

➰ ВК

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

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 19 ноября в 15:00.
‼Время необычное‼

Место проведения: ОНЛАЙН. Для получения ссылки пишите на почту kudinov.andrey@gmail.com.

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

Докладчики: Д.П. Шкатов (Университет Йоханнесбурга, ЮАР)

Название: Введение в семантику первопорядковых модальных логик - часть 3

Аннотация.
Третий доклад из серии, основанной на вводных лекциях о семантике первопорядковых модальных логик, прочитанных совместно с В. Б. Шехтманом летом 2025 года в рамках ESSLLI 2025. Будут изложены некоторые методы доказательства полноты по Крипке неканонических логик и представлено краткое введение в семантику пучков Крипке.

➰ ВК

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

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

24.11.2025, jointly with S.I. Adian seminar, I.G. Lysenok (Steklov Mathematical Institute, https://www.mathnet.ru/person/8818): A sample iterated small cancellation theory for groups of Burnside type.

We develop yet another technique to present the free Burnside group B(m,n) of odd exponent n with m≥2 generators as a group satisfying a certain iterated small cancellation condition. Using the approach, we provide a reasonably accessible proof that B(m,n) is infinite with a moderate bound n2000 on the odd exponent n.

➰ ВК

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

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

This Monday 24 November, 18:30 MSK, we will have a talk by Alexander Shen.

Upcrossing inequalities revisited

Bishop used upcrossing inequalities to prove Birkhoff's ergodic theorem. Vyugin used his inequality (in one of the forms) to prove the algorithmic version of it (for Martin-L\"of random sequences). It turns out that another version (a stronger one, from a different paper of Bishop) immediately implies the result of Barmpalias and Lewis-Pye about lower semicomputable randoms: if $a_n$ and $b_n$ are computable increasing sequences of rational numbers that converge to reals $A$ and $B$, and $A$ is random, then $(B-b_n)/(A-a_n)$ converges. And, to finish the story, Misha Andreev invented a simple and nice proof of the Bishop's inequality used in this argument.

➰ ВК

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

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

27 ноября и 4 декабря 2025 г. состоятся два доклада Т.Г. Пшеницына «Сложность релевантной логики и её разновидностей».

Время: 16:00
Место: МИАН, ауд. 530 + Контур.Толк
Для получения ссылки зарегистрируйтесь на странице семинара: https://www.mathnet.ru/conf2533
(ссылка единая для всех заседаний в этом семестре).

Аннотация:
Классическая импликация не является релевантной, поскольку в классической логике верен закон A→(B→A): истинное утверждение A следует из любого другого утверждения B. Этот закон соответствует структурному правилу ослабления, согласно которому можно произвольным образом усиливать посылку импликации или ослаблять ее заключение. Релевантная логика R — это субструктурная логика классического типа без правила ослабления, но с правилом дистрибутивности. Оказывается, что задача доказуемости в этой логике неразрешима: к ней можно свести задачу равенства в полугруппах (Уркхарт, 1984). С другой стороны, R без дистрибутивности — в литературе такая логика ещё обозначается через CFL_{ec} — оказывается разрешимой, что следует из так называемого "трюка Крипке". При этом сложность доказуемости в CFL_{ec} является Аккерман-полной задачей; если же ограничиться импликативным фрагментом R, сложность падает до 2-EXPTIME. В доказательстве последних двух результатов используются алгоритмические задачи для разновидностей счетчиковых машин с "ненадёжными вычислениями".

В докладах будет дан обзор всех этих результатов.

Литература:
[1] Urquhart, A. (1984). The Undecidability of Entailment and Relevant Implication. The Journal of Symbolic Logic, 49(4), 1059–1073.
[2] Urquhart, A. (1999). The Complexity of Decision Procedures in Relevance Logic II. The Journal of Symbolic Logic, 64(4), 1774–1802.
[3] Schmitz, S. (2016). Implicational Relevance Logic is 2-EXPTIME-complete. The Journal of Symbolic Logic, 81(2), 641–661.

➰ ВК

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

💥В среду 26 ноября состоится очередное занятие просеминара по математической логике и информатике.

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

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 Вопросная_сложность_2025.pdf

➰ ВК

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

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 26 ноября в 14:00.

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

Название: Проблема унификации для подсистем полимодальной логики доказуемости GLP

Докладчик: Никита Лукашов (НИУ ВШЭ)

Аннотация:

Полимодальная логика доказуемости GLP со счётным числом модальностей была введена Г. Джапаридже в 1980-х годах и нашла интересные применения в теории доказательств. Несмотря на неполноту по Крипке, GLP разрешима и для неё были установлены многие обычные свойства модальных логик.

Большинство положительных результатов о GLP были получены с помощью сведения к её подсистеме J, которая уже является полной по Крипке относительно класса, так называемых, стратифицированных моделей. Однако это сведение, к сожалению, не сохраняет тип унификации: Л.Д. Беклемишевым (2025 год) было показано, что логика GLP в языке даже с двумя модальностями обладает нулевым типом унификации, в то время как мною было установлено, что соответствующие подсистемы J с ограниченным числом модальностей обладают конечным типом унификации.

В своём докладе я представлю мои результаты касательно типа унификации J и её подсистем J_t в языках с модальностями [0], [1], … [t-1]. Обобщив методы С. Гилярди (конец 1990-х годов) для одномодального случая, мне удалось показать, что для всех t логики J_t обладают конечным типом унификации. При этом для всей логики J с бесконечным числом модальностей мне удалось установить нулевой тип унификации.

Доклад основан на статье: Lukashov N. V. Unification in subsystems of polymodal provability logic GLP //Logic Journal of the IGPL. – 2025. – Т. 33. – №. 6. – (to appear).

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
26 ноября в 18:10 состоится 106-е заседание научно-теоретического семинара «Формальная философия».

Тема доклада: Модальность и время у Аристотеля.

Докладчик: Жозе да Мата (SBL, Бразильское общество логики).

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

Особый интерес представляет фаталистический аргумент. Аристотель не только опровергает его, но и заимствует из него конструкцию «предложения двух рук» (и не только её). Такая структура позволяет выразить противоречие и играет важную роль в модальной логике. Кстати, стоит помнить слова профессора Бажанова о Васильеве: «В тезисах Васильева некоторые структуры можно было понимать как модальные суждения (…)».
_____________________

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

Анонс и регистрация: https://llfp.hse.ru/announcements/1104853489.html

➰ ВК

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

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

Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 108 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.

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

Название: Топологическая семантика модальной логики

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

Аннотация:
В докладе рассматриваются два классических топологических подхода к интерпретации модального оператора ромб (◇), предложенные МакКинси и Тарским: через оператор замыкания C и через оператор производной множества d.
Эти интерпретации приводят к двум различным семантикам модальной логики: C-логикам, являющимся нормальными расширениями S4, и d-логикам, являющимся расширениями wK4.
Поскольку для любого топологического пространства X и любого множества A выполнено равенство CA = A ∪ dA, с помощью оператора производного множества можно "почувствовать" более тонкую структуру пространства, чем с помощью замыкания, что делает d-семантику более выразительной.
В докладе обсуждаются основные различия между C- и d-семантиками и то, как эти различия проявляются при изучении конкретных топологических классов: субмаксимальных пространств (submax), дверных пространств (door) и I-spaces. Для каждого из этих классов устанавливается модальная определимость или неопределимость относительно обеих семантик.

➰ ВК

#матлог #поздравляем

Поздравляем студента нашей кафедры Руслана Голова (научный руководитель - Кузнецов С.Л.) с выступлением на VI конференции курсовых работ студентов младших курсов 🎉
На данной конференции студенты представляют существенные научные результаты, которые они получили, работая под научным руководством на 1-2 курсах 😱

Презентация прикреплена к посту.

Аннотация прошедшего доклада:

В данном докладе я представляю простое, но выразительное расширение классической кодировки Чёрча, которое позволяет представлять не только натуральные числа, но и более богатые алгебраические структуры внутри лямбда-исчисления, в частности кольцо ℤ и его стандартные расширения ℤ/dℤ и ℤ[i]. Центральным техническим инструментом является новая лямбда-структура, построенная из проектора и квазипроекторного комбинатора. Эта структура включает в себя обычные булевы значения и числовые кодировки Чёрча и естественным образом обобщает их на конечнозначные логики. На её основе мы определяем эффективные кодировки пар и проективных остатков ℤ/dℤ с использованием проекторов, кольцевых сдвигов и индексов де Брейна, что позволяет избежать хорошо известной временной сложности O(n²).

Отдельная часть доклада посвящена бинарному представлению лямбда-термов, которое делает возможной прямую компиляцию лямбда-выражений и компактное хранение больших множеств термов в памяти при уменьшенном объёмной сложности. Наконец, я представляю алгоритмы бинаризации вместе с тремя их полными реализациями: объектно-ориентированной версией на C#, функциональной реализацией на Rust и новым стеково-функциональным подходом, основанным на модели данных с вектором глубины и реализованным в массивно-функциональном языке программирования Uiua.

📝 Бинарное_лямбда_исчисления_расширенной_кодировки_Черча_Финал_.pdf

➰ ВК

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

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

01.12.2025, Incidences, tilings, and fields

M. Skopenkov (HSE University and KAUST, https://arxiv.org/search/?searchtype=author&query=Skopenkov%2C+M), online talk

The master theorem, introduced independently by Richter-Gebert and by Fomin and the first author, provides a method for proving incidence theorems of projective geometry (more precisely, quasi-identities) using triangular tilings of surfaces. We investigate which incidence theorems over C and R can or cannot be proved via the master theorem. For this, we formalize the notion of a tiling proof. We introduce a hierarchy of classes of theorems based on the underlying topological spaces. A key tool is considering the same theorems over finite fields.
This is a joint work with P. Pylyavskyy.

➰ ВК

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

💥В среду 3 декабря состоится очередное занятие просеминара по математической логике и информатике.

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

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме: https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 Вопросная_сложность_2025.pdf

➰ ВК

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

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.

Семинар пройдет в среду 3 декабря в 14:00.

Место проведения:
ОНЛАЙН + трансляция на большом экране по адресу МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.

Название: Логика топологической достижимости

Докладчик: Александр Гагарин

Аннотация:
Доклад посвящен одной логике, связанной с путями в топологических пространствах. Вводится бинарная модальность "достижимости" γ(A,B), интерпретируемая в точке x как "существует путь из x в точку, где истинно B, и во всех промежуточных точках которого истинно A". Ранее эта связка изучалась для александровских топологий и для симплициальных комплексов; две соответствующие логики разрешимы и конечно аксиоматизируемы (Bezhanishvili, Bussi, Ciancia, Fernández-Duque и Gabelaia 2024). В докладе будет рассмотрена логика всех топологий в языке с модальностями ☐A ("внутренность A") и γ(A,B), которая также оказалась конечно аксиоматизируемой и разрешимой. Для доказательства используется переход к подходящему варианту окрестностной семантики.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
3 декабря в 18:10 состоится заседание научно-исследовательского семинара «From the Logical Point of View».

Тема доклада: Структурная теория доказательств на службе у формальной эпистемологии.

Докладчик: Юрий Казаков (стажер-исследователь МЛ ЛогЛинФФ).

Аннотация: Наиболее популярным подходом к формальной эпистемологии и эпистемической логике остается теоретико-модельный. Редко когда свежие логики удостаиваются соответствующей структурной теории доказательств, несмотря на удобство последней. В своей недавней статье С. Негри и Э. Павлович предлагают достаточно естественное место для теории доказательств в контексте хинтиковской теории интеррогативного знания. Также особый интерес вызывают теории, обладающие свойством контрмодели и обратимостью правил. Они позволяют не только делать утверждения о выводимости формул, но и наоборот, об их невыводимости, что может быть полезно для рассмотрения эпистемических парадоксов. В рамках доклада также планируется осветить другие неожиданные связи теорий доказательств генценовского типа и эпистемической логики в контексте субструктурных логик и теоретико-доказательственной семантики.
_____________________

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

Анонс и регистрация: https://llfp.hse.ru/announcements/1106841952.html

➰ ВК

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

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

4 декабря 2025 г. продолжение доклада Т.Г. Пшеницына «Сложность релевантной логики и её разновидностей».

Время: 16:00
Место: МИАН, ауд. 530 + Контур.Толк
Для получения ссылки зарегистрируйтесь на странице семинара: www.mathnet.ru/conf2533
(ссылка единая для всех заседаний в этом семестре).

➰ ВК

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

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

8 December, 18:30 MSK

Sasha Kozachinskiy

Language identification and generation in the limit.

Assume we have a family of formal languages F. An adversary selects a language L from F and starts enumerating elements of L in some order. Our task is to guess L after seeing finitely many elements of the enumeration. If there is an algorithm that does it regardless of the adversary's actions, we call F identifiable in the limit. Angluin (1980) have obtained necessary and sufficient conditions for countable families to be identifiable in the limit and gave an example of the family of "pattern languages", satisfying these conditions.

Kleinberg and Mullainathan have recently considered a variation of this setting, where the task is not to guess L but to indicate an infinite subset of L after finitely many steps. Families, for which this is possible, are called generatable in the limit. They have shown that any countable family is generatable in the limit. Moreover, it can be done computably whenever membership query for the family is decidable. In the talk I will cover these results.

➰ ВК