Conjunto finito - Finite set

Em matemática (particularmente na teoria dos conjuntos ), um conjunto finito é um conjunto que possui um número finito de elementos . Informalmente, um conjunto finito é um conjunto que se pode, em princípio, contar e terminar de contar. Por exemplo,

é um conjunto finito com cinco elementos. O número de elementos de um conjunto finito é um número natural (um inteiro não negativo ) e é chamado de cardinalidade do conjunto. Um conjunto que não é finito é denominado infinito . Por exemplo, o conjunto de todos os inteiros positivos é infinito:

Os conjuntos finitos são particularmente importantes em combinatória , o estudo matemático da contagem . Muitos argumentos envolvendo conjuntos finitos contam com o princípio do escaninho , que afirma que não pode existir uma função injetiva de um conjunto finito maior para um conjunto finito menor.

Definição e terminologia

Formalmente, um conjunto S é chamado de finito se existe uma bijeção

para algum número natural n . O número n é a cardinalidade do conjunto, denotado como | S | . O conjunto vazio {} ou ∅ é considerado finito, com cardinalidade zero.

Se um conjunto for finito, seus elementos podem ser escritos - de várias maneiras - em uma sequência :

Em combinatória , um conjunto finito com n elementos às vezes é chamado de n -conjunto e um subconjunto com k elementos é chamado de k- subconjunto . Por exemplo, o conjunto {5,6,7} é um conjunto de 3 - um conjunto finito com três elementos - e {6,7} é um subconjunto de 2 dele.

(Aqueles familiarizados com a definição dos próprios números naturais como convencionais na teoria dos conjuntos, a chamada construção de von Neumann , podem preferir usar a existência da bijeção , que é equivalente.)

Propriedades básicas

Qualquer subconjunto próprio de um conjunto finito S é finito e tem menos elementos do que o próprio S. Como consequência, não pode existir um bijeç~ao entre um conjunto finito S e um subconjunto apropriado de S . Qualquer conjunto com essa propriedade é denominado Dedekind-finito . Usando os axiomas ZFC padrão para a teoria dos conjuntos , cada conjunto finito de Dedekind também é finito, mas esta implicação não pode ser provada apenas em ZF (axiomas de Zermelo-Fraenkel sem o axioma de escolha ). O axioma da escolha contável , uma versão fraca do axioma da escolha, é suficiente para provar essa equivalência.

Qualquer função injetiva entre dois conjuntos finitos da mesma cardinalidade também é uma função sobrejetiva (uma sobreposição). Da mesma forma, qualquer sobreposição entre dois conjuntos finitos da mesma cardinalidade também é uma injeção.

A união de dois conjuntos finitos é finita, com

Na verdade, pelo princípio de inclusão-exclusão :

Mais geralmente, a união de qualquer número finito de conjuntos finitos é finita. O produto cartesiano de conjuntos finitos também é finito, com:

Da mesma forma, o produto cartesiano de muitos conjuntos finitos é finito. Um conjunto finito com n elementos possui 2 n subconjuntos distintos. Ou seja, o conjunto de potência de um conjunto finito é finito, com cardinalidade 2 n .

Qualquer subconjunto de um conjunto finito é finito. O conjunto de valores de uma função quando aplicado a elementos de um conjunto finito é finito.

Todos os conjuntos finitos são contáveis , mas nem todos os conjuntos contáveis ​​são finitos. (Alguns autores, no entanto, usam "contável" para significar "infinito contável", portanto, não considere os conjuntos finitos como contáveis.)

O semilattice livre sobre um conjunto finito é o conjunto de seus subconjuntos não vazios, com a operação de junção sendo dada por conjunto de união.

Condições necessárias e suficientes para finitude

Na teoria dos conjuntos de Zermelo-Fraenkel sem o axioma de escolha (ZF), as seguintes condições são todas equivalentes:

  1. S é um conjunto finito. Ou seja, S pode ser colocado em uma correspondência de um para um com o conjunto daqueles números naturais menores do que algum número natural específico.
  2. ( Kazimierz Kuratowski ) S tem todas as propriedades que podem ser provadas por indução matemática começando com o conjunto vazio e adicionando um novo elemento por vez. (Veja abaixo a formulação teórica de conjunto da finitude de Kuratowski.)
  3. ( Paul Stäckel ) S pode receber uma ordenação total bem ordenada para a frente e para trás. Ou seja, cada subconjunto não vazio de S tem o menor e o maior elemento no subconjunto.
  4. Cada função um-para-um de P ( P ( S )) em si mesma está ligada . Ou seja, o conjunto de potência do conjunto de potência de S é Dedekind finito (veja abaixo).
  5. Cada função sobrejetiva de P ( P ( S )) sobre si mesma é um-para-um.
  6. ( Alfred Tarski ) Cada família não vazia de subconjuntos de S tem um elemento mínimo com respeito à inclusão. (Equivalentemente, cada família não vazia de subconjuntos de S tem um elemento máximo com relação à inclusão.)
  7. S pode ser bem ordenado e quaisquer duas ordenações boas nele são de ordem isomórfica . Em outras palavras, as ordenações boas em S têm exatamente um tipo de pedido .

