Cavagnaro, Haight - Dictionary of Classical and Theoretical Mathematics (523108), страница 28
Текст из файла (страница 28)
. , xn ) = i, for all natural numbers i, n ≥ 0 (the constant functions)• Pin (x1 , . . . , xn ) = xi , for all natural numbers n ≥ 1 and 1 ≤ i ≤ n (the projectionfunctions).Let g1 , . . . , gk , f be n–ary functions and leth be a k-ary function; let x denote an n–tuplex1 , . . . , xn .
The function f is obtained fromg1 , . . . , gk and h by composition if for all natural numbers x1 , . . . , xn , f (x) = h(g1 (x), . . . ,gk (x)).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)-tuple y1 , . . . , yn−1 . Thefunction f is obtained from g and h by recursionif for all natural numbers x, y1 , .
. . , yn−1 ,f (0, y)f (x + 1, y)=g(y)=h(x, f (x, y), y).Let f be an n-ary function and let g be an(n + 1)-ary (possibly partial) function. Let xdenote an n-tuple x1 , . . . , xn , and let µ be the© 2001 by CRC Press LLCleast number operator; i.e., (µx)[· · · ] denotesthe least natural number x satisfying property[· · · ]. Let ↓ be an abbreviation of the phrase “isdefined”. If for all natural numbers x1 , . . . , xn ,f (x)==(µy)[g(x, y)0 ∧ (∀z < y)[g(x, z) ↓]] ,then f is obtained from g by the µ-operator.If an n-ary function is partial recursive andtotal (i.e., the domain of the function is all ofNn ), then the function is called recursive (or totalrecursive).Any primitive recursive function (see primitive recursive function) is recursive; for example, the function f (x1 , x2 ) = x1 + x2 is recursive.
However, it is not the case that every (total) recursive function is primitive recursive. Anexample of a recursive function that is not primitive recursive is Ackermann’s function, whichis defined informally by “double recursion”, asfollows.A(0, y)A(x + 1, 0)A(x + 1, y + 1)===S(y)A(x, 1)A(x, A(x + 1, y)).Ackermann’s function grows faster than any primitive recursive function.By the Church-Turing Thesis, any intuitivelycomputable partial function (see Church-TuringThesis, computable) is partial recursive. Thefunction1 if ϕe (e) is definedψ(e) =undefined if ϕe (e) is undefined,where ϕe is the partial recursive function withGödel number e, is partial recursive.partition(1) Of a set. A pairwise disjointcollection of nonempty subsets of the given set,whose union is the given set. For example,{{3, a}, {−2}} is a partition of the set {3, a, −2}.Also, {[n, n + 1) : n ∈ Z} is a partition of R(where each interval [n, n + 1) is the set of realnumbers x such that n ≤ x < n + 1). Seequotient set.(2) Of a positive integer.
If n is a positive integer, a partition of n is a sequence(k1 , k2 , . . . , kr ) of positive integers such thatpentagonal numberk1 ≥ k2 ≥ · · · ≥ kr and k1 + k2 + · · · + kr = n.For example, (4, 3) and (2, 2, 2, 1) are two partitions of 7.Pascal’s triangleA specific triangulararray of numbers, named after the 19th centuryFrench mathematician/philosopher Blaise Pascal, the first few rows of which are given below:11 11 2 11 3 3 11 4 6 4 1If the first row is labeled the “0th row” (forexample, the 4th row is 1 4 6 4 1) andcall the first entry (on the left) of each row the“0th” entry (so the 6 in the middle of the 4th rowis the 2nd entry of that row), then the kthentryof the nth row is the binomial coefficient nk .Although this array is known as Pascal’s triangle, it has been found in Chinese manuscriptsthat were printed 500 years before Pascal’s birth.pathA path from a point x to a point y in atopological space X is any continuous functionf : [0, 1] → X with f (0) = x and f (1) = y.Intuitively, the path is the image of the functionf.Peano spaceA compact, connected locallyconnected metric space.
By the famous HahnMazurkiewicz Theorem, Peano sets are preciselythose sets that occur as continuous images of theunit interval.Peano’s PostulatesA set of axioms for developing the properties (using naive set theory)of the natural numbers. The axioms were published by Peano in 1889 and were based on workby Dedekind.There are five Peano Postulates.(i.) 0 is a natural number.(ii.) For every natural number n, there is anatural number n , called the successor of n.(iii.) For every natural number n, n = 0.(iv.) For any natural numbers m and n, ifm = n , then m = n.(v.) If I is any subset of the natural numberssuch that(a.) 0 ∈ I and© 2001 by CRC Press LLC(b.)for any natural number n, ifn ∈ I , then n ∈ I ,then I contains all natural numbers.This last postulate is the Principle of Mathematical Induction and is applicable to each of theuncountably many subsets of the natural numbers.Peano’s Postulates uniquely determine theset of natural numbers in the sense that if M is aset that satisfies the five postulates above (withthe phrase “n is a natural number” replaced by“n ∈ M”), then M is the set of natural numbers.pedal triangleThe triangle within a giventriangle formed by connecting the non-vertexendpoints of the altitudes of the given triangle.Pell’s equation The equation x 2 − dy 2 = k,where x and y are unknown variables and d andk are integers.
Pell’s equation is an example ofa Diophantine equation (an equation for whichone searches for integer or rational solutions).The integer d is usually assumed to be squarefree (that is, if p is a prime divisor of d, thenp2 is not a divisor of d) and positive becauseotherwise the equation has only finitely manyinteger solutions for x and y, if any.pencil of circles The collection of all circlesin a plane passing through two given points.pencil of lines (1) The collection of all linesin a given plane which pass through a givenpoint.(2) The collection of all lines parallel to agiven line.pencil of planes The collection of all planesin space containing a given line.pencil of spheres The collection of all spherescontaining a given circle.pentadecagonpentagonA polygon having 15 sides.A polygon having five sides.pentagonal number Any positive integer of2the form 3n 2−n (i.e., any entry in the sequence,1, 5, 12, 22, 35, .
. . ).pentahedronpentahedronA polyhedron with five faces.percentFrom the Latin for “per hundred”,percentages are used as alternatives to fractionsor decimals to represent ratios of numerical values. For example, 50% (read “fifty percent”)50represents 100or .50. Thus, 35% of 250 is35.35 × 250 = 87.5 (since 100= 87.5250 ).perfect number A positive integer n havingthe property that the sum of its positive divisors is 2n, i.e., σ (n) = 2n.
Thus, 6 is a perfectnumber since 1 + 2 + 3 + 6 = 2(6). The nexttwo perfect numbers are 28 and 496. All evenperfect numbers have been characterized as being of the form 2p−1 (2p − 1), where both p and2p −1 are prime (i.e., where 2p −1 is a Mersenneprime). There are no known odd perfect numbers. See also abundant number, deficient number, Mersenne prime.perfect setA topological space X with theproperty that every point of X is an accumulation point of X.
That is, given any x ∈ X andany neighborhood U of x, the set (U ∩ X)\{x}is nonempty. All intervals on the real line areperfect. An example of a perfect subset of thereal line which is not an interval is furnished bythe Cantor set. See Cantor set.perfect square An integer a for which thereexists another integer b such that a = b2 . Forexample, 36 = 62 and 289 = 172 are perfectsquares.perigonA 360◦ angle.perimeter(1) The length of a closed curve,especially when considered as the boundary ofa plane figure.(2) The closed curve forming the boundaryof a plane figure.periodic continued fractionfractiona0 +b2a2 +a3 +b3b4a4 +© 2001 by CRC Press LLCperpendicular(1) The relative position ofa pair of lines that intersect so that they form apair of equal adjacent angles.(2) The relative positon of a line and a planesuch that the line is perpendicular to every linewith which it intersects in the plane.(3) The relative position of a pair of planesthat intersect so that a line in one is perpendicular to both the line of intersection and to a linein the other which is perpendicular to the line ofintersection.perpendicular bisectorA line or line segment that bisects a given line segment and isperpendicular to it.
See perpendicular.piA number, denoted π , equal to the ratio between the circumference and diameter ofany circle. It is also the ratio of the area of acircle to the square of its radius. It is knownthat π is a transcendental (and therefore irrational) number. The value of π is approximately3.14159265358979 and, although the value ofevery digit in the decimal expansion of π is notknown, in 1989 David and Gregory Chudnovskycalculated π to 1,011,196,691 decimal place accuracy.point at infinityA point of the hyperplaneat infinity.
See hyperplane at infinity.polar coordinatesTwo numbers (r, θ ) thatdetermine a point P in the (x, y)-plane, r beingthe distance from the origin O and 0 ≤ θ < 2πthe angle that the ray OP makes with the positive x-axis, measured in radians and counterclockwise, except if P = O, which is associated to the number zero only; thus x = r cos θ ,y = r sin θ. If r is allowed to be negative,the pair (−r, θ ) gives the same point as the pair(r, θ + π ).A continuedb1a1 +for which there exist positive integers p and Nso that for all k ≥ N , ak+p = ak and bk+p = bk ....Polish spaceA topological space X that isseparable and completely metrizable.
That is, Xhas a countable dense subset, and there is a metric d inducing the topology on X for which everyCauchy sequence converges. Polish spaces arethe natural setting for descriptive set theory. Ex-predicate calculusamples of Polish spaces include R, Rn , C, Cn ,the Cantor space 2N , and the Baire space NN .Pollard rho method A method for factoringan integer which is known to be composite (using one of the pseudoprime tests, for example).The method is based in part on the fact that,although it is difficult to find factors to largenumbers, it is relatively easy (using Euclid’s algorithm) to find the greatest common divisor oftwo integers.Let m be a positive composite integer anddefine the sequence {ui } recursively as follows:(i.) u0 = 1;(ii.) ui+1 is the unique integer so that ui+1 ≡u2i + 1(modm) and 0 ≤ ui+1 < m.(In general, u0 could be any positive integer andui+1 = f (ui ) for some nonlinear polynomial,f ).
Next, compute Dn = gcd(u2n − un , m) forn = 1, 2, 3, . . . If Dn = 1 for any n, then Dn isa divisor of m.To illustrate the method, let m = 1771. Thenthe first few terms of the sequence (starting withu1 ) defined by u0 = 1 and ui+1 ≡ u2i +1(modm)are 2, 5, 26, 677, 1412, . . . Notice that gcd(u2 −u1 , 1771) = gcd(3, 1771) = 1, and gcd(u4 −u2 , 1771) = gcd(672, 1771) = 7, so 7 is a divisor of 1771 (as is 1771 ÷ 7 = 253). Since 7is prime and 253 is composite, we could repeatPollard’s method to show that 253 is the product of the primes 11 and 23, thus completing thefactorization of 1771.The Pollard rho method was introduced byJ. M.
Pollard in 1975.polygonal numberA positive integer n sothat n dots can be arranged in a specified polygonal pattern. Also called a figurate number. Seealso triangular number, pentagonal number.polynomial A finite sum of multiples of nonnegative integer powers of an indeterminate x,with coefficients in a given set R. For example,3x 5 − 4x 3 + x 2 + 7x − 12 is a polynomial withcoefficients in Z.posetSee partially ordered set.positive numberthan 0.A real number that is greater© 2001 by CRC Press LLCpositive orthantThe set of points (x1 , x2 ,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
