Conjuntos, relações e funções

A linguagem do curso

A aula seguinte define os números naturais por meio de uma função, o sucessor, que é injetora e não atinge o $1$. A unidade seguinte constrói os inteiros e os racionais como classes de uma relação de equivalência; a aula de combinatória define o número de elementos por meio de bijeções; a ordem dos naturais é uma relação de ordem; e a terceira unidade compõe e inverte funções reais. Todas essas palavras pertencem a uma mesma linguagem, que convém fixar antes de usá-la, junto com os primeiros teoremas que o curso invocará depois.

Convém advertir o que se antecipa. Os exemplos usam números naturais pequenos com sua ordem, sua soma, seu produto, a divisibilidade e o resto de uma divisão, tal como se aprendem na escola. A aula seguinte define os naturais por meio dos axiomas de Peano, e as aulas da unidade definem essas operações e demonstram suas propriedades sem usar nenhum exemplo desta, de modo que não há círculo. Nenhum teorema desta aula depende dos exemplos: os números servem apenas para ver os teoremas em ação.

O que se admite

Um conjunto é uma coleção de objetos, seus elementos; escreve-se $a \in A$ para dizer que $a$ pertence a $A$, e $a \notin A$ para negá-lo. Conjunto e pertinência não se definem: são noções primitivas, como o $1$ e o sucessor na aritmética. Ora, nem toda propriedade define um conjunto. Se existisse o conjunto $R$ de todos os conjuntos que não pertencem a si mesmos, a pergunta sobre se $R$ pertence a $R$ não teria resposta, porque pela definição de $R$ se teria $R \in R \leftrightarrow R \notin R$. Essa contradição, descoberta por Russell em 1901, obriga a restringir a formação de conjuntos: uma propriedade apenas seleciona elementos de um conjunto já dado.

Fato admitido (regras da teoria ingênua dos conjuntos). Admitem-se sem demonstração as regras da teoria ingênua dos conjuntos que esta aula usa: dois conjuntos com os mesmos elementos são iguais; de um conjunto dado $A$ e uma propriedade $P$ forma-se o conjunto $\{ x \in A : P(x) \}$ dos elementos de $A$ que a cumprem; e existem o conjunto vazio, o conjunto $\{a, b\}$ cujos únicos elementos são $a$ e $b$, a união dos elementos de um conjunto de conjuntos e o conjunto dos subconjuntos de um conjunto. A existência de um conjunto com as propriedades do conjunto dos naturais é admitida na aula seguinte.

Essas regras fazem parte dos axiomas de Zermelo e Fraenkel, cujo estudo pertence à teoria dos conjuntos e excede este curso; por isso são admitidas, e são declaradas para que se saiba exatamente o que se usa.

Lógica dos quantificadores

As demonstrações combinam enunciados com os conectivos $\neg$, $\wedge$, $\vee$, $\rightarrow$ e $\leftrightarrow$, cujas leis são estudadas no curso complementar Lógica Matemática I: Lógica Proposicional, a partir de sua linguagem; aqui basta lembrar que a implicação $p \rightarrow q$ só é falsa quando $p$ é verdadeira e $q$ falsa, que equivale à sua contrapositiva $\neg q \rightarrow \neg p$, e que as leis de De Morgan negam uma conjunção ou uma disjunção:

Para falar de conjuntos são necessários, além disso, enunciados sobre todos os elementos ou sobre algum. Se $P(x)$ é uma propriedade dos elementos de $A$, o enunciado $(\forall x \in A)\,P(x)$, que se lê «para todo $x$ de $A$, $P(x)$», afirma que todos os elementos de $A$ a cumprem; o enunciado $(\exists x \in A)\,P(x)$, «existe um $x$ de $A$ tal que $P(x)$», afirma que pelo menos um a cumpre; e $(\exists! x \in A)\,P(x)$ afirma que exatamente um a cumpre. Os símbolos $\forall$ e $\exists$ chamam-se quantificadores, universal e existencial.

Fato admitido (negação dos quantificadores). Negar que todos os elementos cumprem uma propriedade é afirmar que algum não a cumpre, e negar que algum a cumpre é afirmar que nenhum a cumpre:

Essas regras, próprias da lógica de primeira ordem, são admitidas; elas estendem as leis de De Morgan, porque se $A = \{a, b\}$ o universal é $P(a) \wedge P(b)$ e o existencial é $P(a) \vee P(b)$. A ordem dos quantificadores importa: o enunciado $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ diz que todo natural tem outro maior, e é verdadeiro; o enunciado $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ diz que há um natural maior que todos, inclusive maior que si mesmo, e é falso.

