[alexpglez]

Buenos días,
Sea [texx] A [/texx] un conjunto y [texx] S\subset A\times A [/texx] una relación binaria. Existe una mínima relación reflexiva ([texx] xRx \; \forall x\in A[/texx]) y transitiva ([texx] xRy \wedge yRz \; \Rightarrow \; xRz, \; \forall xyz\in A[/texx]) que contiene a [texx] S [/texx]:
$$ R=\bigcap \{ F\subset A\times A \; | \; S\subset F, \; F \text{ es reflexiva y transitiva }\} $$

¿Hay algún criterio sencillo (ya sea equivalente o suficiente) para que [texx] R [/texx] sea antisimétrica (y por tanto una relación de orden parcial)?
Por ejemplo, si [texx] S [/texx] es una relación bien fundada, ¿[texx] R [/texx] es un buen orden? Además, si [texx] R [/texx] es un buen orden, ¿[texx] S [/texx] (menos la diagonal) está bien fundada? (Edito: esto claramente es falso...)
Por ejemplo, si [texx] S [/texx] es una relación bien fundada, ¿[texx] R [/texx] es antisimétrica?

En los números naturales [texx] \mathbb N [/texx] consideramos la relación [texx] S=\{(n,n+1) \; | \; n\in \mathbb N\} [/texx]. Intuitivamente [texx] R [/texx] es la relación de orden usual, ¿se os ocurre cómo se podría probar ésto a partir de los axiomas de Peano? es decir, que se cumple la propiedad recursiva:
$$ 0Rn \; \forall n\in \mathbb N $$
$$ n+1Rm \; \Leftrightarrow \; nRm \wedge n\neq m, \;\; \forall nm\in \mathbb N $$

Muchas gracias

PD: está claro que [texx] 0 Rn \; \forall n\in \mathbb N [/texx] se puede probar por inducción sobre [texx] n [/texx]. El caso [texx] n=0 [/texx] es trivial, y si [texx] 0Rn [/texx], como [texx] nRn+1 [/texx], entonces [texx] 0Rn+1 [/texx]. La segunda propiedad es más compleja, intenté hacer inducción sobre [texx] m [/texx] infructuosamente.

PD2: Si [texx] A [/texx] es una clase propia y [texx] S \subset A\times A [/texx] es una clase (conjunto o no), ¿también se puede construir [texx] R [/texx]? (Por ejemplo, [texx] (V,\in) [/texx] o sin el axioma de infinitud, los naturales [texx] \omega [/texx] con [texx] S=\{(n,n+1) \; | \; n\in \omega\} [/texx])

Edito: Antes había escrito simétrica cuando estaba pensando en reflexiva, gracias Carlos por corregirme

[Carlos Ivorra]

Pero, si por \( R \) te refieres siempre a la que has definido:

Buenos días,
Sea [texx] A [/texx] un conjunto y [texx] S\subset A\times A [/texx] una relación binaria. Existe una mínima
$$ R=\bigcap \{ F\subset A\times A \; | \; S\subset F, \; F \text{ es simétrica y transitiva }\} $$

Entonces \( R \) es simétrica, y no puedes esperar que una relación que es simétrica sea también antisimétrica, salvo que sea trivial: si \( aRb \), entonces \( bRa \) por la simetría y \( a=b \) por la antisimetría, luego \( R \) se reduciría a pares \( (a, a) \), pero entonces no contendría a \( S \), si ésta contiene pares \( (a, b) \) con \( a\neq b \). Por lo tanto, salvo que \( S \) sólo tenga pares \( (a, a) \), es imposible que \( R \) sea antisimétrica.

Aunque cambies la definición, no puedes obtener una relación de orden a partir de cualquier relación dada \( S \), pues si \( S \) contiene un ciclo, como \( aSb, bSc, cSa \), una relación que extienda a \( S \) no puede ser de orden.

En resumen, antes de probar nada, tienes que dar una definición distinta de \( R \) que pueda dar lugar a una relación de orden supuesto que \( S \) cumpla algunos requisitos.

[alexpglez]

Pero, si por \( R \) te refieres siempre a la que has definido:

Buenos días,
Sea [texx] A [/texx] un conjunto y [texx] S\subset A\times A [/texx] una relación binaria. Existe una mínima
$$ R=\bigcap \{ F\subset A\times A \; | \; S\subset F, \; F \text{ es simétrica y transitiva }\} $$

Entonces \( R \) es simétrica, y no puedes esperar que una relación que es simétrica sea también antisimétrica

Perdón, lapsus, quería escribir reflexiva [texx] xRx, \forall x\in A [/texx]. Lo edito, gracias, evidentemente no tiene sentido que sea simétrica y de orden.

Aunque cambies la definición, no puedes obtener una relación de orden a partir de cualquier relación dada \( S \), pues si \( S \) contiene un ciclo, como \( aSb, bSc, cSa \), una relación que extienda a \( S \) no puede ser de orden.

Evidentemente, si extendemos [texx] S [/texx] a una relación [texx] R [/texx] reflexiva y transitiva, entonces no es de orden pues [texx] aRc [/texx] y [texx] cRa [/texx] pero [texx] a\neq c [/texx]. Esto me recordaba a lo escrito en tu libro, que si [texx] S [/texx] está bien fundada entonces no puede haber un círculo cerrado como el que comentas, por ejemplo, en este caso no existe un [texx] S [/texx]-minimal.

[geómetracat]

Una condición necesaria y suficiente es que \[ S \] no tenga ciclos, es decir, que no haya una sucesión \[ x_0 S x_1 S x_2 \dots S x_n \] con \[ x_0=x_n \] y \[ n > 1 \]. En particular, si \[ S \] es bien fundada la relación \[ R \] que defines es de orden. No creo que haya una caracterización más simple que esta.

De todas formas un comentario (que igual no te sirve para nada): en el caso general, \[ R \] es una relación reflexiva y transitiva que es lo que se conoce como un preorden. Los preórdenes y los órdenes están bastante cerca. Si \[ P \] es un preorden cualquiera, y defines la relación \[ x \sim y \] si y solo si \[ x R y \] e \[ y R x \], entonces \[ P/\sim \] con la relación inducida es un orden.

[alexpglez]

Una condición necesaria y suficiente es que \[ S \] no tenga ciclos, es decir, que no haya una sucesión \[ x_0 S x_1 S x_2 \dots S x_n \] con \[ x_0=x_n \] y \[ n > 1 \]. En particular, si \[ S \] es bien fundada la relación \[ R \] que defines es de orden. No creo que haya una caracterización más simple que esta.

Entiendo. [texx] xRy [/texx] si y sólo si [texx] x=y [/texx] o hay una sucesión finita [texx] x=x_1Sx_2Sx_3\dots x_{n-1}Sx_n=y [/texx] (es así pues esta es la mínima relación reflexiva y transitiva que extiende a [texx] S [/texx].
Como observación [texx] xRy [/texx] y [texx] yRx [/texx] para [texx] x\neq y [/texx] si y sólo si hay un ciclo cerrado al que pertenecen [texx] x [/texx] e [texx] y [/texx].
Así, como corolario [texx] R [/texx] es antisimétrica si y sólo si no hay ningún ciclo cerrado.

Por otro lado, la caracterización anterior de [texx] R [/texx] permite definirlo incluso para [texx] A [/texx] siendo una clase propia 

Muchas Gracias