Search

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

A model of set theory ZFC is defined in our recent research, in which, for a given n ≥ 3 , (A n) there exists a good lightface Δ n 1 well-ordering of the reals, but (B n) no well-orderings of the reals (not necessarily good) exist in the previous class Δ n − 1 1 . Therefore, the conjunction (A n) ∧ (B n) is consistent, modulo the consistency of ZFC itself. In this paper, we significantly clarify and strengthen this result. We prove the consistency of the conjunction (A n) ∧ (B n) for any given n ≥ 3 on the basis of the consistency of PA 2 , second-order Peano arithmetic, which is a much weaker assumption than the consistency of ZFC used in the earlier result. This is a new result that may lead to further progress in studies of the projective hierarchy. [ABSTRACT FROM AUTHOR]

The paper solves the problem of constructing an evolutionary tree and the evolution of structures along it. This problem has long been posed and extensively researched; it is formulated and discussed below. As a result, we construct an exact cubic-time algorithm which outputs a tree with the minimum cost of embedding into it and of embedding it into a given network (Theorem 1). We construct an algorithm that outputs a minimum embedding of a tree into a network, taking into account incomplete linear sorting; the algorithm depends linearly on the number of nodes in the network and is exact if the sorting cost is not less than the sum of the duplication cost and the loss cost (Theorem 3). We construct an exact approximately quadratic-time algorithm which, for arbitrary costs of SCJ operations, solves the problem of reconstruction of given structures on any two-star tree (Theorem 4). We construct an exact algorithm which reduced the problem of DCJ reconstruction of given structures on any star to a logarithmic-length sequence of SAT problems, each of them being of approximately quadratic size (Theorem 5). The theorems have rigorous and complete proofs of correctness and complexity of the algorithms, and are accompanied by numerical examples and numerous explanatory illustrations, including flowcharts. [ABSTRACT FROM AUTHOR]

We make use of generalized iterations of the Sacks forcing to define cardinal-preserving generic extensions of the constructible universe L in which the axioms of ZF hold and in addition either (1) the parameter-free countable axiom of choice AC ω * fails, or (2) AC ω * holds but the full countable axiom of choice AC ω fails in the domain of reals. In another generic extension of L, we define a set X ⊆ P (ω) , which is a model of the parameter-free part PA 2 * of the 2nd order Peano arithmetic PA 2 , in which CA (Σ 2 1) (Comprehension for Σ 2 1 formulas with parameters) holds, yet an instance of Comprehension CA for a more complex formula fails. Treating the iterated Sacks forcing as a class forcing over L ω 1 , we infer the following consistency results as corollaries. If the 2nd order Peano arithmetic PA 2 is formally consistent then so are the theories: (1) PA 2 + ¬ AC ω * , (2) PA 2 + AC ω * + ¬ AC ω , (3) PA 2 * + CA (Σ 2 1) + ¬ CA . [ABSTRACT FROM AUTHOR]

The notion of ordinal definability and the related notions of ordinal definable sets (class OD) and hereditarily ordinal definable sets (class HOD) belong to the key concepts of modern set theory. Recent studies have discovered more general types of sets, still based on the notion of ordinal definability, but in a more blurry way. In particular, Tzouvaras has recently introduced the notion of sets nontypical in the Russell sense, so that a set x is nontypical if it belongs to a countable ordinal definable set. Tzouvaras demonstrated that the class HNT of all hereditarily nontypical sets satisfies all axioms of ZF and satisfies HOD ⊆ HNT . In view of this, Tzouvaras proposed a problem—to find out whether the class HNT can be separated from HOD by the strict inclusion HOD ⫋ HNT , and whether it can also be separated from the universe V of all sets by the strict inclusion HNT ⫋ V , in suitable set theoretic models. Solving this problem, a generic extension L [ a , x ] of the Gödel-constructible universe L , by two reals a , x , is presented in this paper, in which the relation L = HOD ⫋ L [ a ] = HNT ⫋ L [ a , x ] = V is fulfilled, so that HNT is a model of ZFC strictly between HOD and the universe. Our result proves that the class HNT is really a new rich class of sets, which does not necessarily coincide with either the well-known class HOD or the whole universe V. This opens new possibilities in the ongoing study of the consistency and independence problems in modern set theory. [ABSTRACT FROM AUTHOR]

