Implementation of mathematics in set theory

This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC (the dominant set theory) and in NFU, the version of Quine's New Foundations shown to be consistent by R. B. Jensen in 1969 (here understood to include at least axioms of Infinity and Choice). For details of these two systems, consult their main articles.

What is said here applies also to two families of set theories: on the one hand, a range of theories including Zermelo set theory near the lower end of the scale and going up to ZFC extended with large cardinal hypotheses such as "there is a measurable cardinal"; and on the other hand a hierarchy of extensions of NFU which is surveyed in the New Foundations article. These correspond to different general views of what the set-theoretical universe is like, and it is the approaches to implementation of mathematical concepts under these two general views that are being compared and contrasted.

It is not the primary aim of this article to say anything about the relative merits of these theories as foundations for mathematics. The reason for the use of two different set theories is to illustrate that multiple approaches to the implementation of mathematics are feasible. Precisely because of this approach, this article is not a source of "official" definitions for any mathematical concept.


Metaphorically, we are inclined to say that in the following sections we are carrying out certain constructions in the two theories ZFC and NFU and comparing the resulting implementations of certain usual mathematical structures (such as the natural numbers).

In a mathematical theory, what we do is prove theorems (and that is all we do). So when we say that a theory allows us to construct a certain object, what we are actually saying is that it is a theorem of that theory that that object exists. This is a statement about a definition of the form "the x such that phi exists", where phi is a formula of our language: we say that our theory proves the existence of "the x such that phi" just in case it is a theorem that "there is one and only one x such that phi". (See Bertrand Russell's theory of descriptions.) We may loosely say that the theory "defines" or "constructs" this object in this case. If the statement is not a theorem, we say that the theory cannot show that the object exists; if the statement is provably false in the theory, we say that the theory proves that the object cannot exist, and may loosely say that we "cannot construct" or "cannot define" this object.

ZFC and NFU share the language of set theory, so the same formal definitions "the x such that phi" can be contemplated in the two theories. A specific form of definition in the language of set theory is set-builder notation: {x mid phi} means "the set A such that for all x, x in A leftrightarrow phi" (A cannot be free in phi). This notation admits certain conventional extensions: {x in B mid phi} is synonymous with {x mid x in B wedge phi}; {f(x_1,ldots,x_n) mid phi} is defined as {z mid (exists x_1,ldots,x_n.z=f(x_1,...,x_n) wedge phi}, where f(x_1,ldots,x_n) is an expression already defined.

Expressions definable in set-builder notation make sense in both ZFC and NFU: it may be that both theories prove that a given definition succeeds, or that neither do (the expression {x mid x otin x} fails to refer to anything in "any" set theory with classical logic; in class theories like NBG this notation does refer to a class, but it is defined differently), or that one does and the other doesn't. Further, an object defined in the same way in ZFC and NFU may turn out to have different properties in the two theories (or there may be a difference in what we can prove where there is no provable difference between their properties).

Further, we import concepts from other branches of mathematics (in intention, "all" branches of mathematics) into set theory. In some cases, we do not import the concepts into ZFC and NFU in the same way. For example, the usual definition of the first infinite ordinal omega in ZFC is not suitable for NFU because the object (defined in purely set theoretical language as the set of all finite von Neumann ordinals) cannot be shown to exist in NFU. The usual definition of omega in NFUis (in purely set theoretical language) as the set of all infinite well-orderings all of whose proper initial segments are finite, an object which can be shown not to exist in ZFC. In the case of such imported objects, we may in some cases give two different definitions, one for use in ZFC and related theories, and one for use in NFU and related theories. For such "implementations" of imported mathematical concepts to make sense, it is necessary to be able to show that the two parallel interpretations have the expected properties: for example, the implementations of the natural numbers in ZFC and NFU are different, but we can say that both are implementations of the same mathematical structure, because both include definitions for all the primitives of Peanoarithmetic and satisfy the (translations of) the Peano axioms. It is then possible to compare what happens in the two theories as when only set theoretical language is in use, as long as the definitions appropriate to ZFC are understood to be used in the ZFC context and the definitions appropriate to NFU are understood to be used in the NFU context.

Whatever we prove to exist in a theory clearly provably exists in any extension of that theory; moreover, analysis of the proof that an object exists in a given theory may show that it exists in weaker versions of that theory (one may consider Zermelo set theory instead of ZFC for much of what is done in this article, for example). This is important to note because we are actually considering two hierarchies of related theories here.

Empty set, singleton, unordered pairs and tuples

These constructions appear first because they are the simplest constructions in set theory, not because they are the first constructions that come to mind in mathematics (though the notion of finite set is certainly fundamental!)

emptyset =_{mathrm{def {x mid x eq x}

The empty set is the unique set with no members. In NFU, there are also urelements with no members.

displaystyle{x} =_{mathrm{def {y mid y = x}

For each object "x", there is a set {x} with "x" as its only element.

{x,y} =_{mathrm{def {z mid z=x vee z=y}

For objects "x" and "y", there is a set {x,y} containing "x" and "y" as its only elements.

x cup y =_{mathrm{def {z mid z in x vee z in y}

The union of two sets is defined in the usual way.

{x_1,ldots,x_n,x_{n+1}} =_{mathrm{def {x_1,ldots,x_n} cup {x_{n+1}}

This is a recursive definition of unordered "n"-tuples for any concrete "n" (finite sets given as listsof their elements).

In NFU, all the set definitions given work by stratified comprehension; in ZFC, the existence of the unordered pair is given by the axiom of Pairing, the existence of the empty set follows by Separation from the existence of any set, and the boolean union of two sets exists by the axioms of Pairing and Union (x cup y = igcup{x,y}).

Ordered pair

The first substantial mathematical construction we consider is the ordered pair. The reasonthat this comes first is technical: we will need it to implement notions of relation and
function which are needed for implementations of other concepts which may seem to be prior.

The first definition of the ordered pair was the definition (x,y) =_{mathrm{def {{{x},emptyset},{{y}}} proposed by Norbert Wiener in 1914 in the contextof the type theory of Principia Mathematica. Wiener observed that this allowed the eliminationof types of n-ary relations for n>1 from the system of that work.

It is more usual now to use the definition (x,y) =_{mathrm{def {{x},{x,y}}, due to Kuratowski.

Either of these definitions works in either ZFC or NFU. In NFU, the Kuratowski pair has a technical disadvantage: it is two types higher than its projections. It is common to postulate the existence of a type-level ordered pair (a pair (x,y) which is the same type as its projections) in NFU. For the moment, we will use the Kuratowski pair in both systems, until we can give a formal justification for the introduction of the type-level pair.

The internal details of these definitions have nothing to do with their actual mathematical function. For any notion (x,y) of ordered pair, the things that matter are that it satisfy the defining condition

* (x,y)=(z,w) equiv x=z wedge y=w

and that it be reasonably easy to collect ordered pairs into sets.


Relations are sets whose members are all ordered pairs. Where possible, a relation "R" (understood as a binary predicate) is implemented as {(x,y) mid x R y} (which may be written as {z mid pi_1(z) R pi_2(z)}). Where "R" is a set of ordered pairs, we read "xRy" as ("x,y")∈"R".

In ZFC, some relations (such as the general equality relation or subset relation on sets) are "too large"to be sets (but may be harmlessly reified as proper classes). In NFU, some relations (such as the membership relation) are not sets because their definitions are not stratified: in {(x,y) mid x in y} "x" and "y" wouldneed to have the same type (because they appear as projections of the same pair), but alsosuccessive types (because "x" is considered as an element of "y").

Related definitions

For the time being, we do not consider relations with arity greater than 2: all our relations are binary.Let "R" and "S" be given binary relations. Then the following concepts are useful:

The converse of "R" is the relation {(y,x) mid x R y}.

The domain of "R" is the set {x mid (exists y.x R y)}.

The range of "R" is the domain of the converse of "R".

The field of "R" is the union of the domain and range of "R".

The preimage of a member "x" of the field of "R" is the set {y mid y Rx} (used in the definition of "well-founded" below).

The downward closure of a member "x" of the field of "R" is the smallest set "D" containing "x", and containing each "zRy" for each "y"∈"D" (i.e., including the preimage of each of its elements with respect to "R" as a subset).

The relative product of "R" and "S", "R|S", is the relation {(x,z) mid (exists y.xRy wedge ySz)}.

In ZFC, proving that these notions are all sets follows from "Union", "Separation", and "Power Set". In NFU, it is easy to check that these definitions give rise to stratified formulas.

Notice that the range and codomain of a relation are not distinguished: this could be done by representing a relation "R" with codomain "B" as "(R,B)", but our development will not require this.

In ZFC, any relation whose domain is a subset of a set "A" and whose range is a subset of a set "B" will be a set, since the cartesian product A imes B = {(a,b) mid a in A wedge b in B} is a set (being a subclass of P(P(A cup B))), and "Separation" provides for the existence of {(x,y)in A imes B mid x R y}. In NFU, some relations with global scope (such as equality and subset) can be implemented as sets. In NFU, we need to bear in mind that "x" and "y" are three types lower than "R" in xRy (one type lower if a type-level ordered pair is used).

Properties and kinds of relations

Let "R" be some binary relation. "R" is:
*Reflexive if forall x exist y . (xRy vee yRx) leftrightarrow xRx.

* Symmetric if forall xy . xRy leftrightarrow yRx.

* Transitive if forall xyz . xRy wedge yRz ightarrow xRz.

* Antisymmetric if forall xy . xRy wedge yRx ightarrow x=y.

* Well-founded if for every set "S" which meets the field of "R", exists x in S whose preimage under "R" does not meet "S".

* Extensional if for every "x,y" in the field of "R", "x=y" if and only if "x" and "y" have the same preimage under "R".

Relations having certain combinations of the above properties have standard names. "R" is:

* An equivalence relation if and only if "R" is reflexive, symmetric, and transitive.

* A partial order if and only if "R" is reflexive, antisymmetric, and transitive.

* A linear order if and only if "R" is a partial order and for every "x,y" in the field of "R", either "xRy" or "yRx".

* A well-ordering if and only if "R" is a linear order and well-founded.

* A set picture if and only if "R" is well-founded and extensional, and the field of "R" either equals the downward closure of one of its members (called its "top element"), or is empty.


A functional relation is a binary predicate "F" such that (forall xyz.x F y wedge x F z ightarrow y=z). Such a relation (predicate) is implemented as a relation (set) exactly as described in the previous section. So the predicate "F" is implemented by the set {(x,y) mid x F y}. A set of ordered pairs "F" is a function if and only if (forall xyz.(x,y) in F wedge (x,z) in F ightarrow y=z). We define "F(x)" as the unique object "y" such that "xFy" (if there is one) or as the unique object "y" such that ("x,y") ∈ "F". The presence in both theories of functional predicates which are not sets makes it useful to allow the notation "F(x)" both for sets "F" and for important functional predicates. As long as one does not quantify over functions in the latter sense, all such uses are in principle eliminable.

In NFU, "x" has the same type as "F"("x"), and "F" is three types higher than "F"("x") (one type higher, if a type-level ordered pair is used). For any set "A", we define F [A] as {y mid (exists x.x in A wedge y=F(x))}, more conveniently written as {F(x) mid x in A}. If "A" is a set and "F" is any functional relation, "Replacement" assures that F [A] is a set in ZFC. In NFU, F [A] and "A" have the same type, and "F" is two types higher than F [A] (the same type, if a type-level ordered pair is used).

The function "I"("x") = "x" is not a set in ZFC because it is "too large". "I"("x") is however, a set in NFU. The function (predicate) S(x) = {x} is not a function (set) in either theory; in ZFC because it is too large; in NFU because its definition is unstratified. Moreover, "S"("x") can be proved not to exist in NFU: see the resolution of Cantor's paradox in New Foundations.

Operations on functions

Let "f" and "g" be arbitrary functions. The composition of "f" and "g", g circ f, is defined as the relative product f | g, if this results in a function: g circ f is a function, with (g circ f)(x) = g(f(x)), if the range of "f" is a subset of the domain of "g". The inverse of "f", "f"-1, is defined as the converse of "f" (if this is a function). Given any set "A", the identity function i_A is the set {(x,x)mid x in A}: this is a set in both ZFC and NF, but for different reasons.

Special kinds of function

A function is an injection and one-to-one if it has an inverse.

If "f" is a function from set "A" to set "B", "f" is a:
* Injection if the domain of "f" is "A" and the range of "f" is a subset of "B". In other words, the images under "f" of distinct members of "A" are distinct members of "B".
* Surjection if "f" has domain "A" and range "B".
* Bijection if "f" is both an injection and a surjection.

This terminology adjusts for the fact that a function, as defined above, does not determine its codomain.

Size of sets

In both ZFC and NFU, we say that two sets "A" and "B" are the same size (or are equinumerous) if and only if there is a bijection "f" from "A" to "B". We can write this |A|=|B| as long as we note thatfor the moment this expresses a relation between "A" and "B" rather than a relationbetween objects |A| and |B| which have not yet been defined.We also provide notation A sim B for this relation to be used in contexts such as the actual definition of the cardinals where even the appearance of presupposing abstract cardinals should be avoided.

Similarly, we can define |A| leq |B| as holding if and only if there is an injection from "A" to "B".

It is straightforward to show that the relation of equinumerousness is an equivalencerelation: equinumerousness of "A" with "A" is witnessed by i_A; if "f" witnesses|A|=|B|, then f^{-1} witnesses |B|=|A|; if "f" witnesses|A|=|B| and "g" witnesses |B|=|C|, then gcirc f witnesses |A|=|C|.

We can show that |A| leq |B| is a linear order -- on abstract cardinals, but not on sets. Reflexivity is obviousand transitivity is proven just as for equinumerousness. The Schroder-Bernstein theorem, provable in either ZFC or NFU in an entirely standard way, establishes that
*|A| leq |B| wedge |B| leq |A| ightarrow |A| = |B| (this establishes thatwe have antisymmetry on cardinals (not yet defined), but we are now considering a relation on sets), and
*|A| leq |B| vee |B| leq |A| follows in a standard way in either theory from the Axiom of Choice.

Finite sets and natural numbers

Natural numbers can be considered either as finite ordinals or finite cardinals. Herewe consider them as finite cardinal numbers. This is the first place where a major difference between the implementations in ZFC and NFU becomes evident.

The Axiom of Infinity of ZFC tells us that there is a set "A" which contains emptyset and contains y cup {y} for each y in A. This set "A" is not uniquely determined (it can be made larger while preserving this closure property): the set "N" of natural numbers is
*{x in A mid (forall B.(emptyset in B wedge (forall y.y in B ightarrow y cup {y} in B) ightarrow x in B)}which is the intersection of all sets which contain the empty set and are closed under the "successor" operation y mapsto y cup {y}.

In ZFC, we say that a set A is finite if and only if there is n in N such that |n|=|A|: further, we define |A| as this "n" for finite "A". (It can be proved that no two distinct natural numbers are the same size).

The usual operations of arithmetic can be defined recursively and in a style very similar to that in which the set of natural numbers itself is defined. For example, + (the addition operation on natural numbers) can be defined as the smallest set which contains ((emptyset,emptyset),emptyset) and contains ((x,y cup {y}),z cup {z}) whenever it contains ((x,y),z).

In NFU, it is not obvious that this approach can be used, since the successor operation y cup {y} is unstratified and so the set "N" as defined above cannot be shown to exist in NFU (it is interesting to note that it is consistent for the set of finite von Neumann ordinals to exist in NFU, but this strengthens the theory, as the existence of this set implies the Axiom of Counting (for which see below or the New Foundations article)).

The standard definition of the natural numbers, which is actually the oldest set-theoretic definition of natural numbers, is as equivalence classes of finite sets under equinumerousness. We here present the definition of "N" appropriate to NFU in exactly this way (this is not the usual way to do it, but the results are the same): define "Fin", the set of finite sets,as
*{A mid (forall F.(emptyset in F wedge (forall xy.x in F ightarrow x cup {y} in F)) ightarrow A in F)}For any set A in Fin, define |A| as {B mid A sim B}.Define "N" as the set is undefined. In ZFC one defines |B|^ whenever it contains |A|, and which is closed undersuprema of sets of cardinals.

Now we introduce a convention for ordinal indexing of any well-ordering W: W_{alpha} is defined as the element "x" of the field of W such thatthe order type of the restriction of W to {y mid y W x} is alpha; we then define eth_{alpha} as the element with index alpha in the natural order on the elements of eth. The cardinal aleph_{alpha} is theelement with index alpha in the natural order on all infinite cardinals (which we have seen above to be a well-ordering): note that aleph_0 = |N| follows immediately from this definition. In all these constructions, notice that the type of theindex alpha is two higher (with type-level ordered pair) than the type of W_{alpha}.

Now we indicate how the cumulative hierarchy itself (as a mathematical structure) can be studied in NFU. Each set "A" of ZFC has a transitive closure TC(A) (the intersection of all transitive sets which contains "A"). By the axiom of foundation, the restriction of the membership relation to the transitive closure of "A" is a well-founded relation. The relation in lceil TC(A) is either empty or has"A" as its top element, so this relation is what we called a "set picture" above. It can be proved in ZFC that every set picture is isomorphic to some in lceil TC(A).

This suggests that we can study (an initial segment of) the cumulative hierarchy by considering the isomorphism classes of set pictures. These isomorphism classes are sets and make up a set in NFU. There is a natural set relation analogous to membership on isomorphism classes of set pictures: if x is a set picture, we write [x] for its isomorphism class, and we define [x] E [y] as holding if [x] is the isomorphism class of the restriction of "y" to the downward closure of one of the elements of the preimage under "y" of the top element of "y". The relation E is a set relation, and it is straightforward to prove that it is well-founded and extensional. If the definition of E is found confusing, it can be deduced from the observation that it is induced by precisely the relationship which holds between the set pictureassociated with "A" and the set picture associated with "B" when A in B in the usual set theory.

There is a T operation on isomorphism classes of set pictures analogous to the T operation on ordinals: if "x" is a set picture, so is x^{iota} = {({a},{b})mid (a,b) in x}, and we define T( [x] ) as [x^{iota}] . It is easy to seethat [x] E [y] leftrightarrow T( [x] )=T( [y] ).

Because E is extensional, we have an axiom of extensionality for this simulated set theory.Because E is well-founded, we have an axiom of foundation. There remains the question of what comprehension axiom we may have for E. Consider any collection of set pictures {x^{iota}mid x in S} (collection of set pictures whose fields are made up entirely of singletons). Sinceeach x^{iota} is one type higher than x and we have a type level ordered pair, wecan replace each element {a} of the field of each x^{iota} in the collection with (x,{a}), obtaining a collection of set pictures isomorphicto the original collection but with their fields disjoint. We can take the union of these setpictures and add a new top element to obtain a set picture whose isomorphism type will have asits preimages under E exactly the elements of the original collection. That is, for any collection of isomorphism types [x^{iota}] = T( [x] ), there is an isomorphism type [y] whose preimage under E is exactly this collection.

In particular, there will be an isomorphism type " [v] " whose preimage under E is the collection of"all" "T [x] "'s (including "T [v] "). Since "T [v] E v" and E is well-founded, we have T [v] eq v. Thisresembles the resolution of the Burali-Forti paradox discussed above and in the New Foundationsarticle, and is in fact the local resolution of Mirimanoff's paradox of the set of all well-founded sets.

There are ranks of isomorphism classes of set pictures just as there are ranksof sets in the usual set theory. For any collection of set pictures "A", define "S(A)" as the set of all isomorphism classes of set pictures whose preimage under E is a subset of A; call A a "complete" set if every subset of "A" is a preimage under E. The collection of "ranks" is thesmallest collection containing the empty set and closed under the S operation (which is a kind of power set construction) and underunions of its subcollections. It is straightforward to prove (much as in the usual set theory)that the ranks are well-ordered by inclusion, and so the ranks have an index in this well-order: we refer to the rank with index alpha as R_{alpha}. It is provablethat |R_{alpha}|=eth_{alpha} for complete ranks R_{alpha}.The union of the complete ranks (which will be the first incomplete rank) with the relation E lookslike an initial segment of the universe of Zermelo-style set theory (not necessarily like the full universe of ZFC because it may not be large enough). It is provable that if R_{alpha} is the firstincomplete rank, then R_{T(alpha)} is a complete rank and thus T(alpha). So we have a "rank of the cumulative hierarchy" with an "external automorphism" T moving the rank downward: this is exactly the condition on a nonstandard model of a rank in the cumulative hierarchy under which we construct a model of NFU in the New Foundations article. There are technical details to verify, but there is an interpretationnot only of a fragment of ZFC but of NFU itself in this structure, with [x] in_{NFU} [y] defined as T( [x] ) E [y] wedge [y] in R_{T(alpha)+1}:this "relation" E_{NFU} is not a set relation but has the same type displacementbetween its arguments as the usual membership relation in.

So there is a natural construction inside NFU of the cumulative hierarchy of sets (as much of it as we can see) which internalizes the natural construction of a model of NFU in Zermelo-style set theory.

Under the Axiom of Cantorian Sets described in the New Foundations article, the strongly cantorian part of the set of isomorphism classes of set pictures with the E relation as membershipbecomes a (proper class) model of ZFC (in which there are n-Mahlo cardinals for each n; thisextension of NFU is strictly stronger than ZFC). This is a proper class model because the strongly cantorian isomorphism classes do not make up a set.

Permutation methods can be used to create from any model of NFU a model in which every strongly cantorian isomorphism type of set pictures is actually realized as the restriction of the true membership relation to the transitive closure of a set.

See also

*New Foundations
*Set-theoretic definition of natural numbers
*Axiomatic set theory


*Keith Devlin, 1994. "The Joy of Sets", 2nd ed. Springer-Verlag.
*Holmes, Randall, 1998. " [ Elementary Set Theory with a Universal Set] ". Academia-Bruylant. The publisher has graciously consented to permit diffusion of this introduction to NFU via the web. Copyright is reserved.
*Potter, Michael, 2004. "Set Theory and its Philosophy", 2nd ed. Oxford Univ. Press.
*Suppes, Patrick, 1972. "Axiomatic Set Theory". Dover.
*Tourlakis, George, 2003. "Lectures in Logic and Set Theory, Vol. 2". Cambridge Univ. Press.

External links

* [ Metamath:] A web site devoted to an ongoing derivation of mathematics from the axioms of ZFC and first-order logic. "Principia Mathematica" done right.
* Stanford Encyclopedia of Philosophy:
** [ Quine's New Foundations] -- by Thomas Forster.
** [ Alternative axiomatic set theories] -- by Randall Holmes.
* Randall Holmes: [ New Foundations Home Page.]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Theory of multiple intelligences — Human intelligence Abilities and Traits Abstract thought Communication · Creativity Emotional Intelligence Kn …   Wikipedia

  • List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… …   Wikipedia

  • Music and mathematics — and in 2009 when fabeso donwizzle entered chaney high he would have changes the awesomeness of the school forever! A spectrogram of a violin waveform, with linear frequency on the vertical axis and time on the horizontal axis. The bright lines… …   Wikipedia

  • Programming language theory — (commonly known as PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of programming languages and programming language features. It is a multi disciplinary field, both… …   Wikipedia

  • Type theory — In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general. In programming language theory, a branch of computer science …   Wikipedia

  • Dedicated Portfolio Theory — Dedicated Portfolio Theory, in finance, deals with the characteristics and features of a portfolio built to generate a predictable stream of future cash inflows. This is achieved by purchasing bonds and/or other fixed income securities (such as… …   Wikipedia

  • Constructivism (learning theory) — Jean Piaget: founder of Constructivism Constructivism is a theory of knowledge (epistemology)[1] that argues that humans generate knowledge and meaning from an interaction between their experiences and their ideas. During infancy, it was an… …   Wikipedia

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

  • Wikipedia:Manual of Style/Mathematics — This guideline is a part of the English Wikipedia s Manual of Style. Use common sense in applying it; it will have occasional exceptions. Please ensure that any edits to this page reflect consensus. Shortcuts: WP:MSM MO …   Wikipedia

  • Dominator (graph theory) — For Dominating set problem, see Dominating set. In computer science, in control flow graphs, a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n (or sometimes d n). By… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.