I was recently encouraged to develop a deeper understanding of the Principle of Infinite Descent so that I could become more comfortable with its usage in proofs. I have a few questions that I wanted to run by the community in order to confirm that I have sufficiently absorbed the concept.

The below excerpt, taken from http://elib.mi.sanu.ac.rs/files/journals/tm/31/tm1622.pdf, provides this statement:


Given what we know about the Well-Ordering Principle for Natural Numbers, this statement is logically sound.

Equipped with the above logical statement, the aforementioned math website goes on to prove the following proposition:

There is no infinite strictly decreasing sequence of natural numbers

This proposition is proven using the following argument:

Proposition Proof

Firstly, I wanted to confirm that the reason "we know" $1 \notin A$ (where $1$ here is functioning as the $0$ that I am more familiar with) is that by Peano's Axioms and the Well-Ordering Principle, there is no element smaller than $1$.

Therefore, if $1$ WAS a member of set $A$, there could be no element less than $1$ to continue the infinite sequence...which would necessarily make $A$ finite (contradiction). So, to avoid contradiction, the author moves on with the claim $1 \notin A$.

Secondly, why is the initial assumption that "$\exists$ an infinite set $A$" an acceptable assumption? Is it purely because we know that there are an infinite number of natural numbers and therefore, by defining members of $A$ as "$a_n \in \mathbb N$ and $n \in \mathbb N$" we recognize that the natural number indexing of the elements permits an infinite list?

Finally, I recognize the contradiction. Specifically, we arrive at the simultaneous conclusion that the statement $p(n)$ is true for $\forall n \in \mathbb N$ (i.e. no elements of $n$ are in $A$) while claiming the existence of an infinite set that contains members of $\mathbb N$ (and therefore provide infinitely many instances of $n$'s where $p(n)$ is false). My question is thus, "What is the negation that is performed on the initial assumption"? Is it simply that The set $A$ does not exist? Consequently, given the properties attached to $A$, the conclusion is:

No infinitely sized set can be constructed from strictly decreasing elements selected from the $\mathbb N$.

Is this all correct? Cheers~


Regarding your first question, yes that is precisely the reason we know $1 ∉ A$.

Regarding your second question, the existence of an infinite set is typically an axiom in whatever system you are working in. Since I see that the $∈$ relation is being used in the text that you cite, I am assuming that the system is something at least adjacent to ZFC, for which you can find a list of its axioms (including the axiom of infinity). What you state is more or less correct. $ℕ$ (but actually $ω$) is constructed with the axiom of infinity as the intersection of all inductive sets, and from there we can define functions with the whole of (or only a part of) $ℕ$ (but really $ω$) as the domain. So when we write $\{a_{1},a_{2},\dots \}$ we are in some sense saying that there is a function with $\{1,2,\dots \}$ as the domain and $\{a_{1},a_{2},\dots \}$ as the range.

Your last comment is correct in that the negation of the initial assumption is that the set $A$ does not exist. Your observation of the consequence is also correct in the system I assume we are working in.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.