MAT2033 · 4. hafta · sets and functions

Kümeler: işlemler, kuvvet kümesi ve küme eşitliği ispatı

Alt küme, kuvvet kümesi, kartezyen çarpım, küme işlemleri ve küme eşitliğini üyelik tablosu ya da çift yönlü içermeyle ispatlama.

setelementroster methodset-builder notationempty setsubsetproper subsetcardinalitypower setCartesian productordered pairunionintersectiondifferencecomplementsymmetric differencedisjointVenn diagrammembership tableset identityinclusion-exclusion

Kümeler (sets) ayrık matematiğin “veri yapısı”. Fonksiyonlar, bağıntılar, graflar, olasılık: hepsi kümeler üzerine kurulur. Vizede bu konudan genelde bir hesap parçası (işlemleri yap, kuvvet kümesini yaz) ve bir ispat parçası (iki kümenin eşit olduğunu göster) gelir. Hesap parçası bedava puandır; ispat parçasında üç yöntemden birini şablon gibi uygularsın.

Altın kurallar:

Küme sırasız ve tekrarsızdır. $\{1, 2, 3\} = \{3, 1, 2\} = \{1, 1, 2, 3\}$ .
$\in$ ile $\subseteq$ farklı sorulardır. Birincisi tek bir eleman sorar, ikincisi bütün elemanları.
$\lvert \mathcal{P}(A) \rvert = 2^{\lvert A \rvert}$ . Boş kümeyi ve $A$ ‘nın kendisini yazmayı unutma.
Küme işlemleri mantık işlemleridir. $\cap = \land$ , $\cup = \lor$ , tümleyen $= \lnot$ .
Eşitlik için iki yön, eşitsizlik için tek örnek.

Temel tanımlar

Küme (set): iyi tanımlanmış nesneler topluluğu. Nesnelere eleman (element) denir: $a \in A$ .

İki yazım biçimi:

Roster method (liste): $A = \{2, 4, 6, 8\}$ .
Set-builder notation: $A = \{x \in \mathbb{Z}^+ \mid x \text{ is even and } x < 10\}$ .

Standart kümeler: $\mathbb{N} = \{0, 1, 2, \dots\}$ (Rosen’da 0 dahil), $\mathbb{Z}$ tam sayılar, $\mathbb{Z}^+$ pozitif tam sayılar, $\mathbb{Q}$ rasyoneller, $\mathbb{R}$ reeller. Aralıklar: $[a, b]$ , $(a, b)$ gibi.

Kavram	Tanım	Örnek
Empty set $\emptyset$	hiç elemanı olmayan küme	$\{x \in \mathbb{R} \mid x^2 = -1\} = \emptyset$
Subset $A \subseteq B$	$\forall x\,(x \in A \to x \in B)$	$\{1, 2\} \subseteq \{1, 2, 3\}$
Proper subset $A \subset B$	$A \subseteq B$ ve $A \ne B$	$\{1\} \subset \{1, 2\}$
Equality $A = B$	$A \subseteq B$ ve $B \subseteq A$	$\{1, 2\} = \{2, 1\}$
Cardinality $\lvert A \rvert$	sonlu kümede eleman sayısı	$\lvert \{a, \{a\}\} \rvert = 2$

Her küme için $\emptyset \subseteq A$ ve $A \subseteq A$ . Boş kümenin alt küme olması “vacuous truth” yüzünden: $x \in \emptyset$ hiç doğru olmadığı için koşullu önerme otomatik doğru.

TUZAK · $\emptyset$ ile $\{\emptyset\}$ . $\emptyset$ boş bir kutu. $\{\emptyset\}$ içinde boş bir kutu olan bir kutu: bir elemanı var. $\lvert \emptyset \rvert = 0$ , $\lvert \{\emptyset\} \rvert = 1$ .

Kuvvet kümesi ve kartezyen çarpım

Power set $\mathcal{P}(A)$ : $A$ ‘nın bütün alt kümelerinin kümesi.

$\mathcal{P}(\{a, b, c\}) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$

8 eleman: $2^3$ . Neden $2^n$ ? Her eleman için iki seçenek var: alt kümede ya var ya yok. $n$ eleman, $2 \cdot 2 \cdots 2 = 2^n$ .

