Conjunto finito

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,

{}2,4,6,8,10}{displaystyle {2,4,6,8,10}}

es un conjunto finito de 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 llama conjunto infinito. Por ejemplo, el conjunto de todos los enteros positivos es infinito:

{}1,2,3,...... }.{displaystyle {1,2,3,ldots}.}

Los conjuntos finitos son especialmente importantes en la 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 hay existe una biyeccion

f:: S→ → {}1,...... ,n}{displaystyle fcolon Sto {1,ldotsn}}

para algún número natural n. El número n es la cardinalidad del conjunto, indicada como |S|. El conjunto vacío { } o ∅ se considera finito, con cardinalidad cero.

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

x1,x2,...... ,xn()xi▪ ▪ S,1≤ ≤ i≤ ≤ n).{displaystyle x_{1},x_{2},ldotsx_{n}quad (x_{i}in S, 1leq ileq n).}

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

(Los que conocen la definición de los propios números naturales como convencionales en la teoría de conjuntos, la llamada construcción de von Neumann, pueden preferir utilizar la existencia de la bijeción f:: S→ → n{displaystyle fcolon Sto n}, que es equivalente.)

Propiedades básicas

Cualquier subconjunto propio de un conjunto finito S 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 ZFC estándar para la teoría de conjuntos, cada 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 probar 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

SilencioS∪ ∪ TSilencio≤ ≤ SilencioSSilencio+SilencioTSilencio.{displaystyle TENScup T durableleq TENS sometidaS sobrevivir.}

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

SilencioS∪ ∪ TSilencio=SilencioSSilencio+SilencioTSilencio− − SilencioS∩ ∩ TSilencio.{displaystyle TENScup TTENIDO= T.

Más generalmente, la unión de cualquier número finito de conjuntos finitos es finita. El producto cartesiano de conjuntos finitos también es finito, con:

SilencioS× × TSilencio=SilencioSSilencio× × SilencioTSilencio.{displaystyle TENStimes TTENIDO= SUPERVISIÓNtimes NOVEDAD

Del mismo modo, 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", así que no considere que los conjuntos finitos sean contables).

La semired libre sobre un conjunto finito es el conjunto de sus subconjuntos no vacíos, con 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. S es un juego finito. Eso es, S se puede colocar en una correspondencia de uno a uno con el conjunto de esos números naturales menos que un número natural específico.
2. (Kazimierz Kuratowski) S tiene todas las propiedades que pueden ser probadas por la inducción matemática comenzando con el conjunto vacío y añadiendo un nuevo elemento a la vez. (Ver abajo para la formulación teórica de la finicidad de Kuratowski.)
3. (Paul Stäckel) 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 S tiene un elemento menos y más grande en el subconjunto.
4. Cada función de uno a uno P()P()S) en sí mismo está encendido. Es decir, la potencia de la potencia S es Dedekind-finite (ver abajo).
5. Cada función subjetiva de P()P()S)) en sí mismo es uno a uno.
6. (Alfred Tarski) Todas las familias no vacías de subconjuntos S tiene un elemento mínimo con respecto a la inclusión. (Equivalentemente, cada familia no vacía de subconjuntos de S tiene un elemento maximal con respecto a la inclusión.)
7. S puede ser bien ordenado y cualquier dos bien orden en él son el orden isomorfo. En otras palabras, los bien ordenados en S tienen exactamente un tipo de pedido.

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

1. S es un juego finito.
2. (Richard Dedekind) Cada función de uno a uno S en sí mismo está encendido.
3. Cada función subjetiva de S en sí mismo es uno a uno.
4. S está vacío o cada orden parcial de S contiene un elemento maximal.

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 limitado, pero reconocen su relativa consistencia: 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 los conjuntos infinitos, en ciertos contextos importantes, la distinción formal entre lo finito y lo infinito puede seguir siendo un asunto delicado. La dificultad surge de los teoremas de incompletitud de Gödel. Uno puede interpretar la teoría de los conjuntos hereditariamente finitos dentro de la aritmética de Peano (y ciertamente también viceversa), por lo que la incompletitud de la teoría de la aritmética de Peano implica la de la teoría de los conjuntos hereditariamente finitos. En particular, existe una plétora 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 atestiguar 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. Entonces, al menos desde el punto de vista de la lógica de primer orden, uno solo puede esperar describir la finitud aproximadamente.

De manera más general, las 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 axiomática y aparato lógico. 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 fundada, 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 el significado de conjunto variando de un sistema a otro. Algunos tipos de platónicos podrían considerar que los sistemas formales particulares se aproximan a una realidad subyacente.

Definiciones de la teoría de conjuntos de finitud

