本节以严格的标准数学语言描述了计算机程序中排序的逻辑系统。许多结果是显而易见的，一些符号可能会在各种计算机科学教科书中找到。任何发现以下内容有任何缺陷的人都可以改进它。

第一作者在这里应用的数学很复杂，但并不复杂。

注意：对这些证明的传统方法依赖于略微不稳定的假设。它采用了一种称为“循环不变式”的装置，该装置是在底层程序结构方面定义的。以这种方式构建的证明可以在大多数优秀的算法教科书中找到。

基本概念

不可能对一个无序集合进行排序；但是排序通常并不关注集合，而是关注序列。那么，让我们精确地定义一下我们可以排序的序列，以及可能产生的结果。设S为任何具有全序关系的集合 ( $\mathbb {Z}$ , $Q$ , $\mathbb {R}$ ...) 设A为该集合的有限子集。设J为 $\mathbb {N}$ 的有限子集，即自然数。现在绘制一个函数 $\phi :J\rightarrow S$ 。集合J诱导出所谓的置换群 Sym(J)，即所有从J到J的双射的集合。现在设 $\Phi \equiv \{\mu \in Sym)J):\phi \circ \mu$ 。稍微思考一下就会让读者明白，这里描述的集合正是序列元素的所有可能排列。当然， $\phi _{\mu }=\phi _{\lambda }$ 是可能的，如果恰好一个置换交换索引，使得函数的值在索引处没有改变；但这不是我们关注的主要问题。正如我们所看到的， $\Phi$ 中只有一个函数是递增的。（当 x ≥ y 意味着 f(x) ≥ f(y) 时，函数是递增的）。