Sistemli yazmak için boyuta göre grupla: 0 elemanlı (1 tane), 1 elemanlı (3), 2 elemanlı (3), 3 elemanlı (1).

Cartesian product $A \times B = \{(a, b) \mid a \in A,\ b \in B\}$ . Elemanlar sıralı ikili (ordered pair): $(a, b) = (c, d)$ ancak $a = c$ ve $b = d$ ise. $A = \{1, 2\}$ , $B = \{p, q\}$ :

$A \times B = \{(1, p), (1, q), (2, p), (2, q)\}, \qquad \lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert.$

$B \times A$ ‘nın elemanları $(p, 1)$ gibi, ilk koordinat $B$ ‘den. Yani genelde $A \times B \ne B \times A$ . $A \times \emptyset = \emptyset$ .

Küme işlemleri

İşlem	Tanım (set-builder)	Mantık karşılığı
Union $A \cup B$	$\{x \mid x \in A \lor x \in B\}$	$\lor$
Intersection $A \cap B$	$\{x \mid x \in A \land x \in B\}$	$\land$
Difference $A - B$	$\{x \mid x \in A \land x \notin B\}$	$p \land \lnot q$
Complement $\overline{A}$	$\{x \in U \mid x \notin A\}$	$\lnot$
Symmetric difference $A \oplus B$	$(A - B) \cup (B - A)$	$\oplus$

$A \cap B = \emptyset$ ise $A$ ile $B$ ayrık (disjoint).

Örnek. $U = \{1, \dots, 8\}$ , $A = \{1, 2, 3, 4\}$ , $B = \{3, 4, 5, 6\}$ .

A ∩ B = {3, 4}            A ∪ B = {1, 2, 3, 4, 5, 6}
A − B = {1, 2}            B − A = {5, 6}
Ā = {5, 6, 7, 8}          A ⊕ B = {1, 2, 5, 6}

İçerme-dışlama (inclusion-exclusion): $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ . Örnekte $4 + 4 - 2 = 6$ . Kesişim iki kere sayıldığı için bir kere çıkarılır.

Küme özdeşlikleri (set identities)

Hepsi mantık kanunlarının birebir kopyası:

Kanun	Özdeşlik
Identity	$A \cup \emptyset = A$ , $A \cap U = A$
Domination	$A \cup U = U$ , $A \cap \emptyset = \emptyset$
Complement	$A \cup \overline{A} = U$ , $A \cap \overline{A} = \emptyset$ , $\overline{\overline{A}} = A$
Distributive	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
De Morgan	$\overline{A \cup B} = \overline{A} \cap \overline{B}$ , $\overline{A \cap B} = \overline{A} \cup \overline{B}$
Absorption	$A \cup (A \cap B) = A$ , $A \cap (A \cup B) = A$
Difference	$A - B = A \cap \overline{B}$

Küme eşitliğini ispatlamanın üç yolu

Yol 1: Çift yönlü içerme (double inclusion)

$X = Y$ ‘yi göstermek için $X \subseteq Y$ ve $Y \subseteq X$ ‘i ayrı ayrı göster.

Teorem. $\overline{A \cup B} = \overline{A} \cap \overline{B}$ .

(⊆) Let x ∈ complement(A ∪ B). Then x ∉ A ∪ B, so it is not the case
    that x ∈ A or x ∈ B. By De Morgan's law (logic), x ∉ A and x ∉ B,
    i.e. x ∈ Ā and x ∈ B̄. Hence x ∈ Ā ∩ B̄.
(⊇) Let x ∈ Ā ∩ B̄. Then x ∉ A and x ∉ B, so x is in neither set,
    i.e. x ∉ A ∪ B. Hence x ∈ complement(A ∪ B).
Both inclusions hold, so the sets are equal.  ∎

Yol 2: Üyelik tablosu (membership table)

Doğruluk tablosunun aynısı: 1 “elemanı”, 0 “elemanı değil”. Üç küme 8 satır. Her iki tarafın sütununu hesapla, aynıysa eşit.

Teorem. $A - (B \cap C) = (A - B) \cup (A - C)$ .

$A$	$B$	$C$	$B \cap C$	$A - (B \cap C)$	$A - B$	$A - C$	$(A-B) \cup (A-C)$
1	1	1	1	0	0	0	0
1	1	0	0	1	0	1	1
1	0	1	0	1	1	0	1
1	0	0	0	1	1	1	1
0	1	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0

