Пес Ебленский - Логика первого порядка [entries|archive|friends|userinfo]
rex_weblen

[ website | Наши рисуночки ]
[ userinfo | ljr userinfo ]
[ archive | journal archive ]

Links
[Links:| update journal edit friends fif tiphareth recent comments ]

Логика первого порядка [Jan. 21st, 2023|08:11 pm]
Previous Entry Add to Memories Tell A Friend Next Entry
[Tags|, , ]
[Current Mood | sleepy]
[Current Music |Swans - The Seer]

Начал изучать по Беллу. Базовая теория Ок. Но не понравилось, что много внимания уделяется теории доказательств и алгоритмам. Начал читать Милети. Очень им доволен. Понравилось, что много интересных примеров из алгебры. Единственный минус Милети, что избегаются углубления в Булевы алгебры, Топологию. Но для этого есть Хинман.

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

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

Интересно, что структуры в каждом языке образуют категорию. Там есть естественное понятие морфизма, то есть отображения, которые коммутируют с функциями, сохраняют и отражают предикаты кроме '='. Но тут никакие аксиомы еще не кодируются, поэтому, например, категория структур языка групп (одна нуль-арная операция-константа, одна унарная операция и одна бинарная операция) это еще не то же самое, что и категория групп. Так как никто не гарантирует, что, например, константа будет нейтральным элементом, а унитарная операция инверсией. При этом такие морфизмы не обязательно сохраняют произвольные высказывания. Но если они это делают, то такие морфизмы называются почему-то элементарными. То есть можно еще определить "элементарную категорию" где все морфизмы такие. Если в языке есть знак "=" и в структуре ему действительно соответствует равенство (по дефолту так считается), то элементарные морфизмы будут инъекции.

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

Другая это интересная тема это определимые множества. То есть множества, которые можно задать внутри структуры одной формулой на языке 1-го порядка. Множество определимых множеств для структуры будет алгеброй. Милети ловко доказывает, что все определимые множества комплексных чисел в языке колец это конечные или коконечные множества. Интересное свойство определимых множеств это их инвариантность под действием группы автоморфизмов структуры. Идея определимых множеств развивается в теории алгебраических замыканий. Алгебраическим элементом над множеством X в структуре S называются элементы, которые содержатся в конечных множествах, которые определимы с параметрами в множествe X. Алгебраическое замыкание X это множество всех алгебраических над ним элементов. Если в качестве структуры S взять алгебраически замкнутое поле, а в качестве X какое-то меньшие поле, то его алгебраическое замыкание это алгебраическое замыкание в смысле теории полей. Отсюда и названия. Если S это бесконечное векторное пространство, а X его подмножество, то алгебраическое замыкание X это линейная оболочка span(X). Я заметил, что вся эта теория определения с параметрами связана с подгруппами фиксирующими параметры. Поэтому тут может быть какое-то обобщение теории Галуа. Но я никаких интересных примеров не придумал.

Как и в случае с логикой высказываний множество утверждений, которая содержит все свои следствия называется теорией. Любое множество утверждений можно расширить до теории. Для любой модели S множество всех истинных утверждений про нее тоже будет теорией Th(S). Причем, эта теория будет полна, то есть любое утверждение будет либо ложным, либо истинным. Для любой множества утверждений Phi можно построить класс моделей Mod(Phi), для которых ее утверждения истины. Если класс моделей можно построить как Mod(Phi), то оно называется элементарным классом. Если множество моделей можно взять конечным, то мы получим сильный элементарный класс. Например, класс всех групп будет сильным элементарным классом теории групп (конечное множество аксиом на языке групп). Для класса моделей K тоже можно построить теорию Th(K) всех истинных про них утверждений, но скорее всего не полную. Эти операторы Th и Mod задают связность Галуа между упорядоченными классами множеств утверждений и классов структур. Причем, замкнутыми элементами тут будут именно теории и элементарные классы.

