Em combinatória, estamos quase sempre contando o número de elementos de conjuntos ou número de subconjuntos com determinada propriedade. Por isso este material possui uma seção dedicado a este tópico.
Utilizamos o conceito de conjunto, como no ensino médio, como uma ideia de coleção. Uma noção completa com os axiomas da teoria dos conjuntos foge do propósito deste material. Para mais informações sobre a teoria dos conjuntos veja [6.1] ou Teoria ingênua dos conjuntos 1
a letra grega \(\Omega\) representará o conjunto universo.
letras minúsculas indicarão elementos dos conjuntos. Ex. \(a, b, \ldots, z\text{.}\)
A relação de pertencer será indicada pela letra grega \(\in\) e escrevemos por exemplo, \(a\in A\text{.}\) O conjunto vazio será representado pela letra \(\varnothing\text{.}\) Um conjunto com um número reduzido de elementos será indicado simplesmente listando seus elementos. Por exemplo, o conjunto que consiste nos números \(1, 2\) e \(3\) será representado por
\begin{equation*}
A = \{ 1, 2, 3 \}
\end{equation*}
Um conjunto também pode ser descrito por uma propriedade \(\pi\text{,}\) comum a todos os seus elementos e escrevemos
\begin{equation*}
A = \{ x|x \text{ tem a propriedade } \pi \}.
\end{equation*}
Por exemplo,
\begin{equation*}
A = \{ x|x = 2k, k\in\mathbb{Z} \}
\end{equation*}
é o conjunto dos números inteiros e pares.
Definição1.1.1.
Usamos o símbolo \(\#A\) para representar o número de elementos do conjunto \(A\text{,}\) isto é, a cardinalidade de \(A\text{.}\)
Definição1.1.2.
Se todo elemento de um conjunto \(A\) é também elemento de um conjunto \(B\text{,}\) dizemos que \(A\) é subconjunto de \(B\) e escrevemos simbolicamente \(A\subset B\text{.}\) Se \(A\subset B\) mas existe um elemento \(b\in B\) tal que \(b\notin A\text{,}\) diremos que \(A\) é um subconjunto próprio de B.
Definição1.1.3.
Sejam \(A\) e \(B\) dois conjuntos. \(A\) e \(B\) são chamados de conjuntos iguais quando todo elemento de \(A\) pertence a \(B\) e, reciprocamente, todo elemento de \(B\) pertence a \(A\text{.}\)
\begin{equation*}
A=B \Leftrightarrow (\forall x)(x \in A \Leftrightarrow x \in B ).
\end{equation*}
Isto é, \(A\subset B\) e \(B\subset A\text{;}\) portanto, podemos escrever:
\begin{equation*}
A=B \Leftrightarrow A \subset B \text{ e } B \subset A.
\end{equation*}
Para ilustrar definições, resultados e demonstrações da teoria de conjuntos, é muito comum usar uma representação gráfica chamada de diagrama de Venn.
Definição1.1.4.
Os diagramas de Venn consistem em curvas fechadas simples, tais como círculos ou ovais, desenhadas sobre um plano, de forma a simbolizar os conjuntos e permitir a representação das relações de pertinência entre conjuntos e seus elementos (por exemplo, \(A = \{1, 2, 3, 4\}\))
Figura1.1.5.Conjunto \(A\text{.}\) e relações de continência (inclusão) entre os conjuntos (por exemplo, \(\{1, 3\} \subset \{1, 2, 3, 4\}\)). Assim, duas curvas que não se tocam e estão uma no espaço interno da outra simbolizam conjuntos que possuem continência;
\begin{equation*}
\bigcap_{i=1}^{n}A_i = A_1\cap \cdots \cap A_n =\{ \omega\in\Omega| \omega\in A_1 \text{ e } \omega\in A_2 \text{ e }\cdots \text{ e } \omega\in A_n \}.
\end{equation*}
Dizemos que \(A_1\) e \(A_2\) são disjuntos se \(A_1\cap A_2=\varnothing\text{.}\) E dizemos que \(A_1, A_2, \ldots, A_n\) são disjuntos quando forem disjuntos dois a dois, ou seja,
\begin{equation*}
A_i\cap A_j = \varnothing, \text{ para quaisquer } i, j \in\{1, 2, \ldots n\}, \text{ com } i\neq j.
\end{equation*}
O conjunto complementar de \(A_i\) é o conjunto dos elementos de \(\Omega\) que não pertencem a \(A_i\text{.}\) Simbolicamente
O produto cartesiano de \(A_1\) por \(A_2\) é o conjunto de pares ordenados \((a_1, a_2)\text{,}\) na qual \(a_1\in A_1\) e \(a_2\in A_2\text{.}\) Simbolicamente,
Sejam \(A, B\) e \(C\) conjuntos; então, valem as seguintes propriedades:
\(\displaystyle A\cap (B\cup C) = (A\cap B)\cup(A\cap C);\)
\(\displaystyle A\cup (B\cap C) = (A\cup B)\cap(A\cup C).\)
Demonstração.
Demonstração do item 1:
\begin{align*}
x\in A\cap(B\cup C) \amp \Leftrightarrow x\in A \text{ e } x\in B\cup C \Leftrightarrow x\in A \text{ e } (x\in B \text{ ou } x\in C) \\
\amp \Leftrightarrow (x\in A \text{ e }x\in B) \text{ ou } (x\in A\text{ e }x\in C) \\
\amp \Leftrightarrow (x\in A\cap B) \text{ ou } (x\in A\cap C) \\
\amp \Leftrightarrow x\in (A\cap B)\cup(A\cap C)
\end{align*}
O segundo pode ser demonstrado de forma análoga.
Teorema1.1.9.
(Leis de Morgan) Sejam \(A\) e \(B\) conjuntos. São válidas as seguintes propriedades:
\(\displaystyle (A \cup B)^c=A^c \cap B^c;\)
\(\displaystyle (A \cap B)^c=A^c \cup B^c.\)
Demonstração.
Vamos demonstrar a primeira destas propriedades. A outra é demonstrada de forma análoga. Usamos o fato de que \((A \cup B)^c=A^c \cap B^c\text{,}\) se, e somente se, \((A \cup B)^c \subset A^c \cap B^c\) e \(A^c \cap B^c \subset (A \cup B)^c\text{.}\)
Seja \(x \in (A \cup B)^c\text{,}\) logo \(x \notin (A \cup B)\text{.}\) Sendo assim, \(x \notin A\) e \(x \notin B\text{.}\) Portanto \(x \in A^c\) e \(x \in B^c\text{,}\) logo \(x \in (A^c \cap B^c)\text{.}\) Acabamos de mostrar que \((A \cup B)^c \subset A^c \cap B^c\text{.}\)
Considere \(x \in A^c \cap B^c\text{,}\) então \(x \in A^c\) e \(x \in B^c\text{.}\) Logo \(x \notin A\text{,}\)\(x \notin B\) e \(x \notin (A\cap B)\text{.}\) Portanto, \(x \notin (A \cup B)\text{,}\) sendo assim \(x \in (A \cup B)^c\text{.}\) Acabamos de mostrar que \(A^c \cap B^c \subset (A \cup B)^c\text{.}\) Portanto
\begin{equation*}
(A \cup \ B)^c=A^c \cap B^c.
\end{equation*}
