Axioma de regularidade - Axiom of regularity

Em matemática , o axioma da regularidade (também conhecido como o axioma da base ) é um axioma da teoria dos conjuntos Zermelo-Fraenkel que estabelece que todos os não-vazia conjunto Um contém um elemento que é separado a partir de uma . Na lógica de primeira ordem , o axioma diz:

{\ displaystyle \ forall x \, (x \ neq \ varnothing \ rightarrow \ existe y (y \ in x \ \ land y \ cap x = \ varnothing)).}

O axioma da regularidade junto com o axioma do emparelhamento implica que nenhum conjunto é um elemento de si mesmo, e que não há sequência infinita ( a _n ) tal que a _{i + 1} seja um elemento de a _i para todo i . Com o axioma da escolha dependente (que é uma forma enfraquecida do axioma da escolha ), esse resultado pode ser revertido: se não houver essas sequências infinitas, então o axioma da regularidade é verdadeiro. Portanto, neste contexto, o axioma da regularidade é equivalente à sentença de que não há cadeias de filiação infinitas descendentes.

O axioma foi introduzido por von Neumann (1925) ; foi adotada em formulação mais próxima à encontrada nos livros contemporâneos de Zermelo (1930) . Praticamente todos os resultados nos ramos da matemática baseados na teoria dos conjuntos se mantêm mesmo na ausência de regularidade; veja o capítulo 3 de Kunen (1980) . No entanto, a regularidade torna algumas propriedades dos ordinais mais fáceis de provar; e não apenas permite que a indução seja feita em conjuntos bem ordenados, mas também em classes próprias que são estruturas relacionais bem fundadas , como a ordenação lexicográfica em ${\ displaystyle \ {(n, \ alpha) \ mid n \ in \ omega \ land \ alpha {\ text {é um ordinal}} \} \ ,.}$

Dados os outros axiomas da teoria dos conjuntos de Zermelo – Fraenkel, o axioma da regularidade é equivalente ao axioma da indução . O axioma da indução tende a ser usado no lugar do axioma da regularidade nas teorias intuicionistas (aquelas que não aceitam a lei do meio excluído ), onde os dois axiomas não são equivalentes.

Além de omitir o axioma da regularidade, as teorias dos conjuntos não padronizados de fato postularam a existência de conjuntos que são elementos de si mesmos.

Implicações elementares da regularidade

Nenhum conjunto é um elemento de si mesmo

Seja A um conjunto e aplique o axioma de regularidade a { A }, que é um conjunto pelo axioma do emparelhamento . Vemos que deve haver um elemento de { A } que é separado de { A }. Visto que o único elemento de { A } é A , deve ser que A seja separado de { A }. Então, visto que , não podemos ter A ∈ A (pela definição de disjunto ). ${\ displaystyle A \ cap \ {A \} = \ varnothing}$

Não existe uma sequência decrescente infinita de conjuntos

Suponha, ao contrário, que haja uma função , f , nos números naturais com f ( n +1) um elemento de f ( n ) para cada n . Defina S = { f ( n ): n um número natural}, o intervalo de f , que pode ser visto como um conjunto do esquema de axioma de substituição . Aplicando o axioma de regularidade para S , deixe- B ser um elemento de S que está separado de S . Pela definição de S , B deve ser f ( k ) para algum número natural k . No entanto, nos é dado que F ( k ) contém f ( k + 1), o qual também é um elemento de S . Assim, f ( k + 1) está na intersecção de f ( k ) e S . Isso contradiz o fato de que são conjuntos disjuntos. Uma vez que nossa suposição levou a uma contradição, não deve haver tal função, f .

A inexistência de um conjunto contendo a si mesmo pode ser vista como um caso especial em que a sequência é infinita e constante.

