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

Занятие просеминара 7 ноября отменяется. Слушатели приглашаются на Международную конференцию «Формальная философия 2024».
https://llfp.hse.ru/announcements/968274219.html

Все доклады будут проходить в ауд А-307 в корпусе на Старой Басманной (Ст. Басманная ул., д. 21/4, стр. 4).

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

По вопросам пропусков пишите Оноприенко А.А.

🔗 Международная конференция "Формальная философия 2024"


➰ ВК

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

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

МФТИ, радиотехнический корпус, ауд. РТ 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

В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите заранее на почту kudinov.andrey@gmail.com. С собой иметь паспорт.

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

Докладчик: Шехтман В.Б.

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

Аннотация

Проблема семантической полноты для модальных логик предикатов оказалась очень нетривиальной. Естественная семантика Крипке применима лишь для ограниченного класса логик. Неизвестно, как ее модифицировать, чтобы все логики оказались полными. Однако в других семантиках дело обстоит несколько лучше. В докладе будет дан обзор некоторых результатов о полноте и неполноте модальных предикатных логик в различных семантиках.

➰ ВК

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

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

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

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

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

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

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

Название: Бесконечнозначная первопорядковая логика Лукасевича: исчисления для поиска вывода и полнота инфинитарного аналитического исчисления для предварённых предложений. Часть вторая

Аннотация.
Бесконечнозначная первопорядковая логика Лукасевича относится к математическим нечётким логикам и служит для формализации приближённых рассуждений. Множество всех общезначимых предложений (и множество всех общезначимых предварённых предложений) этой логики неперечислимо; поэтому для неё не существует полного исчисления с рекурсивным множеством аксиом и конечным числом рекурсивных правил вывода. В докладе мы покажем, как удалось доказать полноту одного инфинитарного аналитического исчисления для предварённых предложений данной логики с помощью построений, полученных при разработке ориентированных на поиск вывода исчислений для рассматриваемой логики.
Доклад основан на статьях:
[1] A.S.Gerasimov, "Repetition-free and infinitary analytic calculi for first-order rational Pavelka logic", Siberian Electronic Mathematical Reports, Vol.17, 2020, pp.1869-1899, https://doi.org/10.33048/semi.2020.17.127;
[2] A.S.Gerasimov, "Comparing calculi for first-order infinite-valued Lukasiewicz logic and first-order rational Pavelka logic", Logic and Logical Philosophy, Vol.32, No.2, 2022, pp.269-318, https://doi.org/10.12775/LLP.2022.030;
а также на некоторых неопубликованных результатах докладчика.
В начале второй части доклада будет изложено основное из его первой части, прошедшей 27.09.2024; так что прослушивание первой части доклада не обязательно для понимания второй.

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


➰ ВК

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

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

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

Докладчик: Ф. Д. Холодилов
Тема: «Разложение языков относительно однозначного произведения»

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

➰ ВК

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

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

8 ноября 2024 г.
Докладчик: Ю.С.Капустин
Тема: "Функциональная система С_n и её свойства"

В докладе рассматриваются свойства функциональной системы С_n, порождённой обычными теоретико-множественными операциями и индикаторами мощности множеств до n включительно, носитель которой - множество подмножеств множества целых чисел. Будут рассмотрены основные свойства системы, предполные классы системы и представлен критерий относительной полноты в этой системе.

➰ ВК

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

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

Date: Nov 11, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited (continued)

The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК

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

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

Date: Nov 11, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited (continued)
The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК

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

На занятии просеминара 14 ноября будет тема "Выразимость предикатов" (Александр Калинин, студент кафедры).
Можно заранее порешать задачи (прикреплены к посту).

❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi

Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.

🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо


📝 opredelimost2024.pdf

➰ ВК

#матлог #учёба #миникурсы

На следующей неделе Степан Львович Кузнецов и Станислав Олегович Сперанский (Математический институт им. В.А. Стеклова РАН) в рамках своего визита в Новосибирский государственный университет прочтут мини-курсы.

Лекции пройдут очно в НГУ, возможно также подключение через Zoom. Для получения ссылки зарегистрируйтесь на странице мини-курсов https://sites.google.com/view/mca-logic

Расписание лекций.
ВНИМАНИЕ! Время везде указано новосибирское, т.е. +4 часа от московского, GMT+7.

