[Math] Inductive Subset and the Induction Principle

elementary-set-theory

I'm reading Dudley's Real Probability and Analysis when I came across the following definitions of Inductive Subset and Induction Principle.

enter image description here

I would like to prove the induction princple just like Dudley has done, but I'm a bit confused about the definition of inductive subset.

I translated the highlighted passage as it follows:

$I$ = set of all inductive subsets

$I = \left \{ Y \subset X | \forall (x \in X \rightarrow y \in Y) \forall (y \in X \rightarrow y < x)(x \in Y) \right \} $

Is it correct?

Best Answer

Let $(X, <)$ a p.o. set and let $Y \subset X$.

We say $Y$ inductive iff

$\forall x \in X \ [\forall y \in X \ (y < x \to y \in Y) \to x \in Y].$

The definition is applied to the proof of the Induction Principle considering a well-ordered set $X$ ordered by $<$.

For the non-trivial case, we have $Y \subset X$ and assume that $X \setminus Y$ is not empty.

Let $y$ the least element in $X$ such that $y \notin Y$ (it exists by well-ordering of $X$ : "every non-empty subset of $X$ has a least element").

Please, note that in the proof the author exchanged the role of $x$ and $y$ with respect to the previous definition of inductive set.

Now $y$ is the least element in $X$ which is not in $Y$; thus, all elements $x$ of $X$ that are "less than" $y$ must belong to $Y$.

$Y$ is inductive, and thus from :

$\forall y \in X \ [\forall x \in X \ (x < y \to x \in Y) \to y \in Y]$

we conclude with : $y \in Y$, contradicting the fact that $y \in X$ and $y \notin Y$.

Thus, we have to refute our assumption that $X \setminus Y$ is not empty and we conclude with :

$Y=X$.

Note on the above "symbolization".

The English text says :

for every $x \in X$ such that $y \in Y$ for all $y \in X$ such that $y < x$, we have $x \in Y$.

The text is a little bit convoluted, but it is clear that "we have $x \in Y$" is the "concusion" of the definition, and thus must be the consequent of the conditional.

Thus, we can try with :

$\forall x \in X \ [\text {such that} \ (y \in Y \ \text {for all} \ y \in X \ \text {such that} \ y < x) \to x \in Y].$

Now we have to "unwind" :

$(y \in Y \ \text {for all} \ y \in X \ \text {such that} \ y < x)$

and we can rephrase it as : $(y \in Y \ \text {if, for all} \ y \in X \ \text {such that} \ y < x)$, i.e. with :

$\forall y \in X (y < x \to y \in Y)$.

Related Question