Proof of Carathéodory's Theorem in $\mathbb{R}^n$

Let $z\in\operatorname{conv}S$, and let $\mathcal{N}$ be the set of those $N\in\mathbb{N}$ for which $z$ is a convex combination of $N$ points of $S$ (Convex Weights, the Standard Simplex, and Convex Combinations in $\mathbb{R}^n$ (iii)). By The Convex Hull Consists of the Convex Combinations of Finitely Many Points (i) the set $\mathcal{N}$ is nonempty, so it has a least element $N$ by Arithmetic and Order of the Natural Numbers (xv). Fix $x_{1},\dots,x_{N}\in S$ and $t\in\Delta_{N}$ with $z=\sum_{k=1}^{N}t_{k}x_{k}$. We show that $N\le n+1$; by Arithmetic and Order of the Natural Numbers (vii) it suffices to rule out $n+1<N$, so suppose, for a contradiction, that $n+1<N$. The idea is that $N$ points of $\mathbb{R}^{n}$ with $N>n+1$ are affinely dependent, and moving the weights along such a dependence until one of them vanishes produces a shorter representation.

An affine dependence. Let $A\in\mathcal{M}_{(n+1)\times N}(\mathbb{R})$ be the matrix whose $k$th column is $x_{k}$ with an entry $1$ appended, that is,

$$A_{ik}=(x_{k})_{i}\quad(i\in[n]),\qquad A_{n+1,k}=1,\qquad(k\in[N])$$

(the row index $n+1$ is distinct from those in $[n]$ by Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space (i)). Since $A$ has more columns than rows, A Homogeneous Linear System with More Unknowns than Equations Has a Nonzero Solution (i) gives $\mu\in\mathbb{R}^{N}$ with $\mu\neq0$ and $A\mu=0$. Read row by row through Matrix-Vector Product (i), this says $\sum_{k=1}^{N}\mu_{k}(x_{k})_{i}=0$ for every $i\in[n]$ and $\sum_{k=1}^{N}\mu_{k}=0$. Since sums of points are computed coordinatewise (Convex Sets in $\mathbb{R}^n$: Standing Notation (iii)) and points of $\mathbb{R}^{n}$ with equal coordinates are equal (Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations (iii)), we obtain

$$\sum_{k=1}^{N}\mu_{k}x_{k}=0,\qquad\sum_{k=1}^{N}\mu_{k}=0.$$

Some coefficient $\mu_{k}$ is positive. Otherwise $\mu_{k}\le0$ for every $k$, and since $\mu\neq0$ some coordinate $\mu_{k_{0}}$ is nonzero (Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations (iii)), hence negative; comparing $\sum_{k=1}^{N}\mu_{k}$ termwise with the sum of $N$ zeros would give $\sum_{k=1}^{N}\mu_{k}<0$ (Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (v), Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (iv)), contradicting the display.

Moving along the dependence. The set $P=\{k\in[N]:\mu_{k}>0\}$ is a nonempty subset of the finite set $[N]$, so it is finite, and so is its image $\{t_{k}/\mu_{k}:k\in P\}\subseteq\mathbb{R}$ (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vii), Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iv), Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vi)). This nonempty finite set has a least element $\alpha$ (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (viii)); fix $j\in P$ with $\alpha=t_{j}/\mu_{j}$. As $t_{k}\ge0$ and $\mu_{k}>0$ for $k\in P$, we have $\alpha\ge0$ and $\alpha\mu_{k}\le t_{k}$ for every $k\in P$. Put $t'=t-\alpha\mu\in\mathbb{R}^{N}$. Then $t'_{k}\ge0$ for every $k$ (for $k\in P$ by the choice of $\alpha$, and for $k\notin P$ because $\mu_{k}\le0\le\alpha$), and $t'_{j}=0$. By Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (i) and Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality (ii), applied in $\mathbb{R}$ and in $\mathbb{R}^{n}$, and the two relations displayed above,

$$\sum_{k=1}^{N}t'_{k}=1-\alpha\cdot0=1,\qquad\sum_{k=1}^{N}t'_{k}x_{k}=z-\alpha\cdot0=z.$$

So $t'\in\Delta_{N}$ (Convex Weights, the Standard Simplex, and Convex Combinations in $\mathbb{R}^n$ (i)) and $z=\sum_{k=1}^{N}t'_{k}x_{k}$, with the weight $t'_{j}$ equal to zero.

A shorter representation. Since $N>n+1\ge1$, we can write $N=N'+1$ with $N'\in\mathbb{N}$ (Arithmetic and Order of the Natural Numbers (xii)). Apply Convex Combinations: Small Cases, Splitting Off the Last Point, Dropping a Zero Weight, Joining Two Combinations, and Membership in Convex Sets (iv) to the points $x_{1},\dots,x_{N'+1}$, the weights $t'$ and the index $j$, with the bijection $g_{j}:[N']\to[N'+1]\setminus\{j\}$ it names: the weights $(t'_{g_{j}(1)},\dots,t'_{g_{j}(N')})$ lie in $\Delta_{N'}$ and

$$z=\sum_{k=1}^{N'}t'_{g_{j}(k)}\,x_{g_{j}(k)}.$$

Thus $z$ is a convex combination of the $N'$ points $x_{g_{j}(1)},\dots,x_{g_{j}(N')}$ of $S$, so $N'\in\mathcal{N}$ although $N'<N$, contradicting the minimality of $N$. Hence $N\le n+1$, and $x_{1},\dots,x_{N}$ and $t$ are as claimed.