Conjunto finito

En matemáticas , un conjunto finito es una colección de un número finito de cosas diferentes; estas cosas se llaman elementos o miembros del conjunto y suelen ser objetos matemáticos , como números, símbolos, puntos en el espacio, líneas, otras figuras geométricas , variables u otros conjuntos.

De manera informal, un conjunto finito es un conjunto que, en principio, se podría contar y terminar de contar. Por ejemplo, $${\displaystyle \{2,4,6,8,10\}}$$ es un conjunto finito con cinco elementos. El número de elementos de un conjunto finito es un número natural (posiblemente cero) y se llama cardinalidad (o número cardinal ) del conjunto. Un conjunto que no es un conjunto finito se llama conjunto infinito . Por ejemplo, el conjunto $${\displaystyle \{1,2,3,\ldots \}}$$ de todos los enteros positivos es infinito.

Los conjuntos finitos son particularmente importantes en combinatoria , el estudio matemático del conteo . Muchos argumentos que involucran conjuntos finitos se basan en el principio del palomar , que establece que no puede existir una función inyectiva de un conjunto finito mayor a un conjunto finito menor.

Los números naturales se definen abstractamente mediante los axiomas de Peano y pueden construirse mediante la teoría de conjuntos (por ejemplo, mediante los ordinales de Von Neumann ). Entonces, formalmente, un conjunto${\displaystyle S}$Se denomina finito si existe una biyección.$${\displaystyle f\colon S\to \{1,2,\cdots ,n\}}$$ para algún número natural${\displaystyle n}$, análogo a contar sus elementos. Si${\displaystyle S}$está vacío , esto se satisface vacuamente para${\displaystyle n=0}$con la función vacía . El número${\displaystyle n}$es la cardinalidad del conjunto, denotada como${\displaystyle |S|}$.

Si un conjunto no vacío es finito, sus elementos pueden escribirse en una secuencia : $${\displaystyle x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n).}$$ Si n ≥ 2, entonces existen múltiples secuencias de este tipo. En combinatoria , un conjunto finito con${\displaystyle n}$Los elementos a veces se denominan${\displaystyle n}$-conjunto y un subconjunto con${\displaystyle k}$Los elementos se llaman${\displaystyle k}$-subconjunto . Por ejemplo, el conjunto${\displaystyle \{5,6,7\}}$es un conjunto de 3 elementos  – un conjunto finito con tres elementos  – y${\displaystyle \{6,7\}}$es un subconjunto de 2 elementos.

Esta notación${\displaystyle \{1,\cdots ,n\}}$puede definirse recursivamente como

