Encontrar un universo adecuado para una estructura dada

Question

Encontrar un universo adecuado para una estructura dada

lógica
funciones
Matemáticas
teoría de modelos
Relaciones
álgebra-universal

gianna albertini

Soy nuevo en este foro, así que espero que mi forma matemática de escribir aquí sea correcta, ya que no lo he hecho mucho antes. :(

Actualmente estoy tomando mi clase de lógica y me topé con la siguiente tarea.

Nos dan una estructura $\mathcal{G}$ del álgebra universal que implica el dominio (o universo ) $G$ := $\wp(\mathbb{N})$ (el conjunto potencia de los números naturales), una firma $\omega:=\{\cup,\cap\ , ^c \}$ dónde $\{\cup,\cap\, ^c \}$ es el conjunto de símbolos de función y $^c$ es simplemente el complemento de $\{G'^c= \mathbb{N} \setminus G'$ | $G'\in\wp(\mathbb{N})\}$ - de acuerdo con la definición . (Tenemos una estructura puramente algebraica sin símbolos de relación).

Además, se nos dan dos subconjuntos del universo. $\wp(\mathbb{N})$ (que son, de nuevo, universos en sí mismos) con

(1) $\{G'' \subseteq \mathbb{N}$ | $G''$ finito}.

(2) $\{G'' \subseteq \mathbb{N}$ | $G''$ , $G''^c$ infinito}.

Y, tal como lo entendí, se supone que debemos probar si existe una subestructura de $\mathcal{G}$ sobre el universo (1). Si no, daremos la subestructura más pequeña de $\mathcal{G}$ que contiene (1) . Lo mismo para el universo (2).

Entonces, lo que sí sé es que una subestructura $\mathcal{F}$ (con su universo $F$ ) tiene que cumplir las propiedades

i. el dominio de $\mathcal{F}$ está contenido en el dominio de $\mathcal{G}$ , es decir $|\mathcal{F}| \subseteq |\mathcal{G}|$ . (o $F\subseteq G$ )

ii. $\mathcal{F}$ y $\mathcal{G}$ tener la misma firma $\omega(\mathcal{F}) = \omega(\mathcal{G})$ .

Ahora, entiendo que, trivialmente, (1) no puede ser el universo de una subestructura de $\mathcal{G}$ porque sus subconjuntos no son cerrados bajo el complemento, y (2) tampoco puede serlo, ya que sus subconjuntos no son cerrados bajo la unión. Sin embargo, realmente no sé cómo podría encontrar la subestructura más pequeña de $\mathcal{G}$ que contendría (1), (2), o ambos. Así que realmente agradecería su ayuda.

Muchas gracias Gianna

amrsa

En (1) y (2), es

G \subseteq N

$G \subseteq \mathbb N$ , como lo tienes, o

G \subseteq ℘ (N)

$G \subseteq \wp(\mathbb N)$ ? En el primer caso (como es) es bastante trivial, y lo mismo para ambas preguntas, a menos que esté malinterpretando algo...

gianna albertini

Ciertamente así es

G \subseteq N

$G \subseteq \mathbb{N}$ . Sin embargo, no veo cómo es trivial ... ¿Espero no haber escrito anotaciones conflictivas / confusas?

amrsa

En ese caso, la subestructura generada por

G

$G$ tiene el conjunto subyacente

{\emptyset, GRAMO, norte ∖ GRAMO, norte} .

$\{\varnothing, G, \mathbb N\setminus G, \mathbb N\}.$ Y las operaciones son las mismas que en

℘ (N)

$\wp(\mathbb N)$ . Pero tal vez esto no es lo que quieres?

gianna albertini

¿Quiere decir que su universo propuesto con su firma es la subestructura más pequeña que implica (1) y (2)? Y si cree que lo es, ¿podría explicar por qué implica (1) y (2)? propiedad i. y ii. son triviales obviamente.

amrsa

Si

G \subseteq N

$G\subseteq\mathbb N$ (ya sea finito o infinito), entonces el conjunto anterior se cierra bajo las operaciones de

ω

$\omega$ , y es el conjunto más pequeño que contiene

G

$G$ : en efecto, si

G

$G$ pertenece a cualquiera de esos conjuntos, entonces también lo hace

G^{c} = N ∖ G

$G^c=\mathbb N\setminus G$ , y luego también

\emptyset = G \cap G^{c}

$\varnothing=G\cap G^c$ y

N = G \cup G^{c}

$\mathbb N=G\cup G^c$ .

Alex Kruckmann

Un comentario sobre la escritura. Parece que has usado la letra

G

$G$ por tres cosas completamente diferentes aquí: (a) El dominio de

G

$\mathcal{G}$ ,

G = P (N)

$G = \mathscr{P}(\mathbb{N})$ . (b) Una variable que oscila entre

P (N)

$\mathscr{P}(\mathbb{N})$ en la definición de

^{c}

$^c$ . (c) Un subconjunto de

N

$\mathbb{N}$ utilizado para especificar los subconjuntos de

P (N)

$\mathscr{P}(\mathbb{N})$ que está preguntando en (1) y (2). ¡Esto es bastante confuso!

Alex Kruckmann

Aquí hay algunas otras cosas que me confunden. ¿Puedes aclarar? (1) dices que

^{c}

$^c$ debe ser un símbolo de relación. ¿Cuál es la aridad de este símbolo de relación? ¿Es binario, de modo que

(X, Y)

$(X,Y)$ satisface la relación si y sólo si

Y = X^{c}

$Y = X^c$ ? (2) ¿Está preguntando acerca de un solo finito fijo?

G \subseteq N

$G\subseteq \mathbb{N}$ , o sobre el conjunto de todos

{G \subseteq N ∣ G is finite}

$\{G\subseteq \mathbb{N}\mid G\text{ is finite}\}$ ? Creo que la segunda opción es lo que quisiste decir, pero no está del todo claro. (3) ¿Qué quiere decir con "implica"? ¿Quizás quiso decir "la subestructura más pequeña que contiene [el conjunto definido por] (1)"?

gianna albertini

Lo siento, esta es mi primera pregunta en Stackexchange, así que no conocía las convenciones exactas. :( Con respecto a tus puntos, (1) La aridad (si no me equivoco) es binaria, al mirar cómo

^{c}

$^c$ se define en la tarea. (2) Me refiero a lo último de hecho. Cualquier conjunto arbitrario que sea un subconjunto de (1) o (2). Ya estoy seguro de que no pueden ser un universo para una subestructura potencial, por lo que (3) quiero decir contiene. Lo siento, el inglés no es mi primer idioma, pensé que implicar y contener implicaría lo mismo. @amrsa: Gracias por la explicación.

gianna albertini

@AlexKruckman Acabo de editar la pregunta, espero poder mejorar la legibilidad.

Alex Kruckmann

Gracias por aclarar, ahora está mucho más claro. ¡Bienvenido a Math Stack Exchange!

gianna albertini

Gracias :)) feliz de estar aquí!

amrsa

¡Ay! Esta nueva versión me parece mejor. Verás, decir que el grupo electrógeno es algo así como

G = {F \subseteq N : F is finite}

$G=\{F\subseteq\mathbb N:F\text{ is finite}\}$ es equivalente a

G \subseteq ℘ (N)

$G\subseteq\wp(\mathbb N)$ y

F

$F$ es finito, siempre que

F \in G

$F \in G$ . ¡Ya no es trivial!

Respuestas (1)

Encontrar un universo adecuado para una estructura dada

En (1) y (2), es $G \subseteq \mathbb N$ , como lo tienes, o $G \subseteq \wp(\mathbb N)$ ? En el primer caso (como es) es bastante trivial, y lo mismo para ambas preguntas, a menos que esté malinterpretando algo...
Ciertamente así es $G \subseteq \mathbb{N}$ . Sin embargo, no veo cómo es trivial ... ¿Espero no haber escrito anotaciones conflictivas / confusas?
En ese caso, la subestructura generada por $G$ tiene el conjunto subyacente ${\emptyset, GRAMO, norte ∖ GRAMO, norte} .$ $\{\varnothing, G, \mathbb N\setminus G, \mathbb N\}.$ Y las operaciones son las mismas que en $\wp(\mathbb N)$ . Pero tal vez esto no es lo que quieres?
¿Quiere decir que su universo propuesto con su firma es la subestructura más pequeña que implica (1) y (2)? Y si cree que lo es, ¿podría explicar por qué implica (1) y (2)? propiedad i. y ii. son triviales obviamente.
Si $G\subseteq\mathbb N$ (ya sea finito o infinito), entonces el conjunto anterior se cierra bajo las operaciones de $\omega$ , y es el conjunto más pequeño que contiene $G$ : en efecto, si $G$ pertenece a cualquiera de esos conjuntos, entonces también lo hace $G^c=\mathbb N\setminus G$ , y luego también $\varnothing=G\cap G^c$ y $\mathbb N=G\cup G^c$ .
Un comentario sobre la escritura. Parece que has usado la letra $G$ por tres cosas completamente diferentes aquí: (a) El dominio de $\mathcal{G}$ , $G = \mathscr{P}(\mathbb{N})$ . (b) Una variable que oscila entre $\mathscr{P}(\mathbb{N})$ en la definición de $^c$ . (c) Un subconjunto de $\mathbb{N}$ utilizado para especificar los subconjuntos de $\mathscr{P}(\mathbb{N})$ que está preguntando en (1) y (2). ¡Esto es bastante confuso!
Aquí hay algunas otras cosas que me confunden. ¿Puedes aclarar? (1) dices que $^c$ debe ser un símbolo de relación. ¿Cuál es la aridad de este símbolo de relación? ¿Es binario, de modo que $(X,Y)$ satisface la relación si y sólo si $Y = X^c$ ? (2) ¿Está preguntando acerca de un solo finito fijo? $G\subseteq \mathbb{N}$ , o sobre el conjunto de todos $\{G\subseteq \mathbb{N}\mid G\text{ is finite}\}$ ? Creo que la segunda opción es lo que quisiste decir, pero no está del todo claro. (3) ¿Qué quiere decir con "implica"? ¿Quizás quiso decir "la subestructura más pequeña que contiene [el conjunto definido por] (1)"?
Lo siento, esta es mi primera pregunta en Stackexchange, así que no conocía las convenciones exactas. :( Con respecto a tus puntos, (1) La aridad (si no me equivoco) es binaria, al mirar cómo $^c$ se define en la tarea. (2) Me refiero a lo último de hecho. Cualquier conjunto arbitrario que sea un subconjunto de (1) o (2). Ya estoy seguro de que no pueden ser un universo para una subestructura potencial, por lo que (3) quiero decir contiene. Lo siento, el inglés no es mi primer idioma, pensé que implicar y contener implicaría lo mismo. @amrsa: Gracias por la explicación.
@AlexKruckman Acabo de editar la pregunta, espero poder mejorar la legibilidad.
Gracias por aclarar, ahora está mucho más claro. ¡Bienvenido a Math Stack Exchange!
¡Ay! Esta nueva versión me parece mejor. Verás, decir que el grupo electrógeno es algo así como $G=\{F\subseteq\mathbb N:F\text{ is finite}\}$ es equivalente a $G\subseteq\wp(\mathbb N)$ y $F$ es finito, siempre que $F \in G$ . ¡Ya no es trivial!

Alex Kruckmann · Answer 1

En general, si $\mathcal{A}$ es una estructura y $B\subseteq A$ es un subconjunto del dominio $A$ de $\mathcal{A}$ , entonces $B$ es el dominio de una subestructura de $A$ si y solo si $B$ contiene todas las interpretaciones de símbolos constantes en el lenguaje y está cerrado bajo todas las interpretaciones de símbolos de función en el lenguaje. es decir, si $c$ es un símbolo constante, requerimos que $c^{\mathcal{A}}\in B$ , y si $f$ es un $n$ -símbolo de función aria y $b_1,\dots,b_n\in B$ , requerimos que $f^\mathcal{A}(b_1,\dots,b_n)\in B$ .

Para un subconjunto arbitrario $B\subseteq A$ , hay un subconjunto más pequeño $\langle B\rangle$ que contiene $B$ que es el dominio de una subestructura. Esto se llama la subestructura generada por $B$ . Intuitivamente, $\langle B\rangle$ consta de todos los elementos de $A$ que se puede "construir" a partir de las constantes y los elementos de $B$ aplicando las funciones. Más formalmente, esto puede ser descrito por

⟨ B ⟩ = {t^{A} (b_{1}, \dots, b_{k}) ∣ t (X_{1}, \dots, X_{k}) es un término y b_{1}, \dots, b_{k} \in B} .

$\langle B\rangle = \{t^\mathcal{A}(b_1,\dots,b_k)\mid t(x_1,\dots,x_k) \text{ is a term, and }b_1,\dots,b_k\in B\}.$

Ok, entonces en la situación de tu pregunta, tenemos la estructura. $\mathcal{G} = (\wp(\mathbb{N}),\cup,\cap,^c)$ , dónde $\cup$ , $\cap$ , y $^c$ son símbolos de función (no hay símbolos constantes). Como señalaste, ninguno de los conjuntos dados es el dominio de una subestructura, ya que (1) no es cerrado bajo complementos y (2) no es cerrado bajo intersecciones o unión. Entonces, ¿cuáles son las subestructuras que generan?

Sugerencias:

(1) Los subconjuntos finitos de $\mathbb{N}$ se cierran bajo intersecciones y uniones, pero no bajo complementos. Entonces, como primer paso, podemos agregar sus complementos para obtener $\{X\subseteq \mathbb{N}\mid X\text{ is finite}\}\cup \{X\subseteq \mathbb{N}\mid X^c\text{ is finite}\}$ . ¿Este conjunto es cerrado por intersecciones, uniones y complementos?

(2) el conjunto $F = \{X\subseteq \mathbb{N}\mid X\text{ and }X^c\text{ infinite}\}$ es cerrado bajo complementos, pero no bajo intersecciones y uniones. ¿Qué subconjuntos de $\mathbb{N}$ puedes hacer intersecando dos conjuntos en $F$ ? ¿Qué tal tomando la unión de dos conjuntos en $F$ ?

¡¡Muchas gracias por esta extensa respuesta!! Supongo que lo que me confunde un poco aquí es que la tarea no establece explícitamente si $^c$ es en realidad un símbolo de función o un símbolo de relación. Uno de nuestros tutores aquí dijo que tiene que cerrarse en todas las operaciones. Quizás, todas las operaciones son simplemente símbolos de función. Pero, de nuevo, ¿sería una estructura válida con solo símbolos de función y ningún símbolo de relación?
Veo. En tu pregunta escribiste eso $^c$ es un símbolo de relación, así que opté por eso. Si el problema no especifica, probablemente debería pedirle una aclaración a su profesor, pero creo que es muy probable que $\cap$ , $\cup$ , y $^c$ Todos están destinados a ser símbolos de función. No es necesario que una estructura tenga símbolos de relación: el conjunto de símbolos de relación puede estar vacío (y lo mismo para los símbolos de función y los símbolos constantes).
¡Qué momento, acabo de recibir un correo de nuestro profesor! :) dijo que todos están destinados a ser símbolos de función. Se olvidó de decir eso en la tarea aparentemente. Así que tengo razón, ¡tanto (1) como (2) no pueden estar en lo correcto! lo que también me deja con mi pregunta inicial, aunque... :( si $^c$ era un símbolo de relación, trivialmente, habría sido (1) ¡como una subestructura!
@GiannaAlbertini Edité mi respuesta para abordar la nueva versión de la pregunta.
@GiannaAlbertini Tómese un poco de su tiempo para verificar esto: ¿ Qué debo hacer cuando alguien responde mi pregunta? . Si está satisfecho con esta respuesta, es posible que desee aceptarla, y tal vez incluso votarla a favor, ya que ya tiene el puntaje de reputación necesario.
Muchas gracias profesor, pude descifrar el resto de la prueba gracias a sus sugerencias :D @amrsa hizo exactamente eso ;)

Encontrar un universo adecuado para una estructura dada

gianna albertini

amrsa

gianna albertini

amrsa

gianna albertini

amrsa

Alex Kruckmann

Alex Kruckmann

gianna albertini

gianna albertini

Alex Kruckmann

gianna albertini

amrsa

Respuestas (1)

Alex Kruckmann

gianna albertini

Alex Kruckmann

gianna albertini

Alex Kruckmann

amrsa

gianna albertini

Aclarar sobre el teorema de Birkhoff (en álgebra universal)

Grupos de simetría correspondientes a términos en un álgebra

¿Cuándo podemos encontrar diferentes axiomatizaciones para teorías con los mismos modelos?

¿Qué teorías se conservan bajo el producto?

Tratando de entender la pregunta en el ejercicio sobre las relaciones

¿Es la teoría de los lenguajes formales regulares finitamente axiomatizable?

Paradoja aparente de tipo principal 1

¿Cómo se especifica la semántica completa de SOL y HOL?

Fuerza relativa e indistinguibilidad proposicional de retículas no distributivas

Un número finito de modelos contables implica decidibilidad