Set theory

Set theory Topics

Sort by:

Empty set

The set containing no elements, commonly denoted or , the former of which is used in this work. These correspond to Wolfram Language and TeX characters summarized in the table below.symbolTeXWolfram Language\varnothing\[Diameter]\emptyset\[EmptySet]Unfortunately, some authors use the notation 0 instead of for the empty set (Mendelson 1997). The empty set is generally designated using (i.e., the empty list) in the Wolfram Language.A set that is not the empty set is called a nonemptyset. The empty set is sometimes also known as the null set (Mendelson 1997).The complement of the empty set is the universal set.Strangely, the empty set is both open and closed for any set and topology.A groupoid, semigroup, quasigroup, ringoid, and semiring can be empty. Monoids, groups, and rings must have at least one element, while division algebras and fields must have at least two elements...

Element

If is a member of a set , then is said to be an element of , written . If is not an element of , this is written .The term element also refers to a particular member of a group, or entry in a matrix or unevaluated determinant .

Disjoint sets

Two sets and are disjoint if their intersection , where is the empty set. sets , , ..., are disjoint if for . For example, and are disjoint, but and are not. Disjoint sets are also said to be mutually exclusive or independent.

Superset

A set containing all elements of a smaller set. If is a subset of , then is a superset of , written . If is a proper superset of , this is written .

Directed set

A set together with a relation which is both transitive and reflexive such that for any two elements , there exists another element with and . In this case, the relation is said to "direct" the set.

Subset

A subset is a portion of a set. is a subset of (written ) iff every member of is a member of . If is a proper subset of (i.e., a subset other than the set itself), this is written . If is not a subset of , this is written . (The notation is generally not used, since automatically means that and cannot be the same.)The subsets (i.e., power set) of a given set can befound using Subsets[list].An efficient algorithm for obtaining the next higher number having the same number of 1 bits as a given number (which corresponds to computing the next subset) is given by Gosper (1972) in PDP-10 assembler.The set of subsets of a set is called the power set of , and a set of elements has subsets (including both the set itself and the empty set). This follows from the fact that the total number of distinct k-subsets on a set of elements is given by the binomial sumFor sets of , 2, ... elements, the numbers of subsets are therefore 2, 4, 8, 16, 32, 64, ... (OEIS A000079). For example, the set..

Poretsky's law

The theorem in set theory and logic that for all sets and ,(1)where denotes complement set of and is the empty set. The set is depicted in the above Venn diagram and clearly coincides with iff is empty.The corresponding theorem in a Boolean algebra states that for all elements of ,(2)The version of Poretsky's Law for logic can be derived from (2) using the rules of propositional calculus, namely for all propositions and ,(3)where "is equivalent to" means having the same truth table. In fact, in the following table, the values in the second and in the third column coincide if and only if the value in the first column is 0.( and not ) or (not and )000011101110

Complete product

The complete products of a Boolean algebra of subsets generated by a set of cardinal number are the Boolean functions(1)where each may equal or its complement . For example, the complete products of are(2)Each Boolean function has a unique representation(up to order) as a union of complete products. For example,(3)(4)(5)(Comtet 1974, p. 186).

Matroid

Roughly speaking, a matroid is a finite set together with a generalization of a concept from linear algebra that satisfies a natural set of properties for that concept. For example, the finite set could be the rows of a matrix, and the generalizing concept could be linear dependence and independence of any subset of rows of the matrix.Formally, a matroid consists of a finite set of elements together with a family of nonempty subsets of , called circuits, which satisfy the axioms 1. No proper subset of a circuit is a circuit, 2. If and , then contains a circuit. (Harary 1994, p. 40).An equivalent definition considers a matroid as a finite set of elements together with a family of subsets of , called independent sets, such that 1. The empty set is independent, 2. Every subset of an independent set is independent,3. For every subset of , all maximum independent sets contained in have the same number of elements. (Harary 1994, pp. 40-41).The number..

Set class

A class is a generalized set invented to get around Russell's antinomy while retaining the arbitrary criteria for membership which leads to difficulty for sets. The members of classes are sets, but it is possible to have the class of "all sets which are not members of themselves" without producing a paradox (since is a proper class (and not a set), it is not a candidate for membership in ).The distinction between classes and sets is a concept from vonNeumann-Bernays-Gödel set theory.

Inductive set

A set-theoretic term having a number of different meanings. Fraenkel (1953, p. 37) used the term as a synonym for "finite set." However, according to Russell's definition (Russell 1963, pp. 21-22), an inductive set is a nonempty partially ordered set in which every element has a successor. An example is the set of natural numbers , where 0 is the first element, and the others are produced by adding 1 successively.Roitman (1990, p. 40) considers the same construction in a more abstract form: the elements are sets, 0 is replaced by the empty set , and the successor of every element is the set . In particular, every inductive set contains a sequence of the formFor many other authors (e.g., Bourbaki 1970, pp. 20-21; Pinter 1971, p. 119), an inductive set is a partially ordered set in which every totally ordered subset has an upper bound, i.e., it is a set fulfilling the assumption of Zorn's lemma.The versions..

Set

A set is a finite or infinite collection of objects in which order has no significance, and multiplicity is generally also ignored (unlike a list or multiset). Members of a set are often referred to as elements and the notation is used to denote that is an element of a set . The study of sets and their properties is the object of set theory.Older words for set include aggregate and set class. Russell also uses the unfortunate term manifold to refer to a set.Historically, a single horizontal overbar was used to denote a set stripped of any structure besides order, and hence to represent the order type of the set. A double overbar indicated stripping the order from the set and hence represented the cardinal number of the set. This practice was begun by set theory founder Georg Cantor.Symbols used to operate on sets include (which means "and" or intersection), and (which means "or" or union). The symbol is used to denote the set containing..

Proper subset

A proper subset of a set , denoted , is a subset that is strictly contained in and so necessarily excludes at least one member of . The empty set is therefore a proper subset of any nonempty set.For example, consider a set . Then and are proper subsets, while and are not.

Finite set