A forma lógica de um enunciado dita a maneira de demonstrá-lo. As estratégias que esta aula usa são as seguintes; sua justificação lógica é estudada na aula sobre as técnicas de dedução.

• Para demonstrar $(\forall x \in A)\,P(x)$, toma-se um elemento $x$ de $A$ qualquer, sem supor dele nada além de sua pertinência a $A$, e demonstra-se $P(x)$.
• Para demonstrar $(\exists x \in A)\,P(x)$, exibe-se um elemento concreto de $A$ que cumpre $P$; para refutar $(\forall x \in A)\,P(x)$, basta um contraexemplo, um elemento que não a cumpre.
• Para demonstrar $p \rightarrow q$, supõe-se $p$ e deduz-se $q$; ou então demonstra-se a contrapositiva $\neg q \rightarrow \neg p$; ou então supõe-se $p \wedge \neg q$ e chega-se a uma contradição.
• Para demonstrar $p \leftrightarrow q$, demonstram-se as duas implicações $p \rightarrow q$ e $q \rightarrow p$.

Conjuntos

Pertinência, igualdade e inclusão

Um conjunto é descrito por extensão, enumerando seus elementos entre chaves, como $\{1, 2, 3\}$, ou por compreensão, por meio de uma propriedade, como $\{ n \in \mathbb{N} : n \leq 3 \}$, que é o mesmo conjunto. A regra de extensionalidade diz que um conjunto fica determinado por seus elementos:

Daí segue que em uma descrição por extensão não importam nem a ordem nem as repetições: $\{1, 2, 2\}$ e $\{2, 1\}$ são o mesmo conjunto, porque têm os mesmos elementos. Segue também que há um só conjunto sem elementos, o conjunto vazio $\emptyset$: dois conjuntos sem elementos têm os mesmos elementos, isto é, nenhum.

Definição (inclusão). Um conjunto $A$ está contido em um conjunto $B$, ou é um subconjunto de $B$, quando todo elemento de $A$ é elemento de $B$:

Se, além disso, $A \neq B$, diz-se que $A$ é um subconjunto próprio de $B$.

O conjunto vazio está contido em todo conjunto $A$, porque a implicação $x \in \emptyset \rightarrow x \in A$ tem sempre o antecedente falso e é, portanto, verdadeira. Convém distinguir a pertinência da inclusão: $1 \in \{1, 2\}$ e $\{1\} \subseteq \{1, 2\}$ são verdadeiros, ao passo que $\{1\} \in \{1, 2\}$ é falso, porque os únicos elementos de $\{1, 2\}$ são $1$ e $2$, e o conjunto $\{1\}$ não é igual a nenhum deles: $\{1\} \neq 1$, porque o conjunto que tem como único elemento o $1$ não se confunde com o $1$, e $\{1\} \neq 2$.

União, interseção e diferença

Definição (operações com conjuntos). A união de $A$ e $B$ é o conjunto dos elementos que pertencem a algum deles; a interseção, o dos que pertencem a ambos; e a diferença $A \setminus B$, o dos que pertencem a $A$ e não a $B$:

Se $B \subseteq A$, a diferença $A \setminus B$ chama-se complementar de $B$ em relação a $A$. Dois conjuntos são disjuntos quando sua interseção é vazia.

Cada operação traduz um conectivo: a união, a disjunção; a interseção, a conjunção; a diferença, a conjunção com uma negação. Se isso é assim, cada lei lógica produz uma lei dos conjuntos: a união e a interseção são comutativas, associativas e distributivas uma em relação à outra porque os conectivos o são, e todas essas leis se demonstram como o teorema seguinte. O complementar é tomado sempre em relação a um conjunto de referência, porque um conjunto de tudo o que não está em $B$ reconstruiria o paradoxo de Russell.

O conjunto das partes

Os subconjuntos de um conjunto formam por sua vez um conjunto, cuja existência foi admitida no início. O conjunto das partes de $A$, que se denota $\mathcal{P}(A)$, é o conjunto cujos elementos são os subconjuntos de $A$:

Por exemplo, o conjunto das partes de $\{1, 2, 3\}$ tem oito elementos: o vazio, três conjuntos de um elemento, três de dois elementos e o próprio $\{1, 2, 3\}$.

