Set de piese

În matematică , având în vedere un set S , setul de părți ale lui S , scris ${\mathcal {P}}(S)$ ${\ displaystyle {\ mathcal {P}} (S)}$ ${\ mathcal {P}} (S)$ , este mulțimea tuturor subseturilor posibile ale lui S. Această colecție de seturi se mai numește puterea setului S sau booleanul lui S.

De exemplu, dacă S este setul $\{a,b,c\}$ ${\ displaystyle \ {a, b, c \}}$ $\ {a, b, c \}$ , apoi lista completă a subseturilor sale este:

$\varnothing$ ${\ displaystyle \ varnothing}$ $\ varnothing$ ( setul gol )
$\{a\}$ ${\ displaystyle \ {a \}}$ $\{la\}$
$\{b\}$ ${\ displaystyle \ {b \}}$ $\ {b \}$
$\{c\}$ ${\ displaystyle \ {c \}}$ $\ {c \}$
$\{a,b\}$ ${\ displaystyle \ {a, b \}}$ $\ {a, b \}$
$\{a,c\}$ ${\ displaystyle \ {a, c \}}$ $\ {a, c \}$
$\{b,c\}$ ${\ displaystyle \ {b, c \}}$ $\ {b, c \}$
$\{a,b,c\}$ ${\ displaystyle \ {a, b, c \}}$ $\ {a, b, c \}$ care coincide cu întregul în sine ${S}$ ${\ displaystyle {S}}$ ${S}$

și, prin urmare, ansamblul părților lui S este

{\mathcal {P}}(S)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},S\}

{\ displaystyle {\ mathcal {P}} (S) = \ {\ varnothing, \ {a \}, \ {b \}, \ {c \}, \ {a, b \}, \ {a, c \}, \ {b, c \}, S \}}

\ mathcal {P} (S) = \ {\ varnothing, \ {a \}, \ {b \}, \ {c \}, \ {a, b \}, \ {a, c \}, \ { b, c \}, S \}

Cardinalitatea setului de piese

Argumentul diagonal al lui Cantor arată că setul de părți ale unui set (infinit sau nu ^[1] ) are întotdeauna o cardinalitate strict mai mare decât cea a setului în sine.

Seturi finite

Dacă S este o mulțime finită cu $|S|=n$ ${\ displaystyle | S | = n}$ $| S | = n$ elemente, atunci setul de părți din S conține $|{\mathcal {P}}(S)|=2^{n}$ ${\ displaystyle | {\ mathcal {P}} (S) | = 2 ^ {n}}$ $| \ mathcal {P} (S) | = 2 ^ n$ subseturi.

Demonstrație

Dovadă că $|{\mathcal {P}}(S)|=2^{n}$ ${\ displaystyle | {\ mathcal {P}} (S) | = 2 ^ {n}}$ $| \ mathcal {P} (S) | = 2 ^ n$ , cu S mulțime finită și de ordine n : ( dovadă prin inducție pe n (forma I))

Dacă n = 0 în mod necesar $S\equiv \emptyset$ ${\ displaystyle S \ equiv \ emptyset}$ $S \ equiv \ emptyset$ . Prin urmare ${\mathcal {P}}(S)=\{\emptyset \}\Rightarrow |{\mathcal {P}}(S)|=2^{0}=1$ ${\ displaystyle {\ mathcal {P}} (S) = \ {\ emptyset \} \ Rightarrow | {\ mathcal {P}} (S) | = 2 ^ {0} = 1}$ $\ mathcal {P} (S) = \ {\ emptyset \} \ Rightarrow | \ mathcal {P} (S) | = 2 ^ 0 = 1$ . Vera.

Fie n> 0 și să presupunem că afirmația este adevărată pentru n-1 . Adică, dacă S este un set astfel încât $|S|=n-1$ ${\ displaystyle | S | = n-1}$ $| S | = n-1$ asa de $|{\mathcal {P}}(S)|=2^{n-1}$ ${\ displaystyle | {\ mathcal {P}} (S) | = 2 ^ {n-1}}$ $| \ mathcal {P} (S) | = 2 ^ {n-1}$ .

