Números, Conjuntos e Listas

Linguagem dos Números Naturais

Os números naturais são a base da aritmética e de todo o desenvolvimento numérico da matemática, informática, etc.

• Constantes: $0$ (Zero).
• Funções: $\lit{Succ}_1$ (Sucessor).
  • $\fat{Succ}{x}$ lê-se “o sucessor de $x$”.
• Relações: $\lit{Nat}_1$ (Número Natural).
  • $\fat{Nat}{x}$ lê-se “$x$ é um número natural”.
• Regras (Axiomas de Peano):
  1. Zero é um número (natural). $$ \fat{Nat}{0} $$
  2. O sucessor de um número é um número. $$ \forall n~\del{\fat{Nat}{n} \to \fat{Nat}{\fat{Succ}{n}}} $$
  3. Zero não é um sucessor. $$ \forall n~\del{0\not=\fat{Succ}{n}} $$
  4. Números diferentes têm sucessores diferentes. $$ \forall m, n~\del{m\not=n \to \fat{Succ}{m} \not= \fat{Succ}{n}} $$
  5. O Princípio de Indução é de segunda ordem; não pode ser enunciado na lógica de primeira ordem e, portanto, não será usado aqui. $$ \forall R ~\del{R\at{0} \land \forall n~R\at{n} \to R\at{\fat{Succ}{n}}} \to R = \lit{Nat} $$

Escrita de números e as operações aritméticas comuns

As definições iniciais são suficientes para toda a aritmética. Normalmente escrevemos expressões como $2 + 3 \times 4$ que não fazem parte dessas definições.

Números naturais

Embora só tenha sido definido um número natural, o $0$, os restantes resultam de aplicações sucessivas função $\lit{Succ}$: $$ \begin{aligned} 1 &:= \fat{Succ}{0} \cr 2 &:= \fat{Succ}{1} = \fat{Succ}{\fat{Succ}{0}}\cr 3 &:= \fat{Succ}{2} = \fat{Succ}{\fat{Succ}{\fat{Succ}{0}}}\cr &\vdots \end{aligned} $$ Usa-se “$a := b$” para indicar que $a$ é, por definição, $b$. Também se escreve “$x’$” em vez de “$\fat{Succ}{x}$”: $$ \begin{aligned} 1 &:= 0’ \cr 2 &:= 1’ = 0’‘\cr 3 &:= 2’ = 1’’ = 0’‘’\cr &\vdots \end{aligned} $$

Em geral também se escreve “$x \in \mathbb{N}$” em vez de “$\fat{Nat}{x}$”.

Operações

As operações comuns da aritmética, soma, produto, subtração e divisão, são definidas a partir de $\lit{Succ}$. Por exemplo:

Definição (Soma)

A soma é a função binária $\lit{Soma}_2$ definida recursivamente da seguinte forma:

• Base: $$ \forall m~\fat{Nat}{m} \to \fat{Soma}{0, m} = m $$
• Passo: $$ \forall n,m~\fat{Nat}{n} \land \fat{Nat}{m} \to \fat{Soma}{ \fat{Succ}{n}, m} = \fat{Succ}{\fat{Soma}{n,m}} $$

Como é comum, escreve-se $n + m$ em vez $\fat{Soma}{n, m}$.

Exemplo. $2 + 2 = 4$

Definição (Subtração)

A subtração é a função binária $\lit{Subt}_2$ definida a partir da $\lit{Soma}$ da seguinte forma: $$ \forall n, m, k~\del{\fat{Subt}{n,m} = k \liff \fat{Soma}{m, k} = n} $$ Como é comum, escreve-se “$n - m$” em vez “$\fat{Subt}{n, m}$”.

Linguagem dos Conjuntos

“Conjunto” é o conceito matemático mais fundamental. Com conjuntos definem-se relações, funções, e outros objetos como, por exemplo, os números naturais.

• Termos: São de dois tipos, elementos e conjuntos.
• Constantes: $\emptyset$ lê-se “conjunto vazio”.
• Relações:
  • Conjunto: $\lit{Conjunto}_1$; “$\fat{Conjunto}{x}$” lê-se “$x$ é um conjunto”.
  • Pertence: $\fat{Pertence}{x,y}$ também se escreve $x \in y$ e lê-se “$x$ pertence a $y$” ou “$x$ é elemento de $y$”.
  • Subconjunto: $\fat{Subconjunto}{x,y}$ também se escreve $x \subseteq y$ e lê-se “$x$ está contido em $y$” ou “$x$ é sub-conjunto de $y$” ou “$y$ contém $x$”.
• Funções:
  • Interseção: $\fat{Interseção}{x,y}$ também se escreve $x \cap y$ e lê-se “a interseção de $x$ com $y$”.
  • União: $\fat{União}{x,y}$ também se escreve $x \cup y$ e lê-se “a união de $x$ com $y$”.
  • Inclusão: $\fat{Inclusão}{x,y}$ também se escreve $\cbr{x|y}$ e lê-se “a inclusão de $x$ a $y$”.
