Кафедра математической логики и теории алгоритмов мехмата МГУ

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

Семинар «Вероятностные и субструктурные логические системы» (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 марта (пятница) не состоится. Доклад переносится на другое время, о чем мы сообщим дополнительно.

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

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

➰ ВК