Esquema de axioma de substituição - Axiom schema of replacement

Na teoria dos conjuntos , o esquema de axioma de substituição é um esquema de axiomas na teoria dos conjuntos de Zermelo – Fraenkel (ZF) que afirma que a imagem de qualquer conjunto sob qualquer mapeamento definível também é um conjunto. É necessário para a construção de certos conjuntos infinitos em ZF.

O esquema axiomático é motivado pela ideia de que o fato de uma classe ser um conjunto depende apenas da cardinalidade da classe, não da posição de seus elementos. Assim, se uma classe é "pequena o suficiente" para ser um conjunto, e há uma submissão dessa classe para uma segunda classe, o axioma afirma que a segunda classe também é um conjunto. No entanto, como ZFC fala apenas de conjuntos, não de classes próprias, o esquema é declarado apenas para sobreposições definíveis, que são identificadas com suas fórmulas definidoras .

Demonstração

Esquema axiomático de substituição: a imagem do domínio definido sob a função de classe definível é ela própria um conjunto ,.${\ displaystyle F [A]}$${\ displaystyle A}$${\ displaystyle F}$${\ displaystyle B}$

Suponha que haja uma relação binária definível (que pode ser uma classe adequada ) de forma que para cada conjunto exista um único conjunto que se mantenha. Existe uma função definível correspondente , onde se e somente se . Considere a classe (possivelmente adequada) definida de forma que, para cada conjunto , se e somente se houver um with . é chamada de imagem de sob e denotada ou (usando a notação set-builder ) . ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle P (x, y)}$${\ displaystyle F_ {P}}$${\ displaystyle F_ {P} (x) = y}$ ${\ displaystyle P (x, y)}$${\ displaystyle B}$${\ displaystyle y}$${\ displaystyle y \ in B}$${\ displaystyle x \ in A}$${\ displaystyle F_ {P} (x) = y}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle F_ {P}}$${\ displaystyle F_ {P} [A]}$${\ displaystyle \ {F_ {P} (x): x \ in A \}}$

O esquema axioma de substituição afirma que se é uma função de classe definível, como acima, e é qualquer conjunto, então a imagem também é um conjunto. Isso pode ser visto como um princípio de pequenez: o axioma afirma que se é pequeno o suficiente para ser um conjunto, também é pequeno o suficiente para ser um conjunto. Está implícito no axioma mais forte de limitação de tamanho . ${\ displaystyle F}$${\ displaystyle A}$${\ displaystyle F [A]}$${\ displaystyle A}$${\ displaystyle F [A]}$

Como é impossível quantificar funções sobre definíveis na lógica de primeira ordem, uma instância do esquema é incluída para cada fórmula na linguagem da teoria dos conjuntos com variáveis ​​livres entre elas ; mas não é gratuito em . Na linguagem formal da teoria dos conjuntos, o esquema axiomático é: ${\ displaystyle \ phi}$${\ displaystyle w_ {1}, \ dotsc, w_ {n}, A, x, y}$${\ displaystyle B}$${\ displaystyle \ phi}$

${\ displaystyle {\ begin {alinhados} \ forall w_ {1}, \ ldots, w_ {n} \, \ forall A \, ([\ forall x \ in A & \, \ exists! y \, \ phi (x , y, w_ {1}, \ ldots, w_ {n}, A)] \ \ Longrightarrow \ \ existe B \, \ para todos y \, [y \ em B \ Leftrightarrow \ existe x \ em A \, \ phi (x, y, w_ {1}, \ ldots, w_ {n}, A)]) \ end {alinhado}}}$

Para saber o significado de , consulte quantificação de exclusividade . ${\ displaystyle \ existe!}$

Para maior clareza, no caso de nenhuma variável , isso simplifica para: ${\ displaystyle w_ {i}}$

${\ displaystyle {\ begin {alinhado} \ forall A \, ([\ forall x \ in A & \, \ exists! y \, \ phi (x, y, A)] \ \ Longrightarrow \ \ exists B \, \ forall y \, [y \ in B \ Leftrightarrow \ existe x \ in A \, \ phi (x, y, A)]) \ end {alinhado}}}$

