Timeline for (Types of) induction on infinite chains
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2019 at 10:17 | comment | added | Peter LeFanu Lumsdaine | @NotDominicRaab: As you’ve probably seen (but haven’t explicitly said), the facts “property holds for 0” and “if property holds for $2^k$, it holds for $2^{k+1}$” are not sufficient to imply the property holds on the whole of your chain: consider the property “being equal to 0”, which satisfies those facts but doesn’t hold on the whole chain. One natural condition which would suffice to “connect” the chain to 0 is if the property is defined for all real numbers, and is an open property, i.e. defines an open subset of $\mathbb{R}$. | |
| Mar 21, 2019 at 15:41 | comment | added | Dirk | Yes, ok, in this case induction doesn't work, as you have no way to get from $0$ to $2^{-\infty}$, so to speak, there is no proper successor of $0$. That's why I suggested to take a different starting point in this case, because we have a rather easy rule to go from $2^k$ to $2^{k-1}$, and also a highest starting point. As you want to show that the property holds for all elements of the set, it shouldn't make a difference if you start at $0$ or at $2^m$. | |
| Mar 21, 2019 at 14:39 | comment | added | NotDominicRaab | I think you are taking my chain to be upside-down (but I'm not sure, and I hope you are correct!). I know that the result holds for $0$, and that if it holds for $2^k$ then it holds for $2^{k+1}$. I want to understand $2^m$. The issue, as I see it, is that I need to somehow "connect" the infinite descending chain of $2^k$s with the minimal element $0$. | |
| Mar 21, 2019 at 14:35 | comment | added | Dirk | This makes it even easier. In that case, you have a starting point for your chain, $2^m$, and go down from there, completely classical induction. You just need to treat the 0 by hand. | |
| Mar 21, 2019 at 14:35 | comment | added | NotDominicRaab | It'll probably take me a while to process everything you wrote, but regarding your first sentence: I know this, and my question is trying to work out what extra info. I might need. | |
| Mar 21, 2019 at 14:34 | comment | added | NotDominicRaab | Sorry, in my example $m$ was meant to be fixed. I've edited this in. | |
| Mar 21, 2019 at 14:20 | history | answered | Dirk | CC BY-SA 4.0 |