# How to formalize $\text{span}(S)=\{c_1v_1+\cdots+c_kv_k\mid v_1,~\cdots,~v_k\in S,~c_1,~\cdots,~c_k\in F\}$ rigorously in first order language?

In Linear Algebra, the subspace of a vector space $V$ over a field $F$ spanned by a set $S$ of $V$, is defined to be the set of all linear combinations of $S$. Symbolically, it may be written as something like $\text{span}(S)=\{c_1v_1+\cdots+c_kv_k\mid v_1,~\cdots,~v_k\in S,~c_1,~\cdots,~c_k\in F\}$, or $\text{span}(S)=\{c_1v_1+\cdots+c_kv_k\mid\forall i\in\{1,\cdots,k\},~(v_i\in S\wedge c_i\in F)\}$.

It is a satisfactory way to write down the definition for those are just studying linear algebra. However, for someone who has studied rigorous mathematical logic, would definitely argue that this definition is somewhat illed, one reason is that the character of "$k$" here does not explicitly say that itself is mutable; we can pick aribitrary number of vectors in $S$ to generate a linear combination, maybe one, maybe ten. For example, we can choose $v_1,v_2\in S$, then $3v_1+5v_2\in\text{span}(S)$; also, we can choose $w_1,w_2,w_3,w_4,w_5,w_6\in S$, then $3w_1+5w_2+w_3+w_4+2w_5+w_6\in\text{span}(S)$. The predicate which used to generate the set $\text{span}(S)$ by the separtion axiom of $\textsf{ZFC}$, is "$v_1,~\cdots,~v_k\in S,~c_1,~\cdots,~c_k\in F$" or "$\forall i\in\{1,\cdots,k\},~(v_i\in S\wedge c_i\in F)$", they both have a free variable $k$. Also, if we rewrite them as "$\{x\mid \exists k\in\mathbb{N},~v_1,~\cdots,~v_k\in S,~c_1,~\cdots,~c_k\in F,~x=c_1v_1+\cdots c_kv_k\}$". Then is it legal? Can a latter occured variable $v_k$ have a subscript refering to the pre-occuring variable $k$? I never see a well-formed formula in first order language can be built like this way. I think it is illegal and pretty blurred. So, how can we formalize $\text{span}(S)$ in a rigorous first order language? Any suggestions or comments is welcomed.

• Indeed, in general, $\exists k, \exists v_1,...\exists v_k$ is not well-formed. As a matter of fact, here, a correct quantification would be $\exists k\in \mathbb{N},\exists v\in V^k,\exists \lambda \in K^k$ (where $K$ is the base field): you don't quantify over the variables $v_i$, rather over the sequence $v = (v_1,..,v_k)$ (similarly for $\lambda$). – Max Aug 27 '17 at 16:59
• @Max That still doesn't address the OP's concern: you can't quantify over $\mathbb{N}$ explicitly in first-order logic. The issue comes down to handling finiteness set-theoretically; there is no first-order formula in the vector space context alone which defines linear combination. – Noah Schweber Aug 27 '17 at 17:03
• @Noah : I thought it was clear that quantification was in set theory, but to me it was obvious, it's onky after reading your answer that I realized it wasn't – Max Aug 27 '17 at 17:32
• @Max That's a clarity that, in my experience, comes with practice. :) – Noah Schweber Aug 27 '17 at 17:37
• I want to draw attention to a detail of Noah Schweber's answer. It is a bad idea to work with sets of vectors. If $v\not=0$, then a list $\langle v\rangle$ is linearly independent, but $\langle v, v\rangle$ is linearly dependent. Multiplicity of vectors matters. Sets do not preserve multiplicity. For example, Sheldon Axler in “Linear Algebra Done Right” works with lists of vectors. – beroal Sep 3 '17 at 21:43

Like everything else having to do with finiteness, the sentence inquestion isn't written in the first-order language of vector spaces, but instead in the language of set theory: we're not working inside a single vector space, but rather inside a model of (say) ZFC, and in that context we can talk about finiteness, finite linear combinations, etc.