For any weighted directed path-cycle graphs, a and b (referred to as structures), and any equal costs of operations (intermergings and duplication), we obtain an algorithm which, by successively applying these operations to a, outputs b if the first structure contains no paralogs (i.e., edges with a repeated name) and the second has no more than two paralogs for each edge. In finding the shortest sequence of operations to be applied to pass from a to b, the algorithm has a multiplicative error of at most 13/9 + ε, where ε is any strictly positive number, and its runtime is of the order of n O (ε − 2.6) , where n is the size of the input pair of graphs. In the case of no paralogs, equal sets of names in the structures, and equal operation costs, we have considered the following conditions on the transformation of a into b: all structures in them are from one cycle; all structures are from one path; all structures are from paths. For each of the conditions, we have obtained an exact (i.e., zero-error) quadratic time algorithm for finding the shortest transformation of a into b. For another list of operations (join and cut of a vertex, and deletion and insertion of an edge) over structures and for arbitrary costs of these operations, we have obtained an algorithm for the extension of structures specified at the leaves of a tree onto its interior vertices. The algorithm is exact if the tree is a star—in this case, structures in the leaves may even have unequal sets of names or paralogs. The runtime of the algorithm is of the order of nΧ + n2log(n), where n is the number of names in the leaves, and Χ is an easily computable characteristic of the structures in the leaves. In the general case, a cubic time algorithm finds a locally minimal solution. [ABSTRACT FROM AUTHOR]

Examples of effectively indiscernible projective sets of real numbers in various models of set theory are presented. We prove that it is true, in Miller and Laver generic extensions of the constructible universe, that there exists a lightface Π 2 1 equivalence relation on the set of all nonconstructible reals, having exactly two equivalence classes, neither one of which is ordinal definable, and therefore the classes are OD-indiscernible. A similar but somewhat weaker result is obtained for Silver extensions. The other main result is that for any n, starting with 2, the existence of a pair of countable disjoint OD-indiscernible sets, whose associated equivalence relation belongs to lightface Π n 1 , does not imply the existence of such a pair with the associated relation in Σ n 1 or in a lower class. [ABSTRACT FROM AUTHOR]

Aim: To confirm algorithm of determination of risk groups with physiological imbalance in the population exposed to unfavorable anthropogenic influences. Methods: The testing included such functional systems as constitution, myocardial contractility, autonomic regulation of the heart rate, regulation of peripheral circulation, psychomotor regulation, respiratory regulation and metabolism. Monitoring is carried out using computerized measurement instrumentation and data processing systems. Results: A risk group with pronounced shifts in the physiological balance was identified, which made up 38% of the surveyed population. The greatest contribution to the imbalance was made by the psychomotor system. Conclusion: We analyzed two different components of organism's adaptation: resistance and resilience. Physiological systems experiencing increasing load attain a tipping points, where even a weak disturbing influence can induce transition to a qualitatively different state. This transition can result in either recovery of the regulatory stability of the system, or its transition to a lower level (dysregulation) with further development of a pathology. In this regard, of paramount importance is early detection of the signals about approaching the tipping points, one of these is the slowing down phenomenon during functional tests. In view of intricate interaction of physiological systems, recording of as much indicators as possible is advisable. The method of partial correlations is effective for evaluation of adaptive interaction of systems. [ABSTRACT FROM AUTHOR]