Observe que esse argumento se aplica apenas a funções f que podem ser representadas como conjuntos, em oposição a classes indefiníveis. Os conjuntos hereditariamente finitos , V _ω , satisfazem o axioma de regularidade (e todos os outros axiomas de ZFC, exceto o axioma do infinito ). Portanto, se formarmos um ultrapower não trivial de V _ω , ele também irá satisfazer o axioma de regularidade. O modelo resultante conterá elementos, chamados de números naturais não padronizados, que satisfazem a definição de números naturais nesse modelo, mas não são realmente números naturais. Eles são números naturais falsos que são "maiores" do que qualquer número natural real. Este modelo conterá sequências descendentes infinitas de elementos. Por exemplo, suponha que n seja um número natural não padrão, então e , e assim por diante. Para qualquer número natural real K , . Esta é uma sequência descendente interminável de elementos. Mas essa sequência não é definível no modelo e, portanto, não é um conjunto. Portanto, nenhuma contradição com a regularidade pode ser provada. ${\ displaystyle (n-1) \ in n}$ ${\ displaystyle (n-2) \ in (n-1)}$ ${\ displaystyle (nk-1) \ in (nk)}$

Definição teórica de conjunto mais simples do par ordenado

O axioma de regularidade permite definir o par ordenado ( a , b ) como { a , { a , b }}; veja o par ordenado para detalhes. Esta definição elimina um par de colchetes da definição canônica de Kuratowski ( a , b ) = {{ a }, { a , b }}.

Cada conjunto tem uma classificação ordinal

Essa era na verdade a forma original do axioma na axiomatização de von Neumann.

Suponha que x seja qualquer conjunto. Seja t o fechamento transitivo de { x }. Seja u o subconjunto de t consistindo de conjuntos não classificados. Se u estiver vazio, então x será classificado e pronto. Caso contrário, aplique o axioma de regularidade a u para obter um elemento w de u que é separado de u . Como w está em u , w não está classificado. w é um subconjunto de t pela definição de fechamento transitivo. Como w é separado de u , cada elemento de w é classificado. Aplicando os axiomas de substituição e união para combinar as classificações dos elementos de w , obtemos uma classificação ordinal para w , a saber . Isso contradiz a conclusão de que w não está classificado. Portanto, a suposição de que u era não vazio deve ser falsa e x deve ter classificação. ${\ displaystyle \ textstyle \ operatorname {rank} (w) = \ cup \ {\ operatorname {rank} (z) +1 \ mid z \ in w \}}$

Para cada dois conjuntos, apenas um pode ser um elemento do outro

Sejam X e Y conjuntos. Em seguida, aplique o axioma de regularidade ao conjunto { X , Y } (que existe pelo axioma de emparelhamento). Vemos que deve haver um elemento de { X , Y } que também é separado dele. Deve ser quer X ou Y . Pela definição de disjunto, então, devemos ter Y não é um elemento de X ou vice-versa.

O axioma da escolha dependente e nenhuma sequência descendente infinita de conjuntos implica regularidade

Seja o conjunto não vazio S um contra-exemplo ao axioma da regularidade; isto é, cada elemento de S tem uma intersecção não-vazia com S . Definimos uma relação binária R em S por , que é inteira por suposição. Assim, pelo princípio da escolha dependente, existe alguma sequência ( um _n ) em S satisfazendo um _n Ra _{n + 1} para todos os n em N . Como se trata de uma cadeia descendente infinita, chegamos a uma contradição e, portanto, esse S não existe. ${\ displaystyle aRb: \ Leftrightarrow b \ in S \ cap a}$

Regularidade e o resto dos axiomas ZF (C)

A regularidade mostrou ser relativamente consistente com o resto de ZF por Skolem (1923) e von Neumann (1929) , o que significa que se ZF sem regularidade é consistente, então ZF (com regularidade) também é consistente. Para sua prova em notação moderna, veja Vaught (2001 , §10.1), por exemplo.

O axioma de regularidade também se mostrou independente dos outros axiomas de ZF (C), supondo que sejam consistentes. O resultado foi anunciado por Paul Bernays em 1941, embora ele não publicasse uma prova até 1954. A prova envolve (e levou ao estudo de) modelos de permutação (ou método) de Rieger-Bernays , que foram usados para outras provas de independência para sistemas não bem fundamentados ( Rathjen 2004 , p. 193 e Forster 2003 , pp. 210–212).

Regularidade e o paradoxo de Russell

