1

Proposition: Let X be a totally ordered non-empty set such that whenever a subset A⊆X satisfies ∀x [(∀y<x ⟹ y∈A)⟹x∈A]; x,y∈X then A=X. Then X is well-ordered.

This is the proposition that I'm trying to prove, my reasoning is the following:

Let B⊆X, B being a not empty set. Suppose B hasn't a minimum and let A be its complement. We want to show A = X.

Case 1: If X has a minimum, then this minimum, call it x0, cannot be in B, for then B would have a minimum. Now let n∈X, assume ∀m∈X (m<n ⟹ m∈A). It follows x∉B, because if it belonged to B then it would be its minimum since all previous elements are in A. Thus n∈A and by hypothesis, we have A = X, which implies B is the empty set. Therefore there cannot be a subset of X with no minimum.

Case 2: If X hasn't a minimum

This is the case where I'm confused because if my supposed subset B, was equal to X, then its complement A would be the empty set, I don't see how I can use a similar argument as the above mentioned. I've seen a proof of this in https://math.blogoverflow.com/2015/03/10/when-can-we-do-induction/

In which they use the same argument as I, with the base case implicitly proved. But It seems to me that assuming in this case, even A has an element is a very strong assumption since we have A equals the empty set.

Could you help me understand why their proof is valid or how to prove this case. Thanks in advance for your answers.

MMMagician
  • 203
  • Your statement of the proposition seems to be missing a quantifier on $y$. – Eric Wofsey Nov 12 '21 at 01:22
  • Thanks for pointing that out, I've made the change. – MMMagician Nov 12 '21 at 02:20
  • 2
    Be more careful with the quantifiers. In the 1st sentence it should say that if $\forall x,(,[\forall y<x,(y\in A)]\implies x\in A,)$ then $X=A.$.... In Case 1, how can you assume that $\forall n,m ,(m<n\implies m\in A$? I don't think this is what you mean to say because it says that any $m\ne \max (X)$ is in $A.$ – DanielWainfleet Nov 12 '21 at 05:27
  • @DanielWainfleet thanks for your comment, I've made the change now. But still, with that change, the problem remains. Because although I had written it wrong, I thought of it in the way you wrote the quantifiers. – MMMagician Nov 12 '21 at 15:40

1 Answers1

1

Suppose $\emptyset\ne A \subset X$ and $A$ has no least member. Let $B=X\setminus A.$

Now if $x\in X$ and $\{y\in X: y<x\}\subset B$ then $x\in B$; otherwise $x$ would be the least member of $A.$ So strong induction does not work for $B$ because $$\forall x\in X \, (\,[\forall y<x (y\in B)]\implies x\in B)$$ but $B=X\setminus A\ne X$.

DanielWainfleet
  • 57,985
  • So instead of trying to show induction fails for $A$, we can show it fails for the complement. – DanielWainfleet Nov 13 '21 at 17:51
  • But why can we assume that B has an element at least? I know its because of the strong induction hypothesis but for this we should prove a base case rigth? To show there is an starting point for induction. – MMMagician Nov 15 '21 at 03:06
  • In strong induction there is no need for a base case. $\forall x\in X , (,[\forall y<x (y\in B)]\implies x\in B)$ is all you see and all you get. – DanielWainfleet Nov 15 '21 at 15:21
  • 1
    A follow-up. If $X$ $is$ well-ordered and $x_0=\min X$ then the sentence $\forall x\in X,([\forall y<x,(y\in B)]\implies x\in B)$ implies the base case $x_0 \in B$ because $\forall y<x_0,(y\in B)$ is true because there is no $y<x_0$ that $fails$ to be in $B$ because there is no $y<x_0$..... BTW I like to use , and ; and \quad to add space between characters, e.g. \forall x\in X,(...... – DanielWainfleet Nov 19 '21 at 20:16