Uyfyhig

El teorema de isomorfismo

Si dos estructuras A y B son isomorfas, entonces son id´nticas e excepto por sus dominios. - A y B son indistinguibles. En particular: La l´gica de primer orden no deber´ poder o ıa distinguir entre estructuras isomorfas. - Vamos a demostrar esto. - ¿Por qu´ este resultado es fundamental? e

39

El teorema de isomorfismo: Una primera versi´n o

Dado: unvocabulario L y L-estructuras A y B. Teorema: Si A y B son estructuras isomorfas, entonces para cada L-oraci´n ϕ se tiene que: o A |= ϕ si y s´lo si o B |= ϕ

¿C´mo podemos demostrar este Teorema? o
- ¿Podemos usar inducci´n? o - Tenemos que demostrar una versi´n mas fuerte del teorema. o

40

El teorema de isomorfismo: Una segunda versi´n o

Notaci´n: Si h : A → B es una biyecci´n que muestra queA y B son o o estructuras isomorfas, entonces h es un isomorfismo de A en B.

Nota: Si σ es una asignaci´n para A, entonces h ◦ σ es una o asignaci´n para B. o Teorema: Sea σ una asignaci´n para A y h un isomorfismo de A o en B. Entonces para toda L-f´rmula ϕ: o (A, σ) |= ϕ si y s´lo si (B, h ◦ σ) |= ϕ o La primera versi´n del teorema es un corolario de esta versi´n m´s o o a fuerte.
41

Elteorema de isomorfismo: Aplicaciones

Antes de demostrar el teorema de isomorfismo, vamos a ver una de sus aplicaciones. Notaci´n: Si (A, σ) |= ϕ(x1 , . . . , xk ) y σ(xi ) = ai (i ∈ [1, k]), entonces o decimos que A |= ϕ(a1 , . . . , ak ). El problema de definibilidad: Dada una estructura A y S ⊆ Ak (k ≥ 1), decimos que S es definible en A si existe una f´rmula ϕ(x1 , . . . , xk ) tal o que S = {(a1, . . . , ak ) ∈ Ak | A |= ϕ(a1 , . . . , ak )}.

42

El problema de definibilidad: Ejemplos

¿Qu´ conjuntos definen las siguientes f´rmulas en N, +, · ? e o ϕ1 (x) ϕ2 (x) ϕ3 (x, y) = ∀y(x + y = y), = ∀y(x · y = y), = ∃z(¬ϕ1 (z) ∧ x + z = y).

Para demostrar que un conjunto es definible tenemos que construir una f´rmula. o ¿C´mo podemos demostrar que un conjunto no es definible? o - ¡Podemosusar el teorema de isomorfismo!
43

El problema de definibilidad y el teorema de isomorfismo
¿Es la multiplicaci´n definible en R, + ? o - Si esto es cierto, entonces existe ϕ(x, y, z) tal que para todo a, b, c ∈ R: R, + |= ϕ(a, b, c) si y s´lo si o a · b = c.

- Entonces para todo isomorfismo h de R, + en R, + , se tiene que: R, + |= ϕ(a, b, c) si y s´lo si o R, + |= ϕ(h(a), h(b), h(c)).Sea h : R → R definida por h(x) =

x . 2

- h es un isomorfismo de R, + en R, + . R, + |= ϕ(2, 2, 4) y R, + |= ϕ(h(2), h(2), h(4)). ¡Tenemos una contradicci´n! o
44

El problema de definibilidad y el teorema de isomorfismo

1. Demuestre que la suma no es definible en R, · . 2. Demuestre que la suma no es definible en N, · . 3. ¿Puede usarse el teorema de isomorfismo para mostrar que lamultiplicaci´n no es definible en N, + ? o

45

El teorema de isomorfismo: Demostraci´n o

Ahora vamos a demostrar por inducci´n la versi´n fuerte del teorema de o o isomorfismo. - Dado: un vocabulario L y L-estructuras A y B. Necesitamos el siguiente lema: Lema: Si σ es una asignaci´n para A y h es un isomorfismo de A en B, o entonces h ◦ σ = h ◦ σ . ˆ Demostraci´n: Por inducci´n en los L-t´rminos. o oe - Para cada constante c ∈ L: h ◦ σ(c) = cB = h(cA ) = h(ˆ (c)) = σ (h ◦ σ )(c). ˆ
46

El teorema de isomorfismo: Demostraci´n o

- Para cada variable x: h ◦ σ(x) = (h ◦ σ)(x) = h(σ(x)) = h(ˆ (x)) = σ (h ◦ σ )(x). ˆ - Para cada funci´n n-aria f ∈ L: Si h ◦ σ(ti ) = (h ◦ σ )(ti ) para todo o ˆ i ∈ [1, n], entonces h ◦ σ(f (t1 , . . . , tn )) = = = = = = f B (h ◦ σ(t1 ), . . . , h ◦ σ(tn )) fB ((h ◦ σ )(t1 ), . . . , (h ◦ σ )(tn )) ˆ ˆ f B (h(ˆ (t1 )), . . . , h(ˆ (tn ))) σ σ h(f A (ˆ (t1 ), . . . , σ (tn ))) σ ˆ h(ˆ (f (t1 , . . . , tn ))) σ (h ◦ σ )(f (t1 , . . . , tn )). ˆ
47

El teorema de isomorfismo: Demostraci´n o

Vamos a demostrar el teorema por inducci´n en la estructura de ϕ: o - Si ϕ = t1 = t2 , entonces: (A, σ) |= t1 = t2 si y s´lo si o σ (t1 ) = σ (t2 ) ˆ ˆ si y...