Conjuntos indutivamente definidos
# Conjuntos indutivamente definidos
## Definição

Suponha que A seja um conjunto e que X seja um subconjunto próprio de A (i.e. X ⊂ A). Agora suponha que F seja um conjunto de funções sobre A, cada uma com sua aridade. Um subconjunto Y de A é dito indutivo em relação a X e F se:
* Y contém X.
* Y é fechado sob as funções de F. Ou seja, Se f є F e, x1, x2, ..., xk є X então, f(x1, x2, ..., xk) є Y.

## Observação

- Aridade: Característica da função relativa ao número de parâmetros que ela recebe. Por exemplo, funções unárias e binárias. A função “eleva ao quadrado” recebe um número e retorna outro número (seu quadrado). Por isso é uma função unária. Já a função “soma” recebe dois números e retorna um número (a soma deles). Portanto é uma função binária.

## Fecho indutivo

Existem duas famosas abordagens para a construção de conjuntos definidos indutivamente:
* Top-down (de cima para baixo).
* Bottom-up (de baixo para cima).

## Top-down

Desejamos encontrar o menor dos conjuntos indutivos sob X e F. Para isso podemos imaginar uma “família” de subconjuntos de A que são todos indutivos sob X e F. Essa família não é vazia, pois o próprio A pertence a ela. Agora tome a intersecção de todos os conjuntos dessa família, o resultado será, naturalmente, o menor dos conjuntos indutivos sob X e F. - Notação: X$^+$

## Bottom-up

Um processo iterativo que começa pelo X, e vai completando com o que falta para que se chegue a um conjunto que seja fechado sob F, portanto indutivo sob X e F. Matematicamente:
Xo = X
Xn+1 = Xn U {f(x1, x2, ..., xk)/(x1, x2, ..., xk) є Xn, f є F, aridade (F) = k}.
Agora tome a união de todos os Xi, 0 ≤ i < ∞. Obtemos assim, no limite, um conjunto que contém X e é fechado sob F, portanto é o fecho indutivo de X sob F. - Notação: X+

## Prova que X$^+$ = X+

X$^+$ = X+
1) X$^+$ ⊆ X+
Como X$^+$ é a intersecção da família de todas os indutivos, basta mostrar que X+ é um membro da família de todos os indutivos. Isto é, X+ é também um conjunto indutivo sob X e F. Devemos mostrar que:
1.1) X+ contém X.
1.2) X+ é fechado sob F.
Pela definição X+ obviamente contém X. Para mostrar que X+ é fechado em F, temos que mostrar que para todo f є F, tal que aridade(F) = k, e toda k-upla w1, w2, ..., wk de argumentos de X+, f(w1, w2, ..., wk) também pertence a X+.
Como X+ é a união de todos Xi, para 0 ≤ i e Xi+1 é definida como sendo Xi U {f(w1, w2, ..., wk)/f є F e w1, w2, ..., wk є Xi} temos que, sempre que w1, w2, ..., wk são elementos de Xi, f(w1, w2, ..., wk) será um elemento de Xi+1, e, portanto, de X+.
2) X+ ⊆ X$^+$
Podemos mostrar que para toda etapa i, Xi ⊆ X$^+$.
Por indução sobre i:
Caso base: i = 0.
Xo ⊆ X$^+$, pois X$^+$ é indutivo e Xo = X.
Caso indutivo:
Hipótese indutiva: Xj ⊆ X$^+$
Tese: Xj+1 ⊆ X$^+$
Pela definição de Xj+1, se Xj ⊆ X$^+$, então Xj+1 ⊆ X$^+$, pois X$^+$ é fechado sob F.