Para todo conjunto $A$, o vazio e o próprio $A$ são elementos de $\mathcal{P}(A)$, e para cada $a$ de $A$ tem-se $\{a\} \in \mathcal{P}(A)$, ao passo que $a$ não é, em geral, elemento de $\mathcal{P}(A)$. Na aula sobre combinatória se demonstrará que um conjunto de $n$ elementos tem $2^n$ subconjuntos.

Pares ordenados e produto cartesiano

Um ponto do plano, uma fração ou uma subtração pendente se descrevem com dois objetos em uma ordem determinada: o par $(3, 5)$ não é o par $(5, 3)$. O conjunto $\{3, 5\}$ não serve para representá-lo, porque é igual a $\{5, 3\}$. A única coisa que se exige de um par ordenado é sua propriedade característica: dois pares são iguais se e somente se têm a mesma primeira componente e a mesma segunda componente. Kuratowski observou em 1921 que basta a noção de conjunto para construir um objeto com essa propriedade.

Definição (par ordenado). O par ordenado de primeira componente $a$ e segunda componente $b$ é o conjunto

Demonstrada a propriedade característica, a construção de Kuratowski pode ser esquecida: tudo o que o curso diz dos pares se deduz dela.

Definição (produto cartesiano). O produto cartesiano de $A$ e $B$ é o conjunto dos pares cuja primeira componente pertence a $A$ e cuja segunda componente pertence a $B$:

A escrita $\{ (a, b) : a \in A \wedge b \in B \}$ não é por si só uma das regras admitidas, que só permitem separar elementos de um conjunto já formado. Ora, esse conjunto existe: se $a \in A$ e $b \in B$, os conjuntos $\{a\}$ e $\{a, b\}$ estão contidos em $A \cup B$, e portanto são elementos de $\mathcal{P}(A \cup B)$; daí segue que o par $(a, b) = \{ \{a\}, \{a, b\} \}$ está contido em $\mathcal{P}(A \cup B)$, isto é, é um elemento de $\mathcal{P}(\mathcal{P}(A \cup B))$. Portanto, o produto cartesiano se forma por separação dentro desse conjunto, que existe pelas regras admitidas: $A \cup B$ é a união dos elementos de $\{A, B\}$, e toma-se duas vezes o conjunto das partes.

O nome lembra Descartes: o plano da geometria analítica é $\mathbb{R} \times \mathbb{R}$. O produto não é comutativo: $\{1\} \times \{2\}$ contém apenas $(1, 2)$, e $\{2\} \times \{1\}$ apenas $(2, 1)$, que é distinto pela propriedade característica.

Relações

Dizer que $2$ divide $6$, que $3$ é menor que $5$ ou que dois dias caem no mesmo dia da semana é afirmar que certos pares de objetos estão relacionados. Se isso é assim, uma relação fica determinada pelos pares que relaciona, e pode ser definida como um conjunto de pares.

Definição (relação). Uma relação de $A$ em $B$ é um subconjunto $R$ do produto $A \times B$; uma relação em $A$ é uma relação de $A$ em $A$. Se $(a, b) \in R$, diz-se que $a$ está relacionado com $b$ por $R$.

Por exemplo, a relação «menor ou igual a» em $\{1, 2, 3\}$ é o conjunto de pares $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. Para as relações de uso frequente escreve-se um símbolo entre os termos, como $a \leq b$ ou $a \mid b$, em vez de $(a, b) \in R$. Quatro propriedades de uma relação em um conjunto se repetem em todo o curso.

Definição (propriedades das relações). Uma relação $R$ em $A$ é reflexiva, simétrica, antissimétrica ou transitiva quando cumpre, respectivamente, as condições seguintes.

• É reflexiva se todo elemento está relacionado consigo mesmo: $(\forall a \in A)\,((a, a) \in R)$;
• É simétrica se a relação de $a$ com $b$ implica a de $b$ com $a$: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$;
• É antissimétrica se dois elementos relacionados em ambos os sentidos são iguais: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$;
• É transitiva se a relação de $a$ com $b$ e a de $b$ com $c$ implicam a de $a$ com $c$: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

No quadriculado de $A \times A$, uma relação é um conjunto de pontos. É reflexiva quando contém toda a diagonal, a dos pares $(a, a)$; é simétrica quando seu desenho é simétrico em relação à diagonal; e é antissimétrica quando nenhum ponto fora da diagonal tem seu simétrico na relação. Antissimétrica não significa «não simétrica»: a igualdade é ambas as coisas, e o problema proposto 1 pede uma relação que não seja nenhuma das duas.

