Iterative argument in math proofs

Question

I am reading proof of subspace of $\mathbb{R^n}$ has a basis. And most of them like this(classic proof): let $S\subset\mathbb{R^n}$ ,if $v_1\neq0$ and $<v_1>=S$, we finished proof, otherwise, we can select an element $v_2\in S-<v_1>$ and consider whether $<v_1,v_2>=S$,if so we finished proof, otherwise we repeat the process, because $n+1$ elements are linear dependent, the process eventually terminates. So we can get a basis.

The same argument occurs in the proof of every two integers have the greatest common divisor, we using the Euclidean algorithm in that proof, and we also conclude the process of Euclidean algorithm eventually terminates, then we can get gcd of two integers.

I can understand the proof intuitively, but I think the those two proofs are not rigorous. Because I think each step in proof must to be clear, in the first proof, I don't illustrate the every step. Let me using an example, if $n=3$, I can say step1: whether $<v_1>=S$, if so, we finished proof, if not we have step 2: let $v_2\in S-<v_1>$, whether $<v_1,v_2>=S$, if so, we finished proof, if not we have step3: let $v_3\in S-<v_1,v_2>$, we must have $<v_1,v_2,v_3>=S$,we finished proof. Each step is clear in this proof($n=3$), but for arbitrary $n$, I think I just deceive myself by thinking first few steps, I don't know(compute) later step look like actually, but I can write rigorous proof for each specific $n$ like $n=3$. I want to show this rigorously, I use the principle of recursive definition(from Topology by Munkres). Let $A$ be the set of all linearly independent set of $S$i.e. $A=\{F\subset S\mid$ all elements in $F$ are linearly independent $\} $, let $a_0\neq 0$ and $\rho(f)=im(f)$ if $<im(f)>=S$, $\rho(f)=im(f)\cup {v}$($v\in S-<im(f)>$), but if we want to $\rho$ be a function, we must select unique $v$, I think it can be use Well-ordering theorem, we can let $v$ be the minimum element in $S-<im(f)>$, however Well-ordering theorem and axiom of choice are equivalent, which means we used AC, but in the classic proof, we don't need AC. If we ignore this, we can get function $h$, which clarify what each step looks like.

Here is my question:

1. Why the classic proof is rigorous? In my opinion, we don't clarify each step, but by just thinking first few step to get whole process, it is like this: We can image square, pentagon, hexagon turely look like, we can image each vertex and edge, but how can we image 100 sided polygon, we can just image part of it, we understand it by image what part of it looks like, but not image the whole shape.

2. Is my attempt correct? If not, please give me hints to finish proof by using principle of recursive definition.(It can be proved by using principle of recursive definition right?) If so, can we complete the proof without using the Well-order theorem?

Answer 1

I have at least two solutions.

1. Let $\ell$ be the maximum of the cardinalities of the linearly independent subsets of $S$. We know $0 \leq \ell \leq n$. Let $\{v_1, \dots, v_{\ell}\}$ be any linearly independent subset of $S$ with cardinality $\ell$. If this set does not span $S$, then letting $v$ be any vector in $S$ that is not in the span of this set, we get a larger linearly independent set $\{v_1, \dots, v_\ell, v\}$, a contradiction. Thus $\{v_1, \dots, v_{\ell}\}$ spans $S$, and is therefore a basis.

2. Use recursive definition to define sets $B_j$, $j \in \mathbb{N}_0$ by $B_0 = \{\}$, $B_1 = \{v_1\}$, etc. by using your algorithm. Argue that $B_j = B_{j + 1}$ for $j \geq n$, and hence $B_n$ is a basis of $S$.