Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для разработчиков поисковой системы см. Powerset (компания) .
Элементы степенного множества множества { x , y , z }, упорядоченные по включению .

В математике , то набор мощности (или Powerset ) из множества S есть множество всех подмножеств из S , включая пустое множество и S самых. [1] В аксиоматической теории множеств (в развитых, например, в ZFC аксиом), существование множества мощности любого множества постулировал по аксиомой набора мощности . [2] Набор степеней S обозначается по-разному как P ( S ), 𝒫 ( S ), [3] P ( S ) , ℙ ( S ) , ℘ ( S ) (использованием " вейерштрассову р "), или 2 S . Обозначение 2 S используется потому, что для любого набора ровно с двумя элементами набор мощности S может быть идентифицирован с набором всех функций из S в этот набор. [1]

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

Пример [ править ]

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

  • {} (также обозначается или , пустое множество или нулевое множество) [3]
  • { x }
  • { y }
  • { z }
  • { х , у }
  • { x , z }
  • { y , z }
  • { x , y , z }

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

Свойства [ править ]

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

Сначала расположите элементы S любым способом. Запишем любое подмножество S в формате {γ 1 , γ 2 , ..., γ n }, где γ i , 1 ≤ i ≤ n , может принимать значение 0 или 1 . Если γ i = 1 , i -й элемент S находится в подмножестве; в противном случае i -й элемент не входит в подмножество. Ясно, что количество различных подмножеств, которые могут быть построены таким образом, равно 2 n, поскольку γ i ∈ {0, 1}.

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

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

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

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

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

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

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

ПодмножествоПоследовательность
цифр		Двоичная
интерпретация		Десятичный
эквивалент
{}0, 0, 0000 (2)0 (10)
{ x }0, 0, 1001 (2)1 (10)
{ y }0, 1, 0010 (2)2 (10)
{ х , у }0, 1, 1011 (2)3 (10)
{ z }1, 0, 0100 (2)4 (10)
{ x , z }1, 0, 1101 (2)5 (10)
{ y , z }1, 1, 0110 (2)6 (10)
{ x , y , z }1, 1, 1111 (2)7 (10)

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

Однако такое конечное двоичное представление возможно только в том случае, если S можно перечислить. Это возможно, даже если S имеет бесконечную мощность, такую ​​как набор целых чисел или рациональных чисел, но не, например, если S является набором действительных чисел, и в этом случае мы не можем перечислить все иррациональные числа, чтобы назначить им определенное конечное местоположение в заказанный набор.

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

Набор мощности тесно связан с биномиальной теоремой . Число подмножеств с K элементов в наборе мощности множества с п элементов задается числом комбинаций , С ( п , к ) , называемый также биномиальных коэффициентов .

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

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

Используя это соотношение, мы можем вычислить по формуле:

Следовательно, можно вывести следующее тождество, предполагая :

Рекурсивное определение [ править ]

Если это конечное множество , то рекурсивное определение из протекает следующим образом :

  • Если , то .
  • В противном случае пусть и ; тогда .

Прописью:

  • Набор мощности пустого набора - это синглтон , единственным элементом которого является пустой набор.
  • Для непустого набора , пусть будет любым элементом набора и его относительным дополнением ; тогда набор мощности представляет собой объединение набора мощности и набора мощности , каждый элемент которого расширяется с помощью элемента.

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

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

Силовой объект [ править ]

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

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

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

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

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

Функторы и кванторы [ править ]

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

См. Также [ править ]

  • Теорема кантора
  • Семейство наборов
  • Поле наборов
  • Комбинация

Ссылки [ править ]

  1. ^ a b Вайсштейн, Эрик В. "Power Set" . mathworld.wolfram.com . Проверено 5 сентября 2020 .
  2. Перейти ↑ Devlin 1979 , p. 50
  3. ^ а б «Исчерпывающий список символов теории множеств» . Математическое хранилище . 2020-04-11 . Проверено 5 сентября 2020 .
  4. ^ Puntambekar 2007 , стр. 1-2
  5. ^ Маклейн , Ик Моердижк (1992) Пучки в геометрии и логики Springer-Verlag. ISBN 0-387-97710-4 См. Стр. 58 

Библиография [ править ]

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

Внешние ссылки [ править ]

  • Мощность установлена в PlanetMath .
  • Набор мощности в nLab
  • Энергетический объект в nLab
  • Алгоритм набора мощности в C ++