A teoria dos conjuntos ingênua (o esquema axioma da compreensão irrestrita e o axioma da extensionalidade ) é inconsistente devido ao paradoxo de Russell . Nas primeiras formalizações de conjuntos, matemáticos e lógicos evitaram essa contradição substituindo o esquema axiomático de compreensão pelo esquema axiomático de separação, muito mais fraco . No entanto, esta etapa por si só leva a teorias de conjuntos que são considerados muito fracos. Portanto, parte do poder de compreensão foi adicionado de volta por meio dos outros axiomas de existência da teoria dos conjuntos de ZF (emparelhamento, união, conjunto de poderes, substituição e infinito) que podem ser considerados como casos especiais de compreensão. Até agora, esses axiomas não parecem levar a qualquer contradição. Posteriormente, o axioma de escolha e o axioma de regularidade foram adicionados para excluir modelos com algumas propriedades indesejáveis. Esses dois axiomas são conhecidos por serem relativamente consistentes.

Na presença do esquema axioma de separação, o paradoxo de Russell torna-se uma prova de que não existe um conjunto de todos os conjuntos . O axioma da regularidade junto com o axioma do emparelhamento também proíbe esse conjunto universal. No entanto, o paradoxo de Russell fornece uma prova de que não existe um "conjunto de todos os conjuntos" usando o esquema de axioma da separação sozinho, sem quaisquer axiomas adicionais. Em particular, ZF sem o axioma da regularidade já proíbe tal conjunto universal.

Se uma teoria é estendida pela adição de um axioma ou axiomas, então quaisquer consequências (possivelmente indesejáveis) da teoria original permanecem consequências da teoria estendida. Em particular, se ZF sem regularidade é estendido adicionando regularidade para obter ZF, então qualquer contradição (como o paradoxo de Russell) que se seguiu da teoria original ainda seguiria na teoria estendida.

A existência de átomos de Quine (conjuntos que satisfazem a fórmula da equação x = { x }, ou seja, têm a si próprios como seus únicos elementos) é consistente com a teoria obtida removendo o axioma de regularidade de ZFC. Várias teorias de conjuntos não bem fundamentadas permitem conjuntos circulares "seguros", como os átomos de Quine, sem se tornarem inconsistentes por meio do paradoxo de Russell.

Regularidade, hierarquia cumulativa e tipos

Na ZF pode-se comprovar que a classe , chamada de universo de von Neumann , é igual à classe de todos os conjuntos. Esta afirmação é até equivalente ao axioma de regularidade (se trabalharmos em ZF com este axioma omitido). A partir de qualquer modelo que não satisfaça o axioma de regularidade, um modelo que o satisfaça pode ser construído tomando apenas conjuntos . ${\ displaystyle \ bigcup _ {\ alpha} V _ {\ alpha}}$ ${\ displaystyle \ bigcup _ {\ alpha} V _ {\ alpha}}$

Herbert Enderton ( 1977 , p. 206) escreveu que "A ideia de posição é um descendente do conceito de tipo de Russell ". Comparando ZF com a teoria dos tipos , Alasdair Urquhart escreveu que "o sistema de Zermelo tem a vantagem de notação de não conter nenhuma variável explicitamente digitada, embora na verdade possa ser visto como tendo uma estrutura de tipo implícita construída nele, pelo menos se o axioma de regularidade é incluídos. Os detalhes desta tipagem implícita são explicitados em [Zermelo 1930] , e novamente em um artigo bem conhecido de George Boolos [Boolos 1971] . "

Dana Scott ( 1974 ) foi mais longe e afirmou que:

A verdade é que só existe uma maneira satisfatória de evitar os paradoxos: a saber, o uso de alguma forma da teoria dos tipos . Isso estava na base das intuições de Russell e Zermelo. Na verdade, a melhor maneira de considerar a teoria de Zermelo é como uma simplificação e extensão da de Russell. (Queremos dizer a teoria simples dos tipos de Russell, é claro.) A simplificação era tornar os tipos cumulativos . Assim, a mistura de tipos é mais fácil e as repetições irritantes são evitadas. Uma vez que os tipos posteriores podem acumular os anteriores, podemos facilmente imaginar a extensão dos tipos ao transfinito - o quão longe queremos ir deve necessariamente ser deixado em aberto. Agora Russell tornou seus tipos explícitos em sua notação e Zermelo os deixou implícitos . [ênfase no original]

