Ferramentas do usuário
Famílias dominantes e famílias ilimitadas
Denotamos por $A^B$ o conjunto de todas as funções $f: B \rightarrow A$. Denotamos por $\omega$ o conjunto dos naturais.
Sejam $f, g \in \omega^\omega$. Dizemos que $f \leq^* g$ se $\{n \in \omega: f(n) > g(n)\}$ é finito.
1 Mostre que são equivalentes: $f \leq^* g$ e existe $n_0$ tal que, para todo $n \geq n_0$, $f(n) \leq g(n)$.Solução
Dizemos que $\preceq$ é uma pré-ordem sobre $X$ se, dados $a, b, c \in X$, temos:
- $a \preceq a$
- se $a \preceq b$ e $b \preceq c$ então $a \preceq c$
2 Mostre que $\leq^*$ é uma pré-ordem.Solução
3 Dê um exemplo de $f, g \in \omega^\omega$ de forma que não vale $f \leq^* g$ nem $g \leq^* f$.
Dizemos que uma família $A \subset \omega^\omega$ é uma família ilimitada se não existe $g \in \omega^\omega$ tal que, para todo $f \in A$, $f \leq^* g$. Dizemos que $A$ é família dominante se para todo $g \in \omega^\omega$, existe $f \in A$ tal que $g \leq^* f$.
4 Dê um exemplo de uma família dominante (pode ser trivial).
5 Mostre que toda família dominante é ilimitada.Solução
6 Seja $\{f_n: n \in \omega\} \subset \omega^\omega$. Mostre que ela não é ilimitada.DicaSolução
Se tiver problemas com os termos do próximo exercício, veja a lista de enumerabilidade.
7 Mostre que não existe uma família dominante enumerável. Solução
A partir daqui, você precisa saber um pouco sobre cardinais.
Defina $\mathfrak b$ como a menor cardinalidade possível para uma família ilimitada. Defina $\mathfrak d$ como a menor cardinalidade para uma família dominante.
8 Mostre as seguintes desigualdades $\aleph_0 < \mathfrak b \leq \mathfrak d \leq \mathfrak c$.
9 Mostre que a hipótese do contínuo implica que $\mathfrak b = \mathfrak d = \mathfrak c$.
10 Mostre que a hipótese do contínuo implica que existe uma família $\mathcal F = \{f_{\alpha} | \alpha < \omega_1\}$ tal que:
- $f_{\alpha} \in \mathcal F$ é crescente, para todo $\alpha < \omega_1$;
- Se $\alpha < \beta < \omega_1$, temos $f_{\alpha} \leq^{*} f_{\beta}$;
- Para todo $g \in \omega^{\omega}$, existe $\alpha < \omega_1$ tal que $\{n < w | g(n) < f_{\beta}(n)\}$ é infinito, sempre que $\alpha < \beta < \omega_1$. Dica
Note que a família $\mathcal F$ é ilimitada.
Se você conhece o axioma de Martin, talvez a lista de aplicações do axioma de Martin seja uma boa pedida.
Ferramentas da página
