Números: notas de aula

Se \(f(a)=b\) não temos o que provar. Suponha que \(f(a)\neq b\text{.}\) Considere \(a'\in X\) e \(b'\in Y\) tais que \(f(a')=b\) e \(f(a)=b'\text{.}\) Note que \(a'\) existe, pois \(f\) é sobrejetiva. Finalmente, defina \(g:X\rightarrow Y\) pondo

É claro que \(f\) é uma bijeção.

Suponha por absurdo que o teorema seja falso. Suponha que

Pelo PBO (Teorema 1.4.4), \(B\) admite um menor elemento \(n_0\text{,}\) ou seja, existe um subconjunto próprio \(A\varsubsetneq I_{n_0}\) e bijeção \(f:A\rightarrow I_{n_0}\text{.}\)

Para garantir a existência de uma bijeção entre um subconjunto próprio de \(I_{n_0-1}\) e o conjunto \(I_{n_0-1}\text{,}\) precisamos considerar dois casos.

1º Caso: Se \(n_0\in A\text{,}\) pelo Lema 5.1.2, existe uma bijeção \(g:A\rightarrow I_{n_0}\) com \(g(n_0)=n_0\text{.}\) Logo

é uma bijeção, na qual, \(A\backslash\{n_0\}\) é um subconjunto próprio de \(I_{n_0-1}\text{.}\)

2º Caso: Se \(n_0\notin A\text{,}\) considere \(a\in A\) tal que \(f(a)=n_0\text{.}\) A função

é uma bijeção, na qual, \(A\backslash\{a\}\) é um subconjunto próprio de \(I_{n_0-1}\text{.}\)

Em ambos os casos, a existência de bijeção entre um subconjuto próprio de \(I_{n_0-1}\) e o conjunto \(I_{n_0-1}\) contradiz a minimalidade de \(n_0\text{.}\) Logo o conjunto \(B\) é vazio.

Suponha que \(m\lt n\text{,}\) então \(I_m\) seria um subconjunto próprio de \(I_n\text{,}\) o que violaria o Teorema 5.1.4, pois

é uma bijeção. Pelo mesmo motivo não é possível que \(n\lt m\text{.}\) Logo \(m=n\text{.}\)

Pela Definição 5.1.1, existe uma bijeção \(\varphi:I_n\rightarrow X\text{.}\) A função \(f:X\rightarrow X\) é injetiva ou sobrejetiva se, e somente se,

também for. Portanto, basta provar o teorema para a função \(g: I_n\rightarrow I_n\text{.}\)

Se \(g\) for injetiva então, pondo \(A=g(I_n)\text{,}\) teremos uma bijeção \(g^{-1}:A\rightarrow I_n\text{.}\) Pelo Teorema 5.1.4, \(A=I_n\) e \(g\) é sobrejetiva.

Reciprocamente, se \(g\) for sobrejetiva, podemos definir uma função \(h:I_n\rightarrow I_n\) da seguinte maneira, para cada \(x\in I_n\text{,}\) podemos escolher \(y=h(x)\in I_n\text{,}\) tal que, \(g(h(x))=x\) para todo \(x\in I_n\text{.}\) Então, \(h\) é injetiva e, pelo que acabamos de provar, \(h\) é sobrejetiva. Para mostrar que \(g\) é injetiva, considere se \(y_1, y_2\in I_n\) tais que

precisamos verificar que \(y_1=y_2\text{.}\) Tomando \(x_1, x_2\in I_n\) com \(h(x_1)=y_1, h(x_2)=y_2\text{,}\) teremos

Como \(x_1=x_2\text{,}\) aplicando \(h\) em ambos os lados, obtemos

logo \(g\) é injetiva.

Sejam \(A\) e \(B\) conjuntos, tais que \(B\) é finito e \(A\subset B\text{.}\) Se \(A=\varnothing\text{,}\) não há o que provar. Suponha \(A\neq\varnothing\text{,}\) faremos a prova por indução sobre o número de elementos de \(B\text{.}\)

Considere a proposição

\(P(1)\) é verdadeiro, pois se \(B\) tem um único elemento, então o subconjunto não vazio de \(B\) é ele próprio e, portanto, \(A=B\) é finito.

Agora, suponha que \(P(n)\) é verdadeira para algum \(n\in \mathbb{N}\text{.}\) Vamos mostrar que \(P(n+1)\) também é verdadeira.

Seja \(B\) um conjunto com \(n+1\) elementos. Se \(A=B\text{,}\) \(A\) é finito. Se \(A\neq B\text{,}\) existe \(b\in B\text{,}\) com \(b\notin A\text{.}\) Então, \(A\subset B\setminus \{b\}\text{.}\) Como \(B\setminus \{b\}\) possui \(n\) elementos, segue-se que \(A\) é finito.

item 1. Se \(f\) é injetiva então ela é uma bijeção de \(X\) sobre um subconjunto \(f(X)\) do conjunto finito \(Y\text{.}\)

item 2. Se \(f\) é sobrejetiva e \(X\) é finito então, podemos definir uma função \(g:Y\rightarrow X\) fazendo o seguinte, para cada \(y\in Y\text{,}\) existe pelo menos um \(x\in X\text{,}\) tal que, \(f(x)=y\text{,}\) defina \(g(y)=x\text{.}\) A função \(g:Y\rightarrow X\text{,}\) é tal que, \(f(g(y))=y\) para todo \(y\in Y\text{.}\) Segue-se que \(g\) é injetiva, pois se \(g(y_1)=g(y_2)\text{,}\) aplicando \(f\) em ambos os lados, obtemos

Logo, como \(g:Y\rightarrow X\) é injetiva e seu contra domímio é finito, pelo item 1. \(Y\) é finito.

Ideia: considerar os casos \(X\cap Y=\emptyset\) e \(X\cap Y\neq\emptyset\text{.}\) Para o caso \(X\cap Y\neq\emptyset\text{,}\) considerar \(Z=X\setminus X\cap Y\text{,}\) que é finito pelo Teorema 5.1.8 e usar o caso anterior para \(Z\cup Y\text{.}\)

Se \(X=\{x_1, \ldots, x_n\}\subset\mathbb{N}\) é finito, pondo \(p=x_1+\cdots+x_n\) vemos que

logo \(X\) é limitado.

Reciprocamente, se \(X\subset\mathbb{N}\) é limitado então \(X\subset I_p\) para algum \(p\in \mathbb{N}\text{,}\) segue do Teorema 5.1.8 que \(X\) é finito.