1
$\begingroup$

If $S=\{\alpha_1, ..., \alpha_s\}$ is an independent set of vectors and $T=\{\beta_1, ..., \beta_t\}$ be any finite set such that $S$ is dependent on $T$, then $s \leq t$.

In my textbook a proof by induction is done on the size of the independent set $S$. The base case is $s = 1$ and the induction is proof of the following conditional statement:

$[\text{Theorem is true for when the size of $S'$ is less than $s$}] \implies [\text{Theorem is true for when the size of $S'$ is $s$}]$.

That is, we assume the antecedent (the induction hypothesis) of the conditional above and also assume the antecedent of the consequent (since the theorem is a conditional) to deduce $s \leq t$. The idea of this I understand.

However, while the induction hypothesis applies to the size of any set $S'$, the author sets this $S'$ as $S' = \{\alpha_1, ..., \alpha_{s-1}\}$ which is necessarily a proper subset of $S$. Why is it the case that setting $S'$ as such comes without a loss of generality?

Thank you in advance.

$\endgroup$

1 Answer 1

0
$\begingroup$

This is a proof by induction. At this step of the proof, it is being assumed that the statement holds for any subset $S'$ of $S$ with less than $s$ elements. But using that assumption doesn't require that use it that $S'$ is any subset $S'$ whatsoever of $S$ with less than $s$ elements. If you can do it using one specific subset with less than $s$ elements, no harm is done.

If what you wanted was to prove that any subset $S'$ of $S$ with less than $s$ elements had a certain property, then, yes, it would be wrong to prove it only for a certain specific set.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! That makes perfect sense - if it is true for all independent sets with less than s elements then it is true for that particular set. The deduction continues from there until $s \leq t$ is arrived. $\endgroup$ Sep 9, 2021 at 12:21

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.