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 . Informalmente, 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 llama cardinalidad (o número cardinal ) del conjunto. Un conjunto que no es finito se llama 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 combinatoria , el estudio matemático del conteo . Muchos argumentos que involucran conjuntos finitos se basan en el principio del casillero , que establece que no puede existir una función inyectiva de un conjunto finito más grande a un conjunto finito más pequeño.

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 a veces se denomina conjunto y un subconjunto con elementos se denomina subconjunto . Por ejemplo, el conjunto es un conjunto de 3 (un conjunto finito con tres elementos) y es un subconjunto de 2 del mismo. ${\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. Como 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 . Utilizando los axiomas estándar de ZFC para la teoría de conjuntos , todo conjunto finito de Dedekind también es finito, pero esta implicación no se puede probar solo en ZF (axiomas de Zermelo-Fraenkel sin el axioma de elección ). El axioma de elección contable , una versión débil del axioma de elección, es suficiente para demostrar 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 también es una inyección.

La unión de dos conjuntos finitos es finita, con

${\displaystyle \displaystyle |S\cup T|\leq |S|+|T|.}$

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

${\displaystyle \displaystyle |S\cup T|=|S|+|T|-|S\cap T|.}$

De manera más general, 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 semired libre sobre un conjunto finito es el conjunto de sus subconjuntos no vacíos, estando la operación de unión dada por 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, se puede colocar en una correspondencia uno a uno con el conjunto de aquellos números naturales menores que algún número natural específico. ${\displaystyle S}$
2. ( Kazimierz Kuratowski ) tiene todas las propiedades que pueden demostrarse mediante inducción matemática comenzando con el conjunto vacío y agregando un nuevo elemento a la vez. ${\displaystyle S}$
3. ( Paul Stäckel ) se le puede dar un orden total que esté bien ordenado tanto hacia adelante como hacia atrás. Es decir, cada subconjunto no vacío de tiene un elemento menor y mayor en el subconjunto. ${\displaystyle S}$ ${\displaystyle S}$
4. Cada función uno a uno desde dentro de sí misma es hacia . Es decir, el conjunto de poderes del conjunto de poderes de es finito de Dedekind (ver más abajo). ^[2] ${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$ ${\displaystyle S}$
5. Cada función sobreyectiva sobre sí misma es uno a uno. ${\displaystyle \wp {\bigl (}\wp (S){\bigr )}}$
6. ( Alfred Tarski ) Cada familia no vacía de subconjuntos de tiene un elemento mínimo con respecto a la inclusión. ^[3] (De manera equivalente, cada familia de subconjuntos de no vacía 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 son de orden isomórfico . En otras palabras, los buenos pedidos 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 ) Cada función uno a uno desde dentro de sí misma es hacia adelante. Un conjunto con esta propiedad se llama Dedekind-finito . ${\displaystyle S}$
3. Cada función sobreyectiva sobre sí misma es uno a uno. ${\displaystyle S}$
4. ${\displaystyle S}$está vacío o cada orden 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 ordenados en orden estrictamente decreciente de intensidad, es decir, si un conjunto cumple un criterio de la lista, entonces cumple con todos los criterios siguientes. En ausencia del axioma de elección, todas las implicaciones inversas son imposibles de demostrar, 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 se defina primero el conjunto de números ordinales finitos; todas son definiciones puras "teóricas de conjuntos" en términos de relaciones de igualdad y membresía, que no involucran ω.) ${\displaystyle S}$ ${\displaystyle S}$

• Yo-finito . Todo conjunto no vacío de subconjuntos de tiene un elemento máximo. (Esto equivale a requerir la existencia de un elemento mínimo. 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 llama conjunto amorfo . ^[6] ) ${\displaystyle S}$
• II-finito . Todo conjunto monótono de subconjuntos de no vacío tiene un elemento máximo. ${\displaystyle \subseteq }$ ${\displaystyle S}$ ${\displaystyle \subseteq }$
• III-finito . El conjunto de potencias 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 futuras (de fuerte a débil) son teoremas dentro de ZF. Se encuentran contraejemplos de las implicaciones inversas (de débil a fuerte) en ZF con urelementos 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 y Rubin 1998, p. 278. Sin embargo, las definiciones I, II, III, IV y V se presentaron en Tarski 1924, págs. 49, 93, junto con pruebas (o referencias a pruebas) de las implicaciones futuras. En aquel momento, la teoría de modelos no estaba lo suficientemente avanzada como para encontrar contraejemplos.

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

Ver 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 de potencias del conjunto de potencias fue demostrada en 1912 por Whitehead y Russell 2009, p. 288. Este teorema de Whitehead/Russell se describe en un lenguaje más moderno en Tarski 1924, págs. 73-74.
3. Tarski 1924, págs. 48-58, demostró que su definición (que también se conoce como I-finito) es equivalente a la definición teórica 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. , págs. 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, págs. 278–280, como en Lévy 1958, págs. 2–3, aunque los detalles de la presentación de las definiciones difieren en algunos aspectos, lo que no afectan los significados de los conceptos.
6. de la Cruz, Dzhafarov y Hall (2006, p.8)
7. Lévy 1958 encontró contraejemplos de cada una de las implicaciones inversas en los modelos de Mostowski. Lévy atribuye la mayoría de los resultados a artículos 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, LCCN  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 los 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, Pablo; Rubin, Jean E. (1998), Consecuencias del axioma de elección , Providence, Rhode Island: Sociedad Matemática Estadounidense, 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 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) del 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ática , 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 cardenales y el axioma de elección", Nederl. Akád. Wetensch. Proc. Ser. A, Indagaciones Matemáticas. , 16 : 26–32, doi :10.1016/S1385-7258(54)50005-3, SEÑOR  0060555
• Whitehead, Alfred Norte ; Russell, Bertrand (febrero de 2009) [1912], Principia Mathematica , vol. Dos, libros mercantiles, ISBN 978-1-60386-183-0

enlaces externos

• Barile, Margherita, "Conjunto finito", MathWorld