Teoria de conjunts

De Viquip??dia

La teoria de conjunts ??s la branca de les matem??tiques que estudia els conjunts. El primer estudi formal sobre el tema va ser realitzat pel matem??tic alemany Georg Cantor en el segle XIX.

Taula de continguts

1 Definici?? de conjunt
- 1.1 La paradoxa de Russell
2 Notaci??
3 Subconjunts i superconjunts
4 Uni?? i intersecci??
5 Difer??ncia i complementari
6 ??lgebra de conjunts

[edita] Definici?? de conjunt

Intu??tivament, un conjunt ??s una agrupaci??, classe o col??lecci?? d'objectes, als quals hom anomena elements del conjunt. Aix??, quan un element a pertany al conjunt S, hom diu que el conjunt S cont?? l'element a, utilitzant la notaci?? a ??? S.

El concepte de conjunt ??s fonamental en matem??tiques perqu?? es troba, impl??citament o expl??cita, en totes les branques de les matem??tiques pures i aplicades. En la seva forma expl??cita, els principis i la terminologia dels conjunts s'utilitzen per a construir proposicions matem??tiques m??s clares i precises i per a explicar conceptes abstractes com ara el concepte d'infinit.

Un conjunt S est?? definit si, donat un objecte qualsevol a, se sap amb seguretat si pertany o no al conjunt.

[edita] La paradoxa de Russell

Aquesta definici?? ??s problem??tica des del punt de vista formal ja que, en definir un conjunt per una propietat, s'arriba a la paradoxa de Russell definint A = {x | x ??? A} (es llegeix A est?? format per tots els elements x tals que x no pertany a A). Veiem que, si x pertany a A, s'ha de complir que x no pertany a A: una propietat i la seva negaci?? s'han de complir al mateix temps. Aix?? va portar a considerar desenvolupaments axiom??tics com els de Zermelo-Frankel i Von Neumann que eviten aquesta paradoxa o contradicci?? de la teoria.

Suposem que hi ha dos tipus de conjunts: els normals, que no es contenen a si mateixos com a element; i els anormals, que es contenen a si mateixos com a element. Per a existir, un conjunt A hauria de ser de nom??s d'un dels dos tipus. Pensem ara en el conjunt V els elements del qual s??n tots els conjunts normals: el conjunt V ??s normal o anormal? Si V f??ra normal es contindria a si mateix com a element, ja que V est?? format per tots els conjunts normals, per??, en contenir-se a si mateix com a element, seria anormal.

La contradicci?? ??s deguda al fet de suposar que la proposici?? "X ??s un conjunt i no ??s element de si mateix" determina un conjunt. Hom pensa llavors en dos tipus de col??leccions:

Classes: Aquelles col??leccions d'objectes especificades per una proposici??.

Conjunts: Aquelles classes que siguen elements d'una altra classe.

Hi ha una distinci?? entre conjunts i classes, on les classes que no siguin conjunts no poden ser elements d'altres classes. Apareix la teoria axiom??tica de conjunts cercant dos fins: garantir l'exist??ncia d'un conjunt i assegurar les construccions amb conjunts que donen com a resultat altres conjunts.

A continuaci?? s'exposa el desenvolupament intu??tiu de la teoria perqu?? ??s el m??s natural per a la majoria de les persones.

[edita] Notaci??

Un conjunt es representa mitjan??ant claus que contenen els seus elements, ja siga de forma expl??cita, escrivint tots i cada un dels elements, o donant una f??rmula, regla o proposici?? que els descriga. Per exemple,

S₁ = {2, 4}
S₂ = {2, 4, 6, ..., 2n, ...} = {tots els sencers parells}
S₃ = {x | $x 2 ??? 6 x + 11 = 3$ }.
S₄ = {tots els barons vius cridats Joan}

La definici?? de S₃ es llig "el conjunt de totes les x tals que $x 2 ??? 6 x + 11 = 3$ ".

[edita] Subconjunts i superconjunts

Si tot element d'un conjunt R pertany tamb?? al conjunt S, es diu que R ??s un subconjunt de S i que S ??s un superconjunt de R. S'utilitza la notaci?? R ??? S. Tot conjunt ??s un subconjunt i un superconjunt de si mateix.

Si R ??? S i almenys un element de S no pertany a R, es diu que R ??s un subconjunt propi de S i que S ??s un superconjunt propi de R. S'utilitza la notaci?? R ??? S.

Si R ??? S i S ??? R, ??s a dir, tot element d'un conjunt pertany tamb?? a l'altre, llavors R i S s??n dos conjunts iguals, la qual cosa s'escriu R = S. En els exemples de l'apartat anterior, S₁ = S₃.

[edita] Uni?? i intersecci??

Siguen A i B dos conjunts.

Els elements que pertanyen a A, a B o a ambd??s formen un altre conjunt S, anomenat uni?? de A i B, escrit A ??? B.

Els elements comuns a A i B formen un conjunt denominat intersecci?? de A i B, escrit A ??? B.

Si A i B no tenen cap element com?? es denominen conjunts disjunts i es representa la seva intersecci?? com un altre conjunt, denominat conjunt buit o nul, el qual es representa amb el s??mbol ??.

