Inducción y recursión

Notas sobre inducción y recursión
Pablo Báez Echevarría
pab_24n@outlook.com

Lógica - Facultad de Ingeniería - Udelar
Julio de 2013

UNIVERSIDAD
DE LA REPUBLICA
URUGUAY

Índice
1. Introducción

3

2. Definiciones inductivas
3
2.1. Forma general de una definición inductiva . . . . . . . . . . . . . . .
3
2.2. Interpretación de las reglas . . . . . . . . . . . . . . . . . . . . .. . .
4
2.2.1. Interpretación constructiva . . . . . . . . . . . . . . . . . . . .
5
2.2.2. Interpretación declarativa . . . . . . . . . . . . . . . . . . . .
6
2.2.3. Equivalencia de las interpretaciones constructiva y declarativa 6
2.3. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3. Principio de Inducción Primitiva (PIP)
3.1. Enunciado formal ydemostración . . . . . . . . . . . . . . . . . . . .
3.2. Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Pertenencia a un conjunto definido inductivamente . . . . . . . . . .

10
10
11
12

4. Esquema de Recursión Primitiva (ERP)
4.1. Definición inductiva libre . . . . . . . . . . . . . . .
4.2. Esquema de recursión primitiva para X . . . . . .
4.3. Ejemplode aplicación . . . . . . . . . . . . . . . . .
4.4. Ejercicio 1 del Examen de Lógica de Julio de 2013

13
13
18
20
21

2

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

1.

Introducción

El objetivo de estas notas es brindar a los estudiantes de Lógica un material de
apoyo para losprimeros temas del curso (inducción y recursión) para los cuales no
hay un libro de cabecera en donde aclararse las dudas e interrogantes que a uno le
surgen leyendo las diapositivas. Ojalá estos apuntes sirvan para dicho propósito.

2.

Definiciones inductivas

2.1.

Forma general de una definición inductiva

Para definir inductivamente un conjunto, llámese X, se sigue el siguienteprocedimiento: se especifica un conjunto U llamado Universo conocido de antemano, y
se dan ciertas reglas (tambíen llamadas cláusulas) que pueden ser de dos tipos:
Ë Base: dicen que ciertos elementos del Universo pertenecen al conjunto X.
Son de la forma: α ∈ X.
Ë Inductivas: dicen que si ciertos elementos del Universo pertenecen a X
entonces otro elemento, formado de alguna manera a partir de losanteriores, también pertenece a X. Son de la forma: Si α1 , . . . , αn ∈ X entonces
F (α1 , . . . , αn ) ∈ X.
De esta manera, de aquí en más, trabajaremos con una definición inductiva genérica, que es la siguiente:
Forma general de de una definición inductiva
Sea U ≠ ∅ el conjunto Universo y X ⊆ U definido inductivamente por
1)
⋮
r)
r+1)
⋮
r+t)

β1 ∈ X
βr ∈ X
Si α1 , . . . , αa1 ∈ X entoncesF1 (α1 , . . . , αa1 ) ∈ X
Si α1 , . . . , αat ∈ X entonces Ft (α1 , . . . , αat ) ∈ X

donde βi ≠ βj , ∀i ≠ j y Fk ∶ U ak → U son funciones, ak ∈ Z+ , ∀k = 1, . . . , t.

En la definición precedente hay r reglas base y t reglas inductivas. Observar que
3

cada regla base introduce un único elemento del Universo al conjunto X. Eso
podría llegar a ser una limitación: por ejemplo,considérese la siguiente definición
inductiva de N × N (como subconjunto de R2 ):
i
ii

Si n ∈ N entonces (n, 0) ∈ N × N
Si (n, m) ∈ N × N entonces (n, m + 1) ∈ N × N

La cláusula i es una cláusula base (o un conjunto de cláusulas base) y no inductiva
porque no supone que tenemos elementos de N × N sino de otro conjunto definido
previamente (el de los números naturales). De esta manera, la regla i,siendo una
regla base, está introduciendo al conjunto que queremos definir, que es N × N,
tantos elementos como tiene N (en vez de uno solo). Naturalmente, para ajustarla
a la definición general que acabamos de dar, uno podría sustituirla por:
i
ii
iii
⋮

(0, 0) ∈ N × N
(1, 0) ∈ N × N
(2, 0) ∈ N × N
⋮

pero en tal caso, hemos dejado de tener un número finito de reglas base. Para...