“Since the columns for $A - (B \cap C)$ and $(A - B) \cup (A - C)$ are identical, the two sets are equal.” ∎

$X - Y$ sütununu doldururken kural: “ $X$ ‘te 1 VE $Y$ ‘de 0” ise 1. $A = 0$ olan satırlarda fark otomatik 0; alt yarıyı hızlı doldurursun.

Yol 3: Set-builder ve mantık kanunları

Her adımı bir tanım ya da mantık kanunuyla gerekçelendir. Soru 9 bu yolun örneği. En kısa yazım budur ama her satırın gerekçesini yazmak zorunlu.

İPUCU · Hangi yolu seçeyim? Soru “use a membership table” diyorsa tablo. “Prove that” diyorsa en güvenlisi çift yönlü içerme; hoca derste genelde onu yapar. Zaman azsa tablo en mekanik yol, hata payı en düşük.

Eşit değil göstermek

Tek somut örnek: küçük kümeler seç ( $\{1\}$ , $\emptyset$ ), iki tarafı hesapla, farklı çıksın. Üyelik tablosunda farklı çıkan satır sana hazır bir örnek verir: o satırda 1 olan kümelere 1 elemanını koy.

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
$\{1, 1, 2\}$ üç elemanlı	İki elemanlı; tekrar sayılmaz
$\emptyset \in A$ her zaman doğru	$\emptyset \subseteq A$ her zaman doğru; $\in$ ayrı soru
$\lvert \{\emptyset\} \rvert = 0$	1
$\mathcal{P}(A)$ ‘yı yazarken $\emptyset$ ya da $A$ ‘yı unutmak	Sayı kontrolü: $2^{\lvert A \rvert}$ eleman
$A \times B = B \times A$	Sıralı ikili; genelde farklı
$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert$	Kesişimi çıkar
“4 ya da 6’ya bölünen”de kesişim 24’ün katları	EKOK: 12’nin katları
Bir örnekte eşit çıktı, demek ki eşit	Eşitlik için genel ispat; eşitsizlik için tek örnek
$A - B = B - A$	Fark değişmeli değil
Çift yönlü içermede tek yönü yazmak	İki yön de lazım

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

Let $U = \{1, 2, \dots, 10\}$ , $A = \{2, 3, 5, 7\}$ and $B = \{1, 2, 3, 4, 5\}$ . Find $A \cap B$ , $A \cup B$ , $A - B$ , $B - A$ and $\overline{A}$ .

Cevabı göster

A∩B = {2,3,5}, A∪B = {1,2,3,4,5,7}, A−B = {7}, B−A = {1,4}, Ā = {1,4,6,8,9,10}

Kesişim: ikisinde ortak olanlar 2, 3, 5. Birleşim: tekrar yazmadan hepsi. $A - B$ : $A$ 'dan $B$ 'de olanları sil, sadece 7 kalır. $B - A$ : $B$ 'den 2, 3, 5'i sil: $\{1, 4\}$ . Tümleyen: $U$ 'da olup $A$ 'da olmayanlar.

Soru 2kolay

Find $\lvert \mathcal{P}(\{a, b, c, d\}) \rvert$ and $\lvert \mathcal{P}(\mathcal{P}(\emptyset)) \rvert$ .

Cevabı göster

16 and 2

$n$ elemanlı kümenin $2^n$ alt kümesi var: $2^4 = 16$ . $\mathcal{P}(\emptyset) = \{\emptyset\}$ , bir elemanlı. Onun kuvvet kümesi $\{\emptyset, \{\emptyset\}\}$ , iki elemanlı: $2^1 = 2$ .

Soru 3kolay

True or false? (a) $\emptyset \in \{1, 2\}$ (b) $\emptyset \subseteq \{1, 2\}$ (c) $\{1\} \in \{1, \{1\}\}$ (d) $\{1\} \subseteq \{1, \{1\}\}$ (e) $\{\{1\}\} \subseteq \{1\}$

Cevabı göster

(a) F (b) T (c) T (d) T (e) F