Now, of course, different models of ZFC may have different notions of "finite" (this follows from the Compactness Theorem). So we may have the following situation, very roughly stated (it's a good exercise to figure out a way to describe this precisely): $M$ and $N$ are two models of ZFC where $M$'s version of $\mathbb{N}$ is nonstandard but $N$'s is standard, $V$ is a vector space in both $M$ and $N$, $s$ is a set of vectors in $M$ and $N$, and $v\in V$ such that $M\models v\in \langle s\rangle$ but $N\models v\not\in\langle s\rangle$.

So notions that make reference to finiteness (among other things) depend on the ambient model of set theory we're living in.

OK, so what does this formula look like? Well, before I say more, the brief summary is:

We're going to find a way to quantify over "finite tuples" (so that we can write "$\exists$ some finite tuple" instead of having a block of quantifiers of variable length, which is of course forbidden) and manage these finite tuples (e.g. talk about the sum of a finite tuple of vectors).

Well, the language of set theory is very . . . parsimonious, so actually writing out explicitly such statements is a serious chore (and this has been used as an argument to develop a different foundation for mathematics than ZFC, one which allows us to express such basic concepts more quickly). But the rough idea is the following. Talking about vector spaces in ZFC is easy if tedious, by using ordered pairs (a vector space is a tuple of sets and functions satisfying some properties). Now we need to talk about finite sequences. Well, ZFC lets us define the things called "finite ordinals." Now, just like nonstandard models of arithmetic will have infinite "natural numbers," these "finite ordinals" might not be actually finite in a given model, but the model will always think that they are. A finite tuple is then a function $f$ with domain a proper initial segment of the set $\omega$ of finite ordinals; and this is perfectly definable in the language of set theory.

This, in turn, lets us define "finite linear combination." Suppose $U$ is a set of vectors. Then $v\in \langle U\rangle$ iff:

• there are functions $f, g$ with domain the same proper initial segment $I$ of $\omega$ and domain $U$ and $F$ respectively (that is, $f$ is a sequence of vectors in $U$ and $g$ is a sequence of scalars, and they have the same length), and

• there is a function $h$ with domain $I$ and codomain $V$ (the idea is that $h(n)$ will be the $n$th partial sum) such that

• $h(\max(I))=v$, $h(0)=0_V$, and $h(k+1)=h(k)+f(k)*g(k)$ for each $k\in I$.

Barring a stupid indexing mismatch on my part (I'm tired), this gives us the notion of linear combination. Specifically, using this as the definition of span, the theory ZFC will be able to prove all the usual theorems about linear independence etc. But these theorems are not stated in the language of vector spaces - rather, they're stated in the far more powerful language of set theory, and they are proved in the far more powerful theory ZFC rather than the theory of vector spaces over a given field.

• I think OP was more asking about the quantification $\exists k, \exists v_1,..., v_k$ – Max Aug 27 '17 at 17:00
• @Max That's what my answer addresses - those quantifiers take place in set theory, not in the vector space itself. – Noah Schweber Aug 27 '17 at 17:02
• Thanks. I haven't complete the study of finiteness of model or some related theorem about it. Maybe it's not the time for me to think my question right now(I need to study the related section in the mathematical logic books first.) But I want to ask that, if I guess correct, is it to say that we can't formalize $\text{span}(S)$ in the syntax-level, we need to get model involved and say something about the model? – Eric Aug 27 '17 at 17:02
• @Eric Not quite. The point of my answer is that we can totally formalize span in the syntax-level, just a bigger syntax level than is obvious: we need to work with the language of set theory, not just of vector spaces, and in a set theory like ZFC, rather than trying to have our "ambient model" be just a vector space. – Noah Schweber Aug 27 '17 at 17:04
• But @Noah, even in set theory, $\exists k, \exists v_1,...,\exists v_k$ is not valid quantification : a well-formed formula cannot have the number of its quantifiers depend on one of its quantifiers. To my mind (OP will say no if it's not the case), that was the issue, don't you think ? – Max Aug 27 '17 at 17:31