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.

Referências https://www.cin.ufpe.br/~mlogica/livros/Apostila%20-%20Logica%20Proposicional.pdf http://w3.impa.br/~paesleme/Logica/Inducao.pdf

Categoria:Matemática aplicada