Részhalmaz

A halmazelméletben egy halmaz valamely elemeinek a halmazát, összességét az adott halmaz részhalmazának nevezzük, beleértve azt az esetet is, amikor az adott halmaz összes elemét kiválasztjuk és azt is, amikor a halmazból egyetlen elemet sem választottunk ki. Az így értelmezett részhalmaz fogalma a halmazelmélet egyik alapvető fogalma.

A részhalmaza B-nek, azaz B tartalmazza A-t.

Definíció

Legyenek ${\displaystyle A}$ és ${\displaystyle B}$ tetszőleges halmazok. Azt mondjuk, hogy ${\displaystyle A}$ részhalmaza a ${\displaystyle B}$ halmaznak, és így jelöljük ${\displaystyle A\subseteq B}$,^[1] ha az a ${\displaystyle A}$ halmaz összes elemét tartalmazza a ${\displaystyle B}$ halmaz, azaz ${\displaystyle \forall a\in A:a\in B}$.
Ha ${\displaystyle A\subseteq B}$, de ${\displaystyle A\neq B}$, azaz ${\displaystyle B}$-nek van legalább egy olyan eleme, amely nem eleme ${\displaystyle A}$-nak, akkor azt mondjuk, hogy ${\displaystyle A}$ valódi részhalmaza ${\displaystyle B}$-nek, és ezt így jelöljük: ${\displaystyle A\subset B}$.^[1]

Jelölések

A részhalmazok mai jelölését először Ernst Schröder használta 1890-ben „Algebra der Logik“ című művében.^[2]

A patkó jelölést fordított irányban is szokták használni. A patkó a tartalmazó halmaz irányába nyitott. Mivel a halmazelméleti tartalmazás kapcsolódik a logikai implikációhoz, azért a patkót az implikáció jelölésére is használják. Néhány szerző a ${\displaystyle \subseteq }$ és ${\displaystyle \supseteq }$ jelek helyett a ${\displaystyle \subset }$ és ${\displaystyle \supset }$ jeleket használja, és nem vezet be külön jelölést a valódi részhalmazra;^[3][4] sőt, nem is használja a valódi részhalmaz fogalmat.

A legtöbb szerző rendre a ${\displaystyle \subset }$ és ${\displaystyle \supset }$ jeleket használja a valódi részhalmaz és a valódi tartalmazó halmaz számára ${\displaystyle \subsetneq }$ és ${\displaystyle \supsetneq }$ helyett.^[2] Ez hasonló a ${\displaystyle \leq }$ és ${\displaystyle <}$ jelekhez. Mivel ezeket akkor használják, ha ez a különbségtétel fontos, az ${\displaystyle \subsetneq }$ és ${\displaystyle \supsetneq }$ jelek ritkán kerülnek elő.

A ${\displaystyle \subsetneq }$ jel változatai ${\displaystyle \varsubsetneq }$, ${\displaystyle \subsetneqq }$ és ${\displaystyle \varsubsetneqq }$. Hogyha ${\displaystyle A}$ nem részhalmaza ${\displaystyle B}$-nek, akkor használható ${\displaystyle A\nsubseteq B:\Longleftrightarrow \lnot \left(A\subseteq B\right)}$ is. Megfelelői ${\displaystyle \varsupsetneq }$ és ${\displaystyle \supsetneq }$, ${\displaystyle \supsetneqq }$ és ${\displaystyle \varsupsetneqq }$, illetve ${\displaystyle \supsetneq }$, és ${\displaystyle A\nsupseteq B}$ a nem tartalmazó halmazra.

A megfelelő Unicode szimbólumok: ⊂, ⊃, ⊆, ⊇, ⊄, ⊅, ⊈, ⊉, ⊊, ⊋.

Tulajdonságok

• Minden halmaz önmagának részhalmaza (de nem valódi részhalmaza), azaz tetszőleges ${\displaystyle A}$ halmazra teljesül, hogy ${\displaystyle A\subseteq A}$.
• Az üres halmaz minden halmaznak részhalmaza (de nem valódi részhalmaza), azaz tetszőleges ${\displaystyle A}$ halmazra teljesül, hogy ${\displaystyle \emptyset \subseteq A}$.
• Ha ${\displaystyle A\subseteq B}$ és ${\displaystyle B\subseteq A}$, akkor ${\displaystyle A=B}$.
• Ha ${\displaystyle A\subseteq B}$ és ${\displaystyle B\subseteq C}$, akkor ${\displaystyle A\subseteq C}$.
• ${\displaystyle A\subseteq B}$ pontosan akkor áll fenn, ha ${\displaystyle A\cup B=B}$.
• ${\displaystyle A\subseteq B}$ pontosan akkor áll fenn, ha ${\displaystyle A=A\cap B}$.
• ${\displaystyle A\subseteq B}$ pontosan akkor áll fenn, ha ${\displaystyle A\backslash B=\emptyset }$.
• A karakterisztikus függvényre:

${\displaystyle A\subseteq B\Leftrightarrow \chi _{A}\leq \chi _{B}}$

• Két halmaz megegyezik, ha mindkettő része a másiknak:

${\displaystyle A=B\Leftrightarrow A\subseteq B\land B\subseteq A}$

Ezt gyakran használják két halmaz egyenlőségének belátására.

• A komplementerképzés megfordítja a tartalmazást:

${\displaystyle A\subseteq B\Rightarrow A^{\rm {c}}\supseteq B^{\rm {c}}}$

Példák

A {dob, kártya} része a {gitár, kártya, digitális kamera, dob} halmaznak

A szabályos sokszögek a sokszögek részhalmaza

