A versão hereditária dessa noção de finitude fraca não é trivial?
Diga que é um conjunto $X$ é $\Pi^1_1$-pseudofinite se cada frase de primeira ordem $\varphi$ com um modelo com conjunto subjacente $X$tem um modelo finito. A existência de infinito$\Pi^1_1$-conjuntos de pseudofinitos são consistentes com $\mathsf{ZF}$, uma vez que, de fato, todo conjunto amorfo é$\Pi^1_1$-pseudofinite .
Talvez surpreendentemente, não está imediatamente claro se a classe de$\Pi^1_1$-conjuntos pseudofinitos precisam ser fechados em uniões finitas. Minha pergunta é o que acontece quando consertamos essa fraqueza pela força bruta:
É consistente com $\mathsf{ZF}$que existe um infinito hereditariamente $\Pi^1_1$-conjunto pseudofinito - isto é, um conjunto infinito $X$ tal que sempre $Y$ é $\Pi^1_1$-pseudofinite, $X\cup Y$ é também $\Pi^1_1$-pseudofinite?
Observe que o hereditariamente $\Pi^1_1$-conjuntos pseudofinitos são fechados sob uniões finitas, então isso realmente "conserta" a situação acima. Uma esperança natural é que os conjuntos amorfos façam o truque novamente, mas não vejo como - certamente o argumento vinculado acima não é suficiente. (Claro que existem noções de finitude mais rígidas do que amorfo - por exemplo, "em qualquer partição em infinitas peças, todas, exceto finitamente, muitas dessas peças são singletons" - mas que eu saiba, todas elas são significativamente mais difíceis de trabalhar, então seria seria muito bom se não tivéssemos que ir lá.)
Respostas
Se eu entendi corretamente, é certamente consistente que existem infinitos hereditariamente $\Pi_1^1$-conjuntos de pseudofinitos. É consistente que a classe de$\Pi_1^1$-conjuntos pseudofinitos são fechados sob uniões finitas. Vou apenas dizer "pseudofinito" em vez de "$\Pi_1^1$-pseudofinite "para o restante desta postagem.
Teorema. Deixar$N$ ser um modelo de ZF-Foundation com um conjunto infinito $A\in N$ satisfatório:
- $A$ é pseudofinito
- Pequenas violações de escolha com $A^{<\omega}$: para todos $X$ há um ordinal $\alpha$ e uma surjection $A^{<\omega}\times\alpha\to X.$
Dentro $N,$a classe de conjuntos pseudofinitos é fechada sob uniões finitas. Em particular,$A$ é hereditariamente $\Pi_1^1$-pseudofinite.
Essas hipóteses são válidas no modelo básico de Fraenkel, com $A$sendo o conjunto de átomos. 1 segura porque$A$ é amorfo, e 2 é válido porque dado $X$ nós podemos bem ordenar tudo $G$- sobreposições fixas do formulário $A^n\to \{gx:g\in G\}$ com $x\in X,$ Onde $G$ é o grupo de simetria, para dar uma sobreposição $A^{<\omega}\times\alpha\to \{gx:g\in G, x\in X\}\supseteq X.$ Portanto, esse modelo tem um infinito hereditariamente $\Pi_1^1$conjunto -pseudofinite.
Já que você perguntou sobre ZF, a declaração "se $x$ e $y$ são pseudofinitos, então são $x\cup y$"é injetivamente limitável no sentido de [1]. Um conjunto pseudofinito não pode admitir uma injeção de $\omega,$ porque isso permitiria interpretar $(\omega,<).$Portanto, não há problema em considerar os modelos Fraenkel-Mostowski. Tenho certeza de que você também pode usar o primeiro modelo Cohen.
O teorema seguirá da equivalência dessas condições para conjuntos não vazios $X\in N$:
- $X$ é pseudofinito
- Há uma sobreposição $\coprod_{i\in \alpha} A^{p_i}\to X$ para alguns $\alpha\in\omega$ e $p\in\omega^\alpha.$
- Há uma sobreposição $A^n\to X$ para alguns $n$.
1⇒2 : Pelas pequenas violações do axioma da escolha, há uma suposição$f:A^{<\omega}\times \alpha\to X.$
A sequência $\beta\mapsto f(A^{<\omega}\times\beta)$ é uma sequência não decrescente bem ordenada em $2^X.$ Se esta sequência for infinita, então podemos restringir a uma função estritamente crescente $g:\omega\to 2^X.$ Isso dá uma surjeção $X\to\omega$ definido por $x\mapsto \min\{n:x\in g(n)\}.$ (Alternativamente, por um teorema de Kuratowski há uma injeção $\omega\to 2^X$ se houver uma surjeição $X\to\omega.$) Isso permitiria $X$ interpretar a teoria não pseudofinita $(\omega,<).$ Então podemos assumir $\alpha<\omega.$
Da mesma forma, a sequência $k\mapsto f(A^{\leq k}\times \alpha)$ é uma sequência não decrescente bem ordenada, então deve se estabilizar em algum $k.$ Então $f$ restringe-se a uma sobreposição $A^{\leq k}\times \alpha\to X.$ Depois de alguma reindexação, ela assume a forma exigida.
2⇒3 : definir$n=2\alpha+\max p_i$ e codificar $i$ usando a relação de igualdade no primeiro $2\alpha$ variáveis
3⇒1 : Recebemos uma surjeção$f:A^n\to X$ e uma estrutura de primeira ordem $\mathcal X$ sobre $X,$ e quer provar que cada teorema $\phi$ de $\mathcal X$tem um modelo finito. Substituindo quaisquer operações por seus gráficos, podemos assumir que$\phi$não usa operações. Também podemos assumir$\phi$não usa igualdade lógica, adicionando uma nova relação de igualdade. Cada relação$R\subseteq X^{a_R}$ pode ser puxado de volta para uma relação $\hat{R}\subseteq (A^n)^{a_R}=A^{na_R}$ de $$\hat{R}(x_{0,0},\dots,x_{a_R-1,n-1})\iff R(f(x_{0,0},\dots,x_{0,n-1}),\dots,f(x_{a_R-1,0},\dots,x_{a_R-1,n-1}))$$ dando uma interpretação de $\mathcal X$ em uma teoria de primeira ordem $\hat{\mathcal X}$ definido em $A.$ A sentença $\phi$ é um teorema de $\hat{\mathcal X},$ então deve haver um modelo finito.
[1]: David Pincus, Zermelo-Fraenkel Consistency Results por Fraenkel-Mostowski Methods, The Journal of Symbolic Logic, Vol. 37, No. 4 (dezembro, 1972), pp. 721-743