Cavagnaro, Haight - Dictionary of Classical and Theoretical Mathematics (523108), страница 31
Текст из файла (страница 31)
. ].Note that only one quantifier suffices, since(∀x)[. . . ] is logically equivalent to ¬(∃x)¬[. . . ].A typical use of quantifiers occurs among theaxioms for group theory. Given a set G with abinary operation · on G (i.e., a function fromG × G to G),(∃e)(∀x)[x · e = e · x = x]is the axiom that states that there is an elementof G that functions as an identity, while(∀x)(∃x ∗ )[x · x ∗ = x ∗ · x = e]is the axiom that states that every element of Ghas an inverse in G.
Here, the quantifiers rangeover the universe (group) G.Also note that order of quantifiers is essential.The statement (∀x)(∃y)[. . . ] does not necessarily have the same meaning as (∃y)(∀x)[. . . ]. Inthe first statement, the y that exists may dependon the choice of x, while in the second statement,the y that exists does not depend on x.of X with x ∈ U, y ∈ V , and X = U ∪ V . Thequasicomponent of x in X is the equivalenceclass of x under this equivalence relation.quotient categoryIf C is a category and ∼is a congruence relation on C, the quotient category of C with respect to ∼ is the category C whose objects are the objects of C and whosemorphisms are the equivalence classes of morphisms of C (with respect to ∼); morphism composition ◦ in C is given by f1 ◦ f2 = f1 ◦ f2 ,where fi is the equivalence class of fi with respect to ∼.quotient map A surjective function p : X →Y between topological spaces such that a subsetU is open in Y if and only if p−1 (U ) is open inX.If ∼ is an equivalence relation on X, then themap q : X → X/ ∼, sending points of X to theirequivalence classes, is sometimes referred to asa quotient map.
This agrees with the presentdefinition for the equivalence relation given byx ∼ y if and only if p(x) = p(y).quotient objectIf A is an object of a category C, a quotient object A is an ordered pair(f, A ), where A is an object of C and f is anepimorphism f : A → A . For example, in thecategory of groups and group homomorphisms,a quotient object of the additive group Z is thepair (f, Z2 ), where f is the group homomorphism that sends even integers to 0 and odd integers to 1. The dual notion of a quotient objectis the notion of a subobject.
See subobject.quotient set A set that is a partition of someother set. In practice, a quotient set is obtainedas the collection of equivalence classes of anequivalence relation on some set. For example,the setquantifier elimination Let L be a first orderlanguage. A theory T of L admits quantifierelimination if, for every well-formed formula ϕof L, there is a quantifier-free formula ψ of Lsuch that (ϕ ↔ ψ) is a theorem of T (T (ϕ ↔ψ)).is a quotient set since it is a partition of Z. Theequivalence relation on Z that gives rise to thisquotient set is: a ∼ b if and only if a − b iseven.quasicomponentGiven a topological spaceX, define an equivalence relation ∼ on X bysetting x ∼ y if there are no open sets U and Vquotient space Let X be a topological spaceand ∼ an equivalence relation on X. Let X∗ bethe set of distinct equivalence classes [x] of X.© 2001 by CRC Press LLC{{all even integers}, {all odd integers}}quotient spaceDefine p : X → X∗ by p(x) = [x] and givethe set X ∗ the quotient topology correspondingto the surjective map p.
See quotient topology.Then X ∗ is called a quotient space of X. Noticethat equivalent points of X are identified to asingle point in X ∗ . This construction thus gives atopological method for factoring out subspacesof a space X analogous to the quotient groupconstruction in group theory.© 2001 by CRC Press LLCquotient topologyGiven a surjective function p : X → Y where X is a topological spaceand Y is a set, the quotient topology on Y induced by p is the topology that makes p a quotient map. (See quotient map.) That is, a subsetU of Y is defined to be an open set of Y if andonly if p−1 (U ) is an open subset of the topological space X.recursionRradicalSee root of a number.radius of regular polygon The radius of theunique circle passing through all the vertices ofa regular polygon.radius of regular polyhedron The radius ofthe unique sphere passing through all the vertices of a regular polyhedron.radix A synonym for base.
See base of number system. For example, the decimal expansionof a real number is also known as its base 10 expansion or its expansion to the radix 10.range(1) Range of a function. The set ofall values attained by a function. The range ofa function f is often denoted by ran(f ).
Thus,if f : A → B is a function, ran(f ) = {y ∈B : (∃x ∈ A) f (x) = y}. For example, iff : R → R is the function given by f (x) = x 2 ,the range of f is [0, ∞). Compare with image.(2) Range of a variable. The set of all valuesa given variable can attain.(3) Range of a binary relation. If R is a binary relation, the range of R, often denoted byran(R), is the set {x : (∃y) (x, y) ∈ R}.rankThe rank of a set x is the least ordinalα such that x ∈ Vα+1 . In particular, for anyordinal α, rank(α) = α.The same notion can be defined using recursion:rank(x) = sup{rank(y) + 1 : y ∈ x} ,assuming sup{∅} = 0.rational function A function that is expressible as a quotient of polynomials.rational numberA real number that can beexpressed as a quotient of integers.
Furthermore, the digits of the decimal expansion of areal number will consist of a sequence which,© 2001 by CRC Press LLCeventually, repeats periodically if and only if thenumber is a rational number. The set of all rational numbers is normally denoted Q or Q.real analytic fiber bundleA fiber bundlesuch that the base space B is a real analytic manifold, the group G is a Lie group, and the coordinate transformations gij : Ui ∩ Uj −→ G arereal analytic maps. See fiber bundle.realizesA model A of a theory T realizes atype if there is a set of elements in A whichsatisfies every formula in .
More precisely, Arealizes (x̄), where x̄ = {x1 , . . . , xn } containsall free variables occurring in the formulas in ,if and only if there is an n-tuple ā of elements ofA such that A |= φ(ā) for every φ(x̄) in (x̄).real numberA number that has an infinitedecimal representation, which may or may notterminate or repeat. If the decimal representation repeats or terminates, the real number is arational number; otherwise it is irrational.The set of real numbers (usually denoted Ror R) can be constructed as the completion ofthe rational numbers, in the sense that every realnumber is the limit of an infinite sequence of(not necessarily distinct) rational numbers.reciprocal If r is a nonzero real number, thenits reciprocal is the number 1r .
For example, the√reciprocal of 23 is 23 and the reciprocal of 2 is√12=√22 .recursion Let f be an n-ary function (n ≥ 1),g be an (n − 1)-ary function, h be an (n + 1)ary function, and y denote the (n − 1)-tupley1 , . . . , yn−1 (all functions are functions on thenatural numbers).
The function f is obtainedfrom g and h by recursion if, for all natural numbers y1 , . . . , yn−1 ,f (0, y)=g(y)f (x + 1, y)=h(x, f (x, y), y).The function f (x, y) = x + y can be defined by recursion as follows. Let S(x) be thesuccessor function; i.e., S(x) = x + 1 for all x.Informally, the recursion equations for f aref (0, y)=yf (x + 1, y)=S(f (x, y)).recursiveMore formally, f is obtained from g and hby recursion asf (0, y)f (x + 1, y)==g(y)h(x, f (x, y), y),where g is the identity function g(y) = y for ally, h(x, y, z) = S(P23 (x, y, z)), and P23 (x, y, z)= y for all x, y, z.Similarly, the factorial function p(n) = n!for all n is obtained by recursion informally as0!(n + 1)!==1(n + 1) · n!.recursiveA function f on the natural numbers which is total (i.e., the domain of f is theset of all natural numbers) and partial recursive.See partial recursive function.
By the ChurchTuring Thesis, the phrase “f is recursive” canmean f is total and computable in any formalsense. See Church-Turing Thesis, computable.A set A of natural numbers is recursive ifits characteristic function is recursive; i.e., thefunction1 if n ∈ AχA (n) =0 if n ∈ Ais recursive.The set A = {n ∈ N : n is prime} is recursive.recursively enumerableA set A of naturalnumbers which is the domain of some partial recursive function.
Equivalently, A is recursivelyenumerable if it is the empty set or it is the rangeof some (total) recursive function; i.e., if A isnon-empty, then there is a computable functionf : N → N which “lists” the elements of A. IfA is the domain of the partial recursive functionwith Gödel number e, then A is denoted by We ,the eth recursively enumerable set.For example, the halting setK = {e : ϕe (e) is defined}(the set of all numbers e such that the partialrecursive function with Gödel number e on inpute is defined) is recursively enumerable, but notrecursive. The set{e : (∀x)[ϕe (x) is defined]}© 2001 by CRC Press LLCis not recursively enumerable.The term computably enumerable (c.e.) issynonymous with recursively enumerable.reductio ad absurdum Literally, “a leadingback to the nonsensical”.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