• {1, 2} valódi részhalmaza az {1, 2, 3} halmaznak.
• {1, 2, 3} nem valódi részhalmaza az {1, 2, 3} halmaznak.
• {1, 2, 3, 4} nem részhalmaza az {1, 2, 3} halmaznak.
• {1, 2, 3} nem részhalmaza az {2, 3, 4} halmaznak.
• {} nem valódi részhalmaza az {1, 2} halmaznak.
• {1, 2, 3} valódi tartalmazó halmaza az {1, 2} halmaznak.
• {1, 2} nem valódi tartalmazó halmaza az {1, 2} halmaznak.
• {1} nem tartalmazó halmaza az {1, 2} halmaznak.
• A prímszámok halmaza valódi részhalmaza a természetes számok halmazának (a természetes számok számelmélete szerint).
• A racionális számok halmaza valódi részhalmaza a valós számok halmazának.

A számhalmazok kapcsolata

• ${\displaystyle \mathbb {N} }$ = természetes számok halmaza ${\displaystyle \{0,1,2,\dots \}}$
• ${\displaystyle \mathbb {Z} }$ = egész számok halmaza ${\displaystyle \{\dots ,-3,-2,-1,0,1,2,\dots \}}$
• ${\displaystyle \mathbb {Q} }$ = racionális számok halmaza (${\displaystyle {\frac {z_{1}}{z_{2}}}}$ alakú számok, ahol ${\displaystyle z_{1},z_{2}\in \mathbb {Z} \land z_{2}\neq 0}$)
• ${\displaystyle \mathbb {Q} '}$ = irracionális számok halmaza (olyan számok, amelyek nem írhatók fel ${\displaystyle {\frac {z_{1}}{z_{2}}}}$ alakban)
• ${\displaystyle \mathbb {R} }$ = valós számok halmaza (a racionális és irracionális számok összessége (${\displaystyle \mathbb {Q} \cup \mathbb {Q} '}$))

Ekkor: ${\displaystyle \mathbb {N} \subset \mathbb {Z} \subset \mathbb {Q} \subset \mathbb {R} }$, továbbá ${\displaystyle \mathbb {Q} '\subset \mathbb {R} }$.

Tartalmazási reláció

A tartalmazási reláció reflexív, antiszimmetrikus és tranzitív:

${\displaystyle A\subseteq A}$

${\displaystyle A\subseteq B\subseteq A\Rightarrow A=B}$

${\displaystyle A\subseteq B\subseteq C\Rightarrow A\subseteq C}$,

ahol is ${\displaystyle A\subseteq B\subseteq C}$ azt jelenti, hogy ${\displaystyle A\subseteq B}$ és ${\displaystyle B\subseteq C}$. Ezért a tartalmazási reláció részben rendezés.

Ha ${\displaystyle H\,}$ halmazok halmaza (halmazrendszer), akkor ${\displaystyle (H,\subseteq )}$ részben rendezett.

Speciális halmazrendszerek

Ha A ⊆ B és B ⊆ C, akkor A ⊆ C

Ha ${\displaystyle H\,}$ halmazrendszer, és ${\displaystyle H\,}$ bármely elemére teljesül, hogy tartalmazza a rendszer egy elemét, vagy a rendszer egy eleme tartalmazza, akkor ${\displaystyle H\,}$ tartalmazási lánc. Ilyen például a balról nem korlátos nyílt valós intervallumok halmaza, ${\displaystyle \{{]{-\infty ,x}[}\mid x\in \mathbb {R} \}}$.

Megkülönböztetünk felszálló és leszálló tartalmazási láncokat:

${\displaystyle A_{1}\subseteq A_{2}\subseteq A_{3}\subseteq \ ...}$ felszálló tartalmazási lánc

${\displaystyle A_{1}\supseteq A_{2}\supseteq A_{3}\supseteq \ ...}$ leszálló tartalmazási lánc

Egy halmazrendszer lamináris, ha bármely két elemére teljesül a kettő közül valamelyik:

• Az egyik tartalmazza a másikat
• A két halmaz diszjunkt.

Ezzel szemben a Sperner-rendszerekben nincs két olyan egymástól különböző halmaz, amelyek egyike tartalmazza a másikat. Például egy alaphalmaz összes adott elemszámú részhalmaza Sprener-rendszert alkot.

Részhalmazok mérete és száma

• Véges halmazok összes részhalmaza véges, és méretükre teljesül, hogy:

  ${\displaystyle A\subseteq B\Rightarrow \left|A\right|\leq \left|B\right|}$

  ${\displaystyle A\subsetneq B\Rightarrow \left|A\right|<\left|B\right|}$

• Végtelen halmazt tartalmazó halmaz is végtelen. Végtelen halmaz esetén a méretre teljesül, hogy:

  ${\displaystyle A\subseteq B\Rightarrow \left|A\right|\leq \left|B\right|}$

• Végtelen halmazok esetén lehet a részhalmaz mérete ugyanakkora, mint a tartalmazó halmazé. Például a természetes számok és az egész számok halmaza is megszámlálható végtelen.
• Cantor tétele szerint, ha ${\displaystyle A}$ halmaz, akkor hatványhalmazának számossága nagyobb, mint az ${\displaystyle A}$ halmaz számossága:

${\displaystyle |A|<{\bigl |}{\mathcal {P}}(A){\bigr |}}$

• Egy véges, ${\displaystyle n}$ elemű halmaz hatványhalmazának ${\displaystyle 2^{n}}$ eleme van.
• Egy véges, ${\displaystyle n}$ elemű halmaz ${\displaystyle k}$ elemszámú részhalmazainak számát az ${\displaystyle {\tbinom {n}{k}}}$ binomiális együttható adja meg.

Lásd még

• Hatványhalmaz

További információk

• Alice és Bob – 19. rész: Alice és Bob ideáljai