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: ${\text{Succ}}_1$ (Sucessor).
  • $\text{Succ}\left(x\right)$ lê-se "o sucessor de $x$".
• Relações: ${\text{Nat}}_1$ (Número Natural).
  • $\text{Nat}\left(x\right)$ lê-se "$x$ é um número natural".
• Regras (Axiomas de Peano):
  1. Zero é um número (natural). $$\text{Nat}\left(0\right)$$
  2. O sucessor de um número é um número. $$\forall n\left(\text{Nat}\left(n\right)\to \text{Nat}\left(\text{Succ}\left(n\right)\right)\right)$$
  3. Zero não é um sucessor. $$\forall n\left(0\ne \text{Succ}\left(n\right)\right)$$
  4. Números diferentes têm sucessores diferentes. $$\forall m,n\left(m\ne n\to \text{Succ}\left(m\right)\ne \text{Succ}\left(n\right)\right)$$
  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\left(R\left(0\right)\wedge \forall nR\left(n\right)\to R\left(\text{Succ}\left(n\right)\right)\right)\to R=\text{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 $\text{Succ}$: $$\begin{array}{rl}1& :=\text{Succ}\left(0\right)\\ 2& :=\text{Succ}\left(1\right)=\text{Succ}\left(\text{Succ}\left(0\right)\right)\\ 3& :=\text{Succ}\left(2\right)=\text{Succ}\left(\text{Succ}\left(\text{Succ}\left(0\right)\right)\right)\\ & ⋮\end{array}$$ Usa-se "$a:=b$" para indicar que $a$ é, por definição, $b$. Também se escreve "$x^{\prime }$" em vez de "$\text{Succ}\left(x\right)$": $$\begin{array}{rl}1& :=0^{\prime }\\ 2& :=1^{\prime }=0^{\prime \prime }\\ 3& :=2^{\prime }=1^{\prime \prime }=0^{\prime \prime \prime }\\ & ⋮\end{array}$$

Em geral também se escreve "$x\in \mathbb{N}$" em vez de "$\text{Nat}\left(x\right)$".

Operações

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

Definição (Soma)

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

• Base: $$\forall m\text{Nat}\left(m\right)\to \text{Soma}\left(0,m\right)=m$$
• Passo: $$\forall n,m\text{Nat}\left(n\right)\wedge \text{Nat}\left(m\right)\to \text{Soma}\left(\text{Succ}\left(n\right),m\right)=\text{Succ}\left(\text{Soma}\left(n,m\right)\right)$$

Como é comum, escreve-se $n+m$ em vez $\text{Soma}\left(n,m\right)$.

Exemplo. $2+2=4$

Definição (Subtração)

A subtração é a função binária ${\text{Subt}}_2$ definida a partir da $\text{Soma}$ da seguinte forma: $$\forall n,m,k\left(\text{Subt}\left(n,m\right)=k\leftrightarrow \text{Soma}\left(m,k\right)=n\right)$$ Como é comum, escreve-se "$n-m$" em vez "$\text{Subt}\left(n,m\right)$".

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: $\varnothing$ lê-se "conjunto vazio".
• Relações:
  • Conjunto: ${\text{Conjunto}}_1$; "$\text{Conjunto}\left(x\right)$" lê-se "$x$ é um conjunto".
  • Pertence: $\text{Pertence}\left(x,y\right)$ também se escreve $x\in y$ e lê-se "$x$ pertence a $y$" ou "$x$ é elemento de $y$".
  • Subconjunto: $\text{Subconjunto}\left(x,y\right)$ 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: $\text{Intersec¸a˜o}\left(x,y\right)$ também se escreve $x\cap y$ e lê-se "a interseção de $x$ com $y$".
  • União: $\text{Unia˜o}\left(x,y\right)$ também se escreve $x\cup y$ e lê-se "a união de $x$ com $y$".
  • Inclusão: $\text{Inclusa˜o}\left(x,y\right)$ também se escreve $\left\{x|y\right\}$ 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\text{Conjunto}\left(s\right)\leftrightarrow s=\varnothing \vee \exists x,s_0\text{Conjunto}\left(s_0\right)\wedge s=\left\{x|s_0\right\}.$$
  2. O vazio não tem elementos. $$\neg \exists x,s\left(\varnothing =\left\{x|s\right\}\right).$$
  3. Acrescentar um elemento que já está no conjunto não tem efeito. $$\forall x,s\left(x\in s\leftrightarrow s=\left\{x|s\right\}\right).$$
  4. Os (únicos) elementos que estão num conjunto (são elementos que) foram incluídos. $$\forall x,s\left(x\in s\leftrightarrow \left[\exists y,s_0\left(s=\left\{y|s_0\right\}\wedge \left(x=y\vee x\in s_0\right)\right)\right]\right).$$

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

• O conjunto $\varnothing$ tem zero elementos.
• O conjunto $\left\{\varnothing \right\}$ tem um elemento, o conjunto $\varnothing$.
• O conjunto $\left\{\left\{\varnothing \right\}\right\}$ também tem um elemento, $\left\{\varnothing \right\}$. Portanto, como $\left\{\varnothing \right\}\ne \varnothing$, também $\left\{\left\{\varnothing \right\}\right\}\ne \left\{\varnothing \right\}$ porque os respetivos elementos são diferentes.
• Sucessivamente, $\left\{\left\{\left\{\varnothing \right\}\right\}\right\}\ne \left\{\left\{\varnothing \right\}\right\}$, 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{array}{rlrlrl}\left[2,2\right]& \ne \left[2\right]& & & \left\{2,2\right\}& =\left\{2\right\}\\ \left[1,2\right]& \ne \left[2,1\right]& & & \left\{1,2\right\}& =\left\{2,1\right\}\end{array}$$

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

Notação:

• $\left[x|y\right]:\text{Cons}\left(x,y\right)$.
• $\left[x\right]:\left[x|\left[\right]\right]$.
• $\left[x_1,x_2,\dots \right]:\left[x_1|\left[x_2,\dots \right]\right]$.

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 $\text{Cons}$ nas listas é análoga a $\text{Succ}$ nos números e à inclusão nos conjuntos.