Материал: Ответы на экзаменационные вопросы по дискретной математике

Утверждение 2 (признак бесконечности множества). Множество бесконечно тогда и только тогда, когда оно эквивалентно некоторому своему собственному подмножеству.

Доказательство. По определению: множество бесконечно тогда и только тогда, когда из него можно выделить собственное счётное подмножество . По предыдущему утверждению множества и равномощны, что и требовалось доказать.

Произведение двух мощностей и — мощность прямого произведения двух множеств и (), мощность одного из которых равна , а другого (очевидно, что произведение мощностей не зависит от выбора множеств и , а зависит только от их мощностей). Аналогично определяется — произведение любого числа мощностей.

Если , , то .

Выше мы доказали, что …

4. Алгебраическая структура. Полугруппа, моноид, группа. Примеры

Бинарная алгебраическая операция (или закон композиции) на непустом множестве — отображение множества всех упорядоченных пар в множество объектов любой природы. При этом если упорядоченной паре , где , ставится в соответствие элемент , то пишут и называют бинарной операцией на множестве , а совокупность двух объектов называют алгебраической системой с основным множеством и бинарной операцией . Причём говорят, что операция определяет на алгебраическую структуру. Тот факт, что обязательно принадлежит множеству , называется замкнутостью структуры по отношению к этой операции. Далее, если не оговорено противное, мы будем считать все рассматриваемые бинарные операции замкнутыми.

Все алгебраические структуры с одним набором операций можно классифицировать следующим образом:

• Простые алгебраические структуры (бинарных операций нет):

  • Множество.

  • Множество с отмеченной точкой.

  • Некоторые другие…

• Группообразные структуры (одна бинарная операция).

  • Магма.

  • Полугруппа.

  • Моноид.

  • Группа.

  • Полурешётка.

  • Некоторые другие…

• Кольцеобразные структуры (две бинарные операции: сложение и умножение).

  • Полукольцо.

  • Почтикольцо.

  • Кольцо.

  • Область целостности.

  • Поле.

  • Некоторые другие…

• Решётчатые структуры (две или более бинарные операции).

  • Полная решётка.

  • Булева алгебра.

  • Некоторые другие…

• Арифметика (две бинарные операции: сложение и умножение, бесконечные множества).

  • Арифметика Робинсона.

  • Арифметика Пеано.

Мы рассмотрим 6 следующих структур: 3 с одной бинарной операцией — полугруппы, моноиды и группы; 3 с двумя бинарными операциями — кольца, области целостности и поля.

Подструктура данной алгебраической структуры— подмножество множества , само являющееся структурой с теми же структурными операциями.

Пример. Подполугруппа — подмножество полугруппы, само являющееся полугруппой, подмоноид — подмножество моноида, само являющееся моноидом, подгруппа — подмножество группы, само являющееся группой.

Каждая структура содержит:

• Несобственные подструктуры: сама структура и нейтральный элемент (см. далее).

• Собственные подструктуры: все остальные подструктуры (то есть те, которые не являются несобственными).

Пример. Множество . Его несобственные подмножества: ( — означает пустое множество); собственные: . По такой аналогии можно понимать и подструктуры алгебраических структур.

Символы:

• — квантор всеобщности. — для любого (всякого, каждого) значения из : истинно.

• — квантор существования. — существует (найдётся) значение из такое, что истинно. — существует и единственный.

• — отрицание. — для любого (всякого, каждого) значения из : не истинно (ложно). — существует (найдётся) значение из такое, что не истинно (ложно).

• — символ сложения. Результат называется суммой.

• — символ вычитания. Результат называется разностью.

• — символ умножения. Результат называется произведением.

• — символ деления. Результат называется частным (возможно с остатком).

• — символы произвольных различных бинарных операций.

Числа:

• — натуральные числа.

• — натуральные числа с нулём.

• — чётные натуральные числа. Также с нулём:

• — целые числа. Коротко: .

• — чётные целые числа.

• — целые числа без нуля.

• — положительные целые числа.

• — отрицательные целые числа.

• — целые числа по модулю .

• — рациональные числа (наивное определение).

• — вещественные (действительные) числа (неполное определение). — положительные и отрицательные вещественные числа с нулями.

• — комплексные числа (неполное определение).

Пример. — чётно. — ложно (не любое натуральное чётно).

Пример. — чётно. — истинно (любое чётное целое чётно).

Пример. — чётно. — истинно (найдётся чётное натуральное).

Пример. — чётно. — ложно (не найдётся нечётное среди чётных).

Пример. Вычитание, определённое на множестве , — незамкнутая операция, так как , а сложение — замкнутая: .

Замкнутость множества относительно операции:

Ассоциативность операции (сочетательный закон):

Коммутативность операции (переместительный закон):

Дистрибутивность операции относительно (распределительный закон):

(слева)

(справа)

Если операция является коммутативной, то свойства дистрибутивности слева и справа равносильны.

Обратим внимание на то, что коммутативность и ассоциативность независимы. Например, в множестве операция: — коммутативна, но не ассоциативна, так как:

Магма

Магма — множество с одной бинарной операцией . Помимо требования замкнутости множества относительно заданной на нём операции, других требований к операции и множеству не предъявляется.

Магма не часто изучается как таковая; вместо этого существует несколько различных типов магмы, в зависимости от того, каким аксиомам операция должна удовлетворять.

В следующей таблице представлена классификация алгебраических структур с одной бинарной операцией по свойствам (просто для получения общей картины).