Se o axioma da escolha também for assumido (o axioma da escolha contável é suficiente), as seguintes condições são todas equivalentes:

  1. S é um conjunto finito.
  2. ( Richard Dedekind ) Cada função um-para-um de S em si é sobre.
  3. Cada função sobrejetiva de S sobre si mesmo é um-para-um.
  4. S está vazio ou cada ordenação parcial de S contém um elemento máximo .

Questões fundamentais

Georg Cantor iniciou sua teoria dos conjuntos para fornecer um tratamento matemático dos conjuntos infinitos. Assim, a distinção entre o finito e o infinito está no cerne da teoria dos conjuntos. Certos fundacionalistas, os finitistas estritos , rejeitam a existência de conjuntos infinitos e, portanto, recomendam uma matemática baseada apenas em conjuntos finitos. Os matemáticos convencionais consideram o finitismo estrito muito restritivo, mas reconhecem sua consistência relativa: o universo dos conjuntos hereditariamente finitos constitui um modelo da teoria dos conjuntos de Zermelo-Fraenkel com o axioma do infinito substituído por sua negação.

Mesmo para os matemáticos que abraçam conjuntos infinitos, em certos contextos importantes, a distinção formal entre o finito e o infinito pode permanecer uma questão delicada. A dificuldade decorre dos teoremas da incompletude de Gödel . Pode-se interpretar a teoria dos conjuntos hereditariamente finitos dentro da aritmética de Peano (e certamente também vice-versa), então a incompletude da teoria da aritmética de Peano implica a da teoria dos conjuntos hereditariamente finitos. Em particular, existe uma infinidade dos chamados modelos não padronizados de ambas as teorias. Um aparente paradoxo é que existem modelos não padronizados da teoria dos conjuntos hereditariamente finitos que contêm conjuntos infinitos, mas esses conjuntos infinitos parecem finitos de dentro do modelo. (Isso pode acontecer quando o modelo não possui os conjuntos ou funções necessárias para testemunhar a infinitude desses conjuntos.) Por causa dos teoremas da incompletude, nenhum predicado de primeira ordem, nem mesmo qualquer esquema recursivo de predicados de primeira ordem, pode caracterizar o padrão parte de todos esses modelos. Portanto, pelo menos do ponto de vista da lógica de primeira ordem, podemos apenas esperar descrever a finitude aproximadamente.

De forma mais geral, noções informais como conjunto, e particularmente conjunto finito, podem receber interpretações em uma gama de sistemas formais variando em sua axiomática e aparato lógico. As teorias axiomáticas de conjuntos mais conhecidas incluem a teoria dos conjuntos de Zermelo-Fraenkel (ZF), teoria dos conjuntos de Zermelo-Fraenkel com o Axioma da Escolha (ZFC), teoria dos conjuntos de Von Neumann – Bernays – Gödel (NBG), teoria dos conjuntos não bem fundamentada , Bertrand Russell 's teoria Tipo e todas as teorias de seus vários modelos. Também se pode escolher entre a lógica clássica de primeira ordem, várias lógicas de ordem superior e lógica intuicionista .

Um formalista pode ver o significado de conjunto variando de sistema para sistema. Alguns tipos de platônicos podem ver os sistemas formais específicos como se aproximando de uma realidade subjacente.

Definições teóricas de conjuntos de finitude

Em contextos onde a noção de número natural fica logicamente anterior a qualquer noção de conjunto, pode-se definir um conjunto S como finito se S admitir uma bijeção para algum conjunto de números naturais da forma . Os matemáticos geralmente optam por fundamentar noções de número na teoria dos conjuntos , por exemplo, eles podem modelar os números naturais pelos tipos de ordem de conjuntos finitos bem ordenados . Tal abordagem requer uma definição estrutural de finitude que não depende de números naturais.

Várias propriedades que separam os conjuntos finitos entre todos os conjuntos na teoria ZFC revelam-se logicamente inequivalentes em sistemas mais fracos, como ZF ou teorias de conjuntos intuicionistas. Duas definições aparecem com destaque na literatura, uma devida a Richard Dedekind e a outra a Kazimierz Kuratowski . (Kuratowski é a definição usada acima.)