A set whose elements can be numbered through from 1 to , for some positive integer . The number is called the cardinal number of the set, and is often denoted or . In other words, is equipollent to the set . We simply say that has elements. The empty set is also considered as a finite set, and its cardinal number is 0.A finite set can also be characterized as a set which is not infinite, i.e., as a set which is not equipollent to any of its proper subsets. In fact, if , and , a certain number of elements of do not belong to , so that .For all , the number of subsets having exactly elements (the so-called k-subsets, or combinations of elements out of ) is equal to the binomial coefficient(1)(2)Hence the number of subsets of (i.e., the cardinal number of its power set) is(3)(4)(5)by virtue of the binomial theorem.Assigning to each k-subset of its complement set defines a one-to-one correspondence between the set of k-subsets and the set of -subsets of . This proves the..

Rank

The word "rank" refers to several related concepts in mathematics involving graphs, groups, matrices, quadratic forms, sequences, set theory, statistics, and tensors.In graph theory, the graph rank of a graph is defined as , where is the number of vertices on and is the number of connected components (Biggs 1993, p. 25).In set theory, rank is a (class) function from sets to ordinal numbers. The rank of a set is the least ordinal number greater than the rank of any member of the set (Mirimanoff 1917; Moore 1982, pp. 261-262; Rubin 1967, p. 214). The proof that rank is well-defined uses the axiom of foundation.For example, the empty set has rank 0 (since it has no members and 0 is the least ordinal number), has rank 1 (since , its only member, has rank 0), has rank 2, and has rank . Every ordinal number has itself as its rank.Mirimanoff (1917) showed that, assuming the class of urelements is a set, for any ordinal number , the class..

Nowhere dense

A set is said to be nowhere dense if the interior of the set closure of is the empty set. For example, the Cantor set is nowhere dense.There exist nowhere dense sets of positive measure. For example, enumerating the rationals in as and choosing an open interval of length containing for each , then the union of these intervals has measure at most 1/2. Hence, the set of points in but not in any of has measure at least 1/2, despite being nowhere dense.

Complement set

Given a set with a subset , the complement (denoted or ) of with respect to is defined as(1)Using set difference notation, the complement isdefined by(2)If , then(3)where is the empty set. The complement is implemented in the Wolfram Language as Complement[l, l1, ...].Given a single set, the second probabilityaxiom gives(4)Using the fact that ,(5)(6)This demonstrates that(7)Given two sets,(8)(9)

Disjoint union

The disjoint union of two sets and is a binary operator that combines all distinct elements of a pair of given sets, while retaining the original set membership as a distinguishing characteristic of the union set. The disjoint union is denoted(1)where is a Cartesian product. For example, the disjoint union of sets and can be computed by finding(2)(3)so(4)(5)

Set difference

The set difference is defined byHere, the backslash symbol is defined as Unicode U+2216.The set difference is therefore equivalent to the complement set, and is implemented in the Wolfram Language as Complement[A, B].The symbol is sometimes also used to denote a set difference (Smith et al. 1997, p. 68).

Concurrent relation

Let and be sets, and let be a relation on . Then is a concurrent relation if and only if for any finite subset of , there exists a single element of such that if , then . Examples of concurrent relations include the following: 1. The relation on either the natural numbers, the integers, the rational numbers, or the real numbers. 2. The relation between elements of an extension of a field , defined by3. The containment relation between open neighborhoods of a given point of a topological space .

Reflexive reduction

The reflexive reduction of a binary relation on a set is the minimum relation on with the same reflexive closure as . Thus for any elements and of , provided that and are distinct and .

Transitive reduction

The transitive reduction of a binary relation on a set is the minimum relation on with the same transitive closure as . Thus for any elements and of , provided that and there exists no element of such that and .The transitive reduction of a graph is the smallest graph such that , where is the transitive closure of (Skiena 1990, p. 203).

Reflexive closure

The reflexive closure of a binary relation on a set is the minimal reflexive relation on that contains . Thus for every element of and for distinct elements and , provided that .

Partial order ideal

An ideal of a partial order is a subset of the elements of which satisfy the property that if and , then . For disjoint chains in which the th chain contains elements, there are ideals. The number of ideals of a -element fence poset is the Fibonacci number .

Ground set

A partially ordered set is defined as an ordered pair . Here, is called the ground set of and is the partial order of .

Well ordered set

A totally ordered set is said to be well ordered (or have a well-founded order) iff every nonempty subset of has a least element (Ciesielski 1997, p. 38; Moore 1982, p. 2; Rubin 1967, p. 159; Suppes 1972, p. 75). Every finite totally ordered set is well ordered. The set of integers , which has no least element, is an example of a set that is not well ordered.An ordinal number is the ordertype of a well ordered set.

Partial order

A relation "" is a partial order on a set if it has: 1. Reflexivity: for all . 2. Antisymmetry: and implies . 3. Transitivity: and implies .For a partial order, the size of the longest chain (antichain) is called the partial order length (partial order width). A partially ordered set is also called a poset.A largest set of unrelated vertices in a partial order can be found using MaximumAntichain[g] in the Wolfram Language package Combinatorica$. MinimumChainPartition[g] in the Wolfram Language package Combinatorica$ partitions a partial order into a minimum number of chains.

Fence poset

A partial order defined by (, ), (, ) for odd .

Duality law

A metatheorem stating that every theorem on partially ordered sets remains true if all inequalities are reversed. In this operation, supremum must be replaced by infimum, maximum with minimum, and conversely. In a lattice, this means that meet and join must be interchanged, and in a Boolean algebra, 1 and 0 must be switched.Each of de Morgan's two laws can be derived from the other by duality.

Totally ordered set

A total order (or "totally ordered set," or "linearly ordered set") is a set plus a relation on the set (called a total order) that satisfies the conditions for a partial order plus an additional condition known as the comparability condition. A relation is a total order on a set (" totally orders ") if the following properties hold. 1. Reflexivity: for all . 2. Antisymmetry: and implies . 3. Transitivity: and implies . 4. Comparability (trichotomy law): For any , either or . The first three are the axioms of a partial order, while addition of the trichotomy law defines a total order.Every finite totally ordered set is well ordered. Any two totally ordered sets with elements (for a nonnegative integer) are order isomorphic, and therefore have the same order type (which is also an ordinal number)...

