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
editarSuponha 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- 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
editarExistem 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
editarDesejamos 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
editarUm 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+
editarX+ = 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.