Инструменты пользователя

Инструменты сайта


others:poryadkovie_strukturi_v_algebre_i_teorii_chisel

Различия

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

Ссылка на это сравнение

Both sides previous revision Предыдущая версия
others:poryadkovie_strukturi_v_algebre_i_teorii_chisel [2015/12/27 20:14]
admin
others:poryadkovie_strukturi_v_algebre_i_teorii_chisel [2016/01/18 13:24] (текущий)
nadjasinizkaja
Строка 1: Строка 1:
 **Порядковые структуры в алгебре и теории чисел** **Порядковые структуры в алгебре и теории чисел**
  
-Второй основной тип математических структур представляют собой структуры,​ определенные //​отношением порядка//,​ формализующие идею сравнения объектов (элементов множества) по величине. Базовым порядковым объектом является упорядоченное множество,​ из которого может быть получено понятие величины,​ ее основные свойства. Отношение порядка исследуется в теории упорядоченных множеств и решеток. Теоретико-решеточный метод ​исследования позволяет более полно исследовать математические объекты, выявить связи и их новые свойства. Изучение порядковой структуры опирается на понятие бинарного отношения на множестве. Порядковая ​структура составляет неотъемлемую часть дискретной математики и входит в математические основы компьютерных наук. Порядковая структура,​ по сравнению с алгебраическим и топологическим типами структур, в явном виде практически не изучается ни в школе, ни в вузе.  +В универсальной алгебре и в теории моделей, структура состоит из набора наряду с коллекцией finitary ​операций и отношений, которые определены на нем.
-Порядковые структуры проявляются в следующих основных понятиях и методах математики:+
  
-1) понятие бинарного отношенияотношения порядка, свойств ​упорядоченных множеств ​(в курсах «Алгебра ​и теория чисел», «Введение в математику»); ​+Универсальная алгебра изучает структуры,​ которые ​обобщают алгебраические структуры, такие как группы, ​кольца, области и векторные ​пространства. Термин ​универсальная алгебра использован для структур без символов отношения.
  
-2) строение упорядоченных числовых структур ​(линейно упорядоченные полукольцакольца ​и поляи их свойства ​(в курсе ​«Числовые системы»);+У теории моделей есть различный объем, который охватывает более произвольные теории, включая основополагающие ​структуры, такие как модели теории множеств. С образцово-теоретической точки зрения структуры - объекты, используемые, чтобы определить семантику логики первого порядка. Для данной теории в теории моделей структуру называют моделью,​ если это удовлетворяет аксиомы определения той теории,​ хотя это иногда ​снимается неоднозначность как семантическая модель, когда каждый обсуждает понятие в более общем урегулировании математических моделей. Логики иногда именуют структуры как интерпретации.
  
-3) теория неравенств и метод математической индукции ​(в курсах «Элементарная ​математика» и «Алгебра и теория чисел»);+В теории базы данных ​структуры без функций изучены как модели для реляционных ​баз данных в форме относительных моделей.
  
-4) перестановки, как способ упорядочения конечного множества и размещения (упорядочения m-элементного множества, состоящего из n-элементов) (в курсе «Теория вероятностей»);+Определение 
 +Формально, структура может ​быть ​определена как тройное, состоящее из области A, подпись σ, и функция интерпретации I, который указывает, как ​подпись ​должна интерпретироваться ​на области. Чтобы указатьчто у структуры есть ​особая подпись σ, можно именовать ее как σ-structure.
  
-5) отношение делимостиНОД ​и НОК ​натуральных чисел (в курсе ​«Алгебра и теория чисел»);+Область 
 +Область структуры - произвольный набор; это также называют основным набором ​структурыее перевозчик (особенно в универсальной алгебре), ​или ее вселенная ​(особенно ​в теории моделей). В классической ​логике первого порядка определение структуры запрещает пустую область.
  
-6) основные числовые системы ​N, Z, Q и R (в курсе «Числовые системы»);+Иногда примечание или используется для области, ​но часто ​никакое письменное различие не сделано между ​структурой ​и ее областью. (Т.е. тот же самый символ относится ​к структуре и к ее области.)
  
