===== Famílias dominantes e famílias ilimitadas =====

<WRAP info>
Denotamos por {{entry>$A^B$}} o conjunto de todas as funções $f: B \rightarrow A$. Denotamos por $\omega$ o conjunto dos naturais.
 </WRAP>


<WRAP info>
Sejam $f, g \in \omega^\omega$. Dizemos que $f \leq^* g$ se $\{n \in \omega: f(n) > g(n)\}$ é finito.
</WRAP>


**~~#~~** 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)$.<wrap help>[[Solucao:leqEquivalencia|Solução]]</wrap> 


<WRAP info>
Dizemos que $\preceq$ é uma {{entry>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$
</WRAP>

**~~#~~** Mostre que $\leq^*$ é uma pré-ordem.<wrap help>[[Solucao:leqPreOrdem|Solução]]</wrap>

**~~#~~** Dê um exemplo de $f, g \in \omega^\omega$ de forma que não vale $f \leq^* g$ nem $g \leq^* f$.

<WRAP info>
Dizemos que uma família $A \subset \omega^\omega$ é uma {{entry>família ilimitada}} se não existe $g \in \omega^\omega$ tal que, para todo $f \in A$, $f \leq^* g$. Dizemos que $A$ é {{entry>família dominante}} se para todo $g \in \omega^\omega$, existe $f \in A$ tal que $g \leq^* f$. 
</WRAP>

**~~#~~** Dê um exemplo de uma família dominante (pode ser trivial).

**~~#~~** Mostre que toda família dominante é ilimitada.<wrap help>[[Solucao:ex5defamilias|Solução]]</wrap>

**~~#~~** Seja $\{f_n: n \in \omega\} \subset \omega^\omega$. Mostre que ela não é ilimitada.<wrap tip>[[dica:ilimitada|Dica]]</wrap><wrap help>[[Solucao:ex6defamilias|Solução]]</wrap>

<WRAP tip>
Se tiver problemas com os termos do próximo exercício, veja a lista de [[lista:Enumerabilidade|enumerabilidade]].
</WRAP>

**~~#~~** Mostre que não existe uma família dominante enumerável. <wrap help>[[Solucao:naoFamDomEnum|Solução]]</wrap> 

<WRAP tip>
A partir daqui, você precisa saber um pouco sobre [[lista:cardinais|cardinais]].
</WRAP>

<WRAP info>
Defina {{entry>$\mathfrak b$}} como a menor cardinalidade possível para uma família ilimitada. Defina {{entry>$\mathfrak d$}} como a menor cardinalidade para uma família dominante.
</WRAP>

**~~#~~** Mostre as seguintes desigualdades $\aleph_0 < \mathfrak b \leq \mathfrak d \leq \mathfrak c$.

**~~#~~** Mostre que a hipótese do contínuo implica que $\mathfrak b = \mathfrak d = \mathfrak c$.

**~~#~~** 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$. <wrap tip> [[Dica:CrescFun|Dica]]</wrap>

Note que a família $\mathcal F$ é ilimitada.

<WRAP tip>
Se você conhece o axioma de Martin, talvez a lista de [[lista:applMA| aplicações do axioma de Martin]] seja uma boa pedida.
</WRAP>