# Funções e cardinalidade

Totalidade, funcionalidade, injetividade, sobrejetividade, inversas e conjuntos infinitos.

Página: https://resumos.rgo.pt/cadeiras/md/funcoes-cardinalidade/

Uma função $f:A\to B$ associa a cada elemento de $A$ exatamente um elemento de $B$. A fórmula de cálculo não define tudo: o domínio e o contradomínio podem mudar as propriedades da mesma expressão. Aqui usamos composição e equivalências das lições de relações.

## Total e funcional

Uma função é uma relação com duas condições:

*   **Totalidade:** para cada $a\in A$, existe $b\in B$ com $(a,b)\in f$.
*   **Funcionalidade:** se $(a,b)\in f$ e $(a,c)\in f$, então $b=c$.

Uma relação só funcional é uma função parcial. Não tem necessariamente um valor para todas as origens. A imagem é $f(A)=\operatorname{rng}(f)=\{f(a):a\in A\}$; pode ser menor do que o contradomínio $B$.

Se $A=\{1,2,3\}$ e $B=\{a,b,c\}$, a relação $\{(1,a),(2,a),(3,b)\}$ é função. Não atingir $c$ não viola totalidade. Já $\{(1,a),(1,b),(2,c),(3,c)\}$ é total e não funcional.

Os conjuntos vazios também têm de ser tratados. Existe uma única função $\emptyset\to B$, a relação vazia. Se $A\ne\emptyset$, não existe função $A\to\emptyset$.

## Injetiva, sobrejetiva e bijetiva

Uma função é **injetiva** se valores iguais só vêm de origens iguais:

$$
\forall a_1,a_2\in A, \quad f(a_1)=f(a_2)\to a_1=a_2.
$$

É **sobrejetiva** se atinge todo o contradomínio:

$$
\forall b\in B,\quad\exists a\in A,\quad f(a)=b.
$$

É **bijetiva** se tem ambas as propriedades. Cada destino tem exatamente uma origem.

Para provar injetividade, começa com $f(a_1)=f(a_2)$ e tenta obter $a_1=a_2$. Para a refutar, apresenta duas origens distintas com o mesmo valor. Para provar sobrejetividade, toma um $b$ arbitrário do contradomínio e encontra uma origem admissível. Para a refutar, apresenta um destino que nunca é atingido.

## O domínio muda a resposta

Para $f:\mathbb Z\to\mathbb Z$, $f(x)=x^2$, cada origem tem uma imagem, mas $1$ e $-1$ chegam ambas a $1$. Logo, a função não é injetiva. Também não é sobrejetiva: a equação $x^2=-1$ não tem solução inteira.

Restringir o domínio a $\mathbb N$ elimina a colisão entre $1$ e $-1$. Se $x,y\ge0$ e $x^2=y^2$, então $(x-y)(x+y)=0$, e ambas as alternativas dão $x=y$, pois $x+y=0$ com $x,y\ge0$ só acontece em $x=y=0$. Porém, $2$ continua sem origem natural. A tabela compara estas alterações:

| Função | Injetiva? | Sobrejetiva? |
| --- | --- | --- |
| $\mathbb Z\to\mathbb Z$ | Não, $f(1)=f(-1)$. | Não, por exemplo não atinge $-1$ nem 2. |
| $\mathbb N\to\mathbb N$ | Sim, dois naturais com quadrados iguais são iguais. | Não, 2 não é quadrado de um natural. |
| $[0,\infty)\to[0,\infty)$ | Sim. | Sim, a origem de $y$ é $\sqrt y$. |

Resolver $x^2=y$ em $\mathbb R$ não prova sobrejetividade em $\mathbb Z$, porque a origem tem de pertencer ao domínio indicado.

Para $g:\mathbb Z\to\mathbb Z$, $g(x)=2x-3$, a injetividade vem de $2x-3=2y-3\Rightarrow x=y$. A imagem são os inteiros ímpares: todo o resultado é ímpar e, dado um ímpar $2k+1$, a origem $k+2$ serve. Não é sobrejetiva para $\mathbb Z$, mas é bijetiva para esse conjunto de ímpares.

## Inversa como relação e como função

A relação $f^{-1}$ existe sempre: troca os pares. Para ser uma função $B\to A$, precisa de totalidade e funcionalidade.

*   Se $f$ é injetiva, $f^{-1}$ é funcional, mas pode faltar uma origem para algum $b\in B$.
*   Se $f$ é sobrejetiva, $f^{-1}$ é total, mas pode ter vários destinos para uma mesma origem.
*   Se $f$ é bijetiva, $f^{-1}$ é uma função total.

Para uma função total $f:A\to B$:

$$
\begin{aligned} f\text{ é injetiva}&\Longleftrightarrow f^{-1}\circ f=\operatorname{id}_A,\\ f\text{ é sobrejetiva}&\Longleftrightarrow f\circ f^{-1}=\operatorname{id}_B. \end{aligned}
$$