Assim, sempre que especifica uma correspondência -para- única , semelhante a uma função on , então todos alcançados dessa forma podem ser reunidos em um conjunto semelhante a . ${\ displaystyle \ phi}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle F}$${\ displaystyle A}$${\ displaystyle y}$${\ displaystyle B}$${\ displaystyle F [A]}$

Formulários

O esquema axiomático de substituição não é necessário para as provas da maioria dos teoremas da matemática comum. Na verdade, a teoria dos conjuntos de Zermelo (Z) já pode interpretar a aritmética de segunda ordem e muito da teoria dos tipos em tipos finitos, que por sua vez são suficientes para formalizar a maior parte da matemática. Embora o esquema de axioma de substituição seja um axioma padrão na teoria dos conjuntos hoje, ele é frequentemente omitido dos sistemas da teoria dos tipos e dos sistemas de base da teoria dos topos .

De qualquer forma, o esquema do axioma aumenta drasticamente a força de ZF, tanto em termos dos teoremas que ele pode provar - por exemplo, os conjuntos que mostraram existir - quanto em termos de sua força de consistência teórica de prova , em comparação com Z. exemplos a seguir:

• Usando a definição moderna de von Neumann , provar a existência de qualquer limite ordinal maior que ω requer a substituição do axioma. O número ordinal ω · 2 = ω + ω é o primeiro ordinal. O axioma do infinito afirma a existência de um conjunto infinito ω = {0, 1, 2, ...}. Pode-se esperar definir ω · 2 como a união da sequência {ω, ω + 1, ω + 2, ...}. No entanto, essas classes arbitrárias de ordinais não precisam ser conjuntos - por exemplo, a classe de todos os ordinais não é um conjunto. A substituição agora permite substituir cada número finito n em ω com o correspondente ω + n , garantindo assim que essa classe seja um conjunto. Como esclarecimento, observe que pode-se facilmente construir um conjunto bem ordenado isomórfico a ω · 2 sem recorrer à substituição - basta tomar a união disjunta de duas cópias de ω, com a segunda cópia maior que a primeira - mas isso não é um ordinal, pois não é totalmente ordenado por inclusão.
• Ordinais maiores dependem da substituição menos diretamente. Por exemplo, w ₁ , o primeiro ordinal incontável , pode ser construído como se segue - o conjunto de ordens bem contáveis existe como um subconjunto dos por separação e powerset (uma relação em A é um subconjunto de , e assim por um elemento do conjunto de alimentação . Um conjunto de relações é, portanto, um subconjunto de )). Substitua cada conjunto bem ordenado por seu ordinal. Este é o conjunto de ordinais contáveis ​​ω ₁ , que pode ser mostrado como incontável. A construção usa substituição duas vezes; uma vez para garantir uma atribuição ordinal para cada conjunto bem ordenado e novamente para substituir os conjuntos bem ordenados por seus ordinais. Este é um caso especial do resultado do número de Hartogs , e o caso geral pode ser provado de forma semelhante.${\ displaystyle P ({\ mathbb {N}} \ times {\ mathbb {N}})}$${\ displaystyle A \ times A}$ ${\ displaystyle P (A \ times A)}$${\ displaystyle P (A \ times A)}$
• À luz do acima, a existência de uma atribuição de um ordinal para cada conjunto bem ordenado também requer substituição. Da mesma forma, a atribuição cardinal de von Neumann, que atribui um número cardinal a cada conjunto, requer substituição, bem como axioma de escolha .
• Para conjuntos de tuplas recursivamente definidos como e para grandes , o conjunto tem uma classificação muito alta para que sua existência possa ser demonstrada a partir da teoria dos conjuntos apenas com o axioma do conjunto de potência, escolha e sem substituição.${\ displaystyle A ^ {n} = A ^ {n-1} \ vezes A}$${\ displaystyle A}$${\ displaystyle \ {A ^ {n} \ mid n \ in {\ mathbb {N}} \}}$
• Da mesma forma, Harvey Friedman mostrou que a substituição é necessária para mostrar que os conjuntos de Borel são determinados . O resultado é comprovada Donald A. Martin 's Borel determinacy teorema .
• ZF com substituição prova a consistência de Z, pois o conjunto V _{ω · 2} é um modelo de Z cuja existência pode ser comprovada em ZF. O número cardinal é o primeiro que pode ser demonstrado que existe em ZF, mas não em Z. Para esclarecimento, observe que o segundo teorema da incompletude de Gödel mostra que cada uma dessas teorias contém uma frase, "expressando" a própria consistência da teoria, que é improvável nessa teoria, se essa teoria for consistente - esse resultado é frequentemente expresso de forma vaga como a afirmação de que nenhuma dessas teorias pode provar sua própria consistência, se for consistente.${\ displaystyle \ aleph _ {\ omega}}$

