Форма записи множества

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

Множества, задаваемые перечислением

Множество можно описать путём перечисления всех его элементов внутри фигурных скобок, как в следующих примерах:

{ 7 , 3 , 15 , 31 } {displaystyle {7,3,15,31}} — это множество, содержащее четыре числа: 3, 7, 15 и 31 и ничего более.
{ a , c , b } = { a , b , c } {displaystyle {a,c,b}={a,b,c}} — это множество, содержащее a, b и c и ничего более (порядок элементов в множестве не рассматривается, только их присутствие).

Такое задание иногда называется «методом перечисления» для конкретного множества.

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

{ 1 , 2 , 3 , … , 100 } {displaystyle {1,2,3,ldots ,100}} — это множество целых чисел между 1 и 100 включительно.
{ 1 , 2 , 3 , … } {displaystyle {1,2,3,ldots }} — это множество всех натуральных чисел.
{ … , − 2 , − 1 , 0 , 1 , 2 , … } = { 0 , 1 , − 1 , 2 , − 2 , … } {displaystyle {ldots ,-2,-1,0,1,2,ldots }={0,1,-1,2,-2,ldots }} — это множество всех целых чисел.

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

Так, { 1 , … , n } {displaystyle {1,dots ,n}} означает множество всех натуральных чисел i {displaystyle i} , таких что 1 ⩽ i ⩽ n {displaystyle 1leqslant ileqslant n} . Другим обозначением для множества { 1 , … , n } {displaystyle {1,dots ,n}} является скобочное обозначение [ n ] {displaystyle [n]} . Небольшим исключением является случай n = 0 {displaystyle n=0} , в котором [ 0 ] = { 1 , … , 0 } {displaystyle [0]={1,dots ,0}} является пустым множеством ∅ {displaystyle emptyset } . Аналогично, { a 1 , … , a n } {displaystyle {a_{1},dots ,a_{n}}} обозначает множество всех a i {displaystyle a_{i}} для 1 ⩽ i ⩽ n {displaystyle 1leqslant ileqslant n} .

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

{ {displaystyle {} номера домов по проспекту Косыгина } {displaystyle }} — это множество всех номеров домов по проспекту Косыгина.

Однако такой подход может привести к потере точности или двусмысленности. Так, список адресов по проспекту Косыгина может означать как список домов, так и список квартир в этих домах.

Определение множеств предикатами

Для записи множества могут использоваться предикаты, а не явное перечисление элементов. В этой форме записи множества имеется три части: переменная, двоеточие или вертикальная черта в качестве разделителя и логический предикат. В этом случае есть переменная слева от разделителя и правило справа от него. Эти три части заключаются в фигурные скобки:

{ x ∣ Φ ( x ) } {displaystyle {xmid Phi (x)}}

или

{ x : Φ ( x ) } . {displaystyle {x:Phi (x)}.}

Разделитель можно читать «такое что», «для которого», или «со свойством». Формула Φ(x) называется правилом или предикатом. Все значения переменной x, для которых выполняется предикат (то есть, он верен) принадлежат определяемому множеству. Все значения x, для которых предикат не выполняется, множеству не принадлежат. Таким образом, { x ∣ Φ ( x ) } {displaystyle {xmid Phi (x)}} — это множество всех значений x, для которых верна формула Φ. Это может быть пустое множество, если никакое значение x не удовлетворяет формуле.

Задание области определения

Область определения E может появиться слева от вертикальной черты :

{ x ∈ E ∣ Φ ( x ) } , {displaystyle {xin Emid Phi (x)},}

или она может быть объединена с предикатом:

{ x ∣ x ∈ E и Φ ( x ) } или { x ∣ x ∈ E ∧ Φ ( x ) } . {displaystyle {xmid xin E{ ext{ и }}Phi (x)}quad { ext{или}}quad {xmid xin Eland Phi (x)}.}

Символ ∈ означает здесь принадлежность множеству, в то время как символ ∧ {displaystyle land } означает логический оператор «И», известный как конъюнкция. Это обозначение представляет множество всех значений x, принадлежащих некоторому множеству E, для которых предикат принимает значение true, то есть истина (см. параграф «Аксиома существования» ниже). Если Φ ( x ) {displaystyle Phi (x)} является конъюнкцией Φ 1 ( x ) ∧ Φ 2 ( x ) {displaystyle Phi _{1}(x)land Phi _{2}(x)} , то форма { x ∈ E ∣ Φ ( x ) } {displaystyle {xin Emid Phi (x)}} иногда записывается в виде { x ∈ E ∣ Φ 1 ( x ) , Φ 2 ( x ) } {displaystyle {xin Emid Phi _{1}(x),Phi _{2}(x)}} , используя запятую вместо ∧ {displaystyle land } .