No mesmo artigo, Scott mostra que um sistema axiomático baseado nas propriedades inerentes da hierarquia cumulativa acaba sendo equivalente a ZF, incluindo regularidade.

História

O conceito de fundamento e posição de um conjunto foram ambos introduzidos por Dmitry Mirimanoff ( 1917 ) cf. Lévy (2002 , p. 68) e Hallett (1996 , §4.4, esp. P. 186, 188). Mirimanoff chamou um conjunto x de "regular" (francês: "ordinaire") se toda cadeia descendente x ∋ x ₁ ∋ x ₂ ∋ ... for finita. Mirimanoff, entretanto, não considerou sua noção de regularidade (e bem fundada) como um axioma a ser observado por todos os conjuntos; em artigos posteriores, Mirimanoff também explorou o que agora é chamado de conjuntos não bem fundamentados ("extraordinaire" na terminologia de Mirimanoff).

Skolem (1923) e von Neumann (1925) apontaram que conjuntos não bem fundados são supérfluos (na p. 404 na tradução de van Heijenoort ) e na mesma publicação von Neumann dá um axioma (p. 412 na tradução) que exclui alguns, mas não todos, conjuntos não bem fundamentados. Em uma publicação subsequente, von Neumann (1928) deu o seguinte axioma (traduzido em notação moderna por A. Rieger):

{\ displaystyle \ forall x \, (x \ neq \ emptyset \ rightarrow \ existe y \ em x \, (y \ cap x = \ emptyset))}

.

Regularidade na presença de urelementos

Urelementos são objetos que não são conjuntos, mas que podem ser elementos de conjuntos. Na teoria dos conjuntos ZF, não há urelementos, mas em algumas outras teorias de conjuntos, como ZFA , existem. Nessas teorias, o axioma da regularidade deve ser modificado. A declaração " " deve ser substituída por uma declaração que não esteja vazia e não seja um elemento. Uma substituição adequada é , que afirma que x é habitado . ${\ displaystyle x \ neq \ emptyset}$ ${\ displaystyle x}$ ${\ displaystyle (\ exists y) [y \ in x]}$

Veja também

Referências

^ Rieger 2011 , pp. 175,178.
^ Urquhart 2003 , p. 305.
^ Lévy 2002 , p. 73
^ Halbeisen 2012 , pp. 62–63.
^ Sangiorgi 2011 , pp. 17–19, 26.
^ Rieger 2011 , p. 179

Origens