-7) алгебра множеств (объединение, пересечение)алгебра высказываний (дизъюнкция и конъюнкция высказываний) (в курсе «Математическая логика»).+Подпись 
 +Подпись структуры состоит из ряда символов функции и символов отношения наряду ​с функциейкоторая приписывает каждому символу s натуральное число, которое называют арностью s, потому что это - арность интерпретации s.
  
 +Так как подписи,​ которые возникают в алгебре часто, содержат только символы функции,​ подпись без символов отношения называют алгебраической подписью. Структуру с такой подписью также называют алгеброй;​ это не должно быть перепутано с понятием алгебры по области.
  
 +Функция интерпретации
 +Функция интерпретации I из назначает функции и отношения к символам подписи. Каждому символу функции f арности n назначают функция не на области. Каждому символу отношения R арности n назначают отношение не на области. Символ функции nullary c называют постоянным символом,​ потому что его интерпретация I (c) может быть отождествлена с постоянным элементом области.
  
 +Когда структура (и следовательно функция интерпретации) дана контекстом,​ никакое письменное различие не сделано между символом s и его интерпретацией I (s). Например,​ если f - двойной символ функции,​ каждый просто пишет, а не.
  
 +Примеры
 +Стандартная подпись σ для областей состоит из двух двойных символов функции + и ×, одноместный символ функции − и два постоянных символа 0 и 1.
  
 +Таким образом структура (алгебра) для этой подписи состоит из ряда элементов вместе с двумя двойными функциями,​ одноместной функцией и двумя выдающимися элементами;​ но нет никакого требования,​ чтобы это удовлетворило любую из полевых аксиом. Рациональные числа Q, действительные числа R и комплексные числа C, как любая другая область,​ могут быть расценены как σ-structures очевидным способом:​
  
 +::
  
 +::
  
 +::
  
 +где
  
 +:: добавление рациональных чисел,
  
 +:: умножение рациональных чисел,
  
 +:: функция,​ которая берет каждое рациональное число x к-x и
  
 +:: номер 0 и
  
 +:: номер 1;
 +
 +и и так же определены.
 +
 +Но кольцо Z целых чисел, который не является областью,​ является также σ-structure таким же образом. Фактически,​ нет никакого требования,​ чтобы любая из полевых аксиом держалась в σ-structure.
 +
 +Подписи для заказанных областей нужно дополнительное бинарное отношение такой как < или ≤, и поэтому структуры для такой подписи не алгебра,​ даже при том, что они - конечно,​ алгебраические структуры в обычном,​ свободном значении слова.
 +
 +Обычная подпись для теории множеств включает единственное бинарное отношение ∈. Структура для этой подписи состоит из ряда элементов и интерпретации ∈ отношения как бинарное отношение на этих элементах.
 +
 +Вызванные фундаменты и закрытые подмножества
 +назван (вызванным) фундаментом если
 +
 +и имейте ту же самую подпись;​
 +область содержится в области:;​ и
 +интерпретации всей функции и символов отношения договариваются.
 +Обычное примечание для этого отношения.
 +
 +Подмножество области структуры называют закрытым,​ если это закрыто под функциями,​ т.е. если следующее условие удовлетворено:​ для каждого натурального числа n, каждый символ функции не f (в подписи) и все элементы,​ результатом применения f к n-кортежу является снова элемент B:.
 +
 +Для каждого подмножества есть самое маленькое закрытое подмножество этого, содержит B. Это называют закрытым подмножеством,​ произведенным B или корпусом B, и обозначило или. Оператор - finitary оператор закрытия на наборе подмножеств.
 +
 +Если и закрытое подмножество,​ то вызванный фундамент,​ где назначает на каждый символ σ ограничение на B его интерпретации в. С другой стороны область вызванного фундамента - закрытое подмножество.
 +
 +Закрытые подмножества (или вызванные фундаменты) структуры формируют решетку. Встречание двух подмножеств - их пересечение. Соединение двух подмножеств - закрытое подмножество,​ произведенное их союзом. Универсальная алгебра изучает решетку фундаментов структуры подробно.
 +
 +Примеры
 +Позвольте σ = {+, ×, −, 0, 1} быть снова стандартной подписью для областей. Когда расценено как σ-structures естественным способом,​ рациональные числа формируют фундамент действительных чисел, и действительные числа формируют фундамент комплексных чисел. Рациональные числа - самый маленький фундамент реального (или комплекс) числа, который также удовлетворяет полевые аксиомы.
 +
 +Набор целых чисел дает еще меньший фундамент действительных чисел, который не является областью. Действительно,​ целые числа - фундамент действительных чисел, произведенных пустым набором,​ используя эту подпись. Понятие в абстрактной алгебре,​ которая соответствует фундаменту области в этой подписи,​ является тем из подкольца,​ а не тем из подполя.
 +
 +Самым очевидным способом определить граф является структура с подписью σ состоящий из единственного символа бинарного отношения E. Вершины графа формируют область структуры,​ и для двух вершин a и b, средства,​ что a и b связаны краем. В этом кодировании понятие вызванного фундамента более строго,​ чем понятие подграфа. Например,​ позвольте G быть графом,​ состоящим из двух вершин,​ связанных краем и позволить H быть графом,​ состоящим из тех же самых вершин,​ но никаких краев. H - подграф G, но не вызванный фундамент. Понятие в теории графов,​ которая соответствует вызванным фундаментам,​ является понятием вызванных подграфов.
 +
 +Гомоморфизмы и embeddings
 +Гомоморфизмы
 +Учитывая две структуры и той же самой подписи σ, (σ-) гомоморфизм от к является картой,​ которая сохраняет функции и отношения. Более точно:
 +
 +Для каждого символа функции не f σ и любых элементов,​ держится следующее уравнение:​
 +::.
 +
 +Для каждого символа отношения не R σ и любых элементов,​ держится следующее значение:​
 +::.
 +
 +Примечание для гомоморфизма h от к.
 +
 +Для каждой подписи σ есть конкретная категория σ-Hom, у которого есть σ-structures как объекты и σ-homomorphisms как морфизмы.
 +
 +Гомоморфизм иногда называют сильным если для каждого символа отношения не R и любых элементов,​ таким образом что, там таковы что и
 +
 +Сильные гомоморфизмы дают начало подкатегории σ-Hom.
 +
 +Эмбеддингс
 +(σ-) гомоморфизм называют (σ-) вложением,​ если это непосредственное и
 +
 +для каждого символа отношения не R σ и любых элементов,​ держится следующая эквивалентность:​
 +::.
 +
 +Таким образом вложение - та же самая вещь как сильный гомоморфизм,​ который является непосредственным.
 +
 +Категория σ-Emb σ-structures и σ-embeddings является конкретной подкатегорией σ-Hom.
 +
 +Вызванные фундаменты соответствуют подобъектам в σ-Emb. Если у σ есть только символы функции,​ σ-Emb - подкатегория мономорфизмов σ-Hom. В этом случае вызванные фундаменты также соответствуют подобъектам в σ-Hom.
 +
 +Пример
 +Столь же замеченный выше, в стандартном кодировании графов как структурирует вызванные фундаменты,​ точно вызванные подграфы. Однако гомоморфизм между графами - та же самая вещь как гомоморфизм между этими двумя структурами,​ кодирующими граф. В примере предыдущей секции,​ даже при том, что подграф H G не вызван,​ идентификатор карты идентичности:​ H → G - гомоморфизм. Эта карта - фактически мономорфизм в категории σ-Hom, и поэтому H - подобъект G, который не является вызванным фундаментом.
 +
 +Проблема гомоморфизма
 +Следующая проблема известна как проблема гомоморфизма:​
 +
 +:Given две конечных структуры и конечной относительной подписи,​ найдите гомоморфизм или покажите,​ что никакой такой гомоморфизм не существует.
 +
 +У
 +каждой ограничительной проблемы удовлетворения (CSP) есть перевод на проблему гомоморфизма.
 +
 +Поэтому сложность CSP может быть изучена,​ используя методы конечной теории моделей.
 +
 +Другое применение находится в теории базы данных,​ где относительная модель базы данных - по существу та же самая вещь как относительная структура. Оказывается,​ что соединительный вопрос на базе данных может быть описан другой структурой в той же самой подписи как модель базы данных. Гомоморфизм от относительной модели до структуры,​ представляющей вопрос,​ является той же самой вещью как решение вопроса. Это показывает,​ что соединительная проблема вопроса также эквивалентна проблеме гомоморфизма.
 +
 +Структуры и логика первого порядка
 +Структуры иногда упоминаются как «структуры первого порядка». Это вводит в заблуждение,​ поскольку ничто в их определении не связывает их ни с какой определенной логикой,​ и фактически они подходят как семантические объекты оба для очень ограниченных фрагментов логики первого порядка,​ таких как используемый в универсальной алгебре,​ и для логики второго порядка. В связи с логикой первого порядка и теорией моделей,​ структуры часто называют моделями,​ даже когда вопрос «модели какой?​» не имеет никакого очевидного ответа.
 +
 +Отношение удовлетворения
 +Каждой структуре первого порядка определили отношение удовлетворения для всех формул на языке, состоящем из языка вместе с постоянным символом для каждого элемента M, который интерпретируется как тот элемент.
 +
 +Это отношение определено,​ индуктивно используя T-схему Тарского.
 +
 +Структура,​ как говорят,​ является моделью теории T, если язык совпадает с языком T, и каждое предложение в T удовлетворено. Таким образом,​ например,​ «кольцо» - структура для языка колец, который удовлетворяет каждую из кольцевых аксиом,​ и модель теории множеств ZFC - структура на языке теории множеств,​ которая удовлетворяет каждую из аксиом ZFC.
 +
 +Определимые отношения
 +Отношение не R на вселенной M структуры,​ как говорят,​ определимо (или явно определимым,​ или - определимый),​ если есть формула φ (x..., x) таким образом что
 +
 +:
 +
 +Другими словами,​ R определим,​ если и только если есть формула φ таким образом что
 +
 +:
 +
 +правильно.
 +
 +Важный особый случай - определимость определенных элементов. Элемент m M определим в если и только если есть формула φ (x) таким образом что
 +
 +:
 +
 +Определимость с параметрами
 +Отношение R, как говорят,​ определимо с параметрами (или - определимый),​ если есть формула φ с параметрами от таким образом,​ что R - определимое использование φ. Каждый элемент структуры - определимое использование самого элемента в качестве параметра.
 +
 +Нужно отметить,​ что некоторые авторы используют определимый,​ чтобы означать определимый без параметров,​ в то время как другие авторы,​ злые определимый с параметрами. Вообще говоря,​ соглашение,​ что определимое средство,​ определимое без параметров,​ более распространено среди теоретиков набора,​ в то время как противоположное соглашение более распространено среди образцовых теоретиков.
 +
 +Неявная определимость
 +Вспомните из вышеупомянутого,​ что отношение не R на вселенной M структуры явно определимо,​ если есть формула φ (x..., x) таким образом что
 +
 +:
 +
 +Здесь формула φ раньше определяла отношение R, должен быть по подписи и таким образом,​ φ может не упомянуть сам R, так как R не находится в подписи. Если есть формула φ на расширенном языке, содержащем язык и новый символ R, и отношение R является единственным отношением на таким образом это, то R, как говорят,​ неявно определим законченный.
 +
 +Теоремой Бет каждое неявно определимое отношение явно определимо.
 +
 +Много-сортированные структуры
 +Структуры,​ как определено выше иногда называют s, чтобы отличить их от более общего s. У много-сортированной структуры может быть произвольное число областей. Виды - часть подписи,​ и они играют роль названий различных областей. Много-сортированные подписи также предписывают,​ на котором сортирует функции,​ и отношения много-сортированной структуры определены. Поэтому арность символов функции или символов отношения должна быть более сложными объектами,​ такими как кортежи своего рода а не натуральные числа.
 +
 +Векторные пространства,​ например,​ могут быть расценены как две сортированных структуры следующим образом. Две сортированных подпись векторных пространств состоит из двух видов V (для векторов) и S (для скаляров) и следующие символы функции:​
 +
 +Если V векторное пространство по области Ф, соответствующая две сортированных структура состоит из векторной области,​ скалярной области и очевидных функций,​ таких как векторный ноль, скалярный ноль или скалярное умножение.
 +
 +Много-сортированные структуры часто используются в качестве удобного инструмента,​ даже когда их можно было избежать с небольшим усилием. Но они редко определяются строгим способом,​ потому что это прямо и утомительно (следовательно не вознаграждающий),​ чтобы выполнить обобщение явно.
 +
 +В большей части математической деятельности не много внимания обращено на виды. Много-сортированная логика,​ однако,​ естественно приводит к теории типа. Как Барт Джейкобс выражается:​ «Логика всегда - логика по теории типа». Этот акцент в свою очередь приводит к категорической логике,​ потому что логика по теории типа категорически соответствует одной («полной») категории,​ захватив логику,​ будучи волокнистой по другой («основной») категории,​ захватив теорию типа.
 +
 +Другие обобщения
 +Частичная алгебра
 +И универсальная алгебра и теория моделей изучают классы (структуры или) алгебра,​ которая определена подписью и рядом аксиом. В случае теории моделей у этих аксиом есть форма предложений первого порядка. Формализм универсальной алгебры намного более строг; по существу это только позволяет предложения первого порядка,​ у которых есть форма универсально определенных количественно уравнений между условиями,​ например,​ x y (x + y = y + x). Одно последствие - то, что выбор подписи более значительный в универсальной алгебре,​ чем это находится в теории моделей. Например,​ класс групп, в подписи,​ состоящей из двойного символа функции × и постоянного символа 1, является элементарным классом,​ но это не разнообразие. Универсальная алгебра решает эту проблему,​ добавляя одноместный символ функции.
 +
 +В случае областей эта стратегия работает только на дополнение. Для умножения это терпит неудачу,​ потому что 0 не имеет мультипликативной инверсии. Специальная попытка иметь дело с этим состояла бы в том, чтобы определить 0 = 0. (Эта попытка терпит неудачу,​ по существу потому что с этим определением 0 × 0 = 1 не верно.) Поэтому каждого естественно ведут позволить частичные функции,​ т.е., функции,​ которые определены только на подмножестве их области. Однако есть несколько очевидных способов обобщить понятия,​ такие как фундамент,​ гомоморфизм и идентичность.
 +
 +Структуры для напечатанных языков
 +В теории типа есть много видов переменных,​ у каждой из которых есть тип. Типы индуктивно определены;​ учитывая два типа δ и σ там также тип σ → δ, который представляет функции от объектов типа σ к объектам типа δ. Структура для напечатанного языка (в обычной семантике первого порядка) должна включать отдельный набор объектов каждого типа, и для типа функции у структуры должна быть полная информация о функции,​ представленной каждым объектом того типа.
 +
 +Языки высшего порядка
 +Есть больше чем одна возможная семантика для логики высшего порядка,​ как обсуждено в статье о логике второго порядка. Используя полную семантику высшего порядка,​ структура должна только иметь вселенную для объектов типа 0, и T-схема расширена так, чтобы квантор по типу высшего порядка был удовлетворен моделью,​ если и только если это disquotationally верно. Используя семантику первого порядка,​ дополнительный вид добавлен для каждого типа высшего порядка,​ как в случае многих сортировал первый язык заказа.
 +
 +Структуры,​ которые являются надлежащими классами
 +В исследовании теории множеств и теории категории,​ иногда полезно рассмотреть структуры,​ в которых область беседы - надлежащий класс вместо набора. Эти структуры иногда называют моделями класса,​ чтобы отличить их от «моделей набора»,​ обсужденных выше. Когда область - надлежащий класс, каждая функция и символ отношения могут также быть представлены надлежащим классом.
 +Второй основной тип математических структур представляют собой структуры,​ определенные //​отношением порядка//,​ формализующие идею сравнения объектов (элементов множества) по величине. Базовым порядковым объектом является упорядоченное множество,​ из которого может быть получено понятие величины,​ ее основные свойства. Отношение порядка исследуется в теории упорядоченных множеств и решеток. Теоретико-решеточный метод исследования позволяет более полно исследовать математические объекты,​ выявить связи и их новые свойства. Изучение порядковой структуры опирается на понятие бинарного отношения на множестве. Порядковая структура составляет неотъемлемую часть дискретной математики и входит в математические основы компьютерных наук. Порядковая структура,​ по сравнению с алгебраическим и топологическим типами структур,​ в явном виде практически не изучается ни в школе, ни в вузе. ​
 +Порядковые структуры проявляются в следующих основных понятиях и методах математики:​
 +
 +1) понятие бинарного отношения,​ отношения порядка,​ свойств упорядоченных множеств (в курсах «Алгебра и теория чисел»,​ «Введение в математику»); ​
 +
 +2) строение упорядоченных числовых структур (линейно упорядоченные полукольца,​ кольца и поля) и их свойства (в курсе «Числовые системы»);​
 +
 +3) теория неравенств и метод математической индукции (в курсах «Элементарная математика» и «Алгебра и теория чисел»);​
 +
 +4) перестановки,​ как способ упорядочения конечного множества и размещения (упорядочения m-элементного множества,​ состоящего из n-элементов) (в курсе «Теория вероятностей»);​
 +
 +5) отношение делимости,​ НОД и НОК натуральных чисел (в курсе «Алгебра и теория чисел»);​
 +
 +6) основные числовые системы N, Z, Q и R (в курсе «Числовые системы»);​
 +
 +7) алгебра множеств (объединение,​ пересечение),​ алгебра высказываний (дизъюнкция и конъюнкция высказываний) (в курсе «Математическая логика»).
  
-~~DISCUSSION~~ 
others/poryadkovie_strukturi_v_algebre_i_teorii_chisel.txt · Последние изменения: 2016/01/18 13:24 — nadjasinizkaja