In this paper we prove that for any m ≥ 1 there exists a generic extension of L , the constructible universe, in which it is true that the set of all constructible reals (here subsets of ω) is equal to the set D 1 m of all reals definable by a parameter free type-theoretic formula with types bounded by m, and hence the Tarski 'definability of definable' sentence D 1 m ∈ D 2 m (even in the form D 1 m ∈ D 21 ) holds for this particular m. This solves an old problem of Alfred Tarski (1948). Our methods, based on the almost-disjoint forcing of Jensen and Solovay, are significant modifications and further development of the methods presented in our two previous papers in this Journal. [ABSTRACT FROM AUTHOR]

We propose a novel linear time algorithm which, given any directed weighted graphs a and b with vertex degrees 1 or 2, constructs a sequence of operations transforming a into b. The total cost of operations in this sequence is minimal among all possible ones or differs from the minimum by an additive constant that depends only on operation costs but not on the graphs themselves; this difference is small as compared to the operation costs and is explicitly computed. We assume that the double cut and join operations have identical costs, and costs of the deletion and insertion operations are arbitrary strictly positive rational numbers. [ABSTRACT FROM AUTHOR]

In this paper, we prove the following. If n ≥ 3 , then there is a generic extension of L , the constructible universe, in which it is true that the set P (ω) ∩ L of all constructible reals (here—subsets of ω) is equal to the set P (ω) ∩ Δ n 1 of all (lightface) Δ n 1 reals. The result was announced long ago by Leo Harrington, but its proof has never been published. Our methods are based on almost-disjoint forcing. To obtain a generic extension as required, we make use of a forcing notion of the form Q = C ℂ × ∏ ν Q ν in L , where C adds a generic collapse surjection b from ω onto P (ω) ∩ L , whereas each Q ν , ν < ω 2 L , is an almost-disjoint forcing notion in the ω 1 -version, that adjoins a subset S ν of ω 1 L . The forcing notions involved are independent in the sense that no Q ν -generic object can be added by the product of C and all Q ξ , ξ ≠ ν . This allows the definition of each constructible real by a Σ n 1 formula in a suitably constructed subextension of the Q -generic extension. The subextension is generated by the surjection b, sets S ω · k + j with j ∈ b (k) , and sets S ξ with ξ ≥ ω · ω . A special character of the construction of forcing notions Q ν is L , which depends on a given n ≥ 3 , obscures things with definability in the subextension enough for vice versa any Δ n 1 real to be constructible; here the method of hidden invariance is applied. A discussion of possible further applications is added in the conclusive section. [ABSTRACT FROM AUTHOR]

Models of set theory are defined, in which nonconstructible reals first appear on a given level of the projective hierarchy. Our main results are as follows. Suppose that n ≥ 2 . Then: 1. If it holds in the constructible universe L that a ⊆ ω and a ∉ Σ n 1 ∪ Π n 1 , then there is a generic extension of L in which a ∈ Δ n + 1 1 but still a ∉ Σ n 1 ∪ Π n 1 , and moreover, any set x ⊆ ω , x ∈ Σ n 1 , is constructible and Σ n 1 in L. 2. There exists a generic extension L in which it is true that there is a nonconstructible Δ n + 1 1 set a ⊆ ω , but all Σ n 1 sets x ⊆ ω are constructible and even Σ n 1 in L , and in addition, V = L [ a ] in the extension. 3. There exists an generic extension of L in which there is a nonconstructible Σ n + 1 1 set a ⊆ ω , but all Δ n + 1 1 sets x ⊆ ω are constructible and Δ n + 1 1 in L. Thus, nonconstructible reals (here subsets of ω) can first appear at a given lightface projective class strictly higher than Σ 2 1 , in an appropriate generic extension of L. The lower limit Σ 2 1 is motivated by the Shoenfield absoluteness theorem, which implies that all Σ 2 1 sets a ⊆ ω are constructible. Our methods are based on almost-disjoint forcing. We add a sufficient number of generic reals to L , which are very similar at a given projective level n but discernible at the next level n + 1 . [ABSTRACT FROM AUTHOR]