Силовой набор - Power set

Элементы набора мощности { x , y , z }, упорядоченные относительно включения .

В математике , то набор мощности (или Powerset ) из множества $S$ есть множество всех подмножеств из $S$ , включая пустое множество и $S$ самых. В аксиоматической теории множеств (в развитых, например, в ZFC аксиом), существование множества мощности любого множества постулировал по аксиомой набора мощности . Powerset из $S$ по - разному обозначается как $P (S)$ , $𝒫 (S)$ , $P (S)$ , , $℘ ($ $S$ $)$ ( с использованием " вейерштрассову р "), или $2$ $S$ . Обозначение $2$ $S$ , означающее набор всех функций от S до данного набора из двух элементов (например, {0, 1}), используется потому, что набор мощности $S$ может быть идентифицирован, эквивалентен или биективен для набора всех функций от $S$ до данного набора двух элементов. ${\ Displaystyle \ mathbb {P} (S)}$

Любое подмножество $P (S)$ называется семейство множеств над $S$ .

Пример

Если $S$ - это множество ${x, y, z}$ , то все подмножества $S$ являются

${}$ (также обозначается или , пустое множество или нулевое множество) ${\ displaystyle \ varnothing}$ ${\ displaystyle \ emptyset}$
${x}$
${y}$
${z}$
${х, у}$
${x, z}$
${y, z}$
${x, y, z}$

