Show that if $\mathcal{A}$ is a collection of inductive sets, then the intersection of the elements of $\mathcal{A}$ is an inductive set

My Attempted Proof:

Let $\mathcal{A}$ be a collection of inductive sets. Then$$\mathcal{A}= \left\{A_i\right\}_{i\in I} $$

where $A_i$ is an inductive set and $I$ is an arbitrary indexing set.

Each $A_i$ contains $1$, and $\forall x \in A_i$ we have $x+1 \in A_i$.

$$\text{Put } \ \ \gamma = \bigcap_{A_i\in\mathcal{A}}A_i$$

Since $1 \in A_i$ for all $A_i\in \mathcal{A} \implies 1 \in \gamma$.

Now put $x = 1$. Since $1 \in \gamma \implies x+1 = 2 \in A_i$ for all $A_i \in \mathcal{A} \implies x+1 \in \gamma$

Now put $x = 2$. Since $2 \in \gamma \implies x+1 = 3 \in A_i$ for all $A_i \in \mathcal{A} \implies x+1 \in \gamma$

Continuing this process recursively we can see that $1 \in \gamma$, $x \in \gamma$ and $x+1 \in \gamma$ for all $x \in \gamma$. Thus $\gamma$ is an inductive set. $\square$

Firstly is my proof correct? If so how rigorous is it? If it is correct and fairly rigorous, then any suggestions on how to improve it? I feel it is a bit hand-wavy at the moment

  • 1
    $\begingroup$ What is your definition of inductive set? I don't think that you are following it . $\endgroup$
    – Crostul
    Dec 17 '16 at 23:05
  • $\begingroup$ Definition of Inductive Set: A subset $A$ of the reals is said to be inductive if it contains the number $1$, and if for every $x \in A$, the number $x+1$ is also in $A$, taken from Topology : A First Course by Munkres $\endgroup$ Dec 17 '16 at 23:42
  • $\begingroup$ This is perfect. Now, why didn't you check that $\cap \mathcal{A}$ is inductive using the definition? You checked that $1 \in \cap \mathcal{A}$. Then you should have checked that for all $x \in \cap \mathcal{A}$, $x+1 \in \cap \mathcal{A}$: this is not the same as saying "continuing this process recursively". $\endgroup$
    – Crostul
    Dec 17 '16 at 23:48
  • $\begingroup$ @Crostul, I believe that is what I was trying to do when I said continuing this process recursively. How would you have checked that for all $x \in \cap\mathcal{A}$, $x+1 \in \cap\mathcal{A}$? I'm just curious as that was exactly what I was trying to prove when I said continuing this process recursively $\endgroup$ Dec 17 '16 at 23:56
  • $\begingroup$ Well, you pick any $x \in \cap \mathcal{A}$. For all $i$ you have $x \in A_i$. But $A_i$ is inductive, so that $x+1 \in A_i$. So, we have that $x+1 \in A_i$ for all $i$, i.e. $x+1 \in \cap \mathcal{A}$. $\endgroup$
    – Crostul
    Dec 17 '16 at 23:58

OP asked for a non-hand-wavy improvement. Here is how I would prove the same statement without mention of recursion (which seems to be the core of your question):


  • A set $A$ is inductive if $0\in A$ and for each $n\in A$, $n+1\in A$.

Proposition. For each nonempty collection $ \mathcal{C} $ of inductive sets, $ \bigcap\mathcal{C} $ is inductive.

Proof. Let $ \mathcal{C} $ be an arbitrary nonempty collection of inductive sets. Therefore $ 0\in\bigcap\mathcal{C} $. To prove $ \bigcap\mathcal{C} $ is inductive, let $ n\in\bigcap\mathcal{C} $ be arbitrary. Therefore for each $ A\in\mathcal{C} $, $ n\in A $. Therefore for each $ A\in\mathcal{C} $, $ n+1\in A $. Therefore $ n+1\in\bigcap\mathcal{C} $. Therefore $ \bigcap\mathcal{C} $ is inductive.

  • 1
    $\begingroup$ Note that often "inductive set" is given in the context of the real numbers. The definition is not very different, but it pertains numbers rather than sets. So this answer, while being 100% correct, might be a bit off mark to people unfamiliar with the set theoretic definition of inductive sets. $\endgroup$
    – Asaf Karagila
    Dec 18 '16 at 12:51
  • $\begingroup$ Edited (thanks) $\endgroup$ Dec 19 '16 at 3:23

The idea is generally correct. Two points, and one caveat:

  1. "Continuing this process recursively" is not particularly formal. It's fine when you're not fully expected to formalize something (e.g., in a paper when the claim is easy enough, or when a full formal statement will be unreadable). But since you've asked for feedback, this should be pointed out.

    The way to formalize "continuing this process recursively" is by induction. Which is a good segue into the next point.

  2. Induction is not what you need here. You want to show that $1\in\gamma$, and that if $x\in\gamma$, then $x+1\in\gamma$. This is not a proof by induction, but rather proving directly from the definition of inductive sets and intersections.

One caveat, however, is that the intersection should be over a non-empty collection. If the context is bounded in $\Bbb R$, however, then the intersection over an empty collection is $\Bbb R$ in which case you're covered and everything is fine. It's just something to note, though.


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.