Милете определяет "характеристическую функцию" I(phi,n) утверждения phi как число неизоморфных структур кардинальности n для которых верно phi. Тогда спектром высказывания phi называется множество натуральных чисел n, таких что I(phi,n) не равно 0, то есть имеются модели кардинальности n. Вопрос о том замкнуто ли множество всех спектров под операцией дополнения является открытым. Оказывается этот вопрос эквивалентен вопросу теории сложности вычислений NE = сo-NE, где NE это класс задач с суб-экспоненциальной сложностью. В более сложной теории моделей рассматриваются и спектры теорий.

Удивительное результаты связаны со свойством убирания кванторов теории. Это свойство, что у любого утверждения есть эквивалентная формула без кванторов. Кажется, что это очень сильное свойство. Тут много удобных результатов. Например, любое определимое множество для модели такой теории можно задать формулой без кванторов. И если есть структура которая вкладывается во все модели этой теории, то эта теория полна. Например алгебраически замкнутые поля обладают свойством убирания кванторов. И если добавить дополнительное утверждение про характеристику поля, то мы получим полную теорию. Отсюда, в частности следует, что определимые подмножества комплексных чисел в языке колец просто устроены: так как можно использовать формулы без кванторов, то это алгебра порождённая множествами корней полиномов с целыми коэффициентами.

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

Некоторые более продвинутые источники про связь между логикой первого порядка, теорией моделей и теорией Галуа:

https://press.uchicago.edu/ucp/books/book/distributed/G/bo6166783.html (развитие темы со связностью Галуа)

https://home.mathematik.uni-freiburg.de/ziegler/preprints/CaLaPiZi-Gal-1.6.pdf

https://arxiv.org/abs/1511.05541
LinkLeave a comment

Comments:
From:(Anonymous)
Date:January 21st, 2023 - 05:24 pm
(Link)
а есть формальное определение множества? формальное определение понятия "элемент"? если да то через какие термины даётся это определение, и какое определение у терминов через которые даётся формальное определение "множества"? аа аа аа?
From:(Anonymous)
Date:January 21st, 2023 - 06:33 pm
(Link)
кастанеда пидорас
[User Picture]
From:[info]rex_weblen
Date:January 22nd, 2023 - 10:24 am
(Link)
Да тут все просто.

Есть языки с синтаксисом понятным. И есть аксиомы на богике первого порядка.

То есть множества это все, а если написать a \in b, то a это элемент b. Все больше никаких определений не нужно. Что такое богика первого порядка определяется всевышними силами рекурсивно.
From:(Anonymous)
Date:January 22nd, 2023 - 12:01 pm
(Link)
а что вот делать с этой такой тёмной мякоткой-писечкой математической интуиции? ведь она всегда рядом, когда думаешь либо о самых простых понятиях, аксиомах, либо когда решаешь сложную задачу - происходят как бы полускрытые процессы, кусочки непросредственного пре-формального понимания.
ну как бы же есть в голове у человека какие-то пре-концепты, базовые и интуиции о пространстве, изменении и порядке например, ну или численная интуиция, хотя это наверное тоже фундаментально интуиция о порядке. то есть об этом Кант пиздел, но мне кажется как раз при занятиях математикой и понимаешь о чём он таки пиздел; конечно эта интуиция часто ложная и без формального языка не обойтись, но она как маяк в каком-то смысле, нет?
[User Picture]
From:[info]rex_weblen
Date:January 22nd, 2023 - 12:43 pm
(Link)
Да, хорошим вопросом было бы не как определить что такое множество, а объяснить почему такое-то определение соответствует интуиции.

Понятно, что вопрос о мотивации тех или иных математических решений он намного сложней и интересней, и просто так формально решен быть не может.
From:(Anonymous)
Date:January 22nd, 2023 - 12:25 pm
(Link)
>Что такое богика первого порядка определяется всевышними силами рекурсивно.

