4

I'm looking for quick clarification on the use of induction, as I'm confused about when it can and can't be applied to claims involving $\infty$.

First, the definition of $\bigcap^ \infty_{n=1} A_n$: the set containing all elements that are members of $A_n \forall n\in N.$ Is this correct?

If the above definition is accurate, can't we use induction to show that an element belongs to the infinite intersection of sets, since we're just making an argument of what's true for all natural numbers? If not, what am I missing? I've read many answers on why induction can't be used for arguments of infinity, but it seems as if the definition of an infinite intersection doesn't use infinity in the way a limit would.

Redstark
  • 71
  • Do you have any links to these answers? There are subtle traps for users of induction, but it doesn't appear to be the case here. – Theo Bendit Sep 23 '19 at 01:29
  • " can't we use induction to show that an element belongs to the infinite intersection of sets, since we're just making an argument of what's true for all natural numbers?" Well, I'd say yes you could IF you could show an element $x$ belongs to every $A_n$. But can you? What is your question? Which $x$ do you think belongs to all of them? How did you show that that $x$ belonged to all of them? If you did that and you didn't change to a different $x$ later then you are fine. But... did you actually do that? – fleablood Sep 23 '19 at 02:15
  • Take $A_n = (0,\frac 1n)$. I can prove non of them are empty. And I ca prove those that aren't empty are subsets of all the lower. And I can prove that no matter how many finite intersections I take I get something. But i can NOT find an $x$ that is in all of them. If $x \le 0$ it isn't in any of them. And if $x > 0$ then for every $n > \frac 1x$ then $x \not \in A_n$. So $\cap_{i=1}^{\infty} A_n$ is empty! – fleablood Sep 23 '19 at 02:18
  • The thing is you seem to be asking a fluke of a question. If $x$ is a specific value, say $\sqrt {\pi}$. If $\sqrt{\pi} \in A_n$ for all $A_n$ that is a statement about the individual but infinite $A_n$. And if $x \in A_n;\forall n$ then $x \in \cap_{k=1}^\infty A_n$. But that is a result of this particular statement. We can't in general make statements about the $A_n$ and conclude things about the infinite intersection. That you can for this question is a fluke. – fleablood Sep 23 '19 at 06:48

2 Answers2

3

Important! Induction lets you say that something is true for every finite natural number, but you can't say anything about any infinite value.

It's a subtle difference.

For instance. If $A_n = (0, \frac 1n)$ then $\cap_{n=1}^{k}A_n = (0, \frac 1n)$ and $\cap_{n=1}^M$ is non-empty for any $M$ but $\cap_{n=1}^{\infty} A_n$ IS empty.

This is because although something is true up to all possible finite $M$ it isn't true for the infinite value $\infty$.

Another example is $\sum_{k=0}^N a_i \frac 1{10^k}$ is rational number (it's a terminating decimal). But $\sum_{k=0}^{\infty} a_i\frac 1{10^k}$ might not be. It could be an infinite non-repeating decimal.

....

So....

If you can find an $x$ so that if $x \in A_k$ than $x\in A_{k+1}$ and that $x \in A_1$ then by induction $x \in $ every possible $A_n$ and $x \in \cap_{n=1}^{\infty} A_n$.

And if you can prove that if $x \in \cap_{n=1}^k A_n$ implies that $x\in \cap_{n=1}^{k+1} A_n$ then (because that means $x \in A_{k+1}$) that $x \in \cap_{n=1}^{\infty} A_n$.

BUT if yo can prove that if $\cap_{n=1}^k A_n$ is not empty implies that $\cap_{n=1}^{k+1} A_n$ is non empty, you have proven by induction that $\cap_{n=1}^M A_n$ is non empty for any $M \in \mathbb N$. !!!!BUT!!! you did NOT prove that $\cap_{n=1}^{\infty} A_n$ is non empty because $\infty$ is not a natural number you can ever reach. Induction says you can reach every finite natural number but it doesn't say anything about reach any infinite value.

fleablood
  • 124,253
  • 1
    With regards to your last paragraph: Does induction not prove that a statement is true for all N — which is precisely the scope of the definition of an infinite intersection? I feel like the infinity notation is misleading in that infinity isn’t being invoked as an infinite large quantity – Redstark Sep 23 '19 at 05:29
  • No. If it is true for all $N$ it is true for all finite intersections. It need not be true about any infinite intersection. "I feel like the infinity notation is misleading in that infinity isn’t being invoked as an infinite large quantity" But it is. The example of say $A_n = (-\frac 1n, 1+\frac 1n)$ then $\cap_{k=1}^M A_n = (-\frac 1M, 1 +\frac 1M)$ is always an open interval (which could be proven by induction for all $M \in \mathbb N$. But $\cap_{k=1}^M A_n = [0,1]$ is not an open interval.... but it depends on what the statement actually is. – fleablood Sep 23 '19 at 06:30
  • On the other hand if $x \in A_k$ for all $k$ then it is in $\cap^\infty A_n$. Bu that's not a statement about the infinite intersection actually but about a specific $x$ being in all $A_n$..... But again I ask what actually is your question. Asking "can I prove $x$ is in an infinite intersection by induction" is little bit like asking "can I find an area of a shape be doing addition" Well, it depends on the question. – fleablood Sep 23 '19 at 06:34
  • @fleablood Exactly, isn't this dependence on question confusing? For example, in proving nested interval property, according to Steven Abbott's Understanding Analysis, it is applicable $\forall n\in N\exists x\in\cap_{n=1}^{\infty}I_n$. In this case, the infinity sign simply means for all natural number. But then in the same book, it differentiates specifically between $\cap_{n=1}^k A_n$ and $\cap_{n=1}^{\infty}A_n$ by saying the latter is infinity case in the infintie de morgan's example. As you can see,without specification, how can one tell whether $\cap_{n=1}^{\infty}A_n$ infinite or not? – Andes Lam Dec 30 '20 at 13:09
  • " In this case, the infinity sign simply means for all natural number. " I don't think it does. I think it implies it is true for all natural numbers as a result but it doesn't mean for all natural numbers. This would be akin to proving something is true for all rationals but showing it is true for all reals. – fleablood Dec 30 '20 at 15:41
  • @fleablood Sorry but I don't understand what do you mean by "it is true for all natural numbers as a result but it doesn't mean for all natural numbers". Aren't these 2 mean the same? – Andes Lam Dec 31 '20 at 06:12
1

Induction could potentially be useful in showing that $x \in \bigcap_{n=1}^\infty A_n$, but it might not be.

It would be helpful in the case that you can easily prove $x \in A_n \Rightarrow x \in A_{n+1}$, but you can not easily prove directly that $x \in A_n$ for arbitrary $n$. I can't immediately think of an example where this holds, but surely one exists.

It would not be necessary if you can just directly show that $x \in A_n$ for all $n$. For instance, if $A_n = (-1/n,1/n)$, then it's very easy to directly show $0 \in A_n$ for all $n$. Induction is not helpful in this case.

kccu
  • 20,808
  • 1
  • 22
  • 41
  • "I can't immediately think of an example where this holds, but surely one exists." $A_n= {2q-3|q\in A_{n-1}}$ and $A_0= \mathbb N$ and $x = 3$. Maybe? – fleablood Sep 23 '19 at 06:44
  • @fleablood Sure, I think that would work. – kccu Sep 23 '19 at 12:52