Cavagnaro, Haight - Dictionary of Classical and Theoretical Mathematics (523108), страница 32
Текст из файла (страница 32)
In mathematics, reductio ad absurdum means proof by contradiction. In a proof by contradiction, one assumesthe hypotheses of the statement to be proved,as well as the negation of the statement to beproved. The proof is complete when a contradiction (i.e., a situation where both a statementA and its negation ¬A are true) is encountered,and one then concludes the statement which wasto be proved.reduction of a languageLet L1 and L2 befirst order languages. The language L1 is a reduction of L2 if L1 ⊆ L2 ; i.e., if L2 is an expansion of L1 .
See expansion of a language.reduct of a structure Let L1 and L2 be firstorder languages such that L1 is a reduction ofL2 . Let A be a structure for L2 . The reduct ofA to L1 is the structure obtained from A whichgives only the interpretations of the predicate,constant, and function symbols in L1 (all interpretations of the additional symbols in L2 arediscarded).
See expansion of a structure.Reeb foliation A Reeb foliation of the sphereS 3 is a codimension-one foliation in which oneleaf is a torus S 1 × S 1 , dividing the sphere intotwo solid tori, and each remaining leaf diffeomorphic to the plane R2 . Thus, the sphere isrepresented as a union of surfaces, only one ofwhich is compact, such that at each point thereis a local coordinate system in which each plane{z = constant} is contained in a single surface.Reeb Stability Theorem Let M be a smoothmanifold with a codimension-one foliation inwhich one of the leaves is diffeomorphic to thesphere S 2 .
Then all leaves of the foliation mustbe spheres or projective planes and the manifoldM must be S 2 × S 1 or the connected sum of twocopies of real projective space RP3 .refinement of a coverGiven a cover {Aα }of a topological space X (that is, X ⊂ ∪Aα ),relative computabilitya second cover {Bβ } is a refinement of {Aα } ifeach Bβ is contained in some Aα .reflexive relationA binary relation R onsome set S such that (x, x) ∈ R, for every x ∈ S.For example, ≤ on Z, the usual order relation onthe set of integers, is a reflexive relation.regular cardinalA cardinal κ such that thecofinality of κ is κ. Thus, κ is regular if, for anyincreasing sequence of ordinals γα < κ whoselength is less than κ, sup γα is also less than κ.For example, any successor cardinal is regular(assuming the axiom of choice), whereas ℵω isnot.regular coveringA concept arising in thetheory of covering spaces.
Assume that B is anarcwise connected, locally arcwise connectedspace. A continuous function π : E −→ Bis a covering map if each point in B has anarcwise connected neighborhood U such thateach component of π −1 (U ) is open in E andis mapped homeomorphically onto U by π . Ifγ : [0, 1] −→ B is a curve, and if π(e) = γ (0),then there is a unique curve γ : [0, 1] −→ Ewith γ (0) = e and π(γ (t)) = γ (t).
γ iscalled a lift of γ . The covering is regular ifwhenever γ is a closed curve in B, then eitherevery lift of γ to a curve in E is closed or no liftof γ is closed. For a regular covering, the covering transformations are in 1-1 correspondencewith π −1 (b), for b any point in B.regularly homotopic immersionsAn immersion is a differentiable map f : M −→ N ,whose derivative df (m) is nonsingular at everypoint p. It is locally an embedding, but it neednot be globally 1-1. Two such immersions, f0and f1 , are regularly homotopic if there is a differentiable map H : M × [0, 1] −→ N withH (m, 0) = f0 (m) and H (m, 1) = f1 (m) forall m in M, such that if ft is defined by ft (m) =H (m, t), then ft is an immersion for each t in[0, 1].
Thus, the immersion f0 can be continuously deformed through immersions to f1 insuch a way that tangent vectors to M vary continuously through the deformation. This rulesout untying a knot by pulling it tight.© 2001 by CRC Press LLCregular neighborhood A regular neighborhood N of a subcomplex L in a simplicial complex K is a neighborhood of L that is formedfrom the simplices of the second derived subdivision of K.If {σ } is the collection of simplices of thesecond derived subdivision of K, then the regular neighborhood of L, denoted N (L) is thecollection of simplexesN (L) = {σ : σ ∩ L = ∅} .regular polygon A (convex) polygon whosesides have equal length, in which case the vertices lie on a circle.
The n vertices of aregular n-gon can be taken to be the points(cos 2πn i , sin 2πn i ), i = 0, . . . , n.regular polyhedron A (convex) polyhedronall of whose faces are congruent and all of whosevertices belong to the same number of faces.There exist only five types, the Platonic solids:tetrahedron, hexahedron, octahedron, dodecahedron, icosahedron (resp. 4,6,8,12,20 faces).regular topological spaceA topologicalspace X in which one-point sets are closed and,given any closed subset A of X and a point x ∈ Xnot in A, there exist disjoint open subsets U andV of X such that A ⊂ U and x ∈ V .relation (1) n-ary relation.
A set of n-tuples.(2) Binary relation. A set of ordered pairs.(3) Ternary relation. A set of ordered triples.(4) Binary relation on a set. If S is an arbitraryset, R is a binary relation on S if R is a subset ofS × S. For example, the relation “m divides n”is a binary relation on the set of natural numbers,since it is the set {(m, n) : m divides n} whichis a subset of N × N.relative complement of a set (with respect toanother set)The relative complement of aset S, with respect to a set U , denoted by U \Sor U − S, is the set of elements that are in U butnot in S. For example, the relative complementof the set of even integers with respect to Z isthe set of odd integers.relative computabilityLet N be the set ofnatural numbers, ϕ be a (possibly partial) func-relative computabilitytion on N and f be a total function on N.
(Afunction is partial if its domain is some subset ofN; a function is total if its domain is all of N.) Intuitively, the function ϕ is computable relative tof if there is an algorithm, or effective procedure,which, given n ∈ N as input, produces ϕ(n) asoutput, in finitely many steps, if n ∈ dom(ϕ),where the algorithm is allowed to make finitelymany queries about values f (y1 ), .
. . , f (yk ) off . Similarly, a set A of natural numbers is computable relative to a set B of natural numbers ifthere is some algorithm which, given n ∈ N asinput, outputs “yes” if n ∈ A or “no” if n ∈ Aafter finitely many steps, where the algorithmis allowed to make finitely many queries aboutmembership y1 ∈ B?, . . . , yk ∈ B? in B.To formalize the notion of relative computability with a mathematical definition, one relativizesone of the formal definitions of computability(see computable, partial recursive function).
Forexample, let ϕ be a partial function on N and letA be a set of natural numbers. The function ϕ ispartial recursive in A (or partial recursive, relative to A) if it can be derived from the initialfunctions, together with χA (the characteristicfunction of A), by finitely many applications ofcomposition, recursion, or the µ-operator. Aset B of natural numbers is recursive in A if itscharacteristic function χB is partial recursive inA.
See partial recursive function. Similarly, thefunction ϕ is Turing computable in A (or Turingreducible to A, or Turing computable, relativeto A) if there is some oracle Turing machinewhich computes it, using an oracle for A. A setB is Turing computable in A if its characteristicfunction χB is Turing computable in A.An oracle Turing machine is a Turing machine with a bi-infinite, read-only oracle tape,which is separate from its work tape (where theinput is originally written), on which is writtenthe characteristic function χA of A; i.e., the tapelooks like.
. . B n0 n1 n2 . . . ,where for all i ≥ 0, ni = 1 if i ∈ A, ni = 0 ifi ∈ A, and . . . B indicates that all cells to the leftof the value of χA (0) are blank. The operation ofthe Turing machine is the same, except that thetransition function is modified to account for thecharacter being scanned on the oracle tape. In© 2001 by CRC Press LLCother words, if Q is the set of machine states, S isthe work tape alphabet, and O = {B, 0, 1} is theoracle tape alphabet, then the transition functionδ has domain some subset of Q × S × O andrange contained in Q × S × {R, L}, and whereδ(q, a, b) = (q̂, â, m) means that if the machineis in state q, scanning symbol a on its work tapeand b on its oracle tape, then it replaces a by â onits work tape, moves the read head on both tapesone cell to the left or right, depending on thevalue of m, and goes into state q̂. Computationof a partial function is the same as for a nonoracle Turing machine; at the beginning of thecomputation, the read head on the oracle tape ispositioned on the cell giving the value of χA (0).See computable for a description of a Turingmachine.By a relativized version of the Church-TuringThesis, all formalizations of relative computability capture the intuitive notion of relative computability, and so the phrase ϕ is computable,relative to A (or ϕ is recursive in A, or ϕ is Acomputable, or ϕ is A-recursive) means that ϕis computable relative to A in any such formalization.
The notation ϕ ≤T A means that ϕ iscomputable, relative to A. The relation ≤T iscalled Turing reducibility.As an example, note that for any set of natural numbers A, its complement A in N is computable, relative to A. In addition, any recursively enumerable (computably enumerable) setB is computable relative to the halting set K ={e : ϕe (e) is defined}, where ϕe denotes the partial recursive function with Gödel number e.relative homology groupGiven a topological space X and a subspace A, the nthrelative singular homology group Hn (X, A) isthe nth homology group of the chain complex{Sq (X)/Sq (A)} obtained by taking the groupSq (X) of chains on X modulo the group Sq (A)of chains on the subspace A. If X is a simplicial(or cellular complex) and A is a subcomplex,the nth simplicial (or cellular) relative homology group Hn (X, A) is just the ordinary homology of the complex X/A with the subcomplexA identified to a point.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
