Let $Q$ be some finite set with $n = |Q|$. Then suppose I want to show that for every nonempty subset $P \subseteq Q$ some property $A$ holds. One natural way to approach this is using induction, and suppose I have an inductive proof in the following sense, I succeeded showing it for the one-element subsets. Now I assume that for some subset $P$ the property holds for every proper nonempty subsets. And then supposing that $P = P' \cup \{q\}$ with $q\notin P'$ I can show that under the assumption $A$ for $P'$ the property $A$ also holds for $P$.

Looking closely, I remember that an induction arguments shows the property holds for all $n$, and that in the above case we do induction on the cardinality of the sets. But its not induction on $n = |Q|$, as this was arbitrary but fixed in advance, its induction on the cardinality of the subsets of $Q$. But the point is we do not have subsets of arbitrary cardinality in $Q$, just of cardinality $k \le n$. So property $A$ cannot hold for every $k$, as for $k > n$ we do not even have such subsets.

So, is it legitimate to call the above proof scheme a proof by induction? And if I want to formalize this more, making explicit what axioms and deduction rules are used, how would this be done?

One idea, we actually prove the statement $$ A'(k) :\Leftrightarrow (k \le n) \rightarrow \forall P \subseteq Q \mbox{ property $A$ holds}. $$ So that the base case is $A'(1)$, and in the inductive step if $k \le n$ we use the hypotheses as $k-1 \le n$ and otherwise the statement holds just by definition, without relying on the hypotheses. But I do not know if this is the way to go here.

  • 1
    $\begingroup$ If there are no subsets of cardinatlity $k>n$ then for the (not existing) subsets with cardinality $k$ the statement is vacuously true. So you can start with something like "if $k>n$ the we are ready, so let's assume that $k\leq n$..." I disagree with: "property $A$ cannot hold for every $k$". You cannot find a subset with that cardinality for which property $A$ does not hold. This because such subsets do not exist. $\endgroup$ – drhab May 11 '17 at 14:15

Yes, a proof like that would still be an inductive proof in the sense that you exploit some kind of 'domino stone' kind of reasoning.

Now, you can set up this induction in many different ways. First of all, to deal with the upper bound, you can indeed do what you are trying to do, which is to make the claim conditional on $k \le n$, but I think a little bit easier way is to incorporate the upper bound in the induction scheme, as I'll demonstrate in the examples below.

Second, you can induce over $k$ with $k$ being the size of the subsets in question. And, since it looks like you can show that any subset with $k+1$ elements has property $A$ if you assume that any subset with $k$ elements has property $A$, you can do ordinary or weak mathematical induction like so:

Definition $A(k)$

$A(k)$: Any $P \subseteq Q$ where $|P|=k$ has property $A$

Induction scheme:

$$(A(0) \land \forall k (k < n \rightarrow (A(k) \rightarrow A(k+1)))) \rightarrow \forall k (k \le n \rightarrow A(k))$$

(and of course, once you have proven $\forall k (k \le n \rightarrow A(k))$, you have thereby proven that for all $P \subseteq Q$: $P$ has property $A$

If it turns out you need a strong version of induction, the induction scheme would be:

$$\forall k (k \le n \rightarrow (\forall m (m < k \rightarrow A(m)) \rightarrow A(k))) \rightarrow \forall k (k \le n \rightarrow A(k))$$

But (and again, I think what will be a little nicer) you can also induce over the subset relation, since that is a well-ordering. That is, rather than making claim about the size of the subsets, you can make the claim directly about these subsets. So, you can do something like this:

$A(P)$: set $P$ has property $A$

(Weak) Induction scheme:

$$(A(\emptyset) \land \forall P (P \subset Q \rightarrow \forall q ((q \in Q \land q \not \in P) \rightarrow A(P \cup \{ q \})))) \rightarrow \forall P (P \subseteq Q \rightarrow A(P))$$

Three nice things about this option is that the claim $A(P)$ talks about a single subset $P$ (as opposed $A(k)$ referring to a class of subsets of a certain size, the fact that you don;t need to refer to any numbers whatsoever, and the fact that the $Q$ provides a nice natural upper bound in this induction scheme.

Finally, the strong induction version for this method may well be the nicest/cleanest version:

(Strong) Induction Scheme:

$$\forall P (P \subseteq Q \rightarrow (\forall R (R \subset P \rightarrow A(R)) \rightarrow A(P))) \rightarrow \forall P (P \subseteq Q \rightarrow A(P))$$

I really like this one, because it is so intuitive: If you can prove that any $P \subset Q$ has property $A$ assuming that all strict subsets $R$ of $P$ have property $A$, then all subsets of $Q$ have property $A$.

  • $\begingroup$ Thanks for the detailed answer, but regarding your 3rd paragraph: Do you really mean $n$ or do you mean $k$ there? As $n$ is fixed in advance and I see no need to do induction over it? $\endgroup$ – StefanH May 11 '17 at 16:06
  • $\begingroup$ @StefanH You're welcome, and yeah, I should $k$ there! $\endgroup$ – Bram28 May 11 '17 at 16:08

There is no intrinsic reason the idea of induction has to use infinite sets. For example, theorems about subgroups of a finite group might use induction on the order of the subgroup. Once you reach the size of the whole group, or whatever maximal size is possible (like a theorem about $p$-subgroups), the proof just stops.

By the same method, you can prove $1+2+\cdots+n = n(n+1)/2$ for all $n$ up through 100 by using the inductive step up to $n=99$ and then just stop.

  • $\begingroup$ Surely, intuitively clear. But I wanted this to be more formally spelled out: for example the usual induction runs $A(0) \land (\forall k : A(k) \rightarrow A(k+1))$ implies $\forall n : A(n)$, or in terms of subsets of $\mathbb N$, if $A \subseteq \mathbb N$ fulfills $0\in A$ and $k \in A$ implies $k+1 \in A$ then $A = \mathbb N$. And I am asking about how to incorporate this "stopping" you mentioned into this formal formulation. $\endgroup$ – StefanH May 11 '17 at 16:12
  • $\begingroup$ Change $\forall k$ to $\forall k \leq N$ and $\forall n$ to $\forall n \leq N+1$. $\endgroup$ – KCd May 11 '17 at 16:52
  • $\begingroup$ Surely, but still you have to prove that this gives a valid deduction scheme. And do you have a different approach than substituting the altered property $A'$ conditional on $k \le N$ (from my question) into the usual induction scheme? $\endgroup$ – StefanH May 11 '17 at 17:16

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.