Exemples: si tenim els conjunts

A = {2, 4, 6}
B = {4, 6, 8, 10}
C = {10, 14, 16, 26}

Llavors:

A ??? B = {2, 4, 6, 8, 10}
A ??? C = {2, 4, 6, 10, 14, 16, 26}
A ??? B = {4, 6}
A ??? C = ??

[edita] Difer??ncia i complementari

El conjunt d'elements que pertanyen a A per?? no pertanyen a B es denomina conjunt difer??ncia entre A i B, escrit A ??? B (i a vegades A \ B).

Seguint amb l'exemple anterior, A ??? B = {2}, B ??? A = {8, 10}.

Si A ??s un subconjunt del conjunt B, el conjunt dels elements que pertanyen a B per?? no a A, ??s a dir, B ??? A, es denomina conjunt complementari de A (respecte a B), la qual cosa s'escriu B ??? A = A^C (que tamb?? pot apar??ixer com ?? o ~A).

[edita] ??lgebra de conjunts

Siguen A, B i C conjunts qualssevol, i U un conjunt tal que A ??? U, B ??? U i C ??? U. Aleshores:

$A \cap A = A\,$
$A \cup A = A$
$A \cap \empty = \empty$
$A \cup \empty = A$ Element neutre de la uni??
$A \cap U = A$ Element neutre de la intersecci??
$A \cup U = U$
$A \cap B = B \cap A$ Propietat commutativa de la intersecci??
$A \cup B = B \cup A$ Propietat commutativa de la uni??
$\left(A^\complement\right)^\complement = A$
$(A \cap B) \cap C = A \cap (B \cap C)$ Propietat associativa de la intersecci??
$(A \cup B) \cup C = A \cup (B \cup C)$ Propietat associativa de la uni??
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ Propietat distributiva de la intersecci??
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ Propietat distributiva de la uni??
$A \subseteq B \iff A \cap B = A$
$A \subseteq B \iff A \cup B = B$
$A \subseteq B \iff B^\complement \subseteq A^\complement$
$A \cap B \subseteq A \subseteq A \cup B$
$C \setminus (A \cap B) = (C \setminus A) \cup (C \setminus B)$
$C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B)$
$C \setminus (B \setminus A) = (A \cap C) \cup (C \setminus B)$
$(B \setminus A) \cap C = (B \cap C) \setminus A = B \cap (C \setminus A)$
$(B \setminus A) \cup C = (B \cup C) \setminus (A \setminus C)$
$A \subseteq B \iff A \setminus B = \empty$
$A \cap B = \empty \iff B \setminus A = B$
$A \setminus A = \empty$
$\empty \setminus A = \empty$
$A \setminus \empty = A$
$A \setminus B = A \cap B^\complement$
$(B \setminus A)^\complement = A \cup B^\complement$
$U \setminus A = A^\complement$
$A \setminus U = \empty$

[edita] Distributivitat entre uni?? i intersecci??

Siguen tres conjunts A, B i C. Es compleix que:

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Aquestes s??n les propietats de l'??lgebra de conjunts, la qual ??s un cas particular del sistema algebraic conegut com a ??lgebra de Boole.

[edita] Producte cartesi?? de conjunts

Si A i B s??n dos conjunts, el conjunt de tots els possibles parells ordenats d'elements de la forma (a, b), on a ??? A i b ??? B, es denomina producte cartesi?? de A i B, escrit normalment com A ?? B.

Exemple: si A = {1, 2} i B = {x, y, z}, llavors

A ?? B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}
B ?? A = {(x, 1), (y, 1), (z, 1), (x, 2), (y, 2), (z, 2)}

En aquest cas, A ?? B ??? B ?? A, perqu?? en ser parells ordenats, el parell (1, x) ??s diferent del parell (x, 1).

[edita] Correspond??ncia o relacions entre conjunts

Donats dos conjunts A i B, que poden ser iguals o distints, podem trobar diverses formes de relacionar els elements de A amb els elements de B.

Per exemple, els elements del conjunt A = {1, 2, 3} es poden relacionar o fer correspondre mitjan??ant una correspond??ncia f amb els elements del conjunt B = {x, y, z} de manera que a tot element de A li corresponga un, cap o diversos elements de B. Aix?? tamb?? es pot expressar aix??:

f(1) = {x, z}, f(2) = ?? , f(3) = {z}

Tamb?? es pot dir que f = {(1, x), (1, z), (3, z)}.

Per tant, una relaci?? o correspond??ncia entre dos conjunts A i B ??s un subconjunt del producte cartesi?? A ?? B. En general, una relaci?? o correspond??ncia entre un conjunt A i un altre B ??s qualsevol subconjunt de A ?? B. Noteu que aix?? inclou el cas del conjunt buit.

Quan tot element de A est?? relacionat amb algun de B es diu que aquest subconjunt de A ?? B ??s una relaci?? o correspond??ncia de A en B.

Quan una correspond??ncia ??s tal que a cada element del primer conjunt li correspon un i nom??s un del segon conjunt, llavors s'anomena aplicaci??, funci?? o mapatge.

Categories: Teoria de conjunts | Desenvolupament de programari | Matem??tica discreta