[Tarea 6] Duda pregunta 2b

[tvergara]

Hola, tengo una duda en la pregunta 2b, ya que creo que encontré un contraejemplo de por qué no podría existir la construcción que piden (considerando que no se puden usar los operadores $\emptyset$, $\bar \alpha$, ni $\cup$).

Esta construcción debe partir por ya sea $I$ o $R$ ya que $Z$ no está permitida. La cardinalidad de $R(\mathfrak{U})$ es $|R|$ y la cardinalidad de $I(\mathfrak{U})$ es de $|A|$.

Además, el paso $\alpha = \gamma \circ \beta$ hace que $|\alpha(\mathfrak{U} )| \leq |\gamma(\mathfrak{U} )| $ y que $|\alpha(\mathfrak{U}) | \leq |\beta(\mathfrak{U} )| $ Al igual que, el paso $\alpha = \gamma \cap \beta$ hace que $|\alpha(\mathfrak{U} )| \leq |\gamma(\mathfrak{U} )| $ y que $|\alpha(\mathfrak{U}) | \leq |\beta(\mathfrak{U} )| $ Finalmente, el paso $\alpha = \gamma^{-1}$ hace que $|\alpha(\mathfrak{U} )| = |\gamma(\mathfrak{U} )| $

Por lo tanto, cada paso reduce o mantiene la cardinalidad. Por end la cardinalidad de una construcción $\alpha$ está acotada por $max(|R|, |A|)$

Por ejemplo, si $\phi(x,y)$ fuese $\exists z_1, \exists z_2 R(z_1, z_2)$ y digamos que efectivamente existe alguna entrada en $R$, este la construcción para este $\phi$ debiese tener cardinalidad $|A|^2$. Sin embargo, si $|R| < |A|^2$ y $|A| >1$, entonces no se debiera poder encontrar una construcción para este $\phi(x,y)$.

Puede ser que sí se deben usar los operadores $\emptyset$, $\bar \alpha$, o $\cup$ para hacer esta construcción? O creo que falta exigir que x e y estén en en algún lado de la consulta? O hay algo que no estoy viendo?

[fjquintana]

Hola!

No es verdad que $\alpha = \gamma \circ \beta$ hace que $|\alpha(\mathfrak{A} )| \leq |\gamma(\mathfrak{A} )| $ y que $|\alpha(\mathfrak{A}) | \leq |\beta(\mathfrak{A} )| $. Por ejemplo, si $R^{\mathfrak{A}} =$ { $(1, 9), (2, 9), (3, 9), (4, 9), (9, 5), (9, 6), (9, 7), (9, 8) $}, y $\gamma = \beta = R$, entonces tendríamos que $|\gamma(\mathfrak{A})| = |\beta(\mathfrak{A})| = 8 $, pero $|\alpha(\mathfrak{A})| = 16$.

[tvergara]

Toda la razón en eso, me confudí en ese paso, pero igual creo que hay algo raro. Pongamos el caso en donde $A = ${$0,1$}, $R = ${$(0,0), (1,1)$} y la fórmula $\alpha(x,y) = \exists z_1,z_2 \ R(x, z_1) \wedge R(z_2, y)$. A simple vista se puede ver que $\alpha(\mathfrak{U}) = ${$ (0,0),(0,1), (1,0),(1,1)$} (ya que siempre basta con $x=z_1$ y $y=z_2$ para satisfacerla)

Sin embargo, notemos que $R = I$, y por ende, como las expresiones bases permitidas eran $R$ e $I$ (ya que $Z$ o está permitido), tenemos que siempre la expresión base con la que debieramos partir la construcción es $I$. Notar que $I \circ I = I$, $I \cap I = I$ y que $I^{-1} = I$. Por ende, ningún paso puede afectar la expresión. Por lo tanto, nunca podemos representar $\alpha(\mathfrak{U})$ ya que $\alpha(\mathfrak{U}) \neq I$.

O qué no estoy viendo? (Perdón lo largo, pero no estoy encontrando la construcción por estos casos)

[juanreutter]

Uff si, muchas gracias Tomás! efectivamente falta algún operador para armar AxA (que se arma usualmente tal y como pones en tu ejemplo!). El operador que no puse es: Si $\alpha$ y $\beta$ son expresiones, entonces $\alpha | \beta$ también es una expresión, con semántica: $$\alpha | \beta (\mathfrak{A}) = \big((a,b) \mid \text{ exiten } c,d \in A, (a,c) \in \alpha(\mathfrak A), (d,b) \in \beta(\mathfrak A)\big)$$

Les pido disculpas a todos por esta omisión, me pasó que cambié la pregunta a última hora y se me fue este detalle.