Funções e 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.