Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 20

Ciągiem nazywamy listę pewnych obiektów w określonym porządku. Zwyczajowo ciąg zapisujemy, umieszczając jego elementy w nawiasach okrągłych. Na przykład ciąg 7, 21, 57 można zapisać jako

(7, 21, 57).

W zbiorze porządek elementów nie ma znaczenia, ale w ciągu jest istotny. W związku z tym (7, 21, 57) nie jest tym samym ciągiem, co (57, 7, 21). Podobnie powtarzanie elementów w ciągu jest istotne, choć nie ma znaczenia w zbiorze. Oznacza to, że ciąg (7, 7, 21, 57) różni się od obu wcześniejszych ciągów, choć zbiór {7, 21, 57} jest identyczny ze zbiorem {7, 7, 21, 57}.

Podobnie jak w przypadku zbiorów, ciągi mogą być skończone lub nieskończone. Ciągi skończone są często nazywane krotkami. Ciąg o k elementach nazywamy k-krotką. Tak więc (7, 21, 57) jest 3-krotką. 2-krotka często bywa nazywana parą uporządkowaną – analogicznie używamy pojęć trójki, czwórki czy piątki uporządkowanej.

Zbiory i ciągi mogą występować jako elementy innych zbiorów i ciągów. Na przykład zbiorem potęgowym zbioru A jest zbiór wszystkich podzbiorów A. Jeśli A będzie zbiorem {0, 1}, wówczas zbiór potęgowy A to zbiór { Ø, {0}, {1}, {0, 1} }. Zbiór wszystkich uporządkowanych par, których elementy to zera i jedynki, to { (0, 0), (0, 1), (1, 0), (1, 1) }.

Jeśli A i B to zbiory, to ich iloczynem kartezjańskim, zapisywanym jako A × B, jest zbiór wszystkich par uporządkowanych, w których pierwszy element należy do zbioru A, zaś drugi należy do zbioru B.

Przykład 0.5

Jeżeli A = {1, 2} i B = {x, y, z}, to

A × B = { (1, x), (1, y), (1, z), (2, x), (2, y), (2, z) }.

■

Możemy również wykonać iloczyn kartezjański k zbiorów A₁, A₂, … , A_k, zapisywany jako A₁ × A₂ × … × A_k. Jest to zbiór złożony ze wszystkich k-krotek (a₁, a₂, … , a_k), w których a_i ∈ A_i.

Przykład 0.6

Jeżeli A i B są takimi zbiorami, jak w przykładzie 0.5, to

A × B × A = { (1, x, 1), (1, x, 2), (1, y, 1), (1, y, 2), (1, z, 1), (1, z, 2),

(2, x, 1), (2, x, 2), (2, y, 1), (2, y, 2), (2, z, 1), (2, z, 2)}.

■

Jeśli tworzymy iloczyn kartezjański zbioru z nim samym, możemy użyć skrótowego zapisu

k

A × A × … × A = A^k.

Przykład 0.7

Zbiór N² jest równy N × N. Składa się ze wszystkich uporządkowanych par liczb naturalnych. Możemy go również zapisać jako {(i, j) : i, j ³ 1}.