Pergandaan Himpunan

Suatu pasangan (x, y) dikatakan pasangan terurut dengan x urutan pertama dan y urutan kedua.

Dua pasangan terurut (a, b) dan (c, d) dikatakan sama jika dan hanya jika a = c dan b = d. Ditulis sebagai:

(a, b) = (c, d) ↔ a = c ∧ b = d

Dapat diperluas menjadi n-pasangan terurut:

(a₁, a₂, …, a_n) = (b₁, b₂, …, b_n) ↔ a_i = b_i untuk i = 1, 2, …, n

Contoh:

(2, 5) ≠ (5, 2) karena berbeda urutan

Definisi Pergandaan Kartesius:

Jika A dan B sembarang himpunan, maka perkalian dua himpuan A dan B (ditulis A × B dan dibaca "A cross B") adalah himpunan dari semua pasangan terurut berbentuk (x,y) dengan x ∈ A dan y ∈ B . Perkalian ini juga disebut “pergandaan Kartesius (Cartesian product)” yang disimbolkan sebagai:

A × B = {(x, y) | x ∈ A ∧ y ∈ B}, bisa juga disimbolkan dengan:

(x, y) ∈ (A × B) ↔ (∀x, y). x ∈ A ∧ y ∈ B

Sifat-sifat pergandaan himpunan:

• Jika himpunan A mempunyai n-anggota dan himpunan B mempunyai m-anggota maka perkalian himpunan A × B mempunyai (n × m) anggota.
• Hasil kali dari himpunan kosong dan semua himpunan adalah himpunan kosong (H × ∅ = ∅ × H = ∅).
• A × B ≠ B × A, tidak komutatif karena urutannya terbalik

Contoh:

Misal H = {a, b} dan K = {c, d}:

H × K = {(a, c), (a, d), (b, c), (b, d)}

K × H = {(c, a), (c, b), (d, a), (d, b)}

Kartu Bridge termasuk contoh pergandaan himpunan

R = {2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A}

S = {♠, ♥, ♦, ♣}

Satu set kartu bride adalah hasil pergandaan himpunan R × S ataupun S × R, hasilnya tidak komutatif tetapi memiliki korespondensi satu-satu.

Telah diketahui bahwa pergandaan himpunan tidak komutatif, selain itu masih ada sifat-sifat lainnya:

1. Tidak asosiatif

(A × B) × C ≠ A × (B × C) ≠ A × B × C

contoh:

A = {1}, B = {2}, C = {3}

(A × B) × C = {(1, 2), 3}

A × (B × C) = {1, (2, 3)}

A × B × C = {(1, 2, 3)}

2. Distributif tunggal dengan majemuk

A × (B ∩ C) = (A × B) ∩ (A × C)

A × (B ∪ C) = (A × B) ∪ (A × C)

A × (B \ C) = (A × B) \ (A × C)

3. Distributif majemuk dengan tunggal

(A ∪ B) × C = (A × C) ∪ (B × C)

(A ∩ B) × C = (A × C) ∩ (B × C)

4. Distributif majemuk dengan majemuk

(A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D)

(A ∪ B) × (C ∪ D) ≠ (A × C) ∪ (B × D), tidak distributif terhadap gabungan

(A ∪ B) × (C ∪ D) = [(A\B) × C] ∪ [(A ∩ B) × (C ∪ D)] ∪ [(B\A) × D]

(A\B) × (C\D) ≠ (A × C) \ (B × D), tidak distributif terhadap selisih

(A\B) × (C\D) = [A × (C\D)] ∪ [(A\B) × C]

5. Komplemen

(A × B)' = (A' × B') ∪ (A' × B) ∪ (A × B')

6. Himpunan bagian

Jika A ⊆ B maka (A × C) ⊆ (B × C)

(A × B) ⊆ (C × D) jika dan hanya jika A ⊆ C dan B ⊆ D