O par $(a_1,a_2)$ pertence a $f^{-1}\circ f$ se $f(a_1)=f(a_2)$. Por isso, a primeira igualdade diz que as únicas origens com imagem igual são as iguais. Já $f\circ f^{-1}$ é a identidade sobre a imagem de $f$, que coincide com $B$ precisamente no caso sobrejetivo.

Para uma relação geral $R\subseteq A\times B$, a totalidade equivale a $\operatorname{id}_A\subseteq R^{-1}\circ R$ e a funcionalidade a $R\circ R^{-1}\subseteq\operatorname{id}_B$. Estas inclusões não pressupõem que $R$ já seja função.

### Fibras e classes de equivalência

Para uma função total $f:A\to B$, a relação $R=f^{-1}\circ f$ junta origens com a mesma imagem:

$$
aRa'\Longleftrightarrow f(a)=f(a').
$$

É sempre uma equivalência: $f(a)=f(a)$ dá reflexividade, trocar os lados dá simetria e encadear igualdades dá transitividade. Não exige que $f$ seja injetiva nem sobrejetiva.

A classe $[a]_R=\{x\in A:f(x)=f(a)\}$ é a **fibra** do valor $f(a)$. Não é o próprio valor $f(a)$, nem o conjunto de todas as imagens.

Com $A=\{1,2,3,4,5\}$, $B=\{u,v,w\}$ e $f(1)=f(3)=u$, $f(2)=f(4)=f(5)=v$:

| Valor em $B$ | Origens com essa imagem |
| --- | --- |
| $u$ | $\{1,3\}$ |
| $v$ | $\{2,4,5\}$ |
| $w$ | $\emptyset$ |

O quociente é $A/R=\{\{1,3\},\{2,4,5\}\}$ e tem dois elementos. A imagem $f(A)=\{u,v\}$ também tem dois, mas contém objetos de outro tipo. A fibra vazia de $w$ não é uma classe, porque não contém nenhuma origem.

A função $[a]_R\mapsto f(a)$ é uma bijeção de $A/R$ para $f(A)$. É bem definida porque representantes da mesma classe têm a mesma imagem; é injetiva pela definição de $R$; é sobrejetiva porque cada imagem vem de alguma origem. Para $A$ finito, isto dá $|A/R|=|f(A)|$. Já $\operatorname{dom}(R)=\operatorname{rng}(R)=A$, pois a reflexividade inclui todos os pares $(a,a)$.

## Composição

Para $f:A\to B$ e $g:B\to C$, $(g\circ f)(x)=g(f(x))$. Aplicamos primeiro $f$.

Com $f(n)=2n$ e $g(n)=n+1$ em $\mathbb Z$, seguimos o mesmo argumento nas duas ordens:

| Ordem | Primeiro valor | Segundo valor |
| --- | --- | --- |
| $g\circ f$ em 3 | $f(3)=6$ | $g(6)=7$ |
| $f\circ g$ em 3 | $g(3)=4$ | $f(4)=8$ |

A composição de funções também não é comutativa. O valor que entra na segunda função é a saída da primeira.

Se ambas são injetivas, a composição é injetiva: $g(f(x))=g(f(y))$ implica $f(x)=f(y)$ e depois $x=y$. Se ambas são sobrejetivas, para cada $c\in C$ existe $b\in B$ com $g(b)=c$ e depois $a\in A$ com $f(a)=b$.

A recíproca exige cuidado. Se $g\circ f$ é injetiva, $f$ tem de ser injetiva, mas $g$ pode falhar injetividade fora da imagem de $f$. Se $g\circ f$ é sobrejetiva, $g$ tem de ser sobrejetiva, mas $f$ pode não atingir todo o $B$.

Para bijeções, a inversa inverte a ordem:

$$
(g\circ f)^{-1}=f^{-1}\circ g^{-1}.
$$

## Cardinalidade finita e infinita

Dois conjuntos têm a mesma cardinalidade quando existe uma bijeção entre eles. Para conjuntos finitos, uma injeção $A\to B$ exige $|A|\le|B|$ e uma sobrejeção exige $|A|\ge|B|$. Se ambos são finitos e têm o mesmo tamanho, uma função é injetiva se e só se é sobrejetiva.

Para conjuntos infinitos, um subconjunto próprio pode ter a mesma cardinalidade que o conjunto. $n\mapsto2n$ é uma bijeção de $\mathbb N$ para os naturais pares. O subconjunto tem menos elementos no sentido de inclusão, mas não no sentido de cardinalidade.

Uma bijeção $h:\mathbb N\to\mathbb Z$ é:

$$
h(n)=\begin{cases} n/2,&n\text{ par},\\ -(n+1)/2,&n\text{ ímpar}. \end{cases}
$$

A sequência de imagens é $0,-1,1,-2,2,\ldots$. A inversa é $h^{-1}(z)=2z$ para $z\ge0$ e $h^{-1}(z)=-2z-1$ para $z<0$. As duas fórmulas mostram que cada inteiro tem uma origem e que essa origem é única.