De acum se presupune că $|S|=n>0$ ${\ displaystyle | S | = n> 0}$ $| S | = n> 0$ neapărat $S\neq \emptyset$ ${\ displaystyle S \ neq \ emptyset}$ $S \ neq \ emptyset$ și trebuie să aibă cel puțin un element. Este $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ un element al setului. Orice subset de S îl poate conține sau nu:

Subseturile care nu conțin $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ , sunt subseturi de $S\backslash \{x_{0}\}$ ${\ displaystyle S \ backslash \ {x_ {0} \}}$ $S \ backslash \ {x_0 \}$ ; atâta timp cât $|S\backslash \{x_{0}\}|=n-1$ ${\ displaystyle | S \ backslash \ {x_ {0} \} | = n-1}$ $| S \ backslash \ {x_0 \} | = n-1$ , astfel de subseturi sunt, prin ipoteza inductivă $2^{n-1}$ ${\ displaystyle 2 ^ {n-1}}$ $2 ^ {n-1}$ .
Subseturile pe care le conțin $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ , sunt subseturi de tip $X\cup \{x_{0}\}$ ${\ displaystyle X \ cup \ {x_ {0} \}}$ $X \ cup \ {x_0 \}$ ; cu X subset de $S\backslash \{x_{0}\}$ ${\ displaystyle S \ backslash \ {x_ {0} \}}$ $S \ backslash \ {x_0 \}$ ; prin urmare, asemenea subseturi sunt, pentru ipoteza inductivă $2^{n-1}$ ${\ displaystyle 2 ^ {n-1}}$ $2 ^ {n-1}$ .

Prin urmare, subseturile lui S sunt în total $2^{n-1}+2^{n-1}=2\cdot 2^{n-1}=2^{n}$ ${\ displaystyle 2 ^ {n-1} + 2 ^ {n-1} = 2 \ cdot 2 ^ {n-1} = 2 ^ {n}}$ $2 ^ {n-1} + 2 ^ {n-1} = 2 \ cdot 2 ^ {n-1} = 2 ^ {n}$ .

O dovadă alternativă se poate baza pe bijecția dintre ${\mathcal {P}}(S)$ ${\ displaystyle {\ mathcal {P}} (S)}$ ${\ mathcal {P}} (S)$ este setul $2^{S}$ ${\ displaystyle 2 ^ {S}}$ $2 ^ S$ funcții $S\to \{0,1\}$ ${\ displaystyle S \ to \ {0,1 \}}$ $S \ to \ {0, 1 \}$ citat mai jos.

De sine $S.$ ${\ displaystyle S}$ $S.$ este un set finit cu $n$ ${\ displaystyle n}$ $n$ elemente, este imediat că ansamblul acestor funcții are $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ subseturi. Aceasta oferă o dovadă alternativă a rezultatului abia văzut.

Seturi infinite

De asemenea, putem lua în considerare setul de părți ale unui set infinit : de exemplu, setul de părți ale setului de numere naturale poate fi pus într -o corespondență unu-la-unu cu setul de numere reale .
Setul de părți are o importanță fundamentală în teoria seturilor infinite. De fapt, în aritmetica transfinită definită de Georg Cantor , operația de „exponențiere”, în sensul identificării cardinalității setului de părți ale unui set infinit dat, este singura modalitate de a avansa în succesiunea numerelor cardinale . În exemplul de mai sus, trecem de la cardinalitatea discretului , adică a mulțimilor pentru care este posibil să se stabilească o corespondență unu-la-unu cu naturali, cum ar fi numere întregi, raționale și fiecare dintre produsele lor carteziene, la cardinalitatea continuumului propriu realelor. Pentru dovada continuumului nenumărat, vezi Argumentul diagonal al lui Cantor .

Algebră

Mulțimea părților unei mulțimi S , cu operațiile de unire , intersecție și complement, formează exemplul prototip al algebrei booleene .

De fapt, se poate arăta că fiecare algebră booleană finită este izomorfă față de algebra booleană a setului de părți ale unei mulțimi finite. Pentru algebre booleene infinite acest lucru nu mai este adevărat, dar fiecare algebră booleană infinită este o subalgebră a unei algebre booleene împreună cu părțile.