$${\displaystyle \{1,\cdots ,n\}=\left\{{\begin{array}{lll}\varnothing {\text{ (el conjunto vacío)}}&{\text{si}}&n=0\\\{1,\cdots ,n-1\}\cup \{n\}&{\text{si}}&n\geq 1\\\end{array}}\right.}$$

Cualquier subconjunto propio de un conjunto finito${\displaystyle S}$es finito y tiene menos elementos que S mismo. En consecuencia, no puede existir una biyección entre un conjunto finito S y un subconjunto propio de S. Cualquier conjunto con esta propiedad se denomina Dedekind-finito . Utilizando los axiomas ZFC estándar para la teoría de conjuntos , todo conjunto Dedekind-finito es también finito, pero esta implicación no puede demostrarse únicamente con ZF (axiomas de Zermelo-Fraenkel sin el axioma de elección ). El axioma de elección numerable , una versión débil del axioma de elección, es suficiente para demostrar esta equivalencia.

Cualquier función inyectiva entre dos conjuntos finitos de la misma cardinalidad es también una función sobreyectiva (una sobreyección). De igual modo, cualquier sobreyección entre dos conjuntos finitos de la misma cardinalidad es también una inyección.

La unión de dos conjuntos finitos es finita, con $${\displaystyle |S\cup T|\leq |S|+|T|.}$$

De hecho, según el principio de inclusión-exclusión : $${\displaystyle |S\cup T|=|S|+|T|-|S\cap T|.}$$ En términos más generales, la unión de cualquier número finito de conjuntos finitos es finita. El producto cartesiano de conjuntos finitos también es finito, con: $${\displaystyle |S\times T|=|S|\times |T|.}$$ De manera similar, el producto cartesiano de un número finito de conjuntos finitos es finito. Un conjunto finito con${\displaystyle n}$elementos tiene${\displaystyle 2^{n}}$subconjuntos distintos. Es decir, el conjunto potencia .${\displaystyle \wp (S)}$de un conjunto finito S es finito, con cardinalidad${\displaystyle 2^{|S|}}$.

Cualquier subconjunto de un conjunto finito es finito. El conjunto de valores de una función aplicada a elementos de un conjunto finito es finito.

Todos los conjuntos finitos son numerables , pero no todos los conjuntos numerables son finitos. (Sin embargo, algunos autores usan "numerable" para referirse a "numerablemente infinito", por lo que no consideran que los conjuntos finitos sean numerables).

El semirretículo libre sobre un conjunto finito es el conjunto de sus subconjuntos no vacíos, donde la operación de unión viene dada por la unión de conjuntos.

En la teoría de conjuntos de Zermelo-Fraenkel sin el axioma de elección (ZF), las siguientes condiciones son todas equivalentes: ^{[ 1 ]}

1. ${\displaystyle S}$es un conjunto finito. Es decir,${\displaystyle S}$se puede establecer una correspondencia biunívoca con el conjunto de aquellos números naturales menores que algún número natural específico.
2. ( Kazimirz Kuratowski )${\displaystyle S}$posee todas las propiedades que pueden probarse por inducción matemática comenzando con el conjunto vacío y agregando un nuevo elemento a la vez.
3. ( Paul Stäckel )${\displaystyle S}$Se puede dar un orden total que esté bien ordenado tanto hacia adelante como hacia atrás. Es decir, cada subconjunto no vacío de${\displaystyle S}$tiene un elemento mínimo y un elemento máximo en el subconjunto.
4. Cada función individual desde${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$en sí mismo es sobre . Es decir, el conjunto potencia del conjunto potencia de${\displaystyle S}$es Dedekind-finito (ver más abajo). ^{[ 2 ]}
5. Toda función sobreyectiva de${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$en sí mismo es uno a uno.
6. ( Alfred Tarski ) Toda familia no vacía de subconjuntos de${\displaystyle S}$tiene un elemento mínimo con respecto a la inclusión. ^{[ 3 ]} (equivalentemente, toda familia no vacía de subconjuntos de${\displaystyle S}$tiene un elemento máximo con respecto a la inclusión.)
7. ${\displaystyle S}$puede ser bien ordenado y cualesquiera dos buenos órdenes en él son isomorfos en orden . En otras palabras, los buenos órdenes en${\displaystyle S}$tener exactamente un tipo de pedido .

Si también se asume el axioma de elección (el axioma de elección contable es suficiente), ^{[ 4 ]} entonces las siguientes condiciones son todas equivalentes:

1. ${\displaystyle S}$es un conjunto finito.
2. ( Richard Dedekind ) Cada función uno a uno de${\displaystyle S}$En sí mismo es sobreyectivo. Un conjunto con esta propiedad se llama Dedekind-finito .
3. Toda función sobreyectiva de${\displaystyle S}$en sí mismo es uno a uno.
4. ${\displaystyle S}$está vacío o cualquier orden parcial de${\displaystyle S}$contiene un elemento máximo .

Una propiedad importante de los conjuntos finitos es que, por ejemplo, si un conjunto tiene cardinalidad 4, entonces no puede tener también cardinalidad 5. Intuitivamente, esto significa que un conjunto no puede tener exactamente 4 elementos y exactamente 5 elementos a la vez. Sin embargo, no es una demostración tan obvia. La siguiente demostración está adaptada de Analysis I de Terence Tao . ^{[ 8 ]}

Lema: Si un conjunto${\displaystyle X}$tiene cardinalidad${\displaystyle n\geq 1,}$y${\displaystyle x_{0}\in X,}$luego el conjunto${\displaystyle X-\{x_{0}\}}$(es decir${\displaystyle X}$con el elemento${\displaystyle x_{0}}$eliminado) tiene cardinalidad${\displaystyle n-1.}$

Prueba: Dado${\displaystyle X}$como se indicó anteriormente, ya que${\displaystyle X}$tiene cardinalidad${\displaystyle n,}$Hay una biyección${\displaystyle f}$de${\displaystyle X}$a${\displaystyle \{1,\,2,\,\dots ,\,n\}.}$Entonces, dado que${\displaystyle x_{0}\in X,}$Debe haber algún número${\displaystyle f(x_{0})}$en${\displaystyle \{1,\,2,\,\dots ,\,n\}.}$Necesitamos encontrar una biyección desde${\displaystyle X-\{x_{0}\}}$a${\displaystyle \{1,\dots n-1\}}$(que puede estar vacío). Defina una función${\displaystyle g}$de tal manera que${\displaystyle g(x)=f(x_{0})}$si${\displaystyle f(x)=n}$, y${\displaystyle g(x)=f(x)}$De lo contrario. Entonces${\displaystyle g}$es una biyección de${\displaystyle X-\{x_{0}\}}$a${\displaystyle \{1,\dots n-1\}.}$

Teorema: Si un conjunto${\displaystyle X}$tiene cardinalidad${\displaystyle n,}$entonces no puede tener ninguna otra cardinalidad. Es decir,${\displaystyle X}$no puede tener cardinalidad${\displaystyle m\neq n.}$

Prueba: Si${\displaystyle X}$es vacío (tiene cardinalidad 0), entonces no puede existir una biyección desde${\displaystyle X}$a cualquier conjunto no vacío${\displaystyle Y,}$puesto que, vagamente , nada puede mapearse a${\displaystyle y_{0}\in Y.}$Supongamos, por inducción , que el resultado ha sido demostrado hasta cierta cardinalidad.${\displaystyle n.}$Si${\displaystyle X,}$tiene cardinalidad${\displaystyle n+1,}$supongamos que también tiene cardinalidad${\displaystyle m.}$Queremos demostrar que${\displaystyle m=n+1.}$Según el lema anterior,${\displaystyle X-\{x_{0}\}}$debe tener cardinalidad${\displaystyle n}$y${\displaystyle m-1.}$Dado que, por inducción, la cardinalidad es única para conjuntos con cardinalidad${\displaystyle n,}$debe ser que${\displaystyle m-1=n,}$y por lo tanto${\displaystyle m=n+1.}$

• FinSet
• Conjunto de puntos discretos
• Número ordinal
• Aritmética de Peano

• Apostol, Tom M. (1974), Análisis matemático (2.ª  ed.), Menlo Park: Addison-Wesley , LCCN 72011473 
• Cohn, Paul Moritz, FRS (1981), Álgebra universal , Dordrecht: D. Reidel , ISBN 90-277-1254-9, LCCN 80-29568 {{citation}}: CS1 maint: varios nombres: lista de autores ( enlace )
• Dedekind, Richard (2012), Was sind und was sollen die Zahlen? , Colección de la Biblioteca de Cambridge (  edición de bolsillo), Cambridge, Reino Unido: Cambridge University Press, ISBN 978-1-108-05038-8
• Dedekind, Richard (1963), Ensayos sobre la teoría de los números , Dover Books on Mathematics, Beman, Wooster Woodruff (edición en rústica  ), Dover Publications Inc., ISBN 0-486-21010-3{{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda )
• de la Cruz, Omar; Dzhafarov, Damir D.; Hall, Eric J. (2006), "Definiciones de finitud basadas en propiedades de orden" (PDF) , Fundamenta Mathematicae , 189 (2): 155– 172, doi : 10.4064/fm189-2-5 , MR 2214576 
• Herrlich, Horst (2006), Axioma de elección , Apuntes de conferencias de matemáticas. 1876, Berlín: Springer-Verlag , ISBN 3-540-30989-6
• Howard, Paul; Rubin, Jean E. (1998), Consecuencias del axioma de elección , Providence, Rhode Island: American Mathematical Society, ISBN 9780821809778
• Kuratowski, Kazimierz (1920), "Sur la notion d'ensemble fini" (PDF) , Fundamenta Mathematicae , 1 : 129– 131, doi : 10.4064/fm-1-1-129-131 , archivado (PDF) desde el original el 15 de mayo de 2011
• Labarre, Anthony E. Jr. (1968), Análisis matemático intermedio , Nueva York: Holt, Rinehart and Winston , LCCN 68019130 
• Lévy, Azriel (1958), "La independencia de varias definiciones de finitud" (PDF) , Fundamenta Mathematicae , 46 : 1–13 , doi : 10.4064/fm-46-1-1-13 , archivado (PDF) del original el 5 de julio de 2003.
• Rudin, Walter (1976), Principios de análisis matemático (3.ª  ed.), Nueva York: McGraw-Hill , ISBN 0-07-054235-X
• Suppes, Patrick (1972) [1960], Teoría axiomática de conjuntos , Dover Books on Mathematics (  edición de bolsillo), Dover Publications Inc., ISBN 0-486-61630-4
• Tao, Terence (2022), Análisis I , Textos y lecturas en matemáticas (4.ª  ed.), Singapur: Springer Science+Business Media , doi : 10.1007/978-3-662-00274-2 , ISBN 978-981-19-7261-4ISSN 2366-8717​ 
• Tarski, Alfred (1924), "Sur les ensembles finis" (PDF) , Fundamenta Mathematicae , 6 : 45– 95, doi : 10.4064/fm-6-1-45-95 , archivado (PDF) desde el original el 15 de mayo de 2011
• Tarski, Alfred (1954), "Teoremas sobre la existencia de sucesores de cardinales y el axioma de elección", Nederl. Akad. Wetensch. Proc. Ser. A, Indagationes Math. , 16 : 26– 32, doi : 10.1016/S1385-7258(54)50005-3 , MR 0060555 
• Whitehead, Alfred North ; Russell, Bertrand (febrero de 2009) [1912], Principia Mathematica , vol.  dos, Merchant Books, ISBN 978-1-60386-183-0

• Barile, Margherita , "Conjunto finito" , MathWorld