Tratando de entender la pregunta en el ejercicio sobre las relaciones

Question

Tratando de entender la pregunta en el ejercicio sobre las relaciones

mmm3

Estoy trabajando por mi cuenta a través de How to Prove It de Daniel J. Velleman y estoy tratando de entender lo que se pide para el ejercicio 9 en la sección 4.4:

Suponer $R$ es una orden parcial en $A$ y $S$ es una orden parcial en $B$ . Definir una relación $L$ en $A \times B$ como sigue: $L = \{ ((a,b),(a',b')) \in (A \times B) \times (A \times B) ~ | ~ aRa', ~ \text{and if} ~ a = a' \text{then} ~ bSb'\}$ .

Específicamente, estoy tratando de entender la definición de la relación $L$ .

Debe $a = a'$ para que cualquier par de pares ordenados pertenezcan $L$ ?

Como ejemplo específico, dejemos $A = \{1, 2\}$ y $B = \{3, 4\}$ . Por lo tanto, $A \times B = \{(1,3), (1,4), (2,3), (2,4)\}$ . Dejar $R = \{(1,1), (2,2), (1,2) \}$ y $B = \{ (3,3), (4,4), (3,4) \}$ .

Ahora en este ejemplo específico es $L = \{ ((1,3), (1,3)), ~((1,4),(1,4)), ~ ((1,3),(1,4)), ~ ((2,3),(2,3)), ~ ((2,4),(2,4)), ~ ((2,3),(2,4))\}$ ?

Actualización: Gracias a todos por las útiles respuestas a mi pregunta.

Un poco más de contexto a mi pregunta:

Una de las razones por las que tengo dificultades con la definición de $L$ es cuando se trata de usarlo cuando se muestra que $L$ es una orden parcial en $A \times B$ .

La definición de $L$ tiene una forma lógica de $P \land (O \implies Q)$ , dónde $P$ es $aRa'$ , $O$ es $a = a$ , y $Q$ es $bSb'$ .

Ahora para mostrar, por ejemplo, que $L$ es una relación reflexiva sobre $A \times B$ debemos demostrar que $\forall (a, b) \in A \times B ((a,b),(a,b)) \in L$ . Para hacer esto, deje $(a,b)$ ser arbitrario y suponer $(a,b) \in A \times B$ . De este modo, $a \in A$ y $aRa$ . Esto muestra el $P$ parte de $P \land (O \implies Q)$ desde arriba.

Ahora debemos demostrar que $a = a \implies bSb$ . El método que se nos muestra para hacer esto en el libro es asumir el antecedente y probar el consecuente. Así que asume $a = a$ , pero esto no nos dice nada sobre $bSb$ . Así que no estoy seguro de qué hacer desde aquí.

¿Quizás debería abrir una nueva pregunta para las cosas en la parte de actualización de esta pregunta?

Después de revisar los comentarios a continuación y pensar más en ello, aquí hay otro intento de mostrar que $L$ es una relación reflexiva sobre $A \times B$ :

Dejar $(a,b)$ ser arbitrario y suponer $(a,b) \in A \times B$ . De este modo $a \in A$ y porqué $R$ es una orden parcial en $A$ , entonces $aRa$ . Ahora asume $a = a$ . Sabemos que desde $(a,b) \in A \times B$ entonces $b \in B$ . Desde $S$ es una orden parcial en $B$ , entonces $bSb$ . Por lo tanto, si $a = a$ entonces $bSb$ . Desde $aRa$ y si $a = a$ entonces $bSb$ , entonces $((a,b),(a,b)) \in L$ . Desde $(a,b)$ fue arbitrario podemos concluir $L$ es una relación reflexiva sobre $A \times B$ . $\square$

Dan Velleman

Tal vez ayudaría tener algo de motivación. Piensa en cómo ordenas alfabéticamente las palabras. Primero comparas las primeras letras. Si las primeras letras son iguales, entonces pasas a las segundas letras, y así sucesivamente. ¿Ves que la definición de

L

$L$ se basa en una idea similar?

mmm3

@DanVelleman gracias por el comentario. Creo que veo la conexión de la que estás hablando. Una de las razones por las que tengo problemas con la definición de

L

$L$ está tratando de usarlo para mostrar que

L

$L$ es una orden parcial en

A \times B

$A \times B$ . He agregado más información a la pregunta para explicar esto con más detalle.

eric torres

"La definición de

L

$L$ tiene una forma lógica de

P \land (R ⟹ Q)

$P\wedge (R \implies Q)$ , dónde

P

$P$ es

a R a'

$aRa′$ ,

R

$R$ es

a = a

$a=a$ , y

Q

$Q$ es

b S b'

$bSb′$ ." Esto es falso. Primero, has reutilizado "

R

$R$ " con diferente semántica, así que vamos con "La definición de

L

$L$ tiene una forma lógica de

P \land (O ⟹ Q)

$P\wedge (O \implies Q)$ , dónde

P

$P$ es

a R a'

$aRa′$ ,

O

$O$ es

a = a

$a=a$ , y

Q

$Q$ es

b S b'

$bSb′$ ." No prueba la definición de un conjunto. Se le da la definición del conjunto: este predicado es verdadero para cada miembro del conjunto.

Dan Velleman

En la Actualización, dices "ahora debemos demostrar que

a = a \Rightarrow b S b^{'}

$a=a \Rightarrow bSb'$ ." Eso no está bien; lo que necesitas mostrar es que

a = a \Rightarrow b S b

$a=a \Rightarrow bSb$ .

mmm3

@EricTowers Sí, usé

R

$R$ de dos maneras diferentes. Gracias por señalar eso. Ahora lo he cambiado a

P \land (O ⟹ Q)

$P \land (O \implies Q)$ . Para mostrar que un par de pares ordenados está en la relación

L

$L$ debemos demostrar que cumplen con la definición de

L

$L$ ¿bien? Eso es lo que estaba tratando de hacer en la sección Actualizar.

mmm3

@DanVelleman Sí, tienes razón. debo mostrar que

a = a ⟹ b S b

$a = a \implies bSb$ al mostrar que

L

$L$ es una relación reflexiva sobre

A \times B

$A \times B$ . Lo he corregido en la sección de actualización. También he añadido en otro intento de prueba que

L

$L$ es una relación reflexiva sobre

A \times B

$A \times B$ . ¿Se ve correcto?

Dan Velleman

@mmm3: Sí, la nueva prueba de que

L

$L$ es reflexivo se ve bien.

Respuestas (3)

Tratando de entender la pregunta en el ejercicio sobre las relaciones

Tal vez ayudaría tener algo de motivación. Piensa en cómo ordenas alfabéticamente las palabras. Primero comparas las primeras letras. Si las primeras letras son iguales, entonces pasas a las segundas letras, y así sucesivamente. ¿Ves que la definición de $L$ se basa en una idea similar?
@DanVelleman gracias por el comentario. Creo que veo la conexión de la que estás hablando. Una de las razones por las que tengo problemas con la definición de $L$ está tratando de usarlo para mostrar que $L$ es una orden parcial en $A \times B$ . He agregado más información a la pregunta para explicar esto con más detalle.
"La definición de $L$ tiene una forma lógica de $P\wedge (R \implies Q)$ , dónde $P$ es $aRa′$ , $R$ es $a=a$ , y $Q$ es $bSb′$ ." Esto es falso. Primero, has reutilizado " $R$ " con diferente semántica, así que vamos con "La definición de $L$ tiene una forma lógica de $P\wedge (O \implies Q)$ , dónde $P$ es $aRa′$ , $O$ es $a=a$ , y $Q$ es $bSb′$ ." No prueba la definición de un conjunto. Se le da la definición del conjunto: este predicado es verdadero para cada miembro del conjunto.
En la Actualización, dices "ahora debemos demostrar que $a=a \Rightarrow bSb'$ ." Eso no está bien; lo que necesitas mostrar es que $a=a \Rightarrow bSb$ .
@EricTowers Sí, usé $R$ de dos maneras diferentes. Gracias por señalar eso. Ahora lo he cambiado a $P \land (O \implies Q)$ . Para mostrar que un par de pares ordenados está en la relación $L$ debemos demostrar que cumplen con la definición de $L$ ¿bien? Eso es lo que estaba tratando de hacer en la sección Actualizar.
@DanVelleman Sí, tienes razón. debo mostrar que $a = a \implies bSb$ al mostrar que $L$ es una relación reflexiva sobre $A \times B$ . Lo he corregido en la sección de actualización. También he añadido en otro intento de prueba que $L$ es una relación reflexiva sobre $A \times B$ . ¿Se ve correcto?
@mmm3: Sí, la nueva prueba de que $L$ es reflexivo se ve bien.

travis bemrose · Answer 1

Dejar $x := ((a,b)\times(a',b'))$ . Si $x \in L$ , depende de si $aRa'$ y si $bSb'$ . Hay 4 posibilidades para los dos últimos. Hagamos una mesa.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline aRa' & & \\ \lnot aRa' \end{array}$

La definición de $L$ es una condición y que comienza con $aRa'$ , por lo que podemos excluir el $\lnot aRa'$ casos.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline aRa' & & \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

Además, la definición de $L$ establece que en el caso de que $aRa'$ , también tenemos que considerar si $a=a'$ , entonces tenemos que dividir el $aRa'$ caso.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline a=a',aRa' & & \\ a \ne a',aRa' & & \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

La segunda parte del condicional dice si $a=a'$ entonces $bSb'$ , para que podamos completar la fila superior.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline a=a',aRa' & x\in L & x \notin L \\ a \ne a',aRa' & & \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

Finalmente, el condicional si es verdadero cuando la hipótesis es falsa, es decir cuando $a \ne a'$ , entonces $aRa'$ hace que la primera mitad del condicional sea verdadera y $a \ne a'$ hace verdadera la segunda mitad, y terminamos la tabla.

$\begin{array}{r|cc} & bSb' & \lnot bSb' \\ \hline a=a',aRa' & x\in L & x \notin L \\ a \ne a',aRa' & x\in L & x\in L \\ \lnot aRa' & x \notin L & x \notin L \end{array}$

Guenterino · Answer 2

Guenterino

Lo interpretaría de la siguiente manera: La relación es la siguiente ((a,b),(a',b')) donde aRa', excepto si a= a'. Si a= a', entonces solo existen las siguientes relaciones ((a,b), (a',b')) donde aRa' y bSb'.

Guenterino

Cambié un poco la respuesta: lo siento por usar una frase extraña. No me tomé el tiempo suficiente para entender su notación. Ahora debería ser consistente.

mmm3

Gracias, eso tiene más sentido para mí ahora.

mmm3

Una pequeña corrección: creo que la última parte de su respuesta debería ser

b S b^{'}

$bSb'$ , no

b R b^{'}

$bRb'$ .

Guenterino

@mmm3 ¡Tienes razón! Lo corregí.

Álvaro p. · Answer 3

¿Debe 𝑎=𝑎′ para que cualquier par de pares ordenados pertenezca a 𝐿?

No. Puedes tener pares $(a,b)\times (a',b')$ dónde $a\neq a'$ mientras $aRa'$ .

Usando tu ejemplo, ya que $(1,2)\in R$ , entonces (1,3)x(2,4) $\in L$ .

Hola Álvaro, gracias por la respuesta. Entonces, para construir sobre su respuesta, ya que $(1,2) \in R$ entonces $((1,3),(2,3)) \in L$ y $((1,4),(2,4)) \in L$ ?
Exactamente. En términos generales, serían todos los pares de la forma $(1,b)\times(2,b')$ .

Tratando de entender la pregunta en el ejercicio sobre las relaciones

mmm3

Dan Velleman

mmm3

eric torres

Dan Velleman

mmm3

mmm3

Dan Velleman

Respuestas (3)

travis bemrose

Guenterino

Guenterino

mmm3

mmm3

Guenterino

Álvaro p.

mmm3

Álvaro p.

Encontrar un universo adecuado para una estructura dada

Inversos de transitividad

establecer relaciones (relación que es simétrica y transitiva pero no reflexiva)

Análisis I (Terence Tao)—Variables libres y ligadas

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

¿Es correcta esta notación de intervalo para la solución de un problema de desigualdad?

¿Qué sucede si la cabeza de una Máquina de Turing de Tiempo Infinito está en la celda más a la izquierda y el programa dicta que se mueva la cabeza hacia la izquierda?

Paradoja aparente de tipo principal 1

Para la relación R=∅R=∅R = \emptyset en {1,2,3}{1,2,3}\{1, 2, 3\}, ¿es reflexiva, simétrica, transitiva?

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