(a) $\{1, 2\}$ 'nin elemanları 1 ve 2; $\emptyset$ onlardan biri değil. (b) Boş küme her kümenin alt kümesidir. (c) $\{1\}$ ikinci eleman olarak listede var. (d) $\{1\}$ 'in tek elemanı 1, o da kümede var. (e) $\{\{1\}\}$ 'in elemanı $\{1\}$ ; $\{1\}$ kümesinin elemanı sadece 1. $\{1\} \ne 1$ , yanlış. $\in$ "eleman mı?", $\subseteq$ "bütün elemanları içeride mi?" diye sorar.

Soru 4orta

Let $A = \{1, 2\}$ and $B = \{x, y, z\}$ . Find $\lvert A \times B \rvert$ , $\lvert A \times B \times A \rvert$ and $\lvert \mathcal{P}(A \times B) \rvert$ .

Cevabı göster

6, 12, 64

$\lvert A \times B \rvert = 2 \cdot 3 = 6$ . Üçlü çarpım: $2 \cdot 3 \cdot 2 = 12$ . $A \times B$ 6 elemanlı bir küme, kuvvet kümesi $2^6 = 64$ elemanlı.

Soru 5orta

Use a membership table to determine whether $(A \cup B) - C = (A - C) \cup (B - C)$ .

Cevabı göster

Equal (identical columns)

8 satır, sıra $A B C$ = 111, 110, 101, 100, 011, 010, 001, 000. $A \cup B$ : 1,1,1,1,1,1,0,0. $(A\cup B) - C$ (" $A \cup B$ 'de 1 ve $C$ 'de 0"): 0,1,0,1,0,1,0,0. $A - C$ : 0,1,0,1,0,0,0,0. $B - C$ : 0,1,0,0,0,1,0,0. Birleşimleri: 0,1,0,1,0,1,0,0. Sütunlar aynı, kümeler eşit.

Soru 6orta

Is $A - (B - C) = (A - B) - C$ for all sets? Prove or give a counterexample.

Cevabı göster

No. A = B = C = {1}: left side {1}, right side ∅.

Küme farkı birleşmeli (associative) değil. $A = B = C = \{1\}$ : $B - C = \emptyset$ , so $A - (B - C) = \{1\}$ . $A - B = \emptyset$ , so $(A - B) - C = \emptyset$ . Farklı. Eşit olmadığını göstermek için tek somut örnek yeter.

Soru 7kolay

In a class of 40 students, 25 take Python, 18 take Java and 9 take both. How many students take neither?

Cevabı göster

$\lvert P \cup J \rvert = \lvert P \rvert + \lvert J \rvert - \lvert P \cap J \rvert = 25 + 18 - 9 = 34$ . İkisini de alan 9 kişi iki kere sayıldı, bir kere çıkardık. Hiçbirini almayan: $40 - 34 = 6$ .

Soru 8zor

Prove that $A \cap (B - A) = \emptyset$ for all sets $A$ and $B$ .

Cevabı göster

An element of both would satisfy x ∈ A and x ∉ A, a contradiction.

Suppose, for contradiction, that some $x \in A \cap (B - A)$ . Then $x \in A$ and $x \in B - A$ ; the second means $x \in B$ and $x \notin A$ . So $x \in A$ and $x \notin A$ , contradiction. Hence the set has no elements. ∎ Boş küme olduğunu göstermenin standart yolu: "bir eleman olsaydı" diye başlayıp çelişki.

Soru 9zor

Prove De Morgan's law $\overline{A \cap B} = \overline{A} \cup \overline{B}$ using set-builder notation and logical equivalences.

Cevabı göster

x ∈ complement(A∩B) ⟺ ¬(x∈A ∧ x∈B) ⟺ x∉A ∨ x∉B ⟺ x ∈ Ā ∪ B̄