Relação com outros esquemas de axioma

Coleção

Esquema axiomático de coleção: a imagem do domínio definido sob a função de classe definível cai dentro de um conjunto .${\ displaystyle f [A]}$${\ displaystyle A}$${\ displaystyle f}$${\ displaystyle B}$

O esquema axioma de coleta está intimamente relacionado e freqüentemente confundido com o esquema axioma de substituição. No restante dos axiomas ZF, é equivalente ao esquema de axioma de substituição. O axioma da coleta é mais forte do que a substituição na ausência do axioma do conjunto de poder ou sua contraparte construtiva de ZF, mas mais fraco no quadro de IZF, que carece da lei do meio excluído .

Enquanto a substituição pode ser lida para dizer que a imagem de uma função é um conjunto, a coleção fala sobre imagens de relações e então apenas diz que alguma superclasse da imagem da relação é um conjunto. Em outras palavras, o conjunto resultante não tem requisito de minimalidade, ou seja, essa variante também não tem o requisito de exclusividade em . Ou seja, a relação definida por não precisa ser uma função - alguns podem corresponder a muitos em . Nesse caso, o conjunto de imagens cuja existência é afirmada deve conter pelo menos um para cada no conjunto original, sem garantia de que conterá apenas um. ${\ displaystyle B}$${\ displaystyle \ phi}$${\ displaystyle \ phi}$${\ displaystyle x \ in A}$${\ displaystyle y}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle y}$${\ displaystyle x}$

Suponha que as variáveis ​​livres de estão entre ; mas nem nem está livre em . Então, o esquema do axioma é: ${\ displaystyle \ phi}$${\ displaystyle w_ {1}, \ dotsc, w_ {n}, x, y}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle \ phi}$

${\ displaystyle \ forall w_ {1}, \ ldots, w_ {n} \, [(\ forall x \, \ exists \, y \ phi (x, y, w_ {1}, \ ldots, w_ {n} )) \ Rightarrow \ forall A \, \ existe B \, \ forall x \ in A \, \ existe y \ in B \, \ phi (x, y, w_ {1}, \ ldots, w_ {n}) ]}$

O esquema axiomático às vezes é declarado sem restrições anteriores (além de não ocorrer livremente ) no predicado : ${\ displaystyle B}$${\ displaystyle \ phi}$${\ displaystyle \ phi}$

${\ displaystyle \ forall w_ {1}, \ ldots, w_ {n} \, \ forall A \, \ exists B \, \ forall x \ in A \, [\ exists y \ phi (x, y, w_ { 1}, \ ldots, w_ {n}) \ Rightarrow \ existe y \ em B \, \ phi (x, y, w_ {1}, \ ldots, w_ {n})]}$

Nesse caso, pode haver elementos em que não estejam associados a nenhum outro conjunto por . No entanto, o esquema de axioma conforme declarado requer que, se um elemento de estiver associado a pelo menos um conjunto , o conjunto de imagens conterá pelo menos um desses . O esquema axiomático resultante também é chamado de esquema axioma de limitação . ${\ displaystyle x}$${\ displaystyle A}$${\ displaystyle \ phi}$${\ displaystyle x}$${\ displaystyle A}$${\ displaystyle y}$${\ displaystyle B}$${\ displaystyle y}$