Um conjunto é **numerável** se é finito ou tem bijeção com $\mathbb N$. Como aprofundamento, os racionais também são numeráveis: percorremos os pares $(p,q)$ com $p\in\mathbb Z,q\ge1$ por valores crescentes de $|p|+q$, e omitimos frações repetidas. Cada etapa é finita e qualquer racional aparece numa delas. Os reais não são numeráveis. Serem ambos infinitos não prova que dois conjuntos tenham a mesma cardinalidade.

## Exercícios

Imagem e inversa

Para $f:\mathbb Z\to\mathbb Z$, $f(n)=3n+1$, decide injetividade e sobrejetividade. Qual contradomínio torna a função bijetiva e qual a inversa?

Pista

Todo o resultado tem resto 1 módulo 3.

Mais uma pista

Se $y=3k+1$, então $k$ é uma origem inteira. O inteiro 0 não é atingido.

Solução

É injetiva porque $3n+1=3m+1$ implica $n=m$. Não é sobrejetiva para $\mathbb Z$, pois 0 exigiria $n=-1/3$. É bijetiva para $B=\{3k+1:k\in\mathbb Z\}$, com domínio $\mathbb Z$ e contradomínio $B$, com inversa $f^{-1}:B\to\mathbb Z$, $f^{-1}(y)=(y-1)/3$.

Confere a tua resposta:

*   Provei a injetividade por igualdade das imagens.
*   Refutei sobrejetividade com um inteiro fora da imagem.
*   Restringi o contradomínio à imagem e escrevi a inversa.

Erros frequentes

Uma fórmula de inversa não basta: verifica que o argumento está no contradomínio escolhido e que o resultado está no domínio original.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/funcoes-cardinalidade/#o-dom%C3%ADnio-muda-a-resposta)

A composição não decide tudo

Constrói $f:A\to B$ e $g:B\to C$ tais que $g\circ f$ seja bijetiva, mas nem $f$ nem $g$ sejam bijetivas.

Pista

Um elemento de $B$ pode ficar fora da imagem de $f$.

Solução

Toma $A=C=\{0\}$ e $B=\{0,1\}$. Define $f(0)=0$ e $g(0)=g(1)=0$. A composição é a única função $\{0\}\to\{0\}$, portanto bijetiva. $f$ não é sobrejetiva, pois não atinge 1. $g$ não é injetiva, pois as duas origens têm a mesma imagem.

Confere a tua resposta:

*   Declarei os três conjuntos e todas as imagens.
*   A composição é injetiva e sobrejetiva.
*   Identifiquei a falha de sobrejetividade de f e de injetividade de g.

Erros frequentes

Uma composição bijetiva obriga $f$ a ser injetiva e $g$ a ser sobrejetiva. Não obriga às outras duas propriedades.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/funcoes-cardinalidade/#composi%C3%A7%C3%A3o)

Classes, imagem e domínio ativo

Sejam $A=\{1,2,3,4,5,6,7\}$, $B=\{u,v,w,z\}$ e $f:A\to B$ definida por $f(1)=f(4)=f(7)=u$, $f(2)=f(5)=f(6)=v$ e $f(3)=w$. Para $R=f^{-1}\circ f$:

1.  Prova que $R$ é equivalência e determina $A/R$.
2.  Calcula $|R|$, $|f(A)|$, $|\operatorname{dom}(R)|$ e $|\operatorname{rng}(R)|$.
3.  $R$ é uma função $A\to A$? E $f^{-1}$ é uma função $B\to A$? Justifica.

Pista

Compõe primeiro f e depois a relação inversa. Duas origens relacionam-se quando chegam ao mesmo valor, não quando têm o mesmo nome.

Solução

Temos $aRb$ se e só se $f(a)=f(b)$. Reflexividade, simetria e transitividade seguem das mesmas propriedades da igualdade. As classes são as três fibras não vazias:

$$
A/R=\{\{1,4,7\},\{2,5,6\},\{3\}\}.
$$

Cada bloco $X$ contribui com todos os pares de $X\times X$, sem pares entre blocos. Logo $|R|=3^2+3^2+1^2=19$. A imagem de $f$ é $\{u,v,w\}$, com 3 elementos. Já $\operatorname{dom}(R)=\operatorname{rng}(R)=A$, com 7 elementos cada, pela reflexividade.

$R$ é total mas não funcional: 1 relaciona-se com 1, 4 e 7. $f^{-1}$ também não é uma função total $B\to A$: $z$ não tem destino, e $u$ tem os três destinos 1, 4 e 7. Assim falham tanto totalidade como funcionalidade da inversa.

Confere a tua resposta:

*   Provei as três propriedades por igualdade de imagens.
*   Listei as fibras não vazias e contei pares por bloco.
*   Distingui a imagem de f, o quociente e a imagem de R.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/funcoes-cardinalidade/#fibras-e-classes-de-equival%C3%AAncia)