В рамках мини-курса С.Л. Кузнецова "Лямбда-исчисление" запланировано три лекции:
(1) 18 ноября (понедельник), 16:20-17:55, ауд. 4140 НГУ,
(2) 19 ноября (вторник), 18:10-19:45, ауд. 4268 НГУ,
(3) 20 ноября (среда), 16:20-17:55, ауд. 4267 НГУ.

В рамках мини-курса С.О. Сперанского "Подход Крипке к формальной теории истины" запланировано три лекции:
(1) 18 ноября (понедельник), 18:10-19:45, ауд. 4140 НГУ,
(2) 19 ноября (вторник), 16:20-17:55, ауд. 4268 НГУ,
(3) 20 ноября (среда), 18:10-19:45, ауд. 4267 НГУ.

---
Аннотация курса С.Л. Кузнецова "Лямбда-исчисление":

Лямбда-исчисление — это логическая система для формализации вычислений посредством операций применения функций и функциональной абстракции. Лямбда-исчисление является основой семейства современных языков программирования, называемых функциональными языками. В рамках мини-курса будет дано введение в лямбда-исчисление, в двух его видах — бестиповом и типизованном. На первой лекции будет рассказано о лямбда-исчислении без типов (в котором любое лямбда-выражение может быть применено, как функция к любому другому), о его основных свойствах и о представлении в нём произвольных вычислимых функций. На второй лекции будут рассмотрены несколько вариантов типизованного лямбда-исчисления (здесь применение ограничено дисциплиной типов), описаны их вычислительные возможности и установлена связь между типизованным лямбда-термами и конструктивными доказательствами (соответствие Карри-Говарда). На третьей лекции будет рассказано о семантике лямбда-исчисления: теоретико-множественных моделях в типизованном случае и моделях Ершова-Скотта в бестиповом.

---
Аннотация курса С.О. Сперанского "Подход Крипке к формальной теории истины":

Пусть L — первопорядковый язык арифметики Пеано, а L' — какое-нибудь его расширение. Из леммы о диагонализации легко следует теорема Тарского о неопределимости истины: если L'-структура M обогащает стандартную модель арифметики, то множество всех (гёделевых номеров) L'-предложений, истинных в M, не определимо в самой M. Стало быть, если L' получается из L добавлением особого одноместного предикатного символа T, и мы хотим интерпретировать T как истинностный предикат для всего L', то T должен принимать как минимум три значения: «истинно», «ложно» и «неопределено», где последнее, в частности, соответствует парадоксу лжеца и ему подобным утверждениям.

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

Цель данного мини-курса — познакомить слушателей с теорией истины по Крипке и её вычислительными аспектами.

🔗 МЦА


➰ ВК

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

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

18.11.2024: no talk

25.11.2024 Johan van Benthem (Stanford, Tsinghua University, University of Amsterdam):
Two Perspectives on Recursion and Induction: Modal Provability Logic and Fixed-Point Logics
Recursion and induction are ubiquitous logical mechanisms. I will compare two styles of dealing with them: one based on well-founded orderings and one on general fixed-point logics, showing that the two are connected in interesting ways. I present some theorems and conjectures to this effect, and if time permits, I will also point out some implications of this theme for discussions of ‘logical constants’ in the philosophy of logic.

🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&


➰ ВК

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

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

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

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

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

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

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

Название: Сложность логики LTL.
Темпоральные логики являются расширениями классической логики высказываний, полученными путём добавления специальных модальностей. Эти модальности, темпоральные операторы, позволяют формулировать утверждения, истинность которых может меняться с течением времени. Простота и выразительность темпоральных логик позволяют использовать их для описания работы различных систем, когда важно уделить внимание последовательности переходов между различными состояниями системы. Логика LTL, также известная как логика линейного времени, впервые была описана в [1].
Данный доклад будет посвящён вычислительной сложности логики линейного времени, а также некоторых её фрагментов.
[1] A. Pnueli. The temporal logic of programs, In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (Providence, RI.). IEEE, New York, 1971, pp. 46-57.

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


➰ ВК

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

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

Date: Nov 18, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited (continued)

The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК

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

На занятии просеминара 21 ноября будет тема "Модальная логика" (Оноприенко А.А.).
Можно заранее порешать задачи (прикреплены к посту).

❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi

Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.

🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо


📝 modal2024.pdf

➰ ВК

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

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

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

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

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

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

Докладчик: Артем Сергеевич Пиманов

Название: Современные модификации онтологических структур времени