$\overline{A \cap B} = \{x \mid x \notin A \cap B\} = \{x \mid \lnot(x \in A \land x \in B)\}$ (def. of intersection) $= \{x \mid x \notin A \lor x \notin B\}$ (De Morgan's law for logic) $= \{x \mid x \in \overline{A} \lor x \in \overline{B}\}$ (def. of complement) $= \overline{A} \cup \overline{B}$ (def. of union). ∎ Her adımın yanına gerekçe yaz.

Soru 10orta

How many integers from 1 to 200 (inclusive) are divisible by 4 or by 6?

Cevabı göster

$\lvert A_4 \rvert = \lfloor 200/4 \rfloor = 50$ , $\lvert A_6 \rvert = \lfloor 200/6 \rfloor = 33$ . Hem 4'e hem 6'ya bölünen = $\operatorname{lcm}(4, 6) = 12$ 'ye bölünen: $\lfloor 200/12 \rfloor = 16$ . Toplam $50 + 33 - 16 = 67$ . Tuzak: kesişimi $4 \cdot 6 = 24$ 'e bölünenler sanmak; doğrusu EKOK 12.

Soru 11kolay

List the elements of $\{x \in \mathbb{Z} \mid x^2 < 10\}$ .

Cevabı göster

{−3, −2, −1, 0, 1, 2, 3}

$x^2 < 10$ ise $\lvert x \rvert \le 3$ ( $3^2 = 9 < 10$ , $4^2 = 16$ ). Negatifleri unutma: $-3$ 'ün karesi de 9.

Soru 12zor

Prove that if $A \subseteq B$ , then $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ .

Cevabı göster

If S ∈ P(A), then S ⊆ A ⊆ B, so S ∈ P(B).

Let $S \in \mathcal{P}(A)$ . By definition $S \subseteq A$ . Let $x \in S$ ; then $x \in A$ , and since $A \subseteq B$ , $x \in B$ . So $S \subseteq B$ , i.e. $S \in \mathcal{P}(B)$ . Since $S$ was arbitrary, $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ . ∎ Alt küme ispatı hep "Let $x \in X$ ... then $x \in Y$ " kalıbıyla yazılır.

Doğrulama: Bütün küme işlemleri JavaScript dizileriyle, üyelik tabloları 8 satırın hepsi hesaplanarak, kuvvet kümesi boyutları üretilerek, sayma soruları 1..200 taranarak node ile kontrol edildi (verify/MAT2033/04.mjs).

Deftere not kartı

Küme: sırasız, tekrarsız. {1,2,2,3} = {3,2,1}, 3 elemanlı. ∈ eleman mı? ⊆ bütün elemanları içeride mi? ∅ ⊆ her küme, ∅ ∈ X ise ayrı soru ∅ 0 elemanlı, {∅} 1 elemanlı. |P(A)| = 2^|A| (∅ ve A dahil) |A×B| = |A|·|B| (a,b) ≠ (b,a) A×B ≠ B×A genelde A∩B ortak, A∪B hepsi, A−B = A∩B̄, Ā = U−A, A⊕B = (A−B)∪(B−A) Mantık sözlüğü: ∩↔∧, ∪↔∨, tümleyen↔¬, ⊆↔→ De Morgan: (A∪B)‾ = Ā∩B̄ (A∩B)‾ = Ā∪B̄ |A∪B| = |A|+|B|−|A∩B| (k ya da m'ye bölünen: kesişim EKOK'a bölünen) Eşitlik ispatı 1: X⊆Y ve Y⊆X ("Let x ∈ X. Then ... so x ∈ Y") Eşitlik ispatı 2: üyelik tablosu, 1/0, sütunlar aynı Eşitlik ispatı 3: set-builder + mantık kanunları Eşit DEĞİL: tek somut örnek (A=B=C={1} gibi) A−(B−C) ≠ (A−B)−C fark birleşmeli değil

$A$	$B$	$C$	$B \cap C$	$A - (B \cap C)$	$A - B$	$A - C$	$(A-B) \cup (A-C)$
1	1	1	1	0	0	0	0
1	1	0	0	1	0	1	1
1	0	1	0	1	1	0	1
1	0	0	0	1	1	1	1
0	1	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0

$A$	$B$	$C$	$B \cap C$	$A - (B \cap C)$	$A - B$	$A - C$	$(A-B) \cup (A-C)$
1	1	1	1	0	0	0	0
1	1	0	0	1	0	1	1
1	0	1	0	1	1	0	1
1	0	0	0	1	1	1	1
0	1	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0

$A$	$B$	$C$	$B \cap C$	$A - (B \cap C)$	$A - B$	$A - C$	$(A-B) \cup (A-C)$
1	1	1	1	0	0	0	0
1	1	0	0	1	0	1	1
1	0	1	0	1	1	0	1
1	0	0	0	1	1	1	1
0	1	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0