• Regras:
  1. Os únicos conjuntos são o vazio e os que resultam de acrescentar um elemento a outro conjunto. $$ \forall s~\fat{Conjunto}{s} \liff s = \emptyset \lor \exists x, s_0~\fat{Conjunto}{s_0} \land s = \cbr{x|s_0}. $$
  2. O vazio não tem elementos. $$ \neg \exists x,s~\del{\emptyset = \cbr{x|s}}. $$
  3. Acrescentar um elemento que já está no conjunto não tem efeito. $$ \forall x, s~\del{x\in s\liff s = \cbr{x|s}}. $$
  4. Os (únicos) elementos que estão num conjunto (são elementos que) foram incluídos. $$ \forall x,s~\del{x\in s\liff \sbr{\exists y,s_0~\del{s = \cbr{y|s_0} \land \del{x = y \lor x \in s_0}}}}. $$

O conjunto vazio, $\emptyset$, desempenha um papel semelhante ao zero $0$ nos números naturais — é a partir de $\empty$ que se formam todos os restantes conjuntos. E, continuando esta analogia, a operação de inclusão é semelhante a sucessor. Por exemplo: $$ \begin{aligned} \cbr{\emptyset} &:= \cbr{ \emptyset ~|~ \emptyset } \cr \cbr{\cbr{\emptyset}} &:= \cbr{\cbr{\emptyset} ~|~ \emptyset}\cr \cbr{\cbr{\cbr{\emptyset}}} &:= \cbr{\cbr{\cbr{\emptyset}} ~|~ \emptyset}\cr &\vdots \end{aligned} $$ Todos estes conjuntos são diferentes:

• O conjunto $\emptyset$ tem zero elementos.
• O conjunto $\cbr{\emptyset}$ tem um elemento, o conjunto $\emptyset$.
• O conjunto $\cbr{\cbr{\emptyset}}$ também tem um elemento, $\cbr{\emptyset}$. Portanto, como $\cbr{\emptyset} \not= \emptyset$, também $$\cbr{\cbr{\emptyset}} \not= \cbr{\emptyset}$$ porque os respetivos elementos são diferentes.
• Sucessivamente, $\cbr{\cbr{\cbr{\emptyset}}} \not= \cbr{\cbr{\emptyset}}$, etc.

Linguagem das Listas

As listas são uma das estruturas de dados mais utilizadas na informática.

As listas são semelhantes aos conjuntos porque têm elementos. A diferença é que uma lista pode ter elementos repetidos e a ordem conta. Por exemplo: $$ \begin{aligned} \sbr{2,2} &\not= \sbr{2} &&& \cbr{2, 2} &= \cbr{2} \cr \sbr{1,2} &\not= \sbr{2, 1} &&& \cbr{1, 2} &= \cbr{2, 1} \cr \end{aligned} $$

• Termos: São de dois tipos, elementos e listas.
• Constantes: $\sbr{~}$ lê-se lista vazia ou nil.
• Relações:
  • Lista: $\lit{List}_1$; “$\fat{List}{x}$” lê-se “$x$ é uma lista”.
  • Pertence: $\lit{Find}_2$; “$\fat{Find}{x, y}$” lê-se “$x$ está em $y$”.
• Funções:
  • Construção: $\lit{Cons}_2$; “$\fat{Cons}{x, y}$” lê-se “construção de $x$ com $y$”.
  • Acrescentar: $\lit{Append}_2$; “$\fat{Append}{x, y}$” lê-se “$y$ acrescentada a $x$”.
  • Primeiro: $\lit{First}_1$; “$\fat{First}{x}$” lê-se “o primeiro de $x$”.
  • Restantes: $\lit{Rest}_1$; “$\fat{Rest}{x}$” lê-se “os restantes de $x$”.
• Regras: (versão informal)
  • $\sbr{~}$ é a lista sem elementos.
  • $\fat{List}{x}:$ $x$ é lista.
  • $\fat{Find}{x,y}:$ $x$ está na lista $y$.
  • $\fat{Cons}{x,y}:$ é a lista que resulta de acrescentar o elemento $x$ à frente de $y$. Isto é, $z = \fat{Cons}{x, y}$ se e só se $x = \fat{First}{z}$ e $y = \fat{Rest}{z}$.
  • $\fat{Append}{x,y}$ é a lista que resulta de acrescentar a lista $y$ ao fim da lista $x$.
  • $\fat{First}{x}:$ o primeiro elemento da lista $x$.
  • $\fat{Rest}{x}:$ a lista $x$ sem o primeiro elemento.

Notação:

• $\sbr{x|y} : \fat{Cons}{x, y}$.
• $\sbr{x}: \sbr{x|\sbr{~}}$.
• $\sbr{x_1, x_2, \ldots}: \sbr{x_1|\sbr{x_2, \ldots}}$.

Tal como o zero nos números naturais e o conjunto vazio nos conjuntos, também a lista vazia é o termo mais simples, a partir do qual resultam todos os outros. A operação $\lit{Cons}$ nas listas é análoga a $\lit{Succ}$ nos números e à inclusão nos conjuntos.