Conjunto finito

ImprimirCitar

Conjunto matemático contendo um número finito de elementos

Na 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 poderia, em princípio, contar e terminar de contar. Por exemplo,

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

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

{1,2,3,ldots }.

Conjuntos finitos são particularmente importantes em combinatória, o estudo matemático da contagem. Muitos argumentos envolvendo conjuntos finitos dependem do princípio da casa dos pombos, 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 houver existe uma bijeção

{displaystyle fcolon Sto {1,ldotsn}}

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

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

{displaystyle x_{1},x_{2},ldotsx_{n}quad (x_{i}in S, 1leq ileq n).}

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

(Aqueles familiarizados com a definição dos números naturais eles mesmos como convencionais na teoria dos conjuntos, a chamada construção de von Neumann, pode preferir usar a existência da bijeção ${displaystyle fcolon Sto n}$ , que é equivalente.)

Propriedades básicas

Qualquer subconjunto próprio de um conjunto finito S é finito e tem menos elementos que o próprio S. Como consequência, não pode existir uma bijeção entre um conjunto finito S e um subconjunto próprio de S. Qualquer conjunto com esta propriedade é chamado Dedekind-finito. Usando os axiomas ZFC padrão para a teoria dos conjuntos, todo conjunto finito de Dedekind também é finito, mas essa implicação não pode ser provada apenas no ZF (axiomas de Zermelo-Fraenkel sem o axioma da 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 de mesma cardinalidade também é uma função sobrejetiva (uma sobrejeção). Da mesma forma, qualquer sobrejeção entre dois conjuntos finitos de mesma cardinalidade também é uma injeção.

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

{displaystyle |Scup T|leq |S|+|T|.}

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

{displaystyle |Scup T|=|S|+|T|-|Scap T|.}

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

{displaystyle |Stimes T|=|S|times |T|.}

Da mesma forma, o produto cartesiano de um número finito de conjuntos finitos é finito. Um conjunto finito com n elementos tem 2ⁿ subconjuntos distintos. Ou seja, o conjunto de potência P(S) de um conjunto finito S é finito, com cardinalidade 2^|S|.

Qualquer subconjunto de um conjunto finito é finito. O conjunto de valores de uma função quando aplicada 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áveis" para significar "contáveis infinitos", portanto, não consideram conjuntos finitos como contáveis.)

A semilattice livre sobre um conjunto finito é o conjunto de seus subconjuntos não vazios, sendo a operação de junção dada pela união de conjuntos.

Condições necessárias e suficientes para finitude

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

S é um conjunto finito. Isso é, S pode ser colocado em uma correspondência one-to-one com o conjunto desses números naturais menos do que algum número natural específico.
(Kazimierz Kuratowski) S tem todas as propriedades que podem ser provadas pela indução matemática começando com o conjunto vazio e adicionando um novo elemento de cada vez. (Ver abaixo para a formulação set-theoretical da finitude Kuratowski.)
(Paul Stäckel) S pode ser dada uma ordem total que é bem ordenada tanto para a frente e para trás. Ou seja, todos os subconjuntos não vazios S tem um mínimo e um maior elemento no subconjunto.
Cada função one-to-one de P(P(S)) em si mesmo está ligado. Isto é, o conjunto de poder do poder S é Dedekind-finite (veja abaixo).
Cada função surjetiva de P(P(S)) em si mesmo é um-para-um.
(Alfred Tarski) Cada família não vazia de subconjuntos de S tem um elemento mínimo em relação à inclusão. (Equivalentemente, cada família não vazia de subconjuntos de S tem um elemento máximo em relação à inclusão.)
S pode ser bem ordenada e quaisquer dois bem-ordens nele são a ordem isomorfo. Em outras palavras, os bem-ordens em S tem exatamente um tipo de ordem.

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

S é um conjunto finito.
(Richard Dedekind) Cada função one-to-one de S em si mesmo está ligado.
Cada função surjetiva de S sobre si mesmo é um-para-um.
S é vazio ou toda ordenação parcial de S contém um elemento máximo.

Questões fundamentais

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

Mesmo para a maioria dos matemáticos que adotam conjuntos infinitos, em certos contextos importantes, a distinção formal entre o finito e o infinito pode permanecer um assunto delicado. 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 de conjuntos hereditariamente finitos que contêm conjuntos infinitos, mas esses conjuntos infinitos parecem finitos de dentro do modelo. (Isso pode acontecer quando o modelo carece dos conjuntos ou funções necessários para testemunhar a infinitude desses conjuntos.) Devido aos 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. Então, pelo menos do ponto de vista da lógica de primeira ordem, só podemos esperar descrever a finitude aproximadamente.

De modo mais geral, noções informais como conjunto, e particularmente conjunto finito, podem receber interpretações em uma variedade de sistemas formais que variam em sua axiomática e aparato lógico. As teorias axiomáticas mais conhecidas incluem a teoria dos conjuntos de Zermelo-Fraenkel (ZF), a teoria dos conjuntos de Zermelo-Fraenkel com o Axioma da Escolha (ZFC), a teoria dos conjuntos de Von Neumann–Bernays–Gödel (NBG), a teoria dos conjuntos não bem fundamentada, A teoria dos tipos de Bertrand Russell e todas as teorias de seus vários modelos. Pode-se também escolher entre 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 set variando de sistema para sistema. Alguns tipos de platônicos podem ver sistemas formais particulares como se aproximando de uma realidade subjacente.

Definições de finitude da teoria de conjuntos

Em contextos onde a noção de número natural se senta logicamente antes de qualquer noção de conjunto, pode-se definir um conjunto S como finito se S admite uma bijeção a algum conjunto de números naturais da forma $<math alttext="{displaystyle {x,|,x(x|x<n?{displaystyle {x,|,x<n}} <img alt="{displaystyle {x,|,x$ . Os matemáticos mais tipicamente escolhem noções básicas de número na teoria dos conjuntos, por exemplo, podem modelar números naturais pelos tipos de ordem de conjuntos bem ordenados finitos. Tal abordagem requer uma definição estrutural de finitude que não depende de números naturais.

Várias propriedades que destacam os conjuntos finitos entre todos os conjuntos na teoria ZFC tornam-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 é chamado de Dedekind infinito se houver uma função injetiva, não-surjetiva $f:Srightarrow S$ . Tal função exibe uma bijeção entre S e um subconjunto adequado de S, nomeadamente a imagem de f. Dado um conjunto infinito Dedekind S, uma função fe um elemento x que não está na imagem de f, podemos formar uma sequência infinita de elementos distintos de S, $x,f(x),f(f(x)),...$ . Por outro lado, dada uma sequência em S consistindo de elementos distintos $x_{1},x_{2},x_{3},...$ , podemos definir uma função f tal que em elementos na sequência ${displaystyle f(x_{i})=x_{i+1}}$ e f comporta-se como a função de identidade de outra forma. Assim, conjuntos infinitos Dedekind contêm subconjuntos que correspondem bijetivamente com os números naturais. Dedekind finito naturalmente significa que cada self-map injetivo também é subjetivo.

A finitude de Kuratowski é definida da seguinte forma. Dado qualquer conjunto S, a operação binária de união dota o powerset P(S) com a estrutura de uma semilattice. Escrevendo K(S) para o sub-semilattice gerado pelo conjunto vazio e pelos singletons, chame o conjunto S Kuratowski finito se S em si pertence a K(S). Intuitivamente, K(S) consiste nos subconjuntos finitos de S. Crucialmente, não é preciso indução, recursão ou uma definição de números naturais para definir gerado por, pois pode-se obter K(S) simplesmente por tomando a interseção de todos os sub-semilattices 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. Kuratowski finito significa que S está no conjunto K(S), construído da seguinte forma. Escreva M para o conjunto de todos os subconjuntos X de P(S) tal 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.

Então K(S) pode ser definido como a interseção de M.

Em ZF, o finito de Kuratowski implica o finito de Dedekind, 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 uma sequência infinita de meias, porque tal sequência permitiria a escolha de uma meia para infinitos 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 força, 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 inversas 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; elas são todas definições "teóricas de conjunto" puras em termos de relações de igualdade e pertinência, não envolvendo ω.)

Eu.... Cada conjunto não vazio de subconjuntos de S tem um elemento ⊆-maximal. (Isso é equivalente a exigir a existência de um elemento ⊆-minimal. Também é equivalente ao conceito numérico padrão de finitude.)
Ia-finite. Para cada partição de S em dois conjuntos, pelo menos um dos dois conjuntos é I-finite. (Um conjunto com esta propriedade que não é I-finite é chamado de um conjunto amorfo.)
II-finito. Cada conjunto não vazio ⊆-monotone de subconjuntos de S tem um elemento ⊆-maximal.
III-finito. O conjunto de energia P(S) é Dedekind finito.
IV-finito. S é Dedekind finito.
V-finito?S| = 0 ou 2 ⋅ |S∣ ∣ ∣S|.
VI-finito?SExecutar = 0 ou;SExecutar = 1S∣²>S|.
VII-finito. S é I-finito ou não bem ordenável.

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

A maioria dessas definições de finitude e seus nomes são atribuídos a Tarski 1954 por Howard & Rubin 1998, pág. 278. No entanto, as definições I, II, III, IV e V foram apresentadas em Tarski 1924, pp. 49, 93, juntamente com provas (ou referências a provas) para as implicações futuras. Naquela época, a teoria dos modelos 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 até VII-finito porque eles podem ter subconjuntos infinitos contáveis.

Contenido relacionado

Más resultados...