Conjuntos indutivamente definidos
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Junho de 2012) |
 | Esta página ou seção carece de contexto. (Maio de 2013) |
Definição[editar | editar código-fonte]
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[editar | editar código-fonte]
- 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[editar | editar código-fonte]
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[editar | editar código-fonte]
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[editar | editar código-fonte]
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+[editar | editar código-fonte]
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.