и, следовательно, набор степеней $S$ равен ${{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}$ .

Характеристики

Если $S$ - конечное множество с мощностью $| S | = n$ (т. е. количество всех элементов в множестве $S$ равно $n$ ), то количество всех подмножеств $S$ равно $| P (S) | = 2 п$ . Этот факт, а также причина обозначения $2 S,$ обозначающего набор мощности $P (S),$ показаны ниже.

Функция индикатора или характеристическая функция подмножества А из множества S с мощностью | S | = n - функция от S до двух элементов набора {0, 1}, обозначаемая как I _A : S → {0, 1}, и указывает, принадлежит ли элемент S к A или нет; Если x в S принадлежит A , то I _A ( x ) = 1 и 0 в противном случае. Каждое подмножество A из S идентифицируется индикаторной функцией I _A или эквивалентно ей , а {0, 1} ^S как набор всех функций от S до {0, 1} состоит из всех индикаторных функций всех подмножеств S . Другими словами, {0, 1} ^S эквивалентен или биективен множеству

степеней P (S)

. Поскольку каждый элемент в S соответствует 0 или 1 при любой функции в {0, 1} ^S , количество всех функций в {0, 1} ^S равно 2 ⁿ . Так как число 2 может быть определена как

{0,1}

(см, например, фон Неймана ординалы ), то

Р (S)

также обозначается как

2 S

. Очевидно

| 2 S | = 2 | S |

держит. Вообще говоря, X ^Y - это множество всех функций от Y до X и | X ^Y | = | X | ^{| Y |}.

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

Множество степеней множества $S$ вместе с операциями объединения , пересечения и дополнения можно рассматривать как прототипический пример булевой алгебры . Фактически, можно показать, что любая конечная булева алгебра изоморфна булевой алгебре степенного множества конечного множества. Для бесконечных булевых алгебр это уже не так, но каждая бесконечная булева алгебра может быть представлена как подалгебра булевой алгебры степенных множеств (см . Теорему Стоуна о представлении ).

Множество степеней множества $S$ образует абелеву группу, когда она рассматривается с операцией симметричной разности (с пустым множеством как единичный элемент, и каждый набор является своим собственным обратным), и коммутативный моноид, когда рассматривается с операцией пересечения . Следовательно, можно показать, доказывая законы распределения , что набор мощности, рассматриваемый вместе с обеими этими операциями, образует булево кольцо .

Представление подмножеств как функций

В теории множеств , $X Y$ представляет собой обозначение , представляющее множество всех функций от $Y$ к $X$ . Поскольку "2" может быть определено как ${0,1}$ (см., Например, порядковые числа фон Неймана ), $2 S$ (т. $Е. {0,1} S$ ) - это набор всех функций от $S$ до ${0,1}$ . Как показано выше , $2 S$ и набор мощности $S$ , $P (S)$ , теоретически считаются идентичными.

Эту эквивалентность можно применить к приведенному выше примеру , в котором $S = {x, y, z}$ , чтобы получить изоморфизм с двоичными представлениями чисел от 0 до $2 n - 1$ , где $n$ - количество элементов в наборе. $S$ или $| S | = п$ . Сначала определяется нумерованный набор ${(x, 1), (y, 2), (z, 3)},$ в котором число в каждой упорядоченной паре представляет позицию парного элемента $S$ в последовательности двоичных цифр, таких как поскольку ${x, y} = 011 (2)$ ; $x$ группы $S$ расположен первым справа в этой последовательности, а $y$ - вторым справа, и 1 в последовательности означает, что элемент $S,$ соответствующий его положению в последовательности, существует в подмножестве $S$ для последовательность 0 означает, что это не так.

Для всего набора мощности $S$ получаем:

Подмножество	Последовательность двоичных цифр	Двоичная интерпретация	Десятичный эквивалент
${}$	$0, 0, 0$	$000 (2)$	$0 (10)$
${x}$	$0, 0, 1$	$001 (2)$	$1 (10)$
${y}$	$0, 1, 0$	$010 (2)$	$2 (10)$
${х, у}$	$0, 1, 1$	$011 (2)$	$3 (10)$
${z}$	$1, 0, 0$	$100 (2)$	$4 (10)$
${x, z}$	$1, 0, 1$	$101 (2)$	$5 (10)$
${y, z}$	$1, 1, 0$	$110 (2)$	$6 (10)$
${x, y, z}$	$1, 1, 1$	$111 (2)$	$7 (10)$

Такое биективное отображение из $P (S)$ в целые числа является произвольным, поэтому это представление всех подмножеств $S$ не уникально, но порядок сортировки нумерованного множества не меняет его мощности. (Например, ${(y, 1), (z, 2), (x, 3)}$ можно использовать для построения другого биективного от $P (S)$ к целым числам без изменения количества взаимно однозначных соответствий.)

Однако такое конечное двоичное представление возможно только в том случае, если S можно перечислить. (В этом примере $x$ , $y$ и $z$ пронумерованы с помощью 1, 2 и 3 соответственно в качестве позиции двоичных последовательностей цифр.) Перечисление возможно, даже если $S$ имеет бесконечную мощность (т. Е. Количество элементов в $S$ бесконечно), например, набор целых или рациональных чисел, но это невозможно, например, если S является набором действительных чисел, и в этом случае мы не можем перечислить все иррациональные числа.

Связь с биномиальной теоремой

Бином теорема тесно связана с набором мощности. A $K$ -элементов комбинация из некоторого множества это другое название для $к$ -элементам подмножества, таким образом, число комбинаций , обозначается как $C (п, K)$ (также называемый биномиальным коэффициент ) представляет собой число подмножеств с $K$ элементами в наборе с $n$ элементов; другими словами, это количество наборов с $k$ элементами, которые являются элементами набора мощности набора с $n$ элементами.

Например, силовой набор из трех элементов имеет:

C (3, 0) = 1 подмножество с 0 элементами (пустое подмножество),
C (3, 1) = 3 подмножества с 1 элементом (одноэлементные подмножества),
C (3, 2) = 3 подмножества с 2 элементами (дополнения к одноэлементным подмножествам),
C (3, 3) = 1 подмножество с 3 элементами (сам исходный набор).

Используя это соотношение, мы можем вычислить по формуле: ${\ textstyle \ left | 2 ^ {S} \ right |}$

{\ displaystyle \ left | 2 ^ {S} \ right | = \ sum _ {k = 0} ^ {| S |} {\ binom {| S |} {k}}}

Следовательно, можно вывести следующее тождество, предполагая : ${\ textstyle | S | = п}$

{\ displaystyle \ left | 2 ^ {S} \ right | = 2 ^ {n} = \ sum _ {k = 0} ^ {n} {\ binom {n} {k}}}

Рекурсивное определение

Если это конечное множество , то рекурсивное определение из протекает следующим образом : ${\ displaystyle S}$ ${\ Displaystyle P (S)}$

Если , то . ${\ Displaystyle S = \ {\}}$ ${\ Displaystyle Р (S) = \ {\, \ {\} \, \}}$
В противном случае пусть и ; тогда . ${\ displaystyle e \ in S}$ ${\ Displaystyle Т = S \ setminus \ {е \}}$ ${\ Displaystyle P (S) = P (T) \ cup \ {t \ cup \ {e \}: t \ in P (T) \}}$

Прописью:

Набор мощности пустого набора - это синглтон , единственным элементом которого является пустой набор.
Для непустого набора , пусть будет любым элементом набора и его относительным дополнением ; тогда набор мощности представляет собой объединение набора мощности и набора мощности , каждый элемент которого дополняется элементом. ${\ displaystyle S}$ ${\ displaystyle e}$ ${\ displaystyle T}$ ${\ displaystyle S}$ ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle e}$