Bernays, Paul Isaac (1941), "Um sistema de teoria dos conjuntos axiomática. Parte II", The Journal of Symbolic Logic , 6 (1): 1-17, doi : 10.2307 / 2267281 , JSTOR 2267281
Bernays, Paul Isaac (1954), "Um sistema de teoria dos conjuntos axiomática. Parte VII" (PDF) , The Journal of Symbolic Logic , 19 (2): 81-96, doi : 10.2307 / 2268864 , JSTOR 2268864
Boolos, George (1971), "The iterative conception of set", Journal of Philosophy , 68 (8): 215–231, doi : 10.2307 / 2025204 , JSTOR 2025204reimpresso em Boolos, George (1998), Logic, Logic and Logic , Harvard University Press, pp. 13-29
Enderton, Herbert B. (1977), Elements of Set Theory , Academic Press
Forster, T. (2003), Logic, induction and sets , Cambridge University Press
Halbeisen, Lorenz J. (2012), Teoria dos conjuntos combinatórios: com uma introdução suave ao forçamento , Springer
Hallett, Michael (1996) [publicado pela primeira vez em 1984], Teoria dos conjuntos Cantoriana e limitação de tamanho , Oxford University Press, ISBN 978-0-19-853283-5
Jech, Thomas (2003), Set Theory: The Third Millennium Edition, Revised and Expanded , Springer, ISBN 978-3-540-44085-7
Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs , Elsevier, ISBN 978-0-444-86839-8
Lévy, Azriel (2002) [publicado pela primeira vez em 1979], Teoria dos conjuntos básicos , Mineola, Nova York: Dover Publications, ISBN 978-0-486-42079-0
Mirimanoff, D. (1917), "Les antinomies de Russell et de Burali-Forti et le probleme fondamental de la theory des ensembles", L'Enseignement Mathématique , 19 : 37-52
Rathjen, M. (2004), "Predicativity, Circularity, and Anti-Foundation" (PDF) , em Link, Godehard (ed.), One Hundred Years of Russell ́s Paradox: Mathematics, Logic, Philosophy , Walter de Gruyter, ISBN 978-3-11-019968-0
Rieger, Adam (2011), "Paradox, ZF, and the Axiom of Foundation" (PDF) , em DeVidi, David; Hallett, Michael; Clark, Peter (eds.), Logic, Mathematics, Philosophy, Vintage Enthusiasms. Ensaios em honra de John L. Bell. , The Western Ontario Series in Philosophy of Science, 75 , pp. 171-187, CiteSeerX 10.1.1.100.9052 , doi : 10.1007 / 978-94-007-0214-1_9 , ISBN 978-94-007-0213-4
Riegger, L. (1957), "Uma contribuição para a teoria dos conjuntos axiomáticos de Gödel" (PDF) , Czechoslovak Mathematical Journal , 7 (3): 323-357, doi : 10.21136 / CMJ.1957.100254
Sangiorgi, Davide (2011), "Origins of bisimulation and coinduction", em Sangiorgi, Davide; Rutten, Jan (eds.), Advanced Topics in Bisimulation and Coinduction , Cambridge University Press
Scott, Dana Stewart (1974), "Axiomatizing set theory", Axiomatic set theory. Proceedings of Symposia in Pure Mathematics Volume 13, Parte II , pp. 207-214
Skolem, Thoralf (1923), teoria dos conjuntos axiomatizadosReimpresso em From Frege to Gödel , van Heijenoort, 1967, na tradução inglesa de Stefan Bauer-Mengelberg, pp. 291–301.
Urquhart, Alasdair (2003), "The Theory of Types", em Griffin, Nicholas (ed.), The Cambridge Companion to Bertrand Russell , Cambridge University Press
Vaught, Robert L. (2001), Set Theory: An Introduction (2ª ed.), Springer, ISBN 978-0-8176-4256-3
von Neumann, John (1925), "Eine axiomatiserung der Mengenlehre", Journal für die Reine und Angewandte Mathematik , 154 : 219-240; tradução em van Heijenoort, Jean (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 , pp. 393-413
von Neumann, John (1928), "Über die Definition durch transfinite Induktion und verwandte Fragen der allgemeinen Mengenlehre", Mathematische Annalen , 99 : 373-391, doi : 10.1007 / BF01459102 , S2CID 120784562
von Neumann, John (1929), "Uber eine Widerspruchfreiheitsfrage in der axiomatischen Mengenlehre", Journal für die Reine und Angewandte Mathematik , 1929 (160): 227–241, doi : 10.1515 / crll.1929.160.227 , S2CID 199545822
Zermelo, Ernst (1930), "Über Grenzzahlen und Mengenbereiche. Neue Untersuchungen über die Grundlagen der Mengenlehre." (PDF) , Fundamenta Mathematicae , 16 : 29-47, doi : 10.4064 / fm-16-1-29-47; tradução em Ewald, WB, ed. (1996), De Kant a Hilbert: Um Livro Fonte em Foundations of Mathematics Vol. 2 , Clarendon Press, pp. 1219–33

links externos

Axioma da fundação no PlanetMath .
Conjunto habitado e o axioma de fundação no nLab

[FOOTNOTERieger2011175,178-1] Rieger 2011 , pp. 175,178.

[FOOTNOTEUrquhart2003305-2] Urquhart 2003 , p. 305.

[FOOTNOTELévy200273-3] Lévy 2002 , p. 73

[FOOTNOTEHalbeisen201262–63-4] Halbeisen 2012 , pp. 62–63.

[FOOTNOTESangiorgi201117–19,_26-5] Sangiorgi 2011 , pp. 17–19, 26.

[FOOTNOTERieger2011179-6] Rieger 2011 , p. 179

Languages

In other projects