Dominance

The dominance relation on a set of points in Euclidean -space is the intersection of the coordinate-wise orderings. A point dominates a point provided that every coordinate of is at least as large as the corresponding coordinate of .A partition dominates a partition if, for all , the sum of the largest parts of is the sum of the largest parts of . For example, for , dominates all other partitions, while is dominated by all others. In contrast, and do not dominate each other (Skiena 1990, p. 52).The dominance orders in are precisely the partially ordered sets of dimension at most .

Dilworth's lemma

The partial order width of a set is equal to the minimum number of chains needed to cover . Equivalently, if a set of elements is partially ordered, then contains a chain of size or an antichain of size . Letting be the cardinal number of , the partial order width, and the partial order length, this last statement says . Dilworth's lemma is a generalization of the Erdős-Szekeres theorem. Ramsey's theorem generalizes Dilworth's lemma.

Tarski's fixed point theorem

Let be any complete lattice. Suppose is monotone increasing (or isotone), i.e., for all , implies . Then the set of all fixed points of is a complete lattice with respect to (Tarski 1955)Consequently, has a greatest fixed point and a least fixed point . Moreover, for all , implies , whereas implies .Consider three examples: 1. Let satisfy , where is the usual order of real numbers. Since the closed interval is a complete lattice, every monotone increasing map has a greatest fixed point and a least fixed point. Note that need not be continuous here. 2. For declare to mean that , , (coordinatewise order). Let satisfy . Then the set(1)(2)is a complete lattice (with respect to the coordinatewise order). Hence every monotone increasing map has a greatest fixed point and a least fixed point. 3. Let and be injections. Then there is a bijection (Schröder-Bernstein theorem), which can be constructed as follows. The power set of ordered by set inclusion,..

Order isomorphic

Two totally ordered sets and are order isomorphic iff there is a bijection from to such that for all ,(Ciesielski 1997, p. 38). In other words, and are equipollent ("the same size") and there is an order preserving mapping between the two.Dauben (1990) and Suppes (1972) call this property "similar." The definitionworks equally well on partially ordered sets.

Cover relation

The transitive reflexive reduction of a partial order. An element of a partially ordered set covers another element provided that there exists no third element in the poset for which . In this case, is called an "upper cover" of and a "lower cover" of .

Strictly between

Let be a partially ordered set, and let . If , then is said to be between and . If is between and and , then is strictly between and .

Maximal element

Let be a partially ordered set. Then an element is said to be maximal if, for all , . Alternatively, an element is maximal such that if for any , then .Note that the definition for a maximal element above is true for any two elements of a partially ordered set that are comparable. However, it may be the case that two elements of a given partial ordering are not comparable.

Complete lattice

A partially ordered set (or ordered set or poset for short) is called a complete lattice if every subset of has a least upper bound (supremum, ) and a greatest lower bound (infimum, ) in .Taking shows that every complete lattice has a greatest element (maximum, ) and a least element (minimum, ).Of course, every complete lattice is a lattice. Moreover, every lattice with a finite set is a complete lattice.

Realizer

A set of linear extensions of a partially ordered set is a realizer of (and is said to realize ) provided that for all , iff is below in every member of .

Linear extension

A linear extension of a partially ordered set is a permutation of the elements , , ... of such that implies . For example, the linear extensions of the partially ordered set are 1234, 1324, 1342, 3124, 3142, and 3412, all of which have 1 before 2 and 3 before 4.

Comparable elements

Suppose is a partial ordering on a nonempty set . Then the elements are said to be comparable provided or .Because two elements in a partially ordered set need not be comparable, it is possible for a partially ordered set to have more than one maximal element. For example, suppose we have a nonempty partially ordered set in which every element is incomparable to every other element, i.e., is totally unordered. It follows that every element of is maximal.

Preorder

A relation "" is called a preorder (or quasiorder) on a set if it satisfies: 1. Reflexivity: for all . 2. Transitivity: and implies . A preorder that also has antisymmetry is a partial order.

Chain

Let be a finite partially ordered set. A chain in is a set of pairwise comparable elements (i.e., a totally ordered subset). The partial order length of is the maximum cardinal number of a chain in . For a partial order, the size of the longest chain is called the partial order length.

Poset dimension

The dimension of a partially ordered set is the size of the smallest realizer of . Equivalently, it is the smallest integer such that is isomorphic to a dominance order in .

Isomorphic posets

Two partially ordered sets are said to be isomorphic if their "structures" are entirely analogous. Formally, partially ordered sets and are isomorphic if there is a bijection from to such that precisely when .

Partially ordered set

A partially ordered set (or poset) is a set taken together with a partial order on it. Formally, a partially ordered set is defined as an ordered pair , where is called the ground set of and is the partial order of .An element in a partially ordered set is said to be an upper bound for a subset of if for every , we have . Similarly, a lower bound for a subset is an element such that for every , . If there is an upper bound and a lower bound for , then the poset is said to be bounded.

Interval order

A partially ordered set is an interval order if it is isomorphic to some set of intervals on the real line ordered by left-to-right precedence. Formally, is an interval order provided that one can assign to each an interval such that in the real numbers iff in .

Ordinal number

In common usage, an ordinal number is an adjective which describes the numerical position of an object, e.g., first, second, third, etc.In formal set theory, an ordinal number (sometimes simply called an "ordinal" for short) is one of the numbers in Georg Cantor's extension of the whole numbers. An ordinal number is defined as the order type of a well ordered set (Dauben 1990, p. 199; Moore 1982, p. 52; Suppes 1972, p. 129). Finite ordinal numbers are commonly denoted using arabic numerals, while transfinite ordinals are denoted using lower case Greek letters.It is easy to see that every finite totally ordered set is well ordered. Any two totally ordered sets with elements (for a nonnegative integer) are order isomorphic, and therefore have the same order type (which is also an ordinal number). The ordinals for finite sets are denoted 0, 1, 2, 3, ..., i.e., the integers one less than the corresponding nonnegative..