Аннотация:
В рамках выступления рассматриваются предпосылки становления современных модификаций онтологических структур времени в контексте проблемы детерминизма.
Влияние представлений о детерминизме прослеживается в различных областях философии, в том числе и во временной логике. Рассмотрение ряда аспектов детерминизма позволяет подробно описать причины формирования в логике определенных подходов к оценке времененных высказываний. Так, в работе рассматривается анализ Артуром Прайором детерминистических аргументов, лежащих в основе классических вариантов семантики Оккамовского и Пирсового типов и принципа «жди и смотри». Дальнейшее изучение данных семантик по ряду логико-философских причин расходится на два самостоятельных и конкурирующих между собой направления: логику пространства-времени (BST) и гипотезу Thin Red Line. Эти системы представляют собой варианты оценки овремененных высказываний через использование пар момент, история, которые ввиду некоторых своих недостатков на текущий момент не завершены. Последнее побудило некоторых исследователей начать поиск альтернативных вариантов оценки. В частности, примечательны работы Джона Макфарлейна, где особое внимание уделяется определению условий адекватной препрезентации идеи открытого будущего. В его понимании ключевым условием является совмещение двух философских интуиций о детерминизме, которое можно реализовать за счет релятивизации оценки высказываний через контекст утверждения.
В дальнейшем на эти работы обратил внимание Томас Мюллер, который, занимаясь вопросом отображения локальных аспектов модальной упорядоченности (в том числе и с философской точки зрения), выдвинул идею семантики переходов. Ее развитие сегодня отражается в работах Антье Румберг, где предлагается вариант семантики с наличием оператора стабильности. Получившийся вариант семантики позволяет разрешить сразу несколько основных вопросов касательно детерминизма. В частности, наличие оператора стабильности позволяет показать специфический характер проявления высказываний о случайных событиях. В свою очередь, оценка высказываний позволяет точно и непротиворечиво реализовать предложенный Прайором принцип «жди и смотри». Но, на наш взгляд, такой вариант семантики имеет ряд проблем с описанными ранее представлениями о природе будущего.

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


➰ ВК

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

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

Date: Nov 25, 2024. Time: 18:30 (MSK), 16:30 (CET)
Title: Word combinatorics and approximations of reals
(Following Matthieu Rosenfeld, LIRMM)

Let $\alpha$ be a real number that we try to approximate by rational numbers $m/n$. It can be done with arbitrary precision, but there is a tradeoff between the precision and the denominator. For given denominator $n$ we can obviously make the error smaller than $0.5/n$ (by rounding $\alpha n$); Dirichlet theorem says that for _some_ n the precision could be much better. Let us an approximation $\eps$-good if $|\alpha n -m|\le\eps$. So for every $n$ there is $1/2$-good approximation with denominator $n$ (obvious), and for every $\eps0$ there are infinitely many denominators that allow $\eps$-good approximations (Dirichlet)

What if we allow only some denominators? Then Dirichlet theorem is no more true. For example, if we allow only denominators $1,2,4,8,16,\ldots$, then $1/3$ = $0.0101010101\ldots$ in binary, has no $1/4$-good approximations ($n\alpha$ has fractional part $1/3$ or $2/3$).

Question: assume that we have some other sequence of denominators $n_1,n_2,\ldots$ that is sparse: $n_i2n_{i-1}$, and some $\eps0$. Is it always possible to find some $\alpha$ that has no $\eps$-good approximations, for some $\eps$ and for all the denominators in the sequence? (Note that we cannot take $\alpha$ randomly, since for every $\eps$ the probability of success in $2\eps$ and the union bound does not work for infinitely many denominators.)

