Tema 3: Conjuntos y Funciones

Dpto. Ciencias de la Computaci´ on e Inteligencia Artificial Universidad de Sevilla

L´ ogica y Computabilidad Curso 2008–09

LC, 2008–09

Conjuntos y Funciones

3.1

Conjuntos I I I

I

Escribimos x ∈ C para expresar que x es un elemento de C . Adem´as, x 6∈ C expresa que x NO es un elemento de C . Dada una propiedad Θ, denotamos por {t : Θ(t)} al conjunto formado por aquellos elementos que verifican la propiedad Θ. El conjunto vac´ıo de denota por ∅.

Igualdad entre conjuntos I

Dos conjuntos A y B son iguales si tienen los mismos elementos, es decir, si Para todo x, x ∈ A

I

x ∈B

Por tanto, dada una propiedad, Θ, si A = {x : Θ(x)} entonces, para todo x, x ∈A

LC, 2008–09

⇐⇒

⇐⇒

Θ(x)

Conjuntos y Funciones

3.2

Subconjuntos I

A es un subconjunto de B, y lo expresamos, A ⊆ B, si todo elemento de A es elemento de B, es decir, Para todo x, x ∈ A

I

=⇒

x ∈B

En consecuencia, A=B

⇐⇒

A⊆B yB⊆A

As´ı, podemos probar que dos conjuntos A y B son iguales por doble inclusi´on, es decir, probando que A ⊆ B y B ⊆ A.

LC, 2008–09

Conjuntos y Funciones

3.3

Operaciones con conjuntos I

Uni´ on: A ∪ B = {x : x ∈ A ´ o x ∈ B}

I

Intersecci´ on: A ∩ B = {x : x ∈ A y x ∈ B}

I

Diferencia: A − B = {x : x ∈ A y x ∈ / B}

I

Complementario: Fijado un conjunto C , para cada A ⊆ C el complementario de A (en C ) se define como A = C − A = {x ∈ C : x ∈ / A}

I

Conjunto Potencia: Dado un conjunto A, el conjunto potencia de A (o conjunto de las partes de A) es P(A) = {C : C ⊆ A}

LC, 2008–09

Conjuntos y Funciones

3.4

Producto cartesiano I

Producto cartesiano: A × B = {(u, v ) : u ∈ A y v ∈ B}, donde (u, v ) denota al par ordenado formado por u y v .

I

La propiedad caracter´ıstica de los pares ordenados es (a, b) = (c, d)

I

⇐⇒

a=c yb=d

En general, para cada n ≥ 3, podemos considerar n-tuplas, (a1 , a2 , ..., an ), cuya propiedad caracter´ıstica es:

(a1 , . . . , an ) = (b1 , . . . , bn )

⇐⇒

a1 = b1 , a2 = b2 , . . . , an = bn

I

A1 × ... × An = {(x1 , ..., xn ) : x1 ∈ A1 ∧ ... ∧ xn ∈ An }.

I