У человека в целом кажется проблема рекурсиями, бесконечными иерархиями, с бесконечностью, при том что люди научились отличать счётные от несчётных бесконечностей и есть целая теория больших кардиналов, однако как будто бы всё что работает и всё что понятно, работает и является понятным локально, если мы начинаем уходить в предел - сразу проблемы.
При чём это видно даже на уровне простого языка, если сыграть в игру "что значит?" - находишь рандомное слово - ищешь его определение, потом ищешь определения слов в том определение и тд, в конце понимаешь, что по-сути значений слов ты и не знаешь. Или такая же игра детская "почемучка", там уже будет бесконечная цепочка причино-следствий.
Думаю людишки в целом вынуждены обитать в конечных мирах, потому что за пределами конечности появляются всякие лавкрафтианские ужасы, шиза и хтонь.
[User Picture]
From:[info]rex_weblen
Date:January 22nd, 2023 - 12:51 pm
(Link)
Мне кажется самые простые определения можно сводить к эмпирическому, когда просто показываешь. Потому что самое простое определение буквы "А" это просто показать на сам символ. А если говорить, что буква "А" это первая буква Русского алфавита, то сразу начнутся вопросы, типа что такое "алфавит", и игра в "почемучку".

Отсюда можно прийти, наверное, что чистого познания быть не может.
From:(Anonymous)
Date:January 22nd, 2023 - 03:57 pm
(Link)
>Русского

Нене, тогда ж придется давать определение русского
From:(Anonymous)
Date:January 23rd, 2023 - 08:14 am
(Link)
можно эмпирически показать нахуй
From:(Anonymous)
Date:January 21st, 2023 - 05:25 pm
(Link)
>Начал изучать по Беллу
О блять еще один кабиночный сиделец нарисовалса маня. Сука когда уже посты вротмненог в фифе будут подряд идти...
From:(Anonymous)
Date:January 21st, 2023 - 07:07 pm
(Link)
пиздец ты быдло
From:(Anonymous)
Date:January 21st, 2023 - 07:38 pm
(Link)
первый документ пу делу
[User Picture]
From:[info]rex_weblen
Date:January 22nd, 2023 - 02:10 pm
(Link)
Я не просто быдло, я и быдло, и бомж!
From:(Anonymous)
Date:January 21st, 2023 - 07:07 pm
(Link)
Логика любого порядка приводит к результату, что вонючая русня это говно.
From:(Anonymous)
Date:January 21st, 2023 - 10:46 pm
(Link)
что ты там "начал изучать", пидар обосраный?

учись у свиньера - как увидит учебник математики, хватает, и бегом в туалет, через час выходит поумневшим

по методу хуйнера-свинера обучались лучшие умы тифаретника, а "начал изучать" - это для пидоров
From:(Anonymous)
Date:January 22nd, 2023 - 12:03 am

Алиса - Кабiнка

(Link)
рождённый в сортире чтит тамбура корни
From:(Anonymous)
Date:January 22nd, 2023 - 09:51 am
(Link)
Ты так Б-га не познаешь, а познаешь только богика первого порядка
[User Picture]
From:[info]rex_weblen
Date:January 22nd, 2023 - 10:16 am
(Link)
А что по этому поводу говорят богики высшего порядка?
From:(Anonymous)
Date:January 22nd, 2023 - 04:03 pm
(Link)
они как покемоны, говорят только свое имя
From:(Anonymous)
Date:January 22nd, 2023 - 03:20 pm
(Link)
СЯУ, что поганые СЖВ затравили художника tacklebox, и он выпилился со всех галерей. Бляди гнойные, суки.
From:(Anonymous)
Date:February 1st, 2023 - 08:39 am
(Link)
Good Morning, Mr. Weblen! Gde mozhno skachat' knigu Mileti.
[User Picture]
From:[info]rex_weblen
Date:February 10th, 2023 - 08:27 pm
(Link)
https://drive.google.com/file/d/1Ig1K7nU7vDYH-SzXAfSAbSjYOM5etDcx/view?usp=sharing

Это версия 2020 года, которая раньше была в открытом доступе.

Еще в интернете много где есть версия 2016 там нет последних глав.

Но мне кажется, что тут последние главы тоже не дописаны относительно, того что продает Cambridge.