Categorical theoryIn mathematical logic, a theory is categorical if it has exactly one model (up to isomorphism). Such a theory can be viewed as defining its model, uniquely characterizing the model's structure. In first-order logic, only theories with a finite model can be categorical. Higher-order logic contains categorical theories with an infinite model. For example, the second-order Peano axioms are categorical, having a unique model whose domain is the set of natural numbers In model theory, the notion of a categorical theory is refined with respect to cardinality.
Ur-elementEn théorie des ensembles, un ur-element (ou urelement) est quelque chose qui n'est pas un ensemble mais qui peut être élément d'un ensemble. Ainsi, si u est un ur-element, et X un ensemble, on peut avoir ou non : u ∈ X, mais X ∈ u est impossible. Ils partagent ainsi avec le seul ensemble vide le fait de ne posséder aucun élément, mais pour des raisons tout à fait différentes : rien ne peut appartenir à un ur-element parce que cela n'a pas de sens, alors que rien n'appartient à l'ensemble vide par définition.
Complexité descriptiveEn informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin.
Élimination des quantificateursEn logique mathématique, ou plus précisément en théorie des modèles, l'élimination des quantificateurs est l'action consistant à trouver une formule sans quantificateur équivalente à une formule donnée contenant éventuellement des quantificateurs dans la théorie considérée d'un certain langage.
Détermination (théorie des ensembles)La détermination est un sous-champ de la théorie des ensembles, une branche des mathématiques, qui s'intéresse aux conditions dans lesquelles un joueur peut avoir ou non une stratégie gagnante dans un jeu, à la complexité d'une telle stratégie quand elle existe, ainsi qu'aux conséquences de l'existence de telles stratégies. Les jeux étudiés en théorie des ensembles sont généralement des jeux de Gale-Stewart, c'est-à-dire des jeux à deux joueurs à où les joueurs font une suite infinie de coups et où aucun match nul n'est possible.
Cumulative hierarchyIn mathematics, specifically set theory, a cumulative hierarchy is a family of sets indexed by ordinals such that If is a limit ordinal, then Some authors additionally require that or that . The union of the sets of a cumulative hierarchy is often used as a model of set theory. The phrase "the cumulative hierarchy" usually refers to the standard cumulative hierarchy of the von Neumann universe with introduced by . A cumulative hierarchy satisfies a form of the reflection principle: any formula in the language of set theory that holds in the union of the hierarchy also holds in some stages .
Théorème de LindströmEn logique mathématique, le théorème de Lindström (publié en 1969 par le logicien suédois Per Lindström) caractérise la logique du premier ordre comme suit : en gros, il s'agit de la logique qui possède le théorème de compacité et le théorème de Löwenheim-Skolem descendant. L'énoncé du théorème est le suivant : Soit L une logique abstraite (i.e. qui vérifie certaines conditions, voir plus loin) qui est plus expressive que la logique du premier ordre.
