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 al .
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.
La definició de l'accepció matemàtica de la paraula catalana conjunt que dona Pompeu Fabra en el diccionari, coincideix gairebé exactament amb la traducció de l'alemany al català de la definició que va donar el principal creador de la teoria de conjunts, Georg Cantor, al començament de la seva obra Beiträge zur Begründung der transfiniten Mengenlehre:Quoted in Dauben, p. 170.
S'entén per "conjunt" qualsevol col·lecció M, considerada com un tot, d'objectes, de la nostra percepció [Anschauung] o del nostre pensament, diferents i ben definits m (dels quals se'n dirà els "elements" de M).
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.
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 ∉ x} (es llegeix A està format per tots els elements x tals que x no pertany a x). Veiem que, si A pertany a A, s'ha de complir que A no pertany a A, i que si A no pertany a A, s'ha de complir que A 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-Fraenkel 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 fora 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, en què 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.
El desenvolupament històric d'una teoria rigorosa de conjunts miniatura|Georg Cantor Cantor va ser el principal creador de la teoria dels conjunts; ho va fer d'una forma que avui es qualifica de teoria ingènua de conjunts. Però, al costat de consideracions elementals, la seva teoria implicava nivells d'abstracció elevats. La verdadera novetat de la teoria de Cantor és que permet parlar de l'infinit. Per exemple, una idea important de Cantor ha estat definir l'equipotència. Dos conjunts A i B són equipotents o, cosa que és el mateix, tenen la mateixa cardinalitat (quan són finits vol dir que tenen el mateix nombre d'elements), si existeix una manera d'associar a cada element de A un i només un element de B i viceversa. Així, es pot demostrar que el conjunt dels naturals té la mateixa cardinalitat que el conjunt dels nombres racionals, encara que sigui un subconjunt propi de . Aquests dos conjunts s'anomenen infinits numerables. D'altra banda, el conjunt dels nombres reals no té la mateixa cardinalitat que o , sinó una cardinalitat superior: es diu que és no numerable. Cantor va donar dues demostracions que no és numerable; la segona d'aquestes demostracions, que fa servir un argument conegut amb el nom dargument de la diagonal de Cantor, ha estat extraordinàriament influent i ha tingut nombroses i diverses aplicacions en lògica i en matemàtiques.
Cantor va aprofundir en la teoria i va construir jerarquies infinites de conjunts infinits, els nombres ordinals i els nombres cardinals. Aquestes construccions van ser discutides en la seva època; l'oposició principal la mantenia Leopold Kronecker; però avui en dia s'accepten per la majoria dels matemàtics.
El desenvolupament de la teoria de conjunts per Cantor era encara «ingènua» en el sentit que no feia servir encara una axiomàtica precisa, i perquè per a ell no hi havia més que una sola teoria dels conjunts, un sol univers de conjunts esperat, mentre que els teòrics dels conjunts d'avui fan jocs malabars amb universos diferents.
Després, de vegades, s'ha simplificat bastant injustament Cantor, resumint la seva teoria en un ús tàcit de l'axioma d'extensionalitat, i una versió massa forta de l'esquema d'axiomes de comprensió, que en substància permetria associar a tota propietat el conjunt objectes que verifiquen aquesta propietat. Tal teoria, que no s'atribuiria a Cantor, és contradictòria. Porta a dues famílies de paradoxes. Unes, com la paradoxa de Berry o la paradoxa de Richard, es relacionen amb el fet que el llenguatge no està ben definit, les altres, com la paradoxa de Russell a un ús massa ampli de la comprensió: quan s'intenta construir el conjunt S = {A|A no pertany a A} de tots els conjunts que no pertanyen a si mateixos, es cau en una contradicció. L'actual esquema d'axiomes de comprensió, proposat per Zermelo, es restringeix per tal d'evitar aquesta paradoxa.
Cantor coneixia, abans del descobriment de la paradoxa de Russell, paradoxes més complexes, però d'igual naturalesa, com la paradoxa de Burali-Forti o la paradoxa del cardinal més gran.il ne considère d'ailleurs pas ceux-ci comme des paradoxes, voir le §2.2 de, Akihiro Kanamori (2008), Set Theory from Cantor to Cohen, to appear in: Andrew Irvine and John H. Woods (editors), The Handbook of the Philosophy of Science, volume 4, Mathematics, Cambridge University Press 2008. Molts teòrics dels conjunts s'inclinen a dir que l'axiomatització més adequada a la teoria desenvolupada per Cantor és la teoria ZFC amb axioma de fundació (vegeu més avall), o la teoria de les classes de von Neumann, Gödel i Bernays, que és, en un cert sentit (que es pot determinar amb precisió), equivalent.
Al tombant del segle, Cantor està cada vegada més impedit per la seva malaltia nerviosa, però les seves solucions a les paradoxes circulen per la seva correspondència i són conegudes, al final del , per Richard Dedekind i, a Göttingen, per David Hilbert i Ernst Zermelo. Tanmateix, per a molts matemàtics de l'època, les paradoxes plantegen un dubte sobre la validesa de la teoria dels conjunts; les solucions proposades per Cantor són massa informals per a convèncer els que les coneixen. Alguns s'orienten cap al mètode axiomàtic, il·lustrat a la mateixa època per Hilbert per als fonaments de la geometria (1899).
Així, el 1908, Ernst Zermelo construeix un sistema d'axiomes per a la teoria dels conjunts. Fora de l'axioma d'extensionalitat, aquests axiomes es poden veure com una restricció de la versió contradictòria de l'esquema d'axiomes de comprensió als casos particulars útils, que no permeten deduir les paradoxes. En aquest sistema, s'inclou igualment l'axioma d'elecció (que no té res a veure amb la comprensió), un axioma molt polèmic en aquell temps, amb el qual s'ha demostrat (el 1904) el teorema de Zermelo, i que igualment ha estat fet servir implícitament per Cantor. El sistema de Zermelo es va completar en els anys 1920 per Abraham Adolf Fraenkel i Thoralf Skolem, que afegiran l'esquema d'axiomes de substitució (altre cas particular de la comprensió no restringida), que dona la teoria coneguda avui sota el nom de ZF (sense axioma d'elecció) o ZFC (amb l'axioma d'elecció). Altres autors han treballat sobre el problema de l'axiomatització de la teoria dels conjunts, sobretot John Von Neumann, que va definir una alternativa molt interessant a ZF: la teoria de les classes.
Notació Un conjunt es representa mitjançant claus que contenen els seus elements, ja siga de manera explícita, escrivint tots i cada un dels elements, o donant una fórmula, regla o proposició que els descriga. Per exemple,
S1 = {2, 4} S₂ = {2, 4, 6, ...} = {tots els enters parells més grans que 1} S₃ = {x|}. S₄ = {tots els barons vius anomenats Joan}
La definició de S₃ es llegeix "el conjunt de totes les x tals que ".
Conceptes en teoria de conjunts 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. Alternativament, alguns autors fan servir R ⊆ S per aquesta noció i reserven el símbol R ⊂ S per indicar que almenys un element de S no pertany a R, i llavors diuen que es diu que R és un subconjunt propi de S Tot conjunt és un subconjunt i un superconjunt de si mateix.
Si S ⊂ R i R ⊂S, é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, S1 = S₃.
Unió i intersecció miniatura|Un diagrama de Venn que il·lustra la intersecció de dos conjunts A i B 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:
Llavors:
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. Quan hi ha un conjunt de referència U dels quals tots els conjunts dels que es parla són subconjunts, aleshores es sobreentén que el complementari es respecte U, i senzillament es parla de conjunt complementari i s'escriu AC =U-A (que també pot aparèixer com à o ~A o A).
Àlgebra de conjunts Siguen A, B i C conjunts qualssevol, i U un conjunt tal que A ⊆ U, B ⊆ U i C ⊆ U. Aleshores:
Element neutre de la unió Element neutre de la intersecció
Propietat commutativa de la intersecció Propietat commutativa de la unió Doble negació Propietat associativa de la intersecció Propietat associativa de la unió Propietat distributiva de la intersecció Propietat distributiva de la unió
Definició
Distributivitat entre unió i intersecció Siguen tres conjunts A, B i C. Es compleix que:
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.
Lleis de De Morgan
Producte cartesià de conjunts