Ordinal comparison

Let and be well ordered sets with ordinal numbers and . Then iff is order isomorphic to an initial segment of (Dauben 1990, p. 199). From this, it can easily be shown that the ordinal numbers are totally ordered by the relation. In fact, they are well ordered by the relation.

Order type

Every totally ordered set is associated with a so-called order type. Two sets and are said to have the same order type iff they are order isomorphic (Ciesielski 1997, p. 38; Dauben 1990, pp. 184 and 199; Moore 1982, p. 52; Suppes 1972, pp. 127-129). Thus, an order type categorizes totally ordered sets in the same way that a cardinal number categorizes sets. The term is due to Georg Cantor, and the definition works equally well on partially ordered sets.The order type of the negative integers is called (Moore 1982, p. 62), although Suppes (1972, p. 128) calls it . The order type of the rationals is called (Dauben 1990, p. 152; Moore 1982, p. 115; Suppes 1972, p. 128). Some sources call the order type of the reals (Dauben 1990, p. 152), while others call it (Suppes 1972, p. 128).In general, if is any order type, then is the same type ordered backwards (Dauben 1990, p. 153)...

Limit ordinal

An ordinal number is called a limit ordinal iff it has no immediate predecessor, i.e., if there is no ordinal number such that (Ciesielski 1997, p. 46; Moore 1982, p. 60; Rubin 1967, p. 182; Suppes 1972, p. 196). The first limit ordinal is .

Model theory

Model theory is a general theory of interpretations of axiomatic set theory. It is the branch of logic studying mathematical structures by considering first-order sentences which are true of those structures and the sets which are definable in those structures by first-order formulas (Marker 1996).Mathematical structures obeying axioms in a system are called "models" of the system. The usual axioms of analysis are second order and are known to have the real numbers as their unique model. Weakening the axioms to include only the first-order ones leads to a new type of model in what is called nonstandard analysis.

Uniquely complemented lattice

A uniquely complemented lattice is a complemented lattice that satisfiesThe class of uniquely complemented lattices is not a subvariety of the class of complemented lattices. On the other hand, there is a well-known class of uniquely complemented lattices that is a subvariety of the variety of complemented lattices, namely the class of Boolean algebras. They form a variety because they are the distributive complemented lattices, and one can prove that any distributive complemented lattice is uniquely complemented.

Locally bounded lattice

A lattice is locally bounded if and only if each of its finitely generated sublattices is bounded.Every locally bounded lattice is locally subbounded, and every locally bounded lattice has a bounded hyperfinite extension in any nonstandard enlargement . This latter nonstandard property characterizes locally subbounded lattices.A locally bounded lattice is locally tight if and only if each of its hyperfinitely generated extensions is internally tight. One can also prove the following result, using nonstandard characterizations of these notions: Let be a locally finite lattice with at least one strictly increasing meet endomorphism and at least one strictly decreasing join endomorphism. If is locally tight, then it is bounded.

Local polarity

Let be a lattice, and let . Then the pair is a local polarity if and only if for each finite set , there is a finitely generated sublattice of that contains and on which the restriction is a lattice polarity.Using nonstandard methods, one may show that the following result holds: Let be a locally finite lattice. Then the set of local polarities of is a relation which is a one-to-one correspondence between its domain and range.

Independent vertex set

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of . The figure above shows independent sets consisting of two subsets for a number of graphs (the wheel graph , utility graph , Petersen graph, and Frucht graph).The polynomial whose coefficients give the number of independent vertex sets of each cardinality in a graph is known as its independence polynomial.A set of vertices is an independent vertex set iff its complement forms a vertex cover (Skiena 1990, p. 218). The counts of vertex covers and independent vertex sets in a graph are therefore the same.The empty set is trivially an independent vertex setsince it contains no vertices, and therefore no edge endpoints.A maximum independent vertex set is an independent vertex set of a graph containing the largest possible number of vertices for the given graph, and the cardinality of this set is called the independence number..

Semialgebraic set

A semialgebraic set is a subset of which is a finite Boolean combination of sets of the form and , where and are polynomials in , ..., over the reals.By Tarski's theorem, the solution set of a quantified system of real algebraic equations and inequalities is a semialgebraic set (Strzebonski 2000).

Antichain

Let be a finite partially ordered set, then an antichain in is a set of pairwise incomparable elements. Antichains are also called Sperner systems in older literature (Comtet 1974).For example, consider to be a family of subsets together with the subset relation (i.e., if is a subset of ). The following table gives the antichains on the set of subsets (i.e., the power set) of the -set for small .antichains123The number of antichains on the -set for , 1, 2, ..., are 1, 2, 5, 19, 167, ... (OEIS A014466). If the empty set is not considered a valid antichain, then these reduce to 0, 1, 4, 18, 166, ... (OEIS A007153; Comtet 1974, p. 273). The numbers obtained by adding one to OEIS A014466, 2, 3, 6, 20, 168, 7581, 7828354, ... (OEIS A000372), are also frequently encountered (Speciner 1972).The number of antichains on the -set are equal to the number of monotonic increasing Boolean functions of variables, and also the number of free distributive lattices..

Cardinal exponentiation

Let and be any sets, and let be the cardinal number of a set . Then cardinal exponentiation is defined by(Ciesielski 1997, p. 68; Dauben 1990, p. 174; Moore 1982, p. 37; Rubin 1967, p. 275, Suppes 1972, p. 116).It is easy to show that the cardinal number of the power set of is , since and there is a natural bijection between the subsets of and the functions from into .

Infinite set

A set of elements is said to be infinite if the elements of a proper subset can be put into one-to-one correspondence with the elements of . An infinite set whose elements can be put into a one-to-one correspondence with the set of integers is said to be countably infinite; otherwise, it is called uncountably infinite.

Cardinal comparison

For any sets and , their cardinal numbers satisfy iff there is a one-to-one function from into (Rubin 1967, p. 266; Suppes 1972, pp. 94 and 116). It is easy to show this satisfies the reflexive and transitive axioms of a partial order. However, it is difficult to show the antisymmetry property, whose proof is known as the Schröder-Bernstein theorem. To show the trichotomy property, one must use the axiom of choice.Although an order type can be defined similarly, it does not seem usual to do so.