В общем случае некорректно рассматривать множество без определения области определения, поскольку область определения может представлять подмножество всех возможных объектов, которые могут существовать, для которых предикат верен. Это может легко привести к противоречию и парадоксу. Например, парадокс Рассела показывает, что выражение { x | x ∉ x } {displaystyle {x~|~x ot in x}} , хотя и выглядит правильно составленным как выражение для определения множества, не может определить множество без получения противоречия.

В случаях, когда множество E ясно определяется из контекста, его можно не задавать. В литературе принято, чтобы автор заранее указал область определения, а потом область при определении множеств не указывается. Например, автор может написать нечто вроде: «Если не указано противное, переменные принадлежат натуральным числам.»

Примеры

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

{ x ∈ R ∣ x > 0 } {displaystyle {xin mathbb {R} mid x>0}} — это множество всех строго положительных вещественных чисел, что можно записать в интервальных обозначениях как ( 0 , ∞ ) {displaystyle (0,infty )} .
{ x ∈ R ∣ | x | = 1 } {displaystyle {xin mathbb {R} mid |x|=1}} — это множество { − 1 , 1 } {displaystyle {-1,1}} . Это множество можно определить также, как { x ∈ R ∣ x 2 = 1 } {displaystyle {xin mathbb {R} mid x^{2}=1}} ; см. параграф «эквивалентные предикаты задают равные множества» ниже.
Для каждого целого m мы можем определить G m = { x ∈ Z ∣ x ⩾ m } = { m , m + 1 , m + 2 , … } {displaystyle G_{m}={xin mathbb {Z} mid xgeqslant m}={m,m+1,m+2,ldots }} . В качестве примеров: G 3 = { x ∈ Z ∣ x ⩾ 3 } = { 3 , 4 , 5 , … } {displaystyle G_{3}={xin mathbb {Z} mid xgeqslant 3}={3,4,5,ldots }} и G − 2 = { − 2 , − 1 , 0 , … } {displaystyle G_{-2}={-2,-1,0,ldots }} .
{ ( x , y ) ∈ R × R ∣ 0 < y < f ( x ) } {displaystyle {(x,y)in mathbb {R} imes mathbb {R} mid 0<y<f(x)}} — это множество пар вещественных чисел, таких что y больше 0 и меньше f(x) для заданной функции f. Здесь декартово произведение R × R {displaystyle mathbb {R} imes mathbb {R} } означает множество всех упорядоченных пар вещественных чисел.
{ n ∈ N ∣ ( ∃ k ) [ k ∈ N ∧ n = 2 k ] } {displaystyle {nin mathbb {N} mid (exists k)[kin mathbb {N} land n=2k]}} — это множество всех чётных натуральных чисел. Знак ∧ {displaystyle land } стоит для обозначения операции «И», которая известна как конъюнкция. Знак ∃ обозначает «существует», который известен как квантор существования. Так, например, ( ∃ x ) P ( x ) {displaystyle (exists x)P(x)} читается как «существует x, такое что P(x) …".
{ n ∣ ( ∃ k ∈ N ) [ n = 2 k ] } {displaystyle {nmid (exists kin mathbb {N} )[n=2k]}} — это другой вариант записи того же самого множества чётных натуральных чисел. Нет необходимости требовать, чтобы n был натуральным числом, поскольку это следует из формулы в правой части.
{ a ∈ R ∣ ( ∃ p ∈ Z ) ( ∃ q ∈ Z ) [ q ≠ 0 ∧ a q = p ] } {displaystyle {ain mathbb {R} mid (exists pin mathbb {Z} )(exists qin mathbb {Z} )[q ot =0land aq=p]}} — это множество рациональных чисел, то есть это вещественные числа, которые можно записать как частное двух целых чисел.

Более сложные выражения в левой части

Расширение формы записи множеств заменяет единственную переменную x выражением. Таким образом вместо { x ∣ Φ ( x ) } {displaystyle {xmid Phi (x)}} мы можем иметь { Ψ ( x ) ∣ Φ ( x ) } , {displaystyle {Psi (x)mid Phi (x)},} , что можно читать как

{ Ψ ( x ) ∣ Φ ( x ) } = { y ∣ ∃ ( x ) , y = Ψ ( x ) и Φ ( x ) } {displaystyle {Psi (x)mid Phi (x)}={ymid exists (x),y=Psi (x){ ext{ и }}Phi (x)}} .

Например:

