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 \{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 \{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 S se llama finito si existe una biyección

${\displaystyle f\colon S\to \{1,\ldots ,n\}}$

para algún número natural n . El número n es la cardinalidad del conjunto, denotada como | S | . El conjunto vacío o ∅ se considera finito, con cardinalidad cero. ^{[1] [2] [3] [4]} ${\displaystyle \{\}}$

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

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

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

(Quienes estén familiarizados con la definición de los números naturales como convencional en la teoría de conjuntos , la llamada construcción de von Neumann , pueden preferir utilizar la existencia de la biyección , que es equivalente). ${\displaystyle f\colon S\to n}$

Propiedades básicas

Cualquier subconjunto propio de un conjunto finito S 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.

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 |S\cup T|\leq |S|+|T|.}$

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

${\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 |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 n elementos tiene 2 ⁿ subconjuntos distintos. Es decir, el conjunto potencia P ( S ) de un conjunto finito S es finito, con cardinalidad 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: ^[5]

1. S es un conjunto finito. Es decir, S puede colocarse en una correspondencia uno a uno con el conjunto de aquellos números naturales menores que algún número natural específico.
2. ( Kazimierz Kuratowski ) S 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. (Ver § Definiciones de finitud de la teoría de conjuntos para una formulación diferente de la finitud de Kuratowski).
3. ( Paul Stäckel ) A S se le puede dar un orden total que esté bien ordenado tanto hacia adelante como hacia atrás. Es decir, todo subconjunto no vacío de S tiene un elemento mínimo y mayor en el subconjunto.
4. Cada función uno a uno desde P ( P ( S )) hacia sí misma es sobre . Es decir, el conjunto de poderes del conjunto de poderes de S es finito de Dedekind (ver más abajo). ^[6]
5. Cada función sobreyectiva de P ( P ( S )) sobre sí misma es uno a uno.
6. ( Alfred Tarski ) Cada familia no vacía de subconjuntos de S tiene un elemento mínimo con respecto a la inclusión. ^[7] (De manera equivalente, cada familia no vacía de subconjuntos de S tiene un elemento máximo con respecto a la inclusión).
7. S puede estar bien ordenado y dos buenos ordenamientos cualesquiera son de orden isomórfico . En otras palabras, los buenos pedidos en S tienen exactamente un tipo de orden .

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

1. S es un conjunto finito.
2. ( Richard Dedekind ) Cada función uno a uno desde S hacia sí misma es sobre.
3. Toda función sobreyectiva de S sobre sí misma es uno a uno.
4. S está vacío o cada ordenamiento parcial de S contiene un elemento máximo .

Cuestiones fundamentales

Georg Cantor inició su teoría de conjuntos para proporcionar un tratamiento matemático de conjuntos infinitos. Así, la distinción entre lo finito y lo infinito se encuentra en el centro de la teoría de conjuntos. Ciertos fundacionalistas, los finitistas estrictos , rechazan la existencia de conjuntos infinitos y recomiendan así una matemática basada únicamente en conjuntos finitos. Los matemáticos convencionales consideran que el finitismo estricto es demasiado restrictivo, pero reconocen su relativa coherencia: el universo de conjuntos hereditariamente finitos constituye un modelo de la teoría de conjuntos de Zermelo-Fraenkel con el axioma del infinito reemplazado por su negación .

Incluso para la mayoría de los matemáticos que abrazan conjuntos infinitos, en ciertos contextos importantes, la distinción formal entre lo finito y lo infinito puede seguir siendo una cuestión delicada. La dificultad surge de los teoremas de incompletitud de Gödel . Se puede interpretar la teoría de conjuntos hereditariamente finitos dentro de la aritmética de Peano (y ciertamente también viceversa), por lo que lo incompleto de la teoría de la aritmética de Peano implica la de la teoría de conjuntos hereditariamente finitos. En particular, existe una gran cantidad de los llamados modelos no estándar de ambas teorías. Una aparente paradoja es que existen modelos no estándar de la teoría de conjuntos hereditariamente finitos que contienen conjuntos infinitos, pero estos conjuntos infinitos parecen finitos desde dentro del modelo. (Esto puede suceder cuando el modelo carece de los conjuntos o funciones necesarios para presenciar la infinitud de estos conjuntos). Debido a los teoremas de incompletitud, ningún predicado de primer orden , ni siquiera ningún esquema recursivo de predicados de primer orden, puede caracterizar el modelo estándar. parte de todos estos modelos. Así, al menos desde el punto de vista de la lógica de primer orden, sólo podemos esperar describir la finitud de forma aproximada.

De manera más general, nociones informales como conjunto, y particularmente conjunto finito, pueden recibir interpretaciones a través de una variedad de sistemas formales que varían en su aparato lógico y axiomático. Las teorías de conjuntos axiomáticas más conocidas incluyen la teoría de conjuntos de Zermelo-Fraenkel (ZF), la teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección (ZFC), la teoría de conjuntos de Von Neumann-Bernays-Gödel (NBG), la teoría de conjuntos no bien fundamentada , La teoría de tipos de Bertrand Russell y todas las teorías de sus diversos modelos. También se puede elegir entre la lógica clásica de primer orden, varias lógicas de orden superior y la lógica intuicionista .

Un formalista podría ver que el significado ^{[ cita necesaria ]} de conjunto varía de un sistema a otro. Algunos tipos de platónicos podrían considerar que determinados sistemas formales se aproximan a una realidad subyacente.

Definiciones de finitud en la teoría de conjuntos

En contextos donde la noción de número natural es lógicamente anterior a cualquier noción de conjunto, se puede definir un conjunto S como finito si S admite una biyección a algún conjunto de números naturales de la forma . Los matemáticos suelen optar por fundamentar las nociones de números en la teoría de conjuntos ; por ejemplo, podrían modelar los números naturales según los tipos de orden de conjuntos finitos y bien ordenados . Este enfoque requiere una definición estructural de finitud que no dependa de los números naturales. ${\displaystyle \{x\,|\,x<n\}}$

Varias propiedades que distinguen los conjuntos finitos entre todos los conjuntos de la teoría ZFC resultan lógicamente no equivalentes en sistemas más débiles como ZF o teorías de conjuntos intuicionistas. Dos definiciones ocupan un lugar destacado en la literatura, una debida a Richard Dedekind y la otra a Kazimierz Kuratowski . (La definición de Kuratowski es la utilizada anteriormente).

Un conjunto S se llama infinito de Dedekind si existe una función inyectiva, no sobreyectiva . Tal función exhibe una biyección entre S y un subconjunto propio de S , es decir, la imagen de f . Dado un conjunto infinito de Dedekind S , una función f y un elemento x que no está en la imagen de f , se puede formar una secuencia infinita de elementos distintos de S , a saber . Por el contrario, dada una secuencia en S que consta de elementos distintos , se puede definir una función f tal que en los elementos de la secuencia y f se comporte como la función identidad en lo demás. Así, los conjuntos infinitos de Dedekind contienen subconjuntos que se corresponden biyectivamente con los números naturales. Dedekind finito significa naturalmente que todo automapa inyectivo es también sobreyectivo. ${\displaystyle f:S\rightarrow S}$ ${\displaystyle x,f(x),f(f(x)),...}$ ${\displaystyle x_{1},x_{2},x_{3},...}$ ${\displaystyle f(x_{i})=x_{i+1}}$

La finitud de Kuratowski se define de la siguiente manera. Dado cualquier conjunto S , la operación binaria de unión dota al conjunto de potencias P ( S ) con la estructura de una semired . Escribiendo K ( S ) para la subsemired generada por el conjunto vacío y los singletons , llame al conjunto S Kuratowski finito si el propio S pertenece a K ( S ). ^[9] Intuitivamente, K ( S ) consta de los subconjuntos finitos de S . Fundamentalmente, no se necesita inducción, recursividad o una definición de números naturales para definir generado por , ya que se puede obtener K ( S ) simplemente tomando la intersección de todas las subsemiredes que contienen el conjunto vacío y los singletons.

Los lectores que no estén familiarizados con las semiredes y otras nociones del álgebra abstracta pueden preferir una formulación enteramente elemental. Kuratowski finito significa que S se encuentra en el conjunto K ( S ), construido de la siguiente manera. Escriba M para el conjunto de todos los subconjuntos X de P ( S ) tal que:

• X contiene el conjunto vacío;
• Para cada conjunto T en P ( S ), si X contiene T , entonces X también contiene la unión de T con cualquier singleton.

Entonces K ( S ) puede definirse como la intersección de M.

En ZF, Kuratowski finito implica Dedekind finito, pero no al revés. En el lenguaje de una formulación pedagógica popular, cuando el axioma de elección falla estrepitosamente, uno puede tener una familia infinita de calcetines sin posibilidad de elegir un calcetín entre más de un número finito de pares. Eso haría que el conjunto de tales calcetines Dedekind fuera finito: no puede haber una secuencia infinita de calcetines, porque tal secuencia permitiría elegir un calcetín para infinitos pares eligiendo el primer calcetín de la secuencia. Sin embargo, la finitud de Kuratowski fallaría con el mismo par de calcetines.

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 S son distintos. Están ordenados en orden de intensidad estrictamente decreciente, es decir, si un conjunto S cumple un criterio de la lista, entonces cumple 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. ^[10] (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 ω.)

• Yo-finito . Todo conjunto no vacío de subconjuntos de S 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).
• Ia-finito . Para cada partición de S 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 . ^[11] )
• II-finito . Cada conjunto ⊆-monótono de subconjuntos de S no vacío tiene un elemento ⊆-máximo.
• III-finito . El conjunto de potencias P ( S ) es finito de Dedekind.
• IV-finito . S es finito de Dedekind.
• V-finito . ∣ S ∣ = 0 o 2 ⋅ ∣ S ∣ > ∣ S |.
• VI-finito . ∣ S ∣ = 0 o ∣ S ∣ = 1 o ∣ S ∣ ²  > ∣ S ∣.
• VII-finito . S es I-finito o no bien ordenable.

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 . ^[12]

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. Apóstol (1974, pág.38)
2. Cohn (1981, pág.7)
3. Labarre (1968, pág.41)
4. Rudin (1976, pág.25)
5. "El arte de resolver problemas". artofproblemsolving.com . Consultado el 7 de septiembre de 2022 .
6. 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.
7. 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.
8. Canadá, A.; Drabek, P.; Fonda, A. (2 de septiembre de 2005). Manual de ecuaciones diferenciales: ecuaciones diferenciales ordinarias. Elsevier. ISBN 9780080461083.
9. El artículo original de Kuratowski 1920 definió un conjunto S como finito cuando

   P ( S )∖{∅} = ⋂{ X ∈ P ( P ( S )∖{∅}); (∀ x ∈ S , { x }∈ X ) y (∀ A , B ∈ X , A ∪ B ∈ X )}.

   En otras palabras, S es finito cuando el conjunto de todos los subconjuntos no vacíos de S es igual a la intersección de todas las clases X que satisfacen:
   • todos los elementos de X son subconjuntos no vacíos de S ,
   • el conjunto { x } es un elemento de X para todo x en S ,
   • X está cerrado bajo uniones por pares.
   Kuratowski demostró que esto equivale a la definición numérica de un conjunto finito.
10. 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.
11. de la Cruz, Dzhafarov y Hall (2006, p.8)
12. 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
• Levy, Azriel (1958). "La independencia de varias definiciones de finitud" (PDF) . Fundamentos Mathematicae . 46 : 1–13. doi : 10.4064/fm-46-1-1-13 . Archivado (PDF) desde el original el 5 de julio de 2003.
• 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) . Fundamentos 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 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]. Principios Matemáticos . vol. Dos. Libros mercantiles. ISBN 978-1-60386-183-0.

enlaces externos

• Barile, Margarita. "Conjunto finito". MundoMatemático .