D. A halmaz meghatározott dolgok összessége.

A halmaz megadásánál lényeges követelmény, hogy egyértelműen el lehessen dönteni, hogy egy objektum beletartozik-e a halmazba, vagy nem.

Jelölések:

a  A: a eleme az A halmaznak,

a  A: a nem eleme az A halmaznak,

A  B: A részhalmaza B-nek, vagyis A minden eleme eleme a B halmaznak,

A  B: A tartalmazza B-t, B részhalmaza A-nak,

A = B: az A és a B halmaz egyenlő, vagyis elemeik közösek.

A  és a  jelöléseket nem használjuk. Nyilván A = B akkor és csak akkor, ha A  B és
A  B.

A halmaz megadása történhet A = {a, b, c} alakban az elemek felsorolásával, vagy A =
= {x: x-re vonatkozó állítás} alakban, ahol az A elemei azon x-ek, melyre az állítás teljesül.

Műveletek:

1. Egyesítés művelete: A  B = {x: x  A vagy x  B}.

Műveleti szabályok:

1. A  B = B  A (kommutativitás)
2. A  (B  C) = (A  B)  C (asszociativitás)
3. A  B = B akkor és csak akkor teljesül, ha A  B (elnyelési tulajdonság).

1. Metszet művelete: A  B = {x: x  A és x  B}.

Műveleti szabályok:

1. A  B = B  A (kommutativitás)
2. A  (B  C) = (A  B)  C (asszociativitás)
3. A  B = B akkor és csak akkor teljesül, ha A  B (elnyelési tulajdonság).
4. A  (B  C) = (A  B)  (A  C) (disztributív tulajdonság)
5. A  (B  C) = (A  B)  (A  C) (disztributív tulajdonság).

1. Kivonás művelete: A – B = {x: x  A és x  B}.

D. Üres halmaznak nevezzük azt a halmazt, amelynek egyetlen eleme sincs, jelölése Ø.

D. A és B halmazok diszjunktak, ha nincs közös elemük, azaz A  B = Ø. Több halmaz diszjunkt, ha bármely kettőnek nincs közös eleme.
Az üres halmaz számossága 0, a véges halmaz számossága az elemeinek a száma. A problémát csak a végtelen halmazok okozzák.

D. Két halmaz, A és B egyenlő számosságú, ha van olyan f: A  B függvény, amely bijektív.

A definíció alapján az N és a pozitív páros számok hamazának a számossága megegyezik, noha az utóbbi részhalmaza az előbbinek. A bijektív f függvény f(x) = 2x.

D. Az A halmaz megszámlálható, ha A üres, ha A véges halmaz, vagy ha A N-nel egyenlő számosságú. Ha A végtelen halmaz, de megszámlálható, akkor a számossága megszámlálhatóan végtelen.

Ha A N-nel egyenlő számosságú, akkor létezik f: N  A bijektív függvény, ami azt jelenti, hogy A elemeit sorozatba rendeztük. A megszámlálhatóan végtelen számosság tehát ekvivalens a sorozatba rendezhetőséggel.

T. Ha az A₁, A₂, … halmazok megszámlálhatóak, akkor egyesítésük is megszámlálható.

B. Rendezzük sorozatba az egyes A_k halmazok elemeit:

A₁: a₁₁, a₁₂, a₁₃, a₁₄, …

A₂: a₂₁, a₂₂, a₂₃, a₂₄, …

A₃: a₃₁, a₃₂, a₃₃, a₃₄, …

…

Ún. átlós kiválasztással készítsük el a következő sorozatba rendezést: a₁₁, a₁₂, a₂₁, a₁₃, a₂₂, a₃₁, a₁₄, a₂₃, a₃₂, a₄₁, a₁₅, … . Ha az A₁, A₂, … halmazok nem voltak diszjuktak, akkor a sorozatban ismétlődések vannak, de ezeket kihagyva a sorozatba rendezés megmarad.

K. A racionális számok halmaza megszámlálható.

B. Legyen az A_k halmaz a k nevezőjű törtek halmaza (akkor is, ha a tört egyszerűsíthető). A_k nyilván megszámlálható, és az A_k-k egyesítése Q.

T. Az [a, b] halmaz, ha a < b, akkor nem megszámlálható.

B. Tegyük fel, hogy megszámlálható halmaz, akkor létezik olyan f: N  [a, b] függvény, amelyik bijektív. Osszuk fel [a, b]-t két intervallumra úgy, hogy az osztópont f(1)-től különböző legyen. Ekkor valamelyik zárt részintervallum nem tartalmazza f(1)-et jelöljük ezt a részintervallumot [a₁, b₁]-gyel. Hasonlóan [a₁, b₁] felosztásából kaphatunk egy [a₂, b₂] 
 [a₁, b₁] részintervallumot, mely nem tartalmazza az f(2)-t. Az eljárást folytatjuk, a k-adik lépésben kapott új [a_k, b_k] intervallum is része lesz az előzőnek és nem tartalmazza f(k)-t. A Cantor axióma szerint az intervallumoknak van közös pontjuk, legyen ez x. Az f bijektív volta miatt valamilyen n-re f(n) = x, de mivel [a_n, b_n] nem tartalmazza f(n)-et, x-et sem tartalmazhatja, ami ellentmondás.

A nem megszámlálható számosságok között további megkülönböztetéseket lehet tenni, de erre nem térünk ki.