(n Si A1 = ... = An = A, escribiremos An = A × A× ... ×A. Adem´as, la n–tupla (x1 , . . . , xn ) se denotar´a por ~x .

LC, 2008–09

Conjuntos y Funciones

3.5

Funciones I

Una funci´ on f es un conjunto de pares ordenados, tal que (a, b) ∈ f y (a, c) ∈ f

I

=⇒

b=c

El dominio de una funci´ on f es el conjunto: dom(f ) = {x : ∃y ((x, y ) ∈ f )}

I

El rango de f es el conjunto: rang (f ) = {y : ∃x ((x, y ) ∈ f )}

I

Si f es una funci´on, para cada a ∈ dom(f ) existe un u ´nico b ∈ rang (f ) tal que (a, b) ∈ f . Por ello usaremos la notaci´on habitual, f (a) = b para expresar que (a, b) ∈ f .

I

Ejemplo: Sea A un conjunto. La funci´ on identidad de A es la funci´on IdA : A → A, dada por IdA (x) = x.

LC, 2008–09

Conjuntos y Funciones

3.6

Igualdad entre funciones I

Notaci´on: Escribiremos f (x) ↓ para expresar que x ∈ dom(f ) y utilizaremos la notaci´ on f (x) ↑ para expresar que x∈ / dom(f ). (En este u ´ltimo caso se dice que f no est´a definida en x).

I

Si f y g son funciones, entonces f = g si y s´ olo si tienen los mismos elementos (pares ordenados). Por tanto,   dom(f ) = dom(g ) y f =g ⇐⇒  para todo x ∈ dom(f ), f (x) = g (x)

⇐⇒

LC, 2008–09

  f (x) ↓ ⇐⇒ y Para todo x,  f (x) = g (x)

g (x) ↓

Conjuntos y Funciones

3.7

Tipos de funciones Sean A y B dos conjuntos y f una funci´ on. I

on total de A en B) y f es una aplicaci´ on de A en B (o funci´ escribiremos f : A −→ B, si dom(f ) = A

I

f es una funci´ on parcial de A en B, f : A − → B, si dom(f ) ⊆ A

I

y rang (f ) ⊆ B

y

Una funci´on f : A − → B es: I

inyectiva si para todo x1 , x2 ∈ dom(f ), f (x1 ) = f (x2 )

LC, 2008–09

rang (f ) ⊆ B

=⇒

x1 = x2

I

sobreyectiva (o suprayectiva o exhaustiva) si rang (f ) = B, es decir, ∀y ∈ B∃x ∈ A(f (x) = y )

I

biyectiva si es total, inyectiva y sobreyectiva. Conjuntos y Funciones

3.8

Composici´ on de funciones Sean f : A − → B y g : B − → C . Se define la composici´ on de f y g como la funci´on (parcial) h : A − → C dada por h = {(x, y ) ∈ A × C : Existe z ∈ B tal que f (x) = z y g (z) = y } Gr´aficamente, f

g

A −→ B −→ C x 7→ f (x) 7→ g (f (x))

(= h(x))

Notaci´on: h = g ◦ f .

LC, 2008–09

Conjuntos y Funciones

3.9

Funci´ on inversa I

Dada una funci´on f decimos que una funci´ on g es la inversa de f si, para todo x y todo y se tiene, f (x) = y

⇐⇒

g (y ) = x

I

Si existe, la inversa de f es u ´nica y se denota por f −1 .

I

Sea f una funci´on. Entonces, f tiene inversa

I

⇐⇒

f es inyectiva.

Proposici´ on: Sea f : A −→ B una aplicaci´ on. Entonces, 1. f −1 es aplicaci´ on de B en A ⇐⇒ f es biyectiva (en cuyo caso, f −1 tambi´en ser´a biyectiva) 2. Si f es biyectiva, f ◦ f −1 = IdB y f −1 ◦ f = IdA . Si, adem´as, A = B entonces, f ◦ f −1 = f −1 ◦ f

LC, 2008–09

Conjuntos y Funciones

3.10

Conjuntos numerables Definici´ on: Un conjunto A es numerable si existe una aplicaci´on biyectiva de N en A. I

Si un conjunto, A, es numerable, entonces los elementos de A pueden ordenarse en una lista infinita sin repeticiones: a0 , a1 , . . . , an , . . .

I

N2 es numerable. Para probarlo, basta demostrar que la siguiente funci´on J : N2 → N es biyectiva: J(x, y ) =

(x + y )(x + y + 1) +x 2

I

En general, para cada k ≥ 2, el conjunto Nk es numerable.

I

El conjunto de los n´ umeros racionales Q es numerable.

LC, 2008–09

Conjuntos y Funciones

3.11

Conjuntos no numerables No todo conjunto infinito es numerable. I

Ejemplos: I I I

El conjunto de los n´ umeros reales, R. El intervalo [0, 1) ⊆ R. P(N).

Estos resultados fueron probados por G. Cantor utilizando la misma idea b´asica: El m´etodo diagonal de Cantor.

LC, 2008–09

Conjuntos y Funciones

3.12

Predicados y conjuntos Definici´ on: (n ≥ 1) Un predicado n–ario sobre A es una aplicaci´on θ : An → {0, 1}. I

Dado (x1 , . . . , xn ) ∈ An , si θ(x1 , ..., xn ) = 1 diremos que el predicado θ se verifica (o que es cierto) para (x1 , ..., xn ). Escribiremos θ(~x ) en vez de θ(~x ) = 1.

I

Si θ(x1 , ..., xn ) = 0 diremos que el predicado no se verifica (o que es falso) para (x1 , ..., xn ).

I

Podemos identificar un predicado n–ario sobre A, θ : An → {0, 1}, con un subconjunto de An : Sθ = {~x ∈ An : θ(~x ) = 1}

I

LC, 2008–09

Los predicados nos permiten identificar con funciones los subconjuntos de A y, en general, las relaciones entre elementos de A. Conjuntos y Funciones

3.13

Funci´ on caracter´ıstica Definici´ on: Sea B ⊆ An . Llamaremos funci´ on caracter´ıstica del subconjunto B, al predicado CB definido sobre An como sigue:  1 si ~x ∈ B CB (~x ) = 0 si ~x ∈ /B I

La funci´on caracter´ıstica de B ⊆ An , nos permite identificar el conjunto B con un predicado (precisamente, CB ).

I

Si θ es un predicado n–ario sobre A y B = Sθ entonces CB = θ.

LC, 2008–09

Conjuntos y Funciones

3.14

Operaciones con predicados I

Definici´ on: Dados los predicados θ y θ0 , definimos los predicados ¬θ, θ ∨ θ0 , θ ∧ θ0 , θ → θ0 y θ ↔ θ0 , as´ı: I I I I I

I

Estas operaciones reflejan las operaciones entre conjuntos del siguiente modo. Sean θ1 y θ2 predicados n–arios sobre An . Entonces I I I

LC, 2008–09

(¬θ)(~x ) ≡ ¬θ(~x ) = 1 − θ(~x ). (θ ∨ θ0 )(~x ) ≡ θ(~x ) ∨ θ0 (~x ) = max(θ(~x ), θ0 (~x )) (θ ∧ θ0 )(~x ) ≡ θ(~x ) ∧ θ0 (~x ) = min(θ(~x ), θ0 (~x )). θ → θ0 = (¬θ) ∨ θ0 . θ ↔ θ0 = (θ → θ0 ) ∧ (θ0 → θ).

Sθ1 ∨θ2 = Sθ1 ∪ Sθ2 . Sθ1 ∧θ2 = Sθ1 ∩ Sθ2 . S¬θ1 = An − Sθ1 .

Conjuntos y Funciones

3.15

Cuantificaci´ on acotada Sea θ(x1 , ..., xn , y ) un predicado (n + 1)–ario sobre N. El predicado obtenido a partir de θ por cuantificaci´ on existencial acotada es el predicado (n + 1)–ario sobre N que denotaremos por (∃z)≤y θ y se define mediante:  1 si existe z0 ≤ y tal que θ(~x , z0 ). (∃z)≤y θ(~x , z) = 0 en caso contrario El predicado obtenido a partir de θ por cuantificaci´ on universal acotada es el predicado (n + 1)–ario sobre N que denotaremos por (∀z)≤y θ y se define mediante:  1 si para todo z0 ≤ y se tiene θ(~x , z0 ). (∀z)≤y θ(~x , z) = 0 en caso contrario I I LC, 2008–09

(∃z)≤y θ(~x , z) = θ(~x , 0) ∨ θ(~x , 1) ∨ ... ∨ θ(~x , y ) (∀z)≤y θ(~x , z) = θ(~x , 0) ∧ θ(~x , 1) ∧ ... ∧ θ(~x , y ) Conjuntos y Funciones

3.16

Cuantificaci´ on no acotada Sea θ(x1 , ..., xn , y ) un predicado (n + 1)–ario sobre N. El predicado obtenido a partir de θ por cuantificaci´ on existencial es el predicado n–ario sobre N que denotaremos por (∃z) θ y se define mediante:  1 si existe z0 tal que θ(~x , z0 ). (∃z) θ(~x , z) = 0 en caso contrario. El predicado obtenido a partir de θ por cuantificaci´ on universal es el predicado n–ario sobre N que denotaremos por (∀z) θ y se define mediante:  1 si para todo z0 se tiene θ(~x , z0 ). (∀z) θ(~x , z) = 0 en caso contrario.

LC, 2008–09

Conjuntos y Funciones

3.17

El principio de minimizaci´ on I

Expresi´ on sobre predicados. Sea θ un predicado 1–ario sobre N. Si ∃x θ(x) entonces ∃m (θ(m) ∧ ∀y < m ¬θ(y )) I

Notaci´ on: indicaremos que m es m´ınimo escribiendo: m = µx(θ(x))

I

Expresi´ on conjuntista. Sea A ⊆ N. Si A 6= ∅ entonces ∃m (m ∈ A ∧ ∀y < m(y ∈ / A)) I

Notaci´ on: indicaremos que m es el m´ınimo escribiendo: m = min(A)

I

Ejercicio: Probar utilizando este principio que: I

LC, 2008–09

“Todo n´ umero natural n ≥ 2 es divisible por un n´ umero primo”. Conjuntos y Funciones

3.18

El principio de Inducci´ on I

Inducci´ on d´ ebil. Teorema: Si θ es un predicado sobre N tal que: 1. Caso base: θ(0), y 2. Paso inductivo: ∀n(θ(n) −→ θ(n + 1))

I

Entonces, ∀n θ(n). Ejercicio: Probar utilizando este principio que: I

n X i=0

I

n X

i=

n(n + 1) 2

(2i + 1) = (n + 1)2

i=0

LC, 2008–09

Conjuntos y Funciones

3.19

El Principio de Inducci´ on (II) I

Inducci´ on fuerte Teorema: Si θ es un predicado sobre N tal que: 1. Caso base: θ(0), y 2. Paso inductivo: ∀n([∀p ≤ n θ(p)] −→ θ(n + 1)).

I

Entonces, ∀n φ(n). Ejercicio: Probar utilizando este principio que: I

LC, 2008–09

“Todo n´ umero natural n ≥ 2 puede descomponerse en un producto de n´ umeros primos”.

Conjuntos y Funciones

3.20