Separação

O esquema de axioma de separação , o outro esquema de axioma em ZFC, está implícito no esquema de axioma de substituição e no axioma de conjunto vazio . Lembre-se de que o esquema axiomático de separação inclui

${\ displaystyle \ forall A \, \ exists B \, \ forall C \, (C \ in B \ Leftrightarrow [C \ in A \ land \ theta (C)])}$

para cada fórmula na linguagem da teoria dos conjuntos em que não é livre. ${\ displaystyle \ theta}$${\ displaystyle B}$

A prova é a seguinte. Comece com uma fórmula que não mencione e um conjunto . Se nenhum elemento de satisfaz, então o conjunto desejado pela instância relevante do esquema axiomático de separação é o conjunto vazio. Caso contrário, escolha um fixo em que se mantenha. Defina uma função de classe que, para qualquer elemento , se mantém e se é falso. Então, a imagem de sob , isto é, o conjunto , existe (pelo axioma da substituição) e é precisamente o conjunto necessário para o axioma da separação. ${\ displaystyle \ theta (C)}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle E}$${\ displaystyle A}$${\ displaystyle \ theta (E)}$${\ displaystyle B}$${\ displaystyle E}$${\ displaystyle A}$${\ displaystyle \ theta (E)}$${\ displaystyle F}$${\ displaystyle D}$${\ displaystyle F (D) = D}$${\ displaystyle \ theta (D)}$${\ displaystyle F (D) = E}$${\ displaystyle \ theta (D)}$${\ displaystyle A}$${\ displaystyle F}$${\ displaystyle B = F''A: = \ {F (x): x \ in A \} = A \ cap \ {x: \ theta (x) \}}$${\ displaystyle B}$

Este resultado mostra que é possível axiomatizar ZFC com um único esquema de axioma infinito. Como pelo menos um desses esquemas infinitos é necessário (ZFC não é finitamente axiomatizável), isso mostra que o esquema de axioma de substituição pode ser o único esquema de axioma infinito em ZFC, se desejado. Como o esquema axiomático de separação não é independente, às vezes é omitido das afirmações contemporâneas dos axiomas de Zermelo-Fraenkel.

A separação ainda é importante, no entanto, para uso em fragmentos de ZFC, por causa de considerações históricas, e para comparação com axiomatizações alternativas da teoria dos conjuntos. Uma formulação da teoria dos conjuntos que não inclua o axioma da substituição provavelmente incluirá alguma forma do axioma da separação, para garantir que seus modelos contenham uma coleção de conjuntos suficientemente rica. No estudo de modelos de teoria dos conjuntos, às vezes é útil considerar modelos de ZFC sem substituição, como os modelos na hierarquia de von Neumann. ${\ displaystyle V _ {\ delta}}$

A prova acima usa a lei do meio excluído ao assumir que se não é vazio, então deve conter um elemento (na lógica intuicionista, um conjunto é "vazio" se não contém um elemento, e "não vazio" é a negação formal deste , que é mais fraco do que "contém um elemento"). O axioma da separação está incluído na teoria dos conjuntos intuicionista . ${\ displaystyle A}$

História

O esquema axiomático de substituição não fazia parte da axiomatização da teoria dos conjuntos de Ernst Zermelo de 1908 ( Z ). Alguma aproximação informal a ele existia nas obras não publicadas de Cantor , e apareceu novamente informalmente em Mirimanoff (1917).

Abraham Fraenkel, entre 1939 e 1949

Thoralf Skolem, na década de 1930

