In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem. The axiom of choice is equivalent to the statement that every partition has a transversal.
In mathematics, the Hausdorff maximal principle is an alternate and earlier formulation of Zorn's lemma proved by Felix Hausdorff in 1914. It states that in any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset, where "maximal" is with respect to set inclusion.
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain necessarily contains at least one maximal element.
Arrow's impossibility theorem is a key result in social choice theory, showing that no ranking-based decision rule can satisfy the requirements of rational choice theory. Most notably, Arrow showed that no such rule can satisfy all of a certain set of seemingly simple and reasonable conditions that include independence of irrelevant alternatives, the principle that a choice between two alternatives A and B should not depend on the quality of some third, unrelated option C.
The Smithset, sometimes called the top-cycle, generalizes the idea of a Condorcet winner to cases where no such winner exists. It does so by allowing cycles of candidates to be treated jointly, as if they were a single Condorcet winner. Voting systems that always elect a candidate from the Smith set pass the Smith criterion. The Smith set and Smith criterion are both named for mathematician John H Smith.
In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.
In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.
In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section) is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of C (the set it is a member of). If the original sets are not disjoint, there are two possibilities for the definition of a transversal:
A Condorcet winner is a candidate who would receive the support of more than half of the electorate in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the Condorcet winner criterion. The Condorcet winner criterion extends the principle of majority rule to elections with multiple candidates.
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that:
Any set of d + 2 points in Rd can be partitioned into two sets whose convex hulls intersect.
In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an undirected complete graph. The name tournament comes from interpreting the graph as the outcome of a round-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser.
In the study of electoral systems, the uncovered set is a set of candidates that generalizes the notion of a Condorcet winner whenever there is a Condorcet paradox. The Landau set can be thought of as the Pareto frontier for a set of candidates, when the frontier is determined by pairwise victories.
In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.
In graph theory and statistics, a graphon is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
In functional analysis, a branch of mathematics, a selection theorem is a theorem that guarantees the existence of a single-valued selection function from a given set-valued map. There are various selection theorems, and they are important in the theories of differential inclusions, optimal control, and mathematical economics.
In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality of preference aggregation rules, such as voting rules. It is an indicator of the extent to which an aggregation rule can yield well-defined choices.
In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or as topological ends of topological spaces associated with the graph.
In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.
Maximal lotteries refers to a probabilistic voting rule. The method uses preferential ballots and returns a probability distribution of candidates that a majority of voters would weakly prefer to any other.
In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique problem is the algorithmic problem of distinguishing random graphs from graphs that have a planted clique. This is a variation of the clique problem; it may be solved in quasi-polynomial time but is conjectured not to be solvable in polynomial time for intermediate values of the clique size. The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption.
Mathematicsportal 
![A tournament on 4 vertices:
A
=
{
1
,
2
,
3
,
4
}
{\displaystyle A=\{1,2,3,4\}}
,
[?]=
{
(
1
,
2
)
,
(
1
,
4
)
,
(
2
,
4
)
,
{\displaystyle \succ =\{(1,2),(1,4),(2,4),}
(
3
,
1
)
,
(
3
,
2
)
,
(
4
,
3
)
}
{\displaystyle (3,1),(3,2),(4,3)\}} 4-tournament.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/8/89/4-tournament.svg/220px-4-tournament.svg.png)