En contextos donde la noción de número natural se sienta lógicamente antes de cualquier noción de conjunto, se puede definir un conjunto S como finito si S admite una bijeción a algún conjunto de números naturales de la forma <math alttext="{displaystyle {x,|,x{}xSilenciox.n}{fnMicrosoft Sans Serif}<img alt="{displaystyle {x,|,x. Los matemáticos eligen más por lo general nociones de número en la teoría de conjuntos, por ejemplo, pueden modelar números naturales por los tipos de orden de conjuntos bien ordenados finitos. Tal enfoque requiere una definición estructural de la finidad que no depende de los números naturales.

Varias propiedades que destacan los conjuntos finitos entre todos los conjuntos en 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 juego S se llama Dedekind infinite si existe una función inyectora, no subjetiva f:S→ → S{displaystyle f:Srightarrow S.. Tal función exhibe una bijección entre S y un subconjunto adecuado S, a saber, la imagen f. Dado un conjunto infinito de Dedekind S, una función f, y un elemento x que no está en la imagen f, podemos formar una secuencia infinita de elementos distintos S, a saber x,f()x),f()f()x)),...{displaystyle x,f(x),f(f(x)),...}. Por el contrario, dada una secuencia en S que consiste en elementos distintos x1,x2,x3,...{displaystyle x_{1},x_{2},x_{3},}, podemos definir una función f tal que sobre elementos en la secuencia f()xi)=xi+1{displaystyle f(x_{i})=x_{i+1} y f se comporta como la función de identidad de otra manera. Así, los conjuntos infinitos de Dedekind contienen subconjuntos que corresponden bijetivamente con los números naturales. Dedekind finite naturalmente significa que cada auto-mapa inyectable también es subjetivo.

La finitud de Kuratowski se define de la siguiente manera. Dado cualquier conjunto S, la operación binaria de unión dota al conjunto potencia P(S) de la estructura de una semired. Escribiendo K(S) para el sub-semiretículo generado por el conjunto vacío y los singletons, llame al conjunto S Kuratowski finito si S pertenece a K(S). Intuitivamente, K(S) consta de los subconjuntos finitos de S. Crucialmente, uno no necesita inducción, recursión o una definición de números naturales para definir generado por ya que uno puede obtener K(S) simplemente por tomando la intersección de todos los subsemiretículos que contienen el conjunto vacío y los singletons.

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

• X contiene el conjunto vacío;
• Para cada juego T dentro 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 viceversa. En el lenguaje de una formulación pedagógica popular, cuando el axioma de elección falla gravemente, 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 finito el conjunto de tales calcetines Dedekind: 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 en la secuencia. Sin embargo, la finitud de Kuratowski fallaría por 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 estrictamente decreciente de fuerza, es decir, si un conjunto S cumple con un criterio en la lista, entonces cumple con todos los siguientes criterios. En ausencia del axioma de elección, todas las implicaciones inversas son indemostrables, pero si se asume el axioma de elección, entonces todos estos conceptos son equivalentes. (Tenga en cuenta que ninguna de estas definiciones necesita definir primero el conjunto de números ordinales finitos; todas son definiciones puras de "teoría de conjuntos" en términos de las relaciones de igualdad y pertenencia, que no involucran a ω).

• I-finite. Cada conjunto no vacío de subconjuntos S tiene un elemento ⊆-maximal. (Esto equivale a exigir la existencia de un elemento ⊆-minimal. También es equivalente al concepto numérico estándar de finiteness.)
• Ia-finite. Para cada partición de S en dos sets, al menos uno de los dos sets es I-finite. (Un conjunto con esta propiedad que no es I-finite se llama un conjunto amorfo.)
• II-finito. Cada conjunto de subconjuntos no vacío ⊆-monotone S tiene un elemento ⊆-maximal.
• III-finito. El sistema de energía P()S) es Dedekind finite.
• IV-finito. S es Dedekind finite.
• V-finito. ▪S▪ = 0 o 2 ⋅SНени нани на на на на на на на на на на ни наSSilencio.
• VI-finito. ▪S▪ = 0 o −S▪ = 1 o −S▪²>S.
• VII-finito. S es definitivamente o no bien ordenable.

Las implicaciones directas (de fuerte a débil) son teoremas dentro de ZF. Los contraejemplos de las implicaciones inversas (de débil a fuerte) en ZF con urelements se encuentran utilizando la teoría de modelos.

La mayoría de estas definiciones de finitud y sus nombres se atribuyen a Tarski 1954 por Howard & Rubín 1998, pág. 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 para encontrar los contraejemplos.

Cada una de las propiedades I-finito a IV-finito 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.