Sua publicação por Abraham Fraenkel em 1922 é o que torna a teoria dos conjuntos moderna Zermelo- Fraenkel a teoria dos conjuntos ( ZFC ). O axioma foi descoberto e anunciado de forma independente por Thoralf Skolem mais tarde no mesmo ano (e publicado em 1923). O próprio Zermelo incorporou o axioma de Fraenkel em seu sistema revisado que publicou em 1930, que também incluiu como um novo axioma de fundação de von Neumann . Embora seja a versão de primeira ordem de Skolem da lista de axiomas que usamos hoje, ele geralmente não recebe nenhum crédito, pois cada axioma individual foi desenvolvido anteriormente por Zermelo ou Fraenkel. A frase “teoria dos conjuntos de Zermelo-Fraenkel” foi impressa pela primeira vez por von Neumann em 1928.

Zermelo e Fraenkel se corresponderam intensamente em 1921; o axioma da substituição foi um tópico importante dessa troca. Fraenkel iniciou correspondência com Zermelo em algum momento de março de 1921. Suas cartas anteriores à datada de 6 de maio de 1921 foram perdidas. Zermelo admitiu pela primeira vez a existência de uma lacuna em seu sistema em uma resposta a Fraenkel datada de 9 de maio de 1921. Em 10 de julho de 1921, Fraenkel concluiu e submeteu para publicação um artigo (publicado em 1922) que descreveu seu axioma como permitindo substituições arbitrárias: "Se M é um conjunto e cada elemento de M é substituído por [um conjunto ou um urelemento], então M se transforma em um conjunto novamente "(conclusão entre parênteses e tradução por Ebbinghaus). A publicação de Fraenkel em 1922 agradeceu a Zermelo por argumentos úteis. Antes desta publicação, Fraenkel anunciou publicamente seu novo axioma em uma reunião da Sociedade Alemã de Matemática realizada em Jena em 22 de setembro de 1921. Zermelo estava presente nesta reunião; na discussão que se seguiu à palestra de Fraenkel, ele aceitou o axioma da substituição em termos gerais, mas expressou reservas quanto à sua extensão.

Thoralf Skolem tornou pública sua descoberta da lacuna no sistema de Zermelo (a mesma lacuna que Fraenkel havia encontrado) em uma palestra que proferiu em 6 de julho de 1922 no 5º Congresso de Matemáticos Escandinavos , realizado em Helsinque ; os procedimentos deste congresso foram publicados em 1923. Skolem apresentou uma resolução em termos de substituições definíveis de primeira ordem: "Seja U uma proposição definida que se aplica a certos pares ( a , b ) no domínio B ; assuma ainda, que para todo a existe no máximo um b tal que U é verdadeiro. Então, como a abrange os elementos de um conjunto M _a , b abrange todos os elementos de um conjunto M _b . " No mesmo ano, Fraenkel escreveu uma resenha do artigo de Skolem, na qual Fraenkel simplesmente afirmou que as considerações de Skolem correspondem às suas.

O próprio Zermelo nunca aceitou a formulação de Skolem do esquema de axioma da substituição. A certa altura, ele chamou a abordagem de Skolem de “teoria dos conjuntos dos empobrecidos”. Zermelo imaginou um sistema que permitiria grandes cardeais . Ele também se opôs fortemente às implicações filosóficas dos modelos contáveis ​​da teoria dos conjuntos , que se seguiram à axiomatização de primeira ordem de Skolem. De acordo com a biografia de Zermelo por Heinz-Dieter Ebbinghaus , a desaprovação de Zermelo da abordagem de Skolem marcou o fim da influência de Zermelo nos desenvolvimentos da teoria e lógica dos conjuntos.

Referências

• Ebbinghaus, Heinz-Dieter (2007), Ernst Zermelo: An Approach to His Life and Work , Springer Science & Business Media, ISBN 978-3-540-49553-6.
• Halmos, Paul R. (1974) [1960], Naive Set Theory , Springer-Verlag, ISBN 0-387-90092-6.
• Jech, Thomas (2003), Set Theory: The Third Millennium Edition, Revised and Expanded , Springer, ISBN 3-540-44085-2.
• Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs , Elsevier, ISBN 0-444-86839-9.