Conjunto finito

Conjunto matemático que contiene un número finito de elementos

En matemáticas , particularmente en teoría de conjuntos , un conjunto finito es un conjunto que tiene un número finito de elementos . De manera informal, un conjunto finito es un conjunto que, en principio, se podría contar y terminar de contar. Por ejemplo,

${\displaystyle \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 denomina cardinalidad (o número cardinal ) del conjunto. Un conjunto que no es un conjunto finito se denomina conjunto infinito . Por ejemplo, el conjunto de todos los números enteros positivos es infinito:

${\displaystyle \displaystyle \{1,2,3,\ldots \}}$

Los conjuntos finitos son particularmente importantes en la 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.

Definición y terminología

Formalmente, un conjunto se llama finito si existe una biyección. ${\displaystyle S}$

${\displaystyle \displaystyle f\colon S\to n}$

para algún número natural (los números naturales se definen como conjuntos en la teoría de conjuntos de Zermelo-Fraenkel ). El número es la cardinalidad del conjunto, denotada como . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle |S|}$

Si un conjunto es finito, sus elementos pueden escribirse —de muchas maneras— en una secuencia :

${\displaystyle \displaystyle x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n).}$

En combinatoria , un conjunto finito con elementos se denomina a veces -conjunto y un subconjunto con elementos se denomina -subconjunto . Por ejemplo, el conjunto es un 3-conjunto (un conjunto finito con tres elementos) y es un 2-subconjunto de él. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \{5,6,7\}}$ ${\displaystyle \{6,7\}}$

Propiedades básicas

Cualquier subconjunto propio de un conjunto finito es finito y tiene menos elementos que el propio S. 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 llama Dedekind-finito . Usando los axiomas estándar de ZFC para la teoría de conjuntos , cada conjunto Dedekind-finito también es finito, pero esta implicación no puede probarse solo en 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 probar esta equivalencia. ${\displaystyle S}$

Cualquier función inyectiva entre dos conjuntos finitos de la misma cardinalidad es también una función sobreyectiva (una sobreyección). De manera similar, 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 \displaystyle |S\cup T|\leq |S|+|T|.}$

De hecho, según el principio de inclusión-exclusión :

${\displaystyle \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 \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 elementos tiene subconjuntos distintos. Es decir, el conjunto potencia de un conjunto finito S es finito, con cardinalidad . ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle \wp (S)}$ ${\displaystyle 2^{|S|}}$

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

Todos los conjuntos finitos son contables , pero no todos los conjuntos contables son finitos. (Algunos autores, sin embargo, usan "contable" para significar "contablemente infinito", por lo que no consideran que los conjuntos finitos sean contables).

La semirretícula libre sobre un conjunto finito es el conjunto de sus subconjuntos no vacíos, siendo la operación de unión dada por la unión de conjuntos.

