Notacion declaratoria

Introduciremos una notacion que hace mas dinamica e intuitiva la manera de escribir las cosas. Por supuesto el precio que esto tiene es que deberemos dedicarnos bastante a aprender a manejar esta notacion en forma precisa, para no perder rigor matematico.

7.10.1 Notacion declaratoria para terminos

t

es un termino de tipo

τ

, entonces escribiremos

t =_{d} t (v_{1}, . . ., v_{n})

para declarar que

v_{1}, . . ., v_{n}

son variables distintas (con

n \geq 1

) y tales que toda variable que ocurre en

t

pertenece a

{v_{1}, . . ., v_{n}}

(no necesariamente toda

v_{j}

debe ocurrir en

t

El uso de declaraciones de la forma

t =_{d} t (v_{1}, . . ., v_{n})

sera muy util cuando se lo convina con ciertas convenciones notacionales que describiremos a continuacion.

Notese que cuando las palabras

P_{i}^{'} s

son terminos,

t (P_{1}, . . ., P_{n})

es un termino (Lema 7.6). Ademas notese que en esta convencion notacional, el orden de las variables

v_{1}, . . ., v_{n}

es clave. Por ejemplo si

τ = (\emptyset, {F U}, \emptyset, {(F U, 2)})

t = F U (F U (x_{2}, x_{16}), x_{3})

y declaramos

t =_{d} t (x_{3}, x_{2}, x_{16})

, entonces

Tambien podriamos haber declarado

t =_{d} t (x_{3}, x_{200}, x_{2}, x_{16}, x_{100})

y en tal caso

t (# #,!!!!, ▴ # ▴, @ @,!!)

denotara la palabra

F U (F U (▴ # ▴, @ @), # #)

Nuevamente cabe destacar que en esta convencion notacional, el orden de las variables

v_{1}, . . ., v_{n}

es clave. Por ejemplo si

τ

t

son los dados en el ejemplo anterior y

A

es dado por

A = {1, 2, 3}

{F U}^{A} (i, j) = j

, para cada

i, j \in A

, tenemos que

Tambien podriamos haber declarado

t =_{d} t (x_{3}, x_{200}, x_{2}, x_{16}, x_{100})

y en tal caso

t^{A} [2, 10, 1, 3, 1000] = 2

Lectura unica de terminos declarados

Para establecer nuestra Convencion Notacional 3, debemos antes probar un lema de "lectura de terminos declarados", el cual sera muy util para hacer demostraciones usando la notacion declaratoria.

7.24 (Lectura unica de terminos declarados). Sea $τ$ un tipo cualquiera y supongamos $t \in T^{τ}$ . Si $t =_{d} t (v_{1}, . . ., v_{n})$ , entonces se da una y solo una de las siguientes:

(1) $t = c,$ para algun $c \in C$
(2) $t = v_{j},$ para algun $j$
(3) $t = f (t_{1}, . . ., t_{m})$ , con $f \in F_{m}$ y $t_{1}, . . ., t_{m} \in T^{τ}$ unicos y tales que las variables que ocurren en cada uno de ellos estan en ${v_{1}, . . ., v_{n}}$

Cabe destacar que esta ultima convencion notacional junto con la Convencion Notacional 1, nos dice que cuando se de el caso (3) del Lema 7.24, si

P_{1}, . . ., P_{n}

son palabras cualesquiera, entonces

t (P_{1}, . . ., P_{n}) = f (t_{1} (P_{1}, . . ., P_{n}), . . ., t_{m} (P_{1}, . . ., P_{n}))

Caracter recursivo de la notacion

t^{A} [a_{1}, . . . ., a_{n}]

El siguiente lema se basa en la Convencion Notacional 3 y nos permite darle caracter recursivo a la notacion

t^{A} [a_{1}, . . . ., a_{n}]

. Esto sera muy util para hacer demostraciones usando la notacion declaratoria.

7.25 (Caracter recursivo de la notacion $t^{A} [a_{1}, . . . ., a_{n}]$ ). Sea $τ$ un tipo cualquiera y $t \in T^{τ}$ . Supongamos $t =_{d} t (v_{1}, . . ., v_{n})$ . Sea $A$ un modelo de tipo $τ$ . Sean $a_{1}, . . ., a_{n} \in A$ . Se tiene que:

(1) Si $t = c,$ entonces $t^{A} [a_{1}, . . . ., a_{n}] = c^{A}$
(2) Si $t = v_{j},$ entonces $t^{A} [a_{1}, . . . ., a_{n}] = a_{j}$
(3) Si $t = f (t_{1}, . . ., t_{m})$ , con $f \in F_{m}$ y $t_{1}, . . ., t_{m} \in T^{τ}$ , entonces $t^{A} [a_{1}, . . . ., a_{n}] = f^{A} (t_{1}^{A} [a_{1}, . . . ., a_{n}], . . ., t_{m}^{A} [a_{1}, . . . ., a_{n}])$

(3) Sea

\vec{b}

una asignacion tal que a cada

v_{i}

le asigna el valor

a_{i}

. Tenemos que

\begin{aligned} t^{A} [a_{1}, . . . ., a_{n}] & = t^{A} [\vec{b}] (por def. de t^{A} [a_{1}, . . . ., a_{n}]) \\ = f^{A} (t_{1}^{A} [\vec{b}], . . ., t_{m}^{A} [\vec{b}]) (por def. de t^{A} [\vec{b}]) \\ = f^{A} (t_{1}^{A} [a_{1}, . . . ., a_{n}], . . ., t_{m}^{A} [a_{1}, . . . ., a_{n}]) (por def. de cada t_{i}^{A} [a_{1}, . . . ., a_{n}]) \end{aligned}

7.26. Supongamos que $F : A \to B$ es un homomorfismo. Sea $t =_{d} (v_{1}, . . ., v_{n}) \in T^{τ}$ . Entonces

$F (t^{A} [a_{1}, a_{2}, . . ., a_{n}]) = t^{B} [F (a_{1}), F (a_{2}), . . ., F (a_{n})]$

{Teo}_{k} :

Sea

F : A \to B

un homomorfismo y sea

t =_{d} (v_{1}, . . ., v_{n}) \in T_{k}^{τ}

. Entonces

F (t^{A} [a_{1}, a_{2}, . . ., a_{n}]) = t^{B} [F (a_{1}), F (a_{2}), . . ., F (a_{n})]

Probaremos primero que vale

{Teo}_{0}

. Como

t =_{d} (v_{1}, . . ., v_{n}) \in T_{0}^{τ} = {V a r \cup C}

, tenemos que dos casos posibles. Si

t = c

, para algún

c \in C

entonces tenemos lo siguiente

\begin{aligned} 2 F (t^{A} [a_{1}, a_{2}, . . ., a_{n}]) & = F (c^{A}) \\ = c^{B} \\ = t^{B} [F (a_{1}), F (a_{2}), . . ., F (a_{n})] \end{aligned}

\begin{aligned} 1 F (t^{A} [a_{1}, a_{2}, . . ., a_{n}]) & = F (a_{j}) \\ = t^{B} [F (a_{1}), F (a_{2}), . . ., F (a_{n})] \end{aligned}

Veamos ahora que

{Teo}_{k} implica {Teo}_{k + 1}

. Podemos suponer que

t \in T_{k + 1}^{τ} - T_{k}^{τ}

, usando el lema anterior tenemos que

t = f (t_{1}, . . ., t_{m})

con

f \in F_{m}

t_{1}, . . ., t_{m} \in T_{k}^{τ}

. Dado a que hemos declarado

t =_{d} (v_{1}, . . ., v_{n})

, por la Convención Notacional 3, tenemos declarados también

t_{1} =_{d} (v_{1}, . . ., v_{n}), . . ., t_{m} =_{d} (v_{1}, . . ., v_{n})

. Entonces

\begin{aligned} 2 F (t^{A} [a_{1}, a_{2}, . . ., a_{n}]) & = F (f^{A} (t_{1}^{A} [a_{1}, a_{2}, . . ., a_{n}], . . ., t_{m}^{A} [a_{1}, a_{2}, . . ., a_{n}])) \\ = f^{B} (F (t_{1}^{A} [a_{1}, a_{2}, . . ., a_{n}]), . . ., F (t_{m}^{A} [a_{1}, a_{2}, . . ., a_{n}]))) \\ = f^{B} (t_{1}^{B} [F (a_{1}), . . ., F (a_{n})], . . ., F (t_{m}^{B} [F (a_{1}), . . ., F (a_{n})]))) & ({\text{Teo}}_{k}) \\ = t^{B} [F (a_{1}), F (a_{2}), . . ., F (a_{n})] \end{aligned}

7.10.2 Notacion declaratoria para formulas

φ

es una formula de tipo

τ

, entonces escribiremos

φ =_{d} φ (v_{1}, . . ., v_{n})

para declarar que

v_{1}, . . ., v_{n}

son variables distintas (con

n \geq 1

) tales que

L i (φ) \subseteq {v_{1}, . . ., v_{n}}

. Tal como para el caso de terminos, el uso de declaraciones de la forma

φ =_{d} φ (v_{1}, . . ., v_{n})

sera muy util cuando se convina con ciertas convenciones notacionales que describiremos a continuacion.

Notese que cuando las palabras

P_{i}^{'} s

son terminos,

φ (P_{1}, . . ., P_{n})

es una formula. Ademas notese que tal como para el caso de terminos, en esta convencion notacional, el orden de las variables

v_{1}, . . ., v_{n}

es clave. Es facil dar el ejemplo analogo al dado para terminos.

Nuevamente cabe destacar que en esta convencion notacional, el orden de las variables

v_{1}, . . ., v_{n}

es clave. Veamos un ejemplo. Sea

τ = (\emptyset, {F}, {E}, {(F, 1), (E, 2)})

y sea

φ = ((F (x_{16}) \equiv F (x_{17})) \land \forall x_{16} E (x_{2}, x_{16}))

Sea

A

el modelo de tipo

τ

dado por

A = {1, 2, 3, 4, 5}

F^{A} (x) = max {x, 3}

E^{A} = {1} \times A

. Entonces

Lectura unica de formulas declaradas

Para establecer nuestra Convencion Notacional 6, debemos antes enunciar un "lema de lectura unica de formulas declaradas".

7.27 (Lectura unica de formulas declaradas). Sea $τ$ un tipo cualquiera y $φ \in F^{τ}$ . Supongamos $φ =_{d} φ (v_{1}, . . ., v_{n})$ . Entonces se una y solo una de las siguientes:

(1) $φ = (t \equiv s)$ , con $t, s \in T^{τ}$ , unicos y tales que las variables que ocurren en $t$ o en $s$ estan todas en ${v_{1}, . . ., v_{n}}$
(2) $φ = r (t_{1}, . . ., t_{m})$ , con $r \in R_{m}$ y $t_{1}, . . ., t_{m} \in T^{τ}$ , unicos y tales que las variables que ocurren en cada $t_{i}$ estan todas en ${v_{1}, . . ., v_{n}}$
(3) $φ = (φ_{1} \land φ_{2})$ , con $φ_{1}, φ_{2} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \cup L i (φ_{2}) \subseteq {v_{1}, . . ., v_{n}}$
(4) $φ = (φ_{1} \lor φ_{2})$ , con $φ_{1}, φ_{2} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \cup L i (φ_{2}) \subseteq {v_{1}, . . ., v_{n}}$
(5) $φ = (φ_{1} \to φ_{2})$ , con $φ_{1}, φ_{2} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \cup L i (φ_{2}) \subseteq {v_{1}, . . ., v_{n}}$
(6) $φ = (φ_{1} \leftrightarrow φ_{2})$ , con $φ_{1}, φ_{2} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \cup L i (φ_{2}) \subseteq {v_{1}, . . ., v_{n}}$
(7) $φ = \neg φ_{1}$ , con $φ_{1} \in F^{τ}$ , unica y tal que $L i (φ_{1}) \subseteq {v_{1}, . . ., v_{n}}$
(8) $φ = \forall v_{j} φ_{1}$ , con $v_{j} \in {v_{1}, . . ., v_{n}}$ y $φ_{1} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \subseteq {v_{1}, . . ., v_{n}}$
(9) $φ = \forall v φ_{1}$ , con $v \in V a r - {v_{1}, . . ., v_{n}}$ y $φ_{1} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \subseteq {v_{1}, . . ., v_{n}, v}$
(10) $φ = \exists v_{j} φ_{1}$ , con $v_{j} \in {v_{1}, . . ., v_{n}}$ y $φ_{1} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \subseteq {v_{1}, . . ., v_{n}}$
(11) $φ = \exists v φ_{1}$ , con $v \in V a r - {v_{1}, . . ., v_{n}}$ y $φ_{1} \in F^{τ}$ , unicas y tales que $L i (φ_{1}) \subseteq {v_{1}, . . ., v_{n}, v}$

Convencion Notacional 6: Cuando hayamos declarado $φ =_{d} φ (v_{1}, . . ., v_{n})$ , entonces:

- si se da el caso (1) del Lema 7.27, supondremos tacitamente que tambien hemos hecho las declaraciones $t =_{d} t (v_{1}, . . ., v_{n})$ y $s =_{d} s (v_{1}, . . ., v_{n})$ .

- si se da el caso (2) del Lema 7.27, supondremos tacitamente que tambien hemos hecho las declaraciones $t_{1} =_{d} t_{1} (v_{1}, . . ., v_{n}), . . ., t_{m} =_{d} t_{m} (v_{1}, . . ., v_{n})$ .

- si se da cualquiera de los casos (3), (4), (5) o (6) del Lema 7.27, supondremos tacitamente que tambien hemos hecho las declaraciones $φ_{1} =_{d} φ_{1} (v_{1}, . . ., v_{n})$ y $φ_{2} =_{d} φ_{2} (v_{1}, . . ., v_{n})$ .

- si se da cualquiera de los casos (7), (8) o (10) del Lema 7.27, supondremos tacitamente que tambien hemos hecho la declaracion $φ_{1} =_{d} φ_{1} (v_{1}, . . ., v_{n})$ .

- si se da el caso (9) o el caso (11) del Lema 7.27, supondremos tacitamente que tambien hemos hecho la declaracion $φ_{1} =_{d} φ_{1} (v_{1}, . . ., v_{n}, v)$ .

Caracter recursivo de la notacion

A ⊨ φ [a_{1}, . . . ., a_{n}]

El siguiente lema se basa en la Convencion Notacional 6 y nos permite darle caracter recursivo a la notacion

A ⊨ φ [a_{1}, . . . ., a_{n}]

. Esto sera muy util para hacer demostraciones usando la notacion declaratoria.

7.28 (Caracter recursivo de la notacion $A ⊨ φ [a_{1}, . . . ., a_{n}]$ ). Supongamos $φ =_{d} φ (v_{1}, . . ., v_{n})$ . Sea $A = (A, i)$ un modelo de tipo $τ$ y sean $a_{1}, . . ., a_{n} \in A$ . Entonces

(1) Si $φ = (t \equiv s)$ , entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $t^{A} [a_{1}, . . ., a_{n}] = s^{A} [a_{1}, . . ., a_{n}]$
(2) Si $φ = r (t_{1}, . . ., t_{m})$ , entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $(t_{1}^{A} [a_{1}, . . ., a_{n}], . . ., t_{m}^{A} [a_{1}, . . ., a_{n}]) \in r^{A}$
(3) Si $φ = (φ_{1} \land φ_{2}),$ entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊨ φ_{1} [a_{1}, . . . ., a_{n}]$ y $A ⊨ φ_{2} [a_{1}, . . . ., a_{n}]$
(4) Si $φ = (φ_{1} \lor φ_{2}),$ entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊨ φ_{1} [a_{1}, . . . ., a_{n}]$ o $A ⊨ φ_{2} [a_{1}, . . . ., a_{n}]$
(5) Si $φ = (φ_{1} \to φ_{2}),$ entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊨ φ_{2} [a_{1}, . . . ., a_{n}]$ o $A ⊭ φ_{1} [a_{1}, . . . ., a_{n}]$
(6) Si $φ = (φ_{1} \leftrightarrow φ_{2}),$ entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si ya sea $A ⊨ φ_{1} [a_{1}, . . . ., a_{n}]$ y $A ⊨ φ_{2} [a_{1}, . . . ., a_{n}]$ o $A ⊭ φ_{1} [a_{1}, . . . ., a_{n}]$ y $A ⊭ φ_{2} [a_{1}, . . . ., a_{n}]$
(7) Si $φ = \neg φ_{1},$ entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊭ φ_{1} [a_{1}, . . . ., a_{n}]$
(8) Si $φ = \forall v_{j} φ_{1},$ entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊨ φ_{1} [a_{1}, . . . ., a, . . ., a_{n}],$ para todo $a \in A .$
(9) Si $φ = \forall v φ_{1},$ con $v \notin {v_{1}, . . ., v_{n}}$ , entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊨ φ_{1} [a_{1}, . . . ., a_{n}, a]$ , para todo $a \in A .$
(10) Si $φ = \exists v_{j} φ_{1}$ , entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊨ φ_{1} [a_{1}, . . . ., a, . . ., a_{n}]$ , para algun $a \in A .$
(11) Si $φ = \exists v φ_{1}$ , con $v \notin {v_{1}, . . ., v_{n}}$ , entonces
1. - $A ⊨ φ [a_{1}, . . . ., a_{n}]$ si y solo si $A ⊨ φ_{1} [a_{1}, . . . ., a_{n}, a]$ , para algun $a \in A .$

7.10 Notacion declaratoria

7.10.1 Notacion declaratoria para terminos

Lectura unica de terminos declarados

Caracter recursivo de la notacion tA[a1,....,an]tA[a1,....,an]

7.10.2 Notacion declaratoria para formulas

Lectura unica de formulas declaradas

Caracter recursivo de la notacion A⊨φ[a1,....,an]A⊨φ[a1,....,an]

Caracter recursivo de la notacion $t^{A} [a_{1}, . . . ., a_{n}]$

Caracter recursivo de la notacion $A ⊨ φ [a_{1}, . . . ., a_{n}]$