# Proof by mathematical induction (nested sets)

Mathematical induction works as follows:

1. Proposition P is true for n=1 (or $$n=0$$);

2. If proposition P is true for a given $$n \in \mathbb{N}$$, then P is true for $$n+1$$.

Then P is true for every $$n \in \mathbb{N}$$.

Now suppose that we want to show by mathematical induction that exists a sequence of non-empty sets:

$$C_0,C_1,\dots,C_n,\dots$$

such that:

$$C_0 \supset C_1 \supset \dots \supset C_n \supset \dots$$

This is our proposition. That means that we want to show that:

1. $$\exists \,C_0,C_1 \mid C_0 \supset C_1$$;

2. If $$\exists \,C_0,C_1,\dots,C_n \mid C_0 \supset C_1 \supset \dots \supset C_n$$ then $$\exists \,C_0,C_1,\dots,C_n,C_{n+1} \mid C_0 \supset C_1 \supset \dots \supset C_n \supset C_{n+1}$$.

Is this the correct way to proceed in this case? Thank you!

• This proposition is meaningless the way it's stated, isn't it? Choosing $C_n=\varnothing$ for all $n$ would do the job. But yes, if you really want to do a proof by induction, this is the way to proceed.
– Zuy
Aug 10, 2020 at 11:31
• Thank you! Yes, actually I made it a little too vague. In addition, suppose that $C_n \neq \emptyset$ for all $n \in \mathbb{N}$ and that each set is properly contained in the previous one. Again, every $C_n$ is a subset of a topological space $X$. Aug 10, 2020 at 11:36
• Alright. In that case, I would set $C_n=\mathbb{N}-\{0,\dots, n\}$ and then prove by induction that this choice works.
– Zuy
Aug 10, 2020 at 11:42
• Actually, I was interested only in the method, than in the general result. I'm studyng the Goursat's theorem (in complex analysis) : you have to split a triangle into four new triangles. Then you take one of those triangles and, again, split this one into four new triangles, and so on "by induction"...I was only wondering about the rigorous use of induction here. Aug 10, 2020 at 11:52
• Then notation $C \subseteq D$ is misleading if you mean that $C$ is properly contained in $D$. Aug 10, 2020 at 11:53

This would not quite get what you want. By applying induction to 1 and 2 you get for every $$n$$ a chain $$C_0 \supsetneq \ldots \supsetneq C_n$$. You just do not get an infinite chain.

Compare it to the following. Let $$P(n)$$ be the statement there is a sequence of natural numbers $$a_1, \ldots, a_n \in \mathbb{N}$$ such that $$a_1 > a_2 > \ldots > a_n$$. It is easy to show that $$P(0)$$ is true and that $$P(n)$$ implies $$P(n+1)$$. So by induction $$P(n)$$ is indeed true for all $$n$$. However, we can never get an infinite strictly decreasing sequence $$a_1 > a_2 > \ldots > a_n > \ldots$$ of natural numbers.

So when combining induction with existence statements, you have to be careful. Because you only get existence for each finite (however big) $$n$$. You do not get existence of the infinite thing. As mentioned in the comments, you could work around this. For example in your decreasing sets case we can define $$C_n = \mathbb{N} - \{0, \ldots, n\}$$. So we already have an infinite collection of sets. Then by induction we can prove that this is indeed a decreasing chain. Now the induction is no longer applied to prove the existence of something, just to prove a desired property about something that already exists.

• That's exactly the point! My original problem is: I have a triangle. I split this triangle into four new triangles (by connecting the three midpoints on the three sides). Then I choose one of these four triangles (I choose the one that satisfies a property that I don't mention here) and I split it exactly as before, and so on...then by induction I obtain an infinite sequence of nested triangles, and each one satisfies a given property. I was wondering how induction works in this case. Maybe I should state that the sequence of nested triangles exists, and then using mathematical induction. Aug 10, 2020 at 12:11

(Posted after previous answer was accepted)

Let $$\{C_n: n\in N\}$$ be a family of sets.

Define proposition $$P$$ such that

$$\forall n \in N: [P(n) \iff \forall m \in N: [m.

Then proceed as you would to prove by induction that, $$\forall n\in N: P(n)$$.

Note that $$P(0)$$ will vacuously true in this case however you may define the $$C_n$$

• But in this case, we have defined the sequence of sets before applying induction. Aug 11, 2020 at 15:47
• This will work for any sequence of sets. Aug 11, 2020 at 15:52
• Yes, that's perfectly clear. But I was wondering if I could use induction not only to show that the sets are nested, but even to show their existence (namely, defining them through induction). I know I'm not making myself very clear, sorry for that. Aug 11, 2020 at 15:57
• To prove the existence of a set, you must use the axioms of set theory, e.g. axioms for the existence of subsets, power sets, etc. Aug 11, 2020 at 16:01
• I'm not making myself clear. This question about induction is due to a doubt I have in the proof of a specific theorem (Goursat theorem). I should have asked it in a more direct way. If you are interested, I reformulated my question at this link math.stackexchange.com/questions/3786252/… Aug 11, 2020 at 16:07