{ 2 n ∣ n ∈ N } {displaystyle {2nmid nin mathbb {N} }} , где N {displaystyle mathbb {N} } — множество всех натуральных чисел — это множество всех чётных натуральных чисел.
{ p / q ∣ p , q ∈ Z , q ≠ 0 } {displaystyle {p/qmid p,qin mathbb {Z} ,q ot =0}} , где Z {displaystyle mathbb {Z} } — множество всех целых чисел — это ℚ, множество всех рациональных чисел.
{ 2 t + 1 ∣ t ∈ Z } {displaystyle {2t+1mid tin mathbb {Z} }} — это множество нечётных целых.
{ ( t , 2 t + 1 ) ∣ t ∈ Z } {displaystyle {(t,2t+1)mid tin mathbb {Z} }} создаёт множество пар, где каждая пара состоит из целого и соответствующего ему нечётного числа.

Если обратные функции можно явно указать, выражение слева может быть исключено посредством простой подстановки. Рассмотрим в качестве примера множество { 2 t + 1 ∣ t ∈ Z } {displaystyle {2t+1mid tin mathbb {Z} }} . Сделаем подстановку u = 2 t + 1 {displaystyle u=2t+1} , откуда получаем t = ( u − 1 ) / 2 {displaystyle t=(u-1)/2} , затем заменим t в форме записи множества

{ 2 t + 1 ∣ t ∈ Z } = { u ∣ ( u − 1 ) / 2 ∈ Z } . {displaystyle {2t+1mid tin mathbb {Z} }={umid (u-1)/2in mathbb {Z} }.}

Эквивалентные предикаты задают равные множества

Два множества равны тогда и только тогда, когда они имеют те же элементы. Множества, определённые формой записи множества равны тогда и только тогда, когда равны их правила построения, включая указание области определения. То есть

{ x ∈ A ∣ P ( x ) } = { x ∈ B ∣ Q ( x ) } {displaystyle {xin Amid P(x)}={xin Bmid Q(x)}}

тогда и только тогда, когда

( ∀ t ) [ ( t ∈ A ∧ P ( t ) ) ⇔ ( t ∈ B ∧ Q ( t ) ) ] {displaystyle (forall t)[(tin Aland P(t))Leftrightarrow (tin Bland Q(t))]} .

Поэтому, чтобы доказать равенство двух множеств, определённых формой записи множества, достаточно доказать эквивалентность их предикатов, включая области определения.

Например:

{ x ∈ R ∣ x 2 = 1 } = { x ∈ Q ∣ | x | = 1 } {displaystyle {xin mathbb {R} mid x^{2}=1}={xin mathbb {Q} mid |x|=1}}

Поскольку два предиката-правила логически эквивалентны:

( x ∈ R ∧ x 2 = 1 ) ⇔ ( x ∈ Q ∧ | x | = 1 ) . {displaystyle (xin mathbb {R} land x^{2}=1)Leftrightarrow (xin mathbb {Q} land |x|=1).}

Эта эквивалентность имеет место, поскольку для любого вещественного числа x мы имеем x 2 = 1 {displaystyle x^{2}=1} тогда и только тогда, когда x рационально и | x | = 1 {displaystyle |x|=1} . В частности, оба множества равны множеству { − 1 , 1 } {displaystyle {-1,1}} .

Аксиома существования множества

Во многих формальных теориях множеств, таких как система Цермело — Френкеля, форма записи множества не является частью формального синтаксиса теории. Вместо этого имеется аксиоматическая схема существования множества, которая утверждает, что если E – множество, а Φ(x) – формула из языка теории множеств, то существует множество Y, членами которого являются в точности элементы E, удовлетворяющие условию Φ:

( ∀ E ) ( ∃ Y ) ( ∀ x ) [ x ∈ Y ⇔ x ∈ E ∧ Φ ( x ) ] . {displaystyle (forall E)(exists Y)(forall x)[xin YLeftrightarrow xin Eland Phi (x)].}

Множество Y, полученное из данной аксиомы есть в точности множество, описанное в форме записи множества { x ∈ E ∣ Φ ( x ) } {displaystyle {xin Emid Phi (x)}} .

Параллели в языках программирования

Аналогичная нотация, доступная во многих языках программирования (особенно Python и Haskell) — это списковое включение, которое комбинирует операции map и фильтр над одним и более списком.

На языке Python скобки записи множества заменяются на квадратные скобки, круглые или фигурные скобки, для определения списка, генератора и набора объектов соответственно. Python использует синтакс английского языка. Haskell заменяет скобки записи множества квадратными скобками и использует математические символы, включая стандартную для записи множества вертикальную черту.

То же самое можно получить в Scala с помощью Sequence Comprehensions, где ключевое слово «for» возвращает список переменных, полученных с помощью ключевого слова «yield».

Рассмотрим следующие задания множеств в некоторых языках программирования:

Форма записи множества и списковое включение являются частными случаями более общей нотации, известной как генератор монад. Эта нотация позволяет операции, подобные map/filter над любой монадой С с нулевым элементом.