La prueba de toda relación binaria con una función de rango está bien fundada.

Question

He probado la siguiente afirmación (fuente de la imagen), me puede decir si mi prueba es correcta? Gracias:

Reivindicación 4: Deje $R$ ser una relación binaria sobre un conjunto $X$, y supongamos $\langle Y, \prec \rangle$ es un estricto w.o. Si existe una función de $rk : X \to Y$ tal que $$ \forall x, y \in X (x \neq y \land \langle x, y \rangle \in R \to rk(x) \prec rk(y)), \tag{*}$$ then the relation $R$ es fundado.

donde se utiliza la siguiente definición de fundado:

$\newcommand{\pair}[2]{\langle#1,#2\rangle}$

Definición 3: Deje $R$ ser una relación binaria sobre un conjunto $X$. Decimos que $R$ es justificado, si para cada subconjunto no vacío $Y \subseteq X$ existe un $z \in Y$ tal que $\pair yz \notin R$ todos los $y \in Y\setminus \{z\}$. Una relación $R$ es estrictamente justificado si está fundado y irreflexiva.

---

Prueba:

Suponga $R$ no está bien fundada. Entonces existe un infinito $R$-descendente secuencia $(x_n)$ tal que $(x_{n+1}, x_n) \in R$, $n \in \mathbb N$, de modo que $S = \{x_n \mid n \in \mathbb N\}$ no tiene un $R$-mínimo elemento. A continuación, $f(S)$ es un subconjunto de a $Y$ que contiene un infinito $R$-descendente secuencia $(f(x_{n+1}), f(x_n)) \in \prec$ lo cual es una contradicción a $(Y,\prec)$ estar bien fundada.

Answer 1

En primer lugar, una anotación de error: $(x_{n+1},x_n)\in R$ no describe un describen una secuencia. Lo que significa es que hay una secuencia $\langle x_n:n\in\Bbb N\rangle$ $X$ tal que $\langle x_{n+1},x_n\rangle\in R$ por cada $n\in\Bbb N$. No hay necesidad para que el susto comillas; sólo tiene que llamar a un $R$-descendente de la secuencia o de una secuencia descendente con respecto a $R$. Del mismo modo, no hay ninguna razón para asustar a las comillas en mínima: acaba de decir $R$-mínimo.

Por lo tanto la sustancia del argumento es correcto, pero es innecesariamente complicado. Deje $A$ ser cualquier no-vacío es subconjunto de a $X$. A continuación, $rk[A]$ es un no-vacío es subconjunto de a $Y$, por lo que tiene un $\prec$-menos el elemento $y$. Deje $a\in A$ ser tal que $rk(a)=y$. Si $\langle x,a\rangle\in R$ algunos $x\in X$,$rk(x)<y$, y por lo tanto $x\notin A$. Por lo tanto, $a$ $R$- el mínimo elemento de $A$, e $R$ está bien fundada.

Answer 2

Yo diría que la afirmación no es cierta en absoluto. Para cualquier% no$X$, la relación de igualdad$$ R=\{(x,x)\mid x\in X\}$ $ satisface la condición$(*)$ para cualquier función de rango$\mathit rk$. Pero no está bien fundamentado debido a la cadena infinitamente descendente$$ \cdots \mathrel R x \mathrel R \cdots \mathrel R x \mathrel R x \mathrel R x$ $

Answer 3

La prueba está bien. Por cierto, es normal tomar$Y$ para ser un ordinal.