People in number theory were interested in this question (and finally proved that the statement is true). Matthieu Rosenfeld noted that we can get a simple proof of this result if we use tools from word combinatorics (e.g., Joe Miller's potential argument for avoiding forbidden strings). This proof will be explained.

➰ ВК

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

На занятии просеминара 28 ноября будет тема "Доказуемо рекурсивные функции и теорема Гёделя" (Беклемишев Л.Д.).

❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi

Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.

🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо


➰ ВК

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

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

МФТИ, радиотехнический корпус, ауд. РТ 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

В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите заранее на почту kudinov.andrey@gmail.com. С собой иметь паспорт.

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

Докладчик: Стас Кикоть

Название: О монотонной определенности и переписываемости рекурсивных запросов относительно представлений

Аннотация:

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

➰ ВК

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

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

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

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

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

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

Докладчик: С.П.Одинцов

Название: Слабо импликативные логики: подходы к определению дефинициальной эквивалентности и определимости.

Аннотация:

В логиках с сильным отрицанием ∼ условия истинности и ложности формул определяются параллельно, а сильное отрицание позволяет переходить от условий истинности к условиям ложности и наоборот. При этом истинность слабой эквивалентности φ ↔ ψ, определяемой обычным образом, означает лишь, что в каждом из возможных миров формулы φ и ψ одновременно истинны. Сильная эквивалентность φ = ψ := (φ ↔ ψ)∧(∼φ ↔ ∼ψ) сохраняет как истинность, так и ложность формул и является конгруэнцией на алгебре формул. Поэтому имеет смысл различать сильные (=) и слабые (↔) версии таких понятий как дефинициальная эквивалентность логик, явная и неявная определимость параметров.

Импликативные логики Фонта - это класс логик с импликацией в языке, допускающих "стандартную" алгебраизацию. В докладе будет введен класс слабо импликативных логик (си-логик) в языке с импликацией и сильным отрицанием. Такие логики являются естественной модификацией импликативных логик и включают практически все известные примеры логик с сильным отрицанием. Далее мы определим понятие слабой дефинициальной эквивалентности для си-логик, сделаем обзор различных подходов к определению Белнаповских модальных логик и покажем, что эти подходы приводят к слабо дефинициально эквивалентным логикам. В классе си-логик будет выделен подкласс логик, обобщающих логики основанные на бирешетках и показано, что для логик этого класса пропадает разница между слабой и сильной версиями дефинициальной эквивалентности.

Известная теорема Крайзеля утверждает, что любая суперинтуиционистская логика обладает свойством Бета, т.е. в каждой из таких логик неявная определимость влечет явную. Мы заметим, что эта теорема легко обобщается на произвольные импликативные логики. А для избыточных слабоимпликативных логик, удовлетворяющих теореме дедукции, из сильной неявной определимости следует слабая явная определимость. К числу избыточных слабоимпликативных логик с теоремой дедукции относятся, например, все расширения избыточной логики Нельсона N3.

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


➰ ВК

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

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

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

Докладчик: Т.Г. Пшеницын
Тема: ''Операции вставки на формальных языках: от простого к сложному''

В данном обзорном докладе будет рассмотрена классическая операция на формальных языках — вставка — и её разновидности. Стандартный вариант этой операции языкам L и M ставит в соответствие множество слов {uyv|uv из L, y из M}. В литературе также изучаются контекстные вставки: например, когда зафиксировано (конечное) множество контекстов C (состоящее из пар слов), и вставка слова возможна только между строками z и t, пара из которых принадлежит C. Есть ещё более хитрая сайт-направленная вставка, которая языкам L и M ставит в соответствие язык {uzytv|uztv из L, zyt из M}; это тоже контекстная вставка, однако контексты z и t здесь определяются не внешним образом, с помощью фиксированного множества C, а внутренним.

Контекстные вставки изначально мотивировались лингвистическими приложениями (например, в работе Галюкшова "Полуконтекстные грамматики" 1981 года), а позднее — приложениями в биоинформатике: если рассматривать молекулы ДНК как слова, то их взаимодействие действительно можно моделировать контекстной вставкой.

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

➰ ВК

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

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

02.12.2024 Wei Wang (Sun Yat-sen University, Guangzhou): Definable Combinatorial Principles in Fragments of Arithmetic (online only)

In fragments of arithmetic, the pigeonhole principle may fail for definable partitions of finite sets. Dimicoupolous and Paris proved that over IΣ_1 the ordinary pigeonhole principle for Σ_n+1 partitions is equivalent to BΣ_n+1 (n0). Later Kaye formulated several second order pigeonhole principles which are used to axiomatise κ-like models of arithmetic. A first order fragment derived from one of Kaye's pigeonhole principles, known as
Σ_n-cardinality scheme or CΣ_n, has interesting independence properties proved by Kaye himself and also proved useful in reverse mathematics. Recently, we study another first order fragment of these pigeonhole principles, called Generalised Pigeonhole Principle (GPHP) by Kaye. We shall introduce some progress concerning Σ_n+1-GPHP from perspectives of both first order arithmetic and reverse mathematics.

🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&


➰ ВК

#матлог #отмены

В связи с болезнью докладчика доклад на НИС "Современные проблемы математической логики" в ВШЭ отменяется.
(https://vk.com/wall-70743963_1833)

Ждем вас в следующую пятницу!

➰ ВК