Mulțimea părților unei mulțimi S formează un grup abelian atunci când considerăm operația de diferență simetrică (cu mulțimea goală ca unitate și fiecare mulțime fiind inversă) și un semigrup comutativ atunci când considerăm operația de intersecție. Prin urmare, se poate arăta (prin demonstrarea legilor distributive ) că ansamblul pieselor, considerate împreună cu ambele operații, formează un inel comutativ.

Bijecție cu ansamblul 2 ^S.

În teoria mulțimilor , $X^{Y}$ ${\ displaystyle X ^ {Y}}$ $X ^ {Y}$ este ansamblul tuturor funcțiilor din $Da$ ${\ displaystyle Y}$ $Da$ la $X$ ${\ displaystyle X}$ $X$ . Numărul natural 2 poate fi definit împreună: $2=\left\{{0,1}\right\}$ ${\ displaystyle 2 = \ left \ {{0,1} \ right \}}$ $2 = \ left \ {{0,1} \ right \}$ (vezi numerele naturale ), atunci $2^{S}$ ${\ displaystyle 2 ^ {S}}$ $2 ^ S$ este setul tuturor funcțiilor de la S la {0,1}.

Prin identificarea unei funcții în $2^{S}$ ${\ displaystyle 2 ^ {S}}$ $2 ^ S$ cu preimaginea corespunzătoare de 1, observăm că există o bijecție între $2^{S}$ ${\ displaystyle 2 ^ {S}}$ $2 ^ S$ Și ${\mathcal {P}}(S)$ ${\ displaystyle {\ mathcal {P}} (S)}$ ${\ mathcal {P}} (S)$ :

${\begin{matrix}\ f:{\mathcal {P}}(S)\longrightarrow 2^{S}\\A\longmapsto \chi _{A}\end{matrix}}$ ${\ displaystyle {\ begin {matrix} \ f: {\ mathcal {P}} (S) \ longrightarrow 2 ^ {S} \\ A \ longmapsto \ chi _ {A} \ end {matrix}}}$ $\ begin {matrix} \ f: \ mathcal {P} (S) \ longrightarrow 2 ^ S \\ A \ longmapsto \ chi_A \ end {matrix}$

unde fiecare funcție $\chi _{A}$ ${\ displaystyle \ chi _ {A}}$ $\ chi_A$ se numește funcția caracteristică a subsetului $LA$ ${\ displaystyle A}$ $LA$ în ${\mathcal {P}}(S)$ ${\ displaystyle {\ mathcal {P}} (S)}$ ${\ mathcal {P}} (S)$ și este definit astfel:

${\begin{matrix}\ f:S\longrightarrow 2=\{0,1\}\\x\longmapsto \left\{{\begin{matrix}1\quad {\mbox{se}}\ x\in A\\0\quad {\mbox{se}}\ x\notin A\end{matrix}}\right.\ \end{matrix}}$ ${\ displaystyle {\ begin {matrix} \ f: S \ longrightarrow 2 = \ {0,1 \} \\ x \ longmapsto \ left \ {{\ begin {matrix} 1 \ quad {\ mbox {se}} \ x \ in A \\ 0 \ quad {\ mbox {se}} \ x \ notin A \ end {matrix}} \ right. \ \ end {matrix}}}$ $\ begin {matrix} \ f: S \ longrightarrow 2 = \ {0, 1 \} \\ x \ longmapsto \ left \ {\ begin {matrix} 1 \ quad \ mbox {se} \ x \ în A \\ 0 \ quad \ mbox {se} \ x \ notin A \ end {matrix} \ right. \ \ end {matrix}$

Prin urmare $|{\mathcal {P}}(S)|=|2^{S}|$ ${\ displaystyle | {\ mathcal {P}} (S) | = | 2 ^ {S} |}$ $| \ mathcal {P} (S) | = | 2 ^ S |$ .

Axioma întregii puteri

În teoria axiomatică a mulțimilor (așa cum s-a dezvoltat pornind de la axiomele lui Zermelo-Fraenkel ), existența setului de părți ale oricărui set, chiar infinit, face obiectul unui postulat numit axioma setului de putere .

Notă

^ Axioma de alegere este necesară pentru dovada mulțimilor infinite.

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe ansamblul părților

linkuri externe

„Power Set” pe MathWorld , la mathworld.wolfram.com .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Axioma de alegere este necesară pentru dovada mulțimilor infinite.

[1]