Aro de ĉiuj subaroj

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En matematiko, aro de ĉiuj subarojpotencaro de donita aro S, skribata kiel \mathcal{P}(S) aŭ 2S, estas la aro de ĉiuj subaroj de S. En aksioma aroteorio (kiel ellaborite ekzemple en la ZFC aksiomoj), la ekzisto de la aro de ĉiuj subaroj de ĉiu aro estas postulata per la aksiomo de aro de ĉiuj subaroj.

Ĉiu subaro F de \mathcal{P}(S) estas familio de aroj super S.

Ekzemple, se S estas la aro {A, B, C} tiam la plena listo de subaroj de S estas:

  • {} (la malplena aro)
  • {A}
  • {B}
  • {C}
  • {A, B}
  • {A, C}
  • {B, C}
  • {A, B, C}

kaj de ĉi tie la aro de ĉiuj subaroj de S estas

\mathcal{P}(S) = {{}, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}}

Se S estas finia aro kun |S|=n eroj, tiam la aro de ĉiuj subaroj de S enhavas |\mathcal{P}(S)| = 2^n erojn. Oni povas, kaj en komputiloj reale faras, prezenti la erojn de \mathcal{P}(S) kiel n-bitajn nombrojn; la n-a bito koncernas la ekziston aŭ foreston de la n-a ero de S. Estas 2n tiaj nombroj.)

Subaro de {A, B, C} Respektiva nombro
{} 0002 = 0
{A} 1002 = 4
{B} 0102 = 2
{C} 0012 = 1
{A, B} 1102 = 6
{A, C} 1012 = 5
{B, C} 0112 = 3
{A, B, C} 1112 = 7

Binoma koeficiento {n \choose k} estas kvanto de n-eraj subaroj en k-era aro.

Tiel en la ekzemplo pli supre, {0 \choose 3} = 1, {1 \choose 3} = 3, {2 \choose 3} = 3, {3 \choose 3} = 1.

Oni povas ankaŭ konsideri la aron de ĉiuj subaroj de malfiniaj aroj. Diagonala argumento de Cantor montras, ke la aro de ĉiuj subaroj de aro (malfinia ĉu ne) ĉiam havas severe pli altan kardinalon ol la aro mem, neformale la aro de ĉiuj subaroj devas esti 'pli granda' ol la originala aro. La aro de ĉiuj subaroj de aro de naturaj nombroj ekzemple povas esti en reciproke unuvalora surĵeto (bijekcia rilato) kun aro de reelaj nombroj. Prezentu subaron de la naturaj nombroj per duuma nombro inter 0 kaj 1 inkluziva. Ekzemple, la aro {1, 3} havas prezenton 0,10100..., kun "1" estas ciferoj kies indeksoj estas en la subaro kaj "0" aliloke. Oni povas tiam sendi ĉi tiun aron (kiu estas [0,1] en la reelaj nombroj) al la tuta reela linio ekzemple per per surĵeto x al \tan\left(\pi(x-0.5)\right).

La aro de ĉiuj subaroj de aro S, kaj ankaŭ la operacioj de unio, komunaĵo kaj komplemento formas la ekzemplon de bulea algebro. Fakte, ĉiu finia bulea algebro estas izomorfia al la bulea algebro de la aro de ĉiuj subaroj de finia aro. Por malfiniaj buleaj algebroj ĉi tiu estas jam ne vera, sed ĉiu malfinia bulea algebro estas subalgebro de aro de ĉiu subara bulea algebro.

La aro de ĉiuj subaroj de aro S formas komutan grupon kiam konsiderita kun la operacio de simetria diferenco (kun la malplena aro kiel ĝia unuo kaj ĉiu aro estante ĝia posedi inverso) kaj komuta duongrupo kiam konsiderita kun la operacio de komunaĵo. Ĝi povas de ĉi tie esti montrita (per pruvo de la distribuecaj leĝoj), ke la aro de ĉiuj subaroj konsideritaj kaj ankaŭ ambaŭ de ĉi tiuj operacioj formas komutan ringon.

La skribmaniero 2S[redakti | redakti fonton]

En aroteorio, XY estas la aro de ĉiuj funkcioj de Y al X. Pro tio ke 2 povas esti difinita kiel {0, 1} (vidu en natura nombro), 2S estas la aro de ĉiuj funkcioj de S al {0, 1}. Per identiganta funkcio en 2S kun la respektiva antaŭbildo de 1, oni vidas ke estas reciproke unuvalora surĵeto inter 2S kaj \mathcal{P}(S), kie ĉiu funkcio estas la nadla funkcio (karakteriza funkcio) de la subaro en \mathcal{P}(S) kun kiu ĝi estas identigita. De ĉi tie 2S kaj \mathcal{P}(S) povas esti konsiderata identaj en senco de arteorio.

Eksteraj ligiloj[redakti | redakti fonton]