Um conjunto S é denominado Dedekind infinito se existe uma função injetiva, não sobrejetiva . Tal função exibe uma bijeção entre S e um subconjunto próprio de S , ou seja, a imagem de f . Dado um conjunto infinito de Dedekind S , uma função f , e um elemento x que não está na imagem de f , podemos formar uma sequência infinita de elementos distintos de S , a saber . Por outro lado, dada uma sequência em S que consiste em elementos distintos , que podem definir uma função f de tal forma que os elementos contidos na sequência e de f comporta-se como a função de identidade de outra forma. Assim, os conjuntos infinitos de Dedekind contêm subconjuntos que correspondem bijetivamente aos números naturais. Dedekind finito naturalmente significa que todo auto-mapa injetivo também é sobrejetivo.

A finitude de Kuratowski é definida como segue. Dado qualquer conjunto S , a operação binária de união dota o conjunto de poderes P ( S ) com a estrutura de uma semilática . Escrevendo K ( S ) para a sub-semilática gerada pelo conjunto vazio e os singletons, chame o conjunto S Kuratowski finito se o próprio S pertencer a K ( S ). Intuitivamente, K ( S ) é constituído pelos subconjuntos finitos de S . Crucialmente, não é necessário indução, recursão ou uma definição de números naturais para definir gerado por, uma vez que pode-se obter K ( S ) simplesmente tomando a interseção de todas as sub-semiláticas contendo o conjunto vazio e os singletons .

Leitores não familiarizados com semilattices e outras noções de álgebra abstrata podem preferir uma formulação inteiramente elementar. Finito Kuratowski significa que S está no conjunto K ( S ), construído como segue. Escreva M para o conjunto de todos os subconjuntos X de P ( S ) de modo que:

  • X contém o conjunto vazio;
  • Para cada conjunto T em P ( S ), se X contém T, então X também contém a união de T com qualquer singleton.

Em seguida, K ( S ) pode ser definido como a intersecção de M .

Em ZF, Kuratowski finito implica Dedekind finito, mas não vice-versa. No jargão de uma formulação pedagógica popular, quando o axioma da escolha falha gravemente, pode-se ter uma família infinita de meias sem nenhuma maneira de escolher uma meia entre mais do que um número finito de pares. Isso tornaria o conjunto de tais meias Dedekind finito: não pode haver sequência infinita de meias, porque tal sequência permitiria a escolha de uma meia para um número infinito de pares, escolhendo a primeira meia na sequência. No entanto, a finitude de Kuratowski falharia para o mesmo conjunto de meias.

Outros conceitos de finitude

Na teoria dos conjuntos ZF sem o axioma da escolha, os seguintes conceitos de finitude para um conjunto S são distintos. Eles são organizados em ordem estritamente decrescente de intensidade, ou seja, se um conjunto S atende a um critério na lista, ele atende a todos os critérios a seguir. Na ausência do axioma da escolha, as implicações reversas são todas improváveis, mas se o axioma da escolha for assumido, todos esses conceitos são equivalentes. (Observe que nenhuma dessas definições precisa que o conjunto de números ordinais finitos seja definido primeiro; todas são definições puras de "conjuntos teóricos" em termos de igualdade e relações de adesão, não envolvendo ω.)

  • I-finito . Cada conjunto não vazio de subconjuntos de S tem um elemento ⊆-máximo. (Isso é equivalente a exigir a existência de um elemento mínimo ⊆. Também é equivalente ao conceito numérico padrão de finitude.)
  • Ia-finito . Para cada partição de S em dois conjuntos, pelo menos um dos dois conjuntos é I-finito.
  • II-finito . Todo conjunto ⊆-monótono não vazio de subconjuntos de S tem um elemento ⊆-máximo.
  • III-finito . O conjunto de potência P ( S ) é Dedekind finito.
  • IV-finito . S é Dedekind finito.
  • V-finito . ∣ S ∣ = 0 ou 2⋅∣ S ∣> ∣ S |.
  • VI-finito . ∣ S ∣ = 0 ou ∣ S ∣ = 1 ou ∣ S2 > ∣ S ∣.
  • VII-finito . S é I-finito ou não está bem ordenado.

As implicações futuras (de forte para fraco) são teoremas dentro de ZF. Contra-exemplos para as implicações reversas (de fraco a forte) em ZF com urelementos são encontrados usando a teoria do modelo .

A maioria dessas definições de finitude e seus nomes são atribuídos a Tarski 1954 por Howard & Rubin 1998 , p. 278. No entanto, as definições I, II, III, IV e V foram apresentadas em Tarski 1924 , pp. 49, 93, junto com as provas (ou referências a provas) para as implicações futuras. Naquela época, a teoria do modelo não estava suficientemente avançada para encontrar os contra-exemplos.

Cada uma das propriedades I-finito a IV-finito é uma noção de pequenez, no sentido de que qualquer subconjunto de um conjunto com tal propriedade também terá a propriedade. Isso não é verdade para V-finito a VII-finito porque eles podem ter subconjuntos infinitos contáveis.

Veja também

Notas

Referências

links externos