Q:

Soft question: How to understand cardinalities, induction, subsequences, WOP

I am okay at basic proof techniques, set theory, functions, ZFC, logic. I'm now studying cardinalities of infinite sets, the relationship between well-ordering principle and complete/regular induction, subsequences, sequences, la grange's theorem, graph theory, injective surjective, countability, graph theory, konigsberg, euler's theorem for edges, faces and am lost. What's the best way to understand these topics? I think they're harder than basic proof techniques, basic set theory, functions, ZFC, logic. Whenever I do an induction, I always get stuck thinking about the base case and when I try to think generally, I can't think of all the generalities with of the infinite example. I don't see how to construct injections and surjections from the natural numbers using cantor's snake. I'm not sure how subsequences work. I either think too much or too little. When we're studying cardinalities, subsequences, induction, I have no idea how the answer is the answer and I feel as if the answers are being pulled out of the arse. 

A:

Re: Induction: The definition of $On,$ the class of ordinals, in ZF (actually inZF without Foundation [Regularity]), implies that if $S$ is a set, or definable class, of ordinals, then $S$ is well-ordered by $\in.$ So if $T$ is a nonempty subset of $S$ or a nonempty definable sub-class of $S,$ then $T$ has a $\in$-least member. 
So to prove that $\forall x\in S\;(p(x)),$ we may be able to show that $$(*)\quad\forall x\in S\;(\neg p(x)\implies \exists y\in S\;[y<x\land \neg p(y)]\;).$$ If then $\phi\ne T= \{x\in S:\neg p(x)\}$ then $T\ne \phi$ and $T$ has no $\in$-least member, a paradox. Note that $(*)$ is equivalent to $$(**)\quad \forall x\in S\;(\;[\forall x'\in S (x'<x\implies p(x'))]\implies [p(x)]\;).$$ The base-case in this method,when $\phi \ne S,$ is $p(\min S)$ . In practice, $(*)$ or $(**)$ is often done separately for the cases when $x$ is a successor or a limit of $S.$
Pierre de Fermat used this method in the early 1600's with $S=\mathbb N.$ He called it "infinite descent".

