在序理论和相关的领域中，如格和畴（域理论）中，全序性（completeness）一般是指对于偏序集存在某个特定的上确界或下确界。值得特别注意的是，这个概念在特定的情况下也应用于完全布尔代数，完全格和完全偏序。并且一个有序域被称为完全的，如果它的任何在这个域中有上界的非空子集，都有一个在这个域中的最小上界；注意这个定义与序理论中的完全有界性（bounded complete）有细小的差别。在同构的意义下，有且仅有一个完全有序域，即实数。

在数理逻辑，一个理论被称为完备的，如果对于其语言中的任何一个句子S，这个理论包括且仅包括S或。一个系统是相容的，如果不存在同时P和非P的证明。哥德尔不完备定理证明了，包含皮亚诺公理的所有公理系统都是不可能既完备又相容的。下面还有一些逻辑中关于完备性的定义。

在证明论和相关的数理逻辑的领域中，一个形式的演算相对于一个特定的逻辑（即相对于它的语义）是完备的，如果任何由一组前提Q根据语义导出的陈述S，都可以从这组前提出发利用这个演算语法地导出。形式地说，导出。一阶逻辑在这个意义下是完备的。特别地，所有逻辑的重言式都可以被证明。即使在经典逻辑中，这与前述的完备性是不同的（即一个陈述和否定陈述对于这个逻辑而言不可能是重言式）。相反的概念被称为可靠性（soundness）。

在计算复杂度理论中，一个问题P对于一个复杂度类C，在某个给定类型的归约下是完全的（完备 (复杂度)），如果P在C中，并且C中的任何问题利用该归约都可以化归到P。例如，NP完全问题在NP类和多项式时间和多对一归约的意义下是完全的。