Подмножества ограниченной мощности

Множество подмножеств $S$ из мощности меньше или равно $х$ иногда обозначается $P К (S)$ или $[S] κ$ , а множество подмножеств с мощности строго меньше , чем $κ$ иногда обозначается $P <х (S)$ или $[S] <κ$ . Точно так же множество непустых подмножеств $S$ можно обозначить $P \geq 1 (S)$ или $P + (S)$ .

Энергетический объект

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

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

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

Некоторые классы алгебр обладают обоими этими свойствами. Первое свойство встречается чаще, и то и другое встречается относительно редко. Один класс, в котором есть и то и другое, - это класс мультиграфов . Учитывая два мультиграфов $G$ и $H$ , A гомоморфизм $Н : G \to H$ состоит из двух функций, одна отображения вершин вершин и другие картографические кромки к краям. Множество $H G$ гомоморфизмов из $G$ в $H$ может быть затем организовано как граф, вершины и ребра которого являются соответственно вершинными и реберными функциями, входящими в это множество. Кроме того, подграфы мультиграфа $G$ находятся в биекции с гомоморфизмами графов из $G$ в мультиграф $Ω,$ определяемый как полный ориентированный граф на двух вершинах (отсюда четыре ребра, а именно две петли и еще два ребра, образующие цикл), дополненных пятое ребро, а именно вторая петля в одной из вершин. Таким образом , мы можем организовать подграфы $G$ как мультиграфе $Ω G$ , называется объект питания из $G$ .

Особенностью мультиграфа как алгебры является то, что его операции унарны. Мультиграф имеет два вида элементов, образующих множество вершин $V$ и ребер $E$ , и две унарные операции $s, t : E \to V,$ задающие исходную (начальную) и целевую (конечную) вершины каждого ребра. Алгебра, все операции которой унарны, называется предпучком . Каждый класс предпучков содержит предпучок $Ω,$ который играет роль для подалгебр, которую 2 играет для подмножеств. Такой класс является частным случаем более общего понятия элементарных топосов как категории, которая замкнута (и, более того, декартово замкнута ) и имеет объект $Ω$ , называемый классификатором подобъектов . Хотя термин «энергетический объект» иногда используется как синоним экспоненциального объекта $Y X$ , в теории топосов требуется, чтобы $Y$ было $Ω$ .

Функторы и кванторы

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

Смотрите также

использованная литература

Список используемой литературы

Девлин, Кейт Дж. (1979). Основы современной теории множеств . Universitext. Springer-Verlag . ISBN 0-387-90441-7. Zbl 0407.04003 .
Халмос, Пол Р. (1960). Теория наивных множеств . Университетская серия по математике. Компания ван Ностранд. Zbl 0087.04403 .
Пунтамбекар, AA (2007). Теория автоматов и формальных языков . Технические публикации. ISBN 978-81-8431-193-8.

Languages

In other projects