Relações de equivalência

A relação «ter a mesma paridade» se comporta como uma igualdade parcial: identifica os números que coincidem em um aspecto, sua paridade, e esquece os demais. As três propriedades que a fazem comportar-se assim recebem um nome.

Definição (relação de equivalência). Uma relação em $A$ é uma relação de equivalência quando é reflexiva, simétrica e transitiva. Escreve-se então $a \sim b$, e diz-se que $a$ é equivalente a $b$. A classe de $a$ é o conjunto dos elementos equivalentes a $a$, e cada um deles é um representante da classe:

O conjunto de todas as classes chama-se conjunto quociente e denota-se $A/{\sim}$.

São relações de equivalência a igualdade, cujas classes têm um só elemento; a mesma paridade, com duas classes; ter o mesmo resto na divisão por $3$, com três; e cair no mesmo dia da semana, com sete, que é o problema resolvido 3. Em geral, se $g$ é uma função definida em $A$, a relação $g(x) = g(y)$ herda da igualdade as três propriedades, e o problema resolvido 5 mostra que toda equivalência é dessa forma.

As classes dividem, portanto, o conjunto em blocos que não se sobrepõem. Esse modo de dividir um conjunto merece uma definição própria.

Definição (partição). Uma partição de um conjunto $A$ é um conjunto de subconjuntos de $A$, chamados blocos, que não são vazios, que são disjuntos dois a dois e cuja união é $A$; equivalentemente, cada elemento de $A$ pertence a exatamente um bloco.

Dar uma equivalência em $A$ e dar uma partição de $A$ são, portanto, duas maneiras de dizer o mesmo; o problema resolvido 4 aproveita isso para contar equivalências. O conjunto quociente é a partição vista como um conjunto novo: ao passar de $A$ a $A/{\sim}$, os elementos equivalentes se fundem em um só.

Do mesmo modo, na aula sobre os números racionais duas frações $(p, q)$ e $(r, s)$ são equivalentes quando $ps = qr$, e um racional é uma classe; e na aula sobre as congruências, os restos módulo $n$ são as classes de uma equivalência entre inteiros.

Relações de ordem

A divisibilidade do exemplo anterior não é simétrica, mas antissimétrica: em vez de identificar elementos, ordena-os. As relações desse tipo recebem um nome próprio.

Definição (ordem). Uma relação em $A$ é uma relação de ordem, ou ordem parcial, quando é reflexiva, antissimétrica e transitiva; escreve-se então $a \preceq b$, e diz-se que $a$ precede $b$. A ordem é total quando dois elementos quaisquer são comparáveis, isto é, quando para quaisquer $a$ e $b$ se tem $a \preceq b$ ou $b \preceq a$.

São ordens a relação $\leq$ entre naturais, que é total pela tricotomia demonstrada na aula sobre as operações com números naturais; a inclusão, pelo teorema de suas propriedades, que não é total, porque $\{1\}$ e $\{2\}$ não são comparáveis; e a divisibilidade entre naturais, cuja antissimetria se demonstra na aula sobre a divisibilidade, que não é total, porque nem $2 \mid 3$ nem $3 \mid 2$. Uma ordem finita se desenha com um diagrama de Hasse: um ponto por elemento, com $b$ mais acima que $a$ quando $a$ precede $b$, e um segmento quando entre ambos não há nenhum outro elemento; a transitividade permite omitir os demais segmentos.

Definição (cotas e elementos extremos). Sejam $\preceq$ uma ordem em $A$ e $X$ um subconjunto de $A$. As cotas e os elementos extremos de $X$ se definem como segue.

• Um elemento $c$ de $A$ é uma cota inferior de $X$ se precede todos os elementos de $X$, e uma cota superior se todos os elementos de $X$ o precedem.
• Um mínimo de $X$ é uma cota inferior de $X$ que pertence a $X$, e um máximo é uma cota superior que pertence a $X$.
• Um elemento $m$ de $X$ é minimal se nenhum elemento de $X$ distinto dele o precede, e maximal se ele não precede nenhum elemento de $X$ distinto de si mesmo.
• O ínfimo de $X$ é o máximo do conjunto de suas cotas inferiores, e o supremo é o mínimo do conjunto de suas cotas superiores, quando existem.