Condiciones necesarias y suficientes para la finitud

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, puede colocarse en correspondencia biunívoca con el conjunto de aquellos números naturales menores que un número natural específico. ${\displaystyle S}$
2. ( Kazimierz Kuratowski ) tiene todas las propiedades que pueden demostrarse por inducción matemática comenzando con el conjunto vacío y añadiendo un nuevo elemento a la vez. ${\displaystyle S}$
3. ( Paul Stäckel ) puede recibir un ordenamiento total que esté bien ordenado tanto hacia delante como hacia atrás. Es decir, cada subconjunto no vacío de tiene tanto un elemento mínimo como un elemento máximo en el subconjunto. ${\displaystyle S}$ ${\displaystyle S}$
4. Toda función biunívoca de en sí misma es sobre . Es decir, el conjunto potencia del conjunto potencia de es Dedekind-finito (ver más abajo). ^[2] ${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$ ${\displaystyle S}$
5. Toda función sobreyectiva desde sí misma es biyectiva. ${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$
6. ( Alfred Tarski ) Toda familia no vacía de subconjuntos de tiene un elemento mínimo con respecto a la inclusión. ^[3] (Equivalentemente, toda familia no vacía de subconjuntos de tiene un elemento máximo con respecto a la inclusión.) ${\displaystyle S}$ ${\displaystyle S}$
7. ${\displaystyle S}$puede estar bien ordenado y dos buenos ordenamientos cualesquiera en él son isomorfos en orden . En otras palabras, los buenos ordenamientos en tienen exactamente un tipo de orden . ${\displaystyle S}$

Si también se supone 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 ) Toda función biunívoca de dentro de sí misma es sobreyectiva. Un conjunto con esta propiedad se llama Dedekind-finito . ${\displaystyle S}$
3. Toda función sobreyectiva desde sí misma es biyectiva. ${\displaystyle S}$
4. ${\displaystyle S}$está vacío o cada ordenamiento parcial de contiene un elemento máximo . ${\displaystyle S}$

Otros conceptos de finitud

En la teoría de conjuntos ZF sin el axioma de elección , los siguientes conceptos de finitud para un conjunto son distintos. Están dispuestos en orden estrictamente decreciente de fuerza, es decir, si un conjunto cumple un criterio de la lista, entonces cumple todos los criterios siguientes. En ausencia del axioma de elección, las implicaciones inversas son todas indemostrables, pero si se supone el axioma de elección, entonces todos estos conceptos son equivalentes. ^[5] (Tenga en cuenta que ninguna de estas definiciones necesita que el conjunto de números ordinales finitos se defina primero; todas son definiciones puramente "teóricas de conjuntos" en términos de las relaciones de igualdad y pertenencia, que no involucran ω). ${\displaystyle S}$ ${\displaystyle S}$

• I-finito . Todo conjunto no vacío de subconjuntos de tiene un elemento -maximal. (Esto es equivalente a requerir la existencia de un elemento -minimal. También es equivalente al concepto numérico estándar de finitud). ${\displaystyle S}$ ${\displaystyle \subseteq }$ ${\displaystyle \subseteq }$
• Ia-finito . Para cada partición de en dos conjuntos, al menos uno de los dos conjuntos es I-finito. (Un conjunto con esta propiedad que no es I-finito se denomina conjunto amorfo . ^[6] ) ${\displaystyle S}$
• II-finito . Todo conjunto -monótono no vacío de subconjuntos de tiene un elemento -maximal. ${\displaystyle \subseteq }$ ${\displaystyle S}$ ${\displaystyle \subseteq }$
• III-finito . El conjunto potencia es finito de Dedekind. ${\displaystyle \wp (S)}$
• IV-finito . es Dedekind finito. ${\displaystyle S}$
• V-finito . o . ${\displaystyle |S|=0}$ ${\displaystyle 2\cdot |S|>|S|}$
• VI-finito . o o . ${\displaystyle |S|=0}$ ${\displaystyle |S|=1}$ ${\displaystyle |S|^{2}>|S|}$
• VII-finito . es I-finito o no bien ordenable. ${\displaystyle S}$

Las implicaciones hacia delante (de fuerte a débil) son teoremas dentro de ZF. Los contraejemplos de las implicaciones inversas (de débil a fuerte) en ZF con urelementos se encuentran utilizando la teoría de modelos . ^[7]

La mayoría de estas definiciones de finitud y sus nombres se atribuyen a Tarski 1954 por Howard & Rubin 1998, p. 278. Sin embargo, las definiciones I, II, III, IV y V se presentaron en Tarski 1924, pp. 49, 93, junto con pruebas (o referencias a pruebas) para las implicaciones futuras. En ese momento, la teoría de modelos no estaba lo suficientemente avanzada como para encontrar los contraejemplos.

Cada una de las propiedades I-finitas a IV-finitas es una noción de pequeñez en el sentido de que cualquier subconjunto de un conjunto con dicha propiedad también tendrá la propiedad. Esto no es cierto para V-finitas a VII-finitas porque pueden tener subconjuntos infinitos numerables.

Véase también

• Conjunto de aletas
• Número ordinal
• Aritmética de Peano

Notas

1. "El arte de resolver problemas", artofproblemsolving.com , consultado el 7 de septiembre de 2022
2. La equivalencia de la definición numérica estándar de conjuntos finitos con la finitud de Dedekind del conjunto potencia del conjunto potencia fue demostrada en 1912 por Whitehead y Russell 2009, pág. 288. Este teorema de Whitehead/Russell es descrito en un lenguaje más moderno por Tarski 1924, págs. 73–74.
3. Tarski 1924, pp. 48-58, demostró que su definición (que también se conoce como I-finita) es equivalente a la definición de teoría de conjuntos de Kuratowski, que luego señaló que es equivalente a la definición numérica estándar a través de la prueba de Kuratowski 1920, pp. 130-131.
4. Herrlich, Horst (2006), "Proposición 4.13", Axioma de elección, Apuntes de conferencias de matemáticas, vol. 1876, Springer, pág. 48, doi :10.1007/11601562, ISBN 3-540-30989-6, consultado el 18 de julio de 2023
5. Esta lista de 8 conceptos de finitud se presenta con este esquema de numeración tanto en Howard y Rubin 1998, pp. 278-280, como en Lévy 1958, pp. 2-3, aunque los detalles de la presentación de las definiciones difieren en algunos aspectos que no afectan los significados de los conceptos.
6. de la Cruz, Dzhafarov y Hall (2006, p.8)
7. Lévy 1958 encontró contraejemplos para cada una de las implicaciones inversas en los modelos de Mostowski. Lévy atribuye la mayoría de los resultados a trabajos anteriores de Mostowski y Lindenbaum.

Referencias

• 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, Código de Comercio de Canadá  80-29568{{citation}}: CS1 maint: multiple names: authors list (link)
• 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 números , Dover Books on Mathematics, Beman, Wooster Woodruff (edición de bolsillo), Dover Publications Inc., ISBN 0-486-21010-3
• 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) del original el 2011-05-15
• Labarre, Anthony E. Jr. (1968), Análisis matemático intermedio , Nueva York: Holt, Rinehart y 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) desde el original el 2003-07-05
• Rudin, Walter (1976), Principios del análisis matemático (3.ª ed.), Nueva York: McGraw-Hill , ISBN 0-07-054235-X
• Suppes, Patrick (1972) [1960], Teoría de conjuntos axiomáticos , Dover Books on Mathematics (edición de bolsillo), Dover Publications Inc., ISBN 0-486-61630-4
• 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 en 2011- 05-15
• 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

Enlaces externos

• Barile, Margherita, "Conjunto finito", MathWorld