Let and be any sets with empty intersection, and let denote the cardinal number of a set . Then(Ciesielski 1997, p. 68; Dauben 1990, p. 173; Rubin 1967, p. 274; Suppes 1972, pp. 112-113).It is an interesting exercise to show that cardinal addition is well-defined. The main steps are to show that for any cardinal numbers and , there exist disjoint sets and with cardinal numbers and , and to show that if and are disjoint and and disjoint with and then . The second of these is easy. The first is a little tricky and requires an appeal to the axioms of set theory. Also, one needs to restrict the definition of cardinal to guarantee if is a cardinal, then there is a set satisfying .

Set partition

A set partition of a set is a collection of disjoint subsets of whose union is . The number of partitions of the set is called a Bell number.

Axiom of the sum set

The axiom of Zermelo-Fraenkel set theory which asserts the existence for any set of the sum (union) of all sets that are elements of . The axiom may be stated symbolically as

Surreal number

Surreal numbers are the most natural collection of numbers which includes both the real numbers and the infinite ordinal numbers of Georg Cantor. They were invented by John H. Conway in 1969. Every real number is surrounded by surreals, which are closer to it than any real number. Knuth (1974) describes the surreal numbers in a work of fiction.The surreal numbers are written using the notation , where , is the simplest number greater than 0, is the simplest number greater than 1, etc. Similarly, is the simplest number less than 0, etc. However, 2 can also be represented by , , , etc.Some simple games have abbreviated names that can be expressed in terms of surreal numbers. For example, , , for an integer , , , and . Most surreal numbers can be represented as hackenbush positions.

Join

In a lattice, any two elements and have a least upper bound. This least upper bound is often called the join of and , and is denoted by .One can also speak of the join operation in a general partially ordered set. If and are two elements in some partially ordered set , and if there is a smallest element (with respect to the given order) with the property that and , then is said to be the join of and .

Distributive lattice

A lattice which satisfies the identitiesis said to be distributive.

Complemented lattice

A complemented lattice is an algebraic structure such that is a bounded lattice and for each element , the element is a complement of , meaning that it satisfies 1. 2. . A related notion is that of a lattice with complements. Such a structure is a bounded lattice such that for each , there is such that and .One difference between these notions is that the class of complemented lattices forms a variety, whilst the class of lattices with complements does not. (The class of lattices with complements is a subclass of the variety of lattices, but it is not a subvariety of the class of lattices.) Every lattice with complements is a reduct of a complemented lattice, by the axiom of choice. To see this, let be a lattice with complements. For each , let denote the set of complements of . Because is a lattice with complements, for each , is nonempty, so by the axiom of choice, we may choose from each collection a distinguished complement for . This defines a function which..

Lattice homomorphism

Let and be lattices, and let . Then is a lattice homomorphism if and only if for any , and . Thus a lattice homomorphism is a specific kind of structure homomorphism. In other words, the mapping is a lattice homomorphism if it is both a join-homomorphism and a meet-homomorphism.If is a one-to-one lattice homomorphism, then it is a lattice embedding, and if a lattice embedding is onto, then it is a lattice isomorphism.An example of an important lattice isomorphism in universal algebra is the isomorphism that is guaranteed by the correspondence theorem, which states that if is an algebra and is a congruence on , then the mapping that is defined by the formulais a lattice isomorphism.

Meet

In a lattice, any two elements and have a greatest lower bound. This greatest lower bound is often called the meet of and , and is denoted by .One can also speak of the meet operation in a general partially ordered set. If and are two elements in some partially ordered set , and if there is a greatest element (with respect to the given order) with the property that and , then is said to be the meet of and .

Ordinal multiplication

Let and be totally ordered sets. Let be the Cartesian product and define order as follows. For any and , 1. If , then , 2. If , then and compare the same way as (i.e., lexicographical order) (Ciesielski 1997, p. 48; Rubin 1967; Suppes 1972). However, Dauben (1990, p. 104) and Moore (1982, p. 40) define multiplication in the reverse order.Like addition, multiplication is not commutative, but it is associative,(1)An inductive definition for ordinal multiplication states that for any ordinal number ,(2)(3)If is a limit ordinal, then is the least ordinal greater than any ordinal in the set (Suppes 1972, p. 212).

Dedekind cut

A set partition of the rational numbers into two nonempty subsets and such that all members of are less than those of and such that has no greatest member. Real numbers can be defined using either Dedekind cuts or Cauchy sequences.

Zermelo set theory

The version of set theory obtained if Axiom 6 of Zermelo-Fraenkelset theory is replaced by 6'. Selection axiom (or "axiom of subsets"): for any set-theoretic formula , , which can be deduced from Axiom 6. However, there seems to be some disagreement in the literature about just which axioms of Zermelo-Fraenkel set theory constitute "Zermelo Set Theory." Mendelson (1997) does not include the axioms of choice, foundation, replacement In Zermelo set theory, but does includes 6'. However, Enderton (1977) includes the axioms of choice and foundation, but does not include the axioms of replacement or Selection.

Ordinal exponentiation

Let and be any ordinal numbers, then ordinal exponentiation is defined so that if then . If is not a limit ordinal, then choose such that ,If is a limit ordinal, then if , . If then, is the least ordinal greater than any ordinal in the set (Rubin 1967, p. 204; Suppes 1972, p. 215).Note that this definition is not analogous to the definition for cardinals, since may not equal , even though and . Note also that .A familiar example of ordinal exponentiation is the definition of Cantor's first epsilon number. is the least ordinal such that . It can be shown that it is the least ordinal greater than any ordinal in .

Let and be disjoint totally ordered sets with order types and . Then the ordinal sum is defined at set where, if and are both from the same subset, the order is the same as in the subset, but if is from and is from , then has order type (Ciesielski 1997, p. 48; Dauben 1990, p. 104; Moore 1982, p. 40).One should note that in the infinite case, order typeaddition is not commutative, although it is associative. For example,(1)In addition, , with the least element, is order isomorphic to , but not to , with the greatest element, since it has a greatest element and the other does not.An inductive definition for ordinal addition states that for any ordinal number ,(2)and(3)If is a limit ordinal, then is the least ordinal greater than any ordinal in the set (Rubin 1967, p. 188; Suppes 1972, p. 205)...

Counting number

A positive integer: 1, 2, 3, 4, ... (OEIS A000027), also called a natural number. However, zero (0) is sometimes also included in the list of counting numbers. Due to lack of standard terminology, the following terms are recommended in preference to "counting number," "natural number," and "whole number."setnamesymbol..., , , 0, 1, 2, ...integersZ1, 2, 3, 4, ...positive integersZ-+0, 1, 2, 3, 4, ...nonnegative integersZ-*0, , , , , ...nonpositive integers, , , , ...negative integersZ--

For a countable set of disjoint events , , ...,

Natural number

The term "natural number" refers either to a member of the set of positive integers 1, 2, 3, ... (OEIS A000027) or to the set of nonnegative integers 0, 1, 2, 3, ... (OEIS A001477; e.g., Bourbaki 1968, Halmos 1974). Regrettably, there seems to be no general agreement about whether to include 0 in the set of natural numbers. In fact, Ribenboim (1996) states "Let be a set of natural numbers; whenever convenient, it may be assumed that ."The set of natural numbers (whichever definition is adopted) is denoted N.Due to lack of standard terminology, the following terms and notations are recommended in preference to "counting number," "natural number," and "whole number."setnamesymbol..., , , 0, 1, 2, ...integersZ1, 2, 3, 4, ...positive integersZ-+0, 1, 2, 3, 4, ...nonnegative integersZ-*0, , , , , ...nonpositive integers, , , , ...negative integersZ--..

Urelement

An urelement contains no elements, belongs to some set, and is not identical with the empty set (Moore 1982, p. 3; Rubin 1967, p. 23). "Ur" is a German prefix which is difficult to translate literally, but has a meaning close to "primeval." Urelements are also called "atoms" (Rubin 1967, Moore 1982) or "individuals" (Moore 1982).In "pure" set theory, all elements are sets and there are no urelements. Often, the axioms of set theory are modified to allow the presence of urelements for ease in representing something. In fact, before Paul Cohen developed the method of forcing, some of the independence theorems in set theory were shown if urelements were allowed.

Internally extendable homomorphism

Let be an infinite set of urelements, and let be an enlargement of the superstructure . Let be finitary algebras with finitely many operations, and let and be their extension monads in . Let be a homomorphism. Then is internally extendable provided that there is an internal subalgebra of which contains and there is a homomorphism such that if , then .For a homomorphism , the following are equivalent: 1. is internally extendable and is a subalgebra of , 2. For some homomorphism , is the restriction to of .

Successor

For any ordinal number , the successor of is (Ciesielski 1997, p. 46). The successor of an ordinal number is therefore the next ordinal, .

Initial ordinal

An ordinal number is called an initial ordinal if every smaller ordinal has a smaller cardinal number (Moore 1982, p. 248; Rubin 1967, p. 271). The s ordinal numbers are just the transfinite initial ordinals (Rubin 1967, p. 272).This proper class can be well ordered and put into one-to-one correspondence with the ordinal numbers. For any two well ordered sets that are order isomorphic, there is only one order isomorphism between them. Let be that isomorphism from the ordinals to the transfinite initial ordinals, thenwhere .

Independence complement theorem

If sets and are independent, then so are and , where is the complement of (i.e., the set of all possible outcomes not contained in ). Let denote "or" and denote "and." Then(1)(2)where is an abbreviation for . But and are independent, so(3)Also, since and are complements, they contain no common elements, which means that(4)for any . Plugging (4) and (3) into (2) then gives(5)Rearranging,(6)Q.E.D.

Inclusion map

Given a subset of a set , the injection defined by for all is called the inclusion map.

Simple function

A simple function is a finite sum , where the functions are characteristic functions on a set . Another description of a simple function is a function that takes on finitely many values in its range.The collection of simple functions is closed under addition and multiplication. In addition, it is easy to integrate a simple function. By approximating a given function by simple functions, the Lebesgue integral of can be calculated.

Set theory

The mathematical theory of sets. Set theory is closely associatedwith the branch of mathematics known as logic.There are a number of different versions of set theory, each with its own rules and axioms. In order of increasing consistency strength, several versions of set theory include Peano arithmetic (ordinary algebra), second-order arithmetic (analysis), Zermelo-Fraenkel set theory, Mahlo, weakly compact, hyper-Mahlo, ineffable, measurable, Ramsey, supercompact, huge, and -huge set theory.

Hall's theorem

There exists a system of distinct representatives for a family of sets , , ..., iff the union of any of these sets contains at least elements for all from 1 to (Harary 1994, p. 53).

Saturated enlargement

Let be a set of urelements, and let be the superstructure with as its set of individuals. Let be a cardinal number. An enlargement is -saturated provided that it satisfies the following:For each internal binary relation , and each set , if is contained in the domain of and the cardinality of is less than , then there exists a in the range of such that if , then .If is -saturated for some cardinal that is greater than or equal to the cardinality of , then we just say that is saturated. If it is -saturated for some cardinal that is greater than or equal to the cardinality of , then we say it is polysaturated.Let be the set of real numbers, as urelements. Let be a cardinal number that is larger than the cardinality of the power set of , and let be a -saturated enlargement of . Let be an internal subset of , and let . Then is a closed subset of (in the usual topology of the real numbers).Using saturated enlargements, one may prove the following result in universal algebra:Let..

Finite

A set which contains a nonnegative integral number of elements is said to be finite. A set which is not finite is said to be infinite. A finite or countably infinite set is said to be countable. While the meaning of the term "finite" is fairly clear in common usage, precise definitions of finite and infinite are needed in technical mathematics and especially in set theory.

Space join

Let and be topological spaces. Then their join is the factor space(1)where is the equivalence relation(2)

Complex projective plane

The set is the set of all equivalence classes of ordered triples under the equivalence relation if for some nonzero complex number .

Hilbert hotel

Let a hotel have a denumerable set of rooms numbered 1, 2, 3, .... Then any finite number of guests can be accommodated without evicting the current guests by moving the current guests from room to room . Furthermore, a denumerable number of guests can be similarly accommodated by moving the existing guests from to , freeing up the denumerable number of rooms .

Countably infinite

Any set which can be put in a one-to-one correspondence with the natural numbers (or integers) so that a prescription can be given for identifying its members one at a time is called a countably infinite (or denumerably infinite) set. Once one countable set is given, any other set which can be put into a one-to-one correspondence with is also countable. Countably infinite sets have cardinal number aleph-0.Examples of countable sets include the integers, algebraic numbers, and rational numbers. Georg Cantor showed that the number of real numbers is rigorously larger than a countably infinite set, and the postulate that this number, the so-called "continuum," is equal to aleph-1 is called the continuum hypothesis. Examples of nondenumerable sets include the real, complex, irrational, and transcendental numbers...

Cantor's equation

where is an ordinal number and is an inaccessible cardinal.

Continuum hypothesis

The proposal originally made by Georg Cantor that there is no infinite set with a cardinal number between that of the "small" infinite set of integers and the "large" infinite set of real numbers (the "continuum"). Symbolically, the continuum hypothesis is that . Problem 1a of Hilbert's problems asks if the continuum hypothesis is true.Gödel showed that no contradiction would arise if the continuum hypothesis were added to conventional Zermelo-Fraenkel set theory. However, using a technique called forcing, Paul Cohen (1963, 1964) proved that no contradiction would arise if the negation of the continuum hypothesis was added to set theory. Together, Gödel's and Cohen's results established that the validity of the continuum hypothesis depends on the version of set theory being used, and is therefore undecidable (assuming the Zermelo-Fraenkel axioms together with the axiom of choice).Conway..

Cantor diagonal method

The Cantor diagonal method, also called the Cantor diagonal argument or Cantor's diagonal slash, is a clever technique used by Georg Cantor to show that the integers and reals cannot be put into a one-to-one correspondence (i.e., the uncountably infinite set of real numbers is "larger" than the countably infinite set of integers). However, Cantor's diagonal method is completely general and applies to any set as described below.Given any set , consider the power set consisting of all subsets of . Cantor's diagonal method can be used to show that is larger than , i.e., there exists an injection but no bijection from to . Finding an injection is trivial, as can be seen by considering the function from to which maps an element of to the singleton set . Suppose there exists a bijection from to and consider the subset of consisting of the elements of such that does not contain . Since is a bijection, there must exist an element of such that . But by the..

Transfinite number

One of Cantor's ordinal numbers , , , ..., , , ... which is "larger" than any whole number.

Sperner's theorem

The maximum cardinal number of a collection of subsets of a -element set , none of which contains another, is the binomial coefficient , where is the floor function.

Cardinal number

In common usage, a cardinal number is a number used in counting (a countingnumber), such as 1, 2, 3, ....In formal set theory, a cardinal number (also called "the cardinality") is a type of number defined in such a way that any method of counting sets using it gives the same result. (This is not true for the ordinal numbers.) In fact, the cardinal numbers are obtained by collecting all ordinal numbers which are obtainable by counting a given set. A set has (aleph-0) members if it can be put into a one-to-one correspondence with the finite ordinal numbers. The cardinality of a set is also frequently referred to as the "power" of a set (Moore 1982, Dauben 1990, Suppes 1972).In Georg Cantor's original notation, the symbol for a set annotated with a single overbar indicated stripped of any structure besides order, hence it represented the order type of the set. A double overbar then indicated stripping the order from the set and thus indicated..

Cardinal multiplication

Let and be any sets. Then the product of and is defined as the Cartesian product(Ciesielski 1997, p. 68; Dauben 1990, p. 173; Moore 1982, p. 37; Rubin 1967, p. 274; Suppes 1972, pp. 114-115).

Graphoid

A graphoid consists of a set of elements together with two collections and of nonempty subsets of , called circuits and cocircuits respectively, such that 1. For any and , , 2. No circuit properly contains another circuit and no cocircuit properly contains another cocircuit, 3. For any painting of with colors exactly one element green and the rest either red or blue, there exists either (a) a circuit containing the green element and no red elements, or (b) a cocircuit containing the green element and no blue elements.

Kneser's conjecture

A combinatorial conjecture formulated by Kneser (1955). It states that whenever the -subsets of a -set are divided into classes, then two disjoint subsets end up in the same class.Lovász (1978) gave a proof based on graph theory. In particular, he showed that the Kneser graph, whose vertices represent the -subsets, and where each edge connects two disjoint subsets, is not -colorable. More precisely, his results says that the chromatic number is equal to , and this implies that Kneser's conjecture is always false if the number of classes is increased to .An alternate proof was given by Bárány (1978).

Independent set

Two sets and are said to be independent if their intersection , where is the empty set. For example, and are independent, but and are not. Independent sets are also called disjoint or mutually exclusive.An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of . The figure above shows independent vertex sets consisting of two subsets for a number of graphs (the wheel graph , utility graph , Petersen graph, and Frucht graph).An independent edge set can be defined similarly(Skiena 1990, p. 219).

Zorn's lemma

If is any nonempty partially ordered set in which every chain has an upper bound, then has a maximal element. This statement is equivalent to the axiom of choice.Renteln and Dundes (2005) give the following (bad) mathematical jokes about Zorn's lemma:Q: What's sour, yellow, and equivalent to the axiomof choice? A: Zorn's lemon.Q: What is brown, furry, runs to the sea, and is equivalent to the axiomof choice? A: Zorn's lemming.

Characteristic function

Given a subset of a larger set, the characteristic function , sometimes also called the indicator function, is the function defined to be identically one on , and is zero elsewhere. Characteristic functions are sometimes denoted using the so-called Iverson bracket, and can be useful descriptive devices since it is easier to say, for example, "the characteristic function of the primes" rather than repeating a given definition. A characteristic function is a special case of a simple function.The term characteristic function is used in a different way in probability, where it is denoted and is defined as the Fourier transform of the probability density function using Fourier transform parameters ,(1)(2)(3)(4)(5)where (sometimes also denoted ) is the th moment about 0 and (Abramowitz and Stegun 1972, p. 928; Morrison 1995).A statistical distribution is not uniquely specified by its moments, but is by its characteristic..

Power set

Given a set , the power set of , sometimes also called the powerset, is the set of all subsets of . The order of a power set of a set of order is . Power sets are larger than the sets associated with them. The power set of is variously denoted or .The power set of a given set can be found in the Wolfram Language using Subsets[s].

Unsorted union

The unsorted union of a list is a list containing the same elements as but with the second and subsequent occurrence of any given element removed. For example, the unsorted union of the set is . The unsorted union differs from the usual union in that the elements of the unsorted union are not necessarily ordered.The unsorted union is implemented in the WolframLanguage as DeleteDuplicates[list].It can be implemented in the Wolfram Languagetop-level code as: UnsortedUnion1[x_] := Tally[x][[All, 1]]or UnsortedUnion2[x_] := Reap[Sow[1, x], _, #1&][[2]]or UnsortedUnion3[x_] := Module[{f}, f[y_] := (f[y] = Sequence[]; y); f /@ x ]Depending on the nature of the list to be unioned, different implementations above may be more efficient, although in general, the first is the fastest.

Symmetric difference

The set of elements belonging to one but not both of two given sets. It is therefore the union of the complement of with respect to and with respect to , and corresponds to the XOR operation in Boolean logic. The symmetric difference can be implemented in the Wolfram Language as: SymmetricDifference[a_, b_] := Union[Complement[a, b], Complement[b, a]]The symmetric difference of sets and is variously written as , , (Borowski and Borwein 1991) or (Harris and Stocker 1998, p. 3). All but the first notation should probably be deprecated since each of the other symbols has a common meaning in other areas of mathematics.For example, for and , , since 2, 3, and 5 are each in one, but not both, sets.

Lattice

An algebra is called a lattice if is a nonempty set, and are binary operations on , both and are idempotent, commutative, and associative, and they satisfy the absorption law. The study of lattices is called lattice theory.Note that this type of lattice is distinct from the regular array of points known as a point lattice (or informally as a mesh or grid). While every point lattice is a lattice under the ordering inherited from the plane, many lattices are not point lattices.Lattices offer a natural way to formalize and study the ordering of objects using a general concept known as the partially ordered set. A lattice as an algebra is equivalent to a lattice as a partially ordered set (Grätzer 1971, p. 6) since 1. Let the partially ordered set be a lattice. Set and . Then the algebra is a lattice. 2. Let the algebra be a lattice. Set iff . Then is a partially ordered set, and the partially ordered set is a lattice. 3. Let the partially ordered set be..

Continuum

The term "continuum" has (at least) two distinct technical meanings in mathematics.The first is a compact connected metric space (Kuratowski 1968; Lewis 1983, pp. 361-394; Nadler 1992; Prajs and Charatonik).The second is the nondenumerable set of real numbers, denoted . The continuum satisfies(1)and(2)where is aleph0 (Aleph-0) and is a positive integer. It is also true that(3)for . However,(4)is a set larger than the continuum. Paradoxically, there are exactly as many points on a line (or line segment) as in a plane, a three-dimensional space, or finite hyperspace, since all these sets can be put into a one-to-one correspondence with each other.The continuum hypothesis, first proposed by Georg Cantor, holds that the cardinal number of the continuum is the same as that of aleph1. The surprising truth is that this proposition is undecidable, since neither it nor its converse contradicts the tenets of set theory...

Union

The union of two sets and is the set obtained by combining the members of each. This is written , and is pronounced " union " or " cup ." The union of sets through is written . The union of a list may be computed in the Wolfram Language as Union[l].Let , , , ... be sets, and let denote the probability of . Then(1)Similarly,(2)(3)(4)(5)(6)The general statement of this property for sets is known as the inclusion-exclusion principle.If and are disjoint sets, then by definition , so(7)Continuing, for a set of disjoint elements , , ..., (8)which is the countable additivityprobability axiom. Now let(9)then(10)

Conjunction

A product of ANDs, denotedThe conjunctions of a Boolean algebra of subsets of cardinality are the functionswhere . For example, the 8 conjunctions of are , , , , , , , and (Comtet 1974, p. 186).A literal is considered a (degenerate) conjunction (Mendelson1997, p. 30).The Wolfram Language command Conjunction[expr, a1, a2, ...] gives the conjunction of expr over all choices of the Boolean variables .

Intersection

The intersection of two sets and is the set of elements common to and . This is written , and is pronounced " intersection " or " cap ." The intersection of sets through is written .The intersection of two lines and is written . The intersection of two or more geometric objects is the point (points, lines, etc.) at which they concur.

Infinity

Infinity, most often denoted as , is an unbounded quantity that is greater than every real number. The symbol had been used as an alternative to M () in Roman numerals until 1655, when John Wallis suggested it be used instead for infinity.Infinity is a very tricky concept to work with, as evidenced by some of the counterintuitive results that follow from Georg Cantor's treatment of infinite sets.Informally, , a statement that can be made rigorous using the limit concept,Similarly,where the notation indicates that the limit is taken from the positive side of the real line.In the Wolfram Language, is represented using the symbol Infinity.

Ultrafilter

Let be a nonempty set, then an ultrafilter on is a nonempty collection of subsets of having the following properties: 1. . 2. If then . 3. If and then . 4. For any subset of , either or its complement . An ultrafilter on is said to be free if it contains the cofinite filter of .

Filter

Let be a nonempty set, then a filter on is a nonempty collection of subsets of having the following properties: 1. , 2. If , then , 3. If and then If is an infinite set, then the collection is a filter called the cofinite (or Fréchet) filter on .In signal processing, a filter is a function or procedure which removes unwanted parts of a signal. The concept of filtering and filter functions is particularly useful in engineering. One particularly elegant method of filtering Fourier transforms a signal into frequency space, performs the filtering operation there, then transforms back into the original space (Press et al. 1992).