Program synthesis is a process that obtains an efficient program out of a specification, preserving its meaning. Fork algebras have been proposed as an algebraic basis for the construction of a program synthesis environment. These algebras have an expressive power that encompasses that of first order logic, and they are also the right abstraction of the set model that considers programs as partial binary relations; these results make fork algebras a sound and powerful framework for this task.An important (...) step in the software construction process is the correct selection and manipulation of datatypes, because they are a powerful tool - with them modularization is easy, and enhancement of readability and early error detection are obtained. Algebraic datatypes , are an important class of datatypes because their properties are of great relevance in program transformation.The main goals of this work are to provide a general mechanism for defining algebraic datatypes in the framework of fork algebras, and, at the same time, establish a syntax that simplifies the notation for the specifications. (shrink)

This paper is about pairing relation algebras as well as fork algebras and related subjects. In the 1991-92 fork algebra papers it was conjectured that fork algebras admit a strong representation theorem . Then, this conjecture was disproved in the following sense: a strong representation theorem for all abstract fork algebras was proved to be impossible in most set theories including the usual one as well as most non-well-founded set theories. Here we show that the (...) above quoted conjecture can still be made true by choosing an appropriate set theory as our foundation of mathematics. Namely, we show that there are non-well-founded set theories in which every abstract fork algebra is representable in the strong sense, i.e. it is isomorphic to a set relation algebra having a fork operation which is obtained with the help of the real pairing function. Further, these non-well-founded set theories are consistent if usual set theory is consistent. Finally, we will discuss related developments in propositional multi-modal logics of quantification and substitution, in algebraic logic e.g. cylindric algebras, the so called finitization problem, and applications to a logic introduced and studied in Tarski-Givant [42]. In particular, representable, weakly higher order cylindric algebras are finitely axiomatizable in a set theory which admits the axiom of foundation for finite sets. (shrink)

Proper fork algebras are algebras of binary relations over a structured set. The underlying set has changed from a set of pairs to a set closed under an injective function. In this paper we present a representation theorem for their abstract counterpart, that entails that proper fork algebras — whose underlying set is closed under an injective function — constitute a finitely based variety.1.

Some varieties that are extensions of relational algebras with two constants that play the role of projections are studied. The classes have as a subvariety the abstract fork algebra equivalent variety involving projections. They are obtained by weakening some laws valid in AFA. Some applications of the varieties in the literature and in the specification of abstract data types are exhibited. For each of the classes obtained, an answer is given to the question: 'Is the relational reduct of (...) the class representable?'. For the subvarieties formed with the models that have a representable relational reduct, a representation theorem is proved. For them the finitization problem is studied. Next the varieties presented are compared by means of the inclusion order. For each class the problem of characterizing finite models is considered. Simple models in the varieties are studied. Finally the existence of equivalent classes with a binary operation like fork is studied. (shrink)

The representational theorem for fork algebras was always misunderstood regarding its applications in program construction. Its application was always described as 'the portability of properties of the problem domain into the abstract calculus of fork algebras'. In this paper we show that the results provided by the representation theorem are by far more important. We show that not only the heuristic power coming from concrete binary relations is captured inside the abstract calculus, but also design strategies for the (...) program development can be successfully expressed. This result makes fork algebras a programming calculus by far more powerful than it was previously thought. (shrink)

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive (...) power of its first-order correspondence language, so both can express the same input–output behavior of processes. (shrink)

We study the generic theory of algebraically closed fields of fixed positive characteristic with a predicate for an additive subgroup, called $\mathrm {ACFG}$. This theory was introduced in [16] as a new example of $\mathrm {NSOP}_{1}$ nonsimple theory. In this paper we describe more features of $\mathrm {ACFG}$, such as imaginaries. We also study various independence relations in $\mathrm {ACFG}$, such as Kim-independence or forking independence, and describe interactions between them.

A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of axioms. The primary example is forking in a simple theory, but o-minimal theories are also known to have an interesting independence relation. Our approach in this paper is to treat independence relations as mathematical objects worth studying. The main application is a better understanding of thorn-forking, which turns out to be (...) closely related to modular pairs in the lattice of algebraically closed sets. (shrink)

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are axiomatized by adding three (...) equations to RAs equational axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is ᵎ x ᵎ for some set ᵎ) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares. (shrink)

A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of axioms. The primary example is forking in a simple theory, but o-minimal theories are also known to have an interesting independence relation. Our approach in this paper is to treat independence relations as mathematical objects worth studying. The main application is a better understanding of thorn-forking, which turns out to be (...) closely related to modular pairs in the lattice of algebraically closed sets. (shrink)

We give an exposition of results of Baldwin–Shelah [2] on saturated free algebras, at the level of generality of complete first order theoriesTwith a saturated modelMwhich is in the algebraic closure of an indiscernible set. We then make some new observations whenM isa saturated free algebra, analogous to (more difficult) results for the free group, such as a description of forking.

We define a generalized notion of rank for stable theories without dense forking chains, and use it to derive that every type is domination-equivalent to a finite product of regular types. We apply this to show that in a small theory admitting finite coding, no realisation of a nonforking extension of some strong type can be algebraic over some realisation of a forking extension.

CM-triviality of a stable theory is a notion introduced by Hrushovski [1]. The importance of this property is first that it holds of Hrushovski's new non 1-based strongly minimal sets, and second that it is still quite a restrictive property, and forbids the existence of definable fields or simple groups (see [2]). In [5], Frank Wagner posed some questions aboutCM-triviality, asking in particular whether a structure of finite rank, which is “coordinatized” byCM-trivial types of rank 1, is itselfCM-trivial. (Actually Wagner (...) worked in a slightly more general context, adapting the definitions to a certain “local” framework, in which algebraic closure is replaced byP-closure, forPsome family of types. We will, however, remain in the standard context, and will just remark here that it is routine to translate our results into Wagner's framework, as well as to generalise to the superstable theory/regular type context.) In any case we answer Wagner's question positively. Also in an attempt to put forward some concrete conjectures about the possible geometries of strongly minimal sets (or stable theories) we tentatively suggest a hierarchy of geometric properties of forking, the first two levels of which correspond to 1-basedness andCM-triviality respectively. We do not know whether this is a strict hierarchy (or even whether these are the “right” notions), but we conjecture that it is, and moreover that a counterexample to Cherlin's conjecture can be found at level three in the hierarchy. (shrink)

We give three counterexamples to the folklore claim that in an arbitrary theory, if a complete type p over a set B does not divide over $C\subseteq B$, then no extension of p to a complete type over $\operatorname {acl}(B)$ divides over C. Two of our examples are also the first known theories where all sets are extension bases for nonforking, but forking and dividing differ for complete types (answering a question of Adler). One example is an $\mathrm {NSOP}_1$ theory (...) with a complete type that forks, but does not divide, over a model (answering a question of d’Elbée). Moreover, dividing independence fails to imply M-independence in this example (which refutes another folklore claim). In addition to these counterexamples, we summarize various related properties of dividing that are still true. We also address consequences for previous literature, including an earlier unpublished result about forking and dividing in free amalgamation theories, and some claims about dividing in the theory of generic $K_{m,n}$ -free incidence structures. (shrink)

ABSTRACT In this paper it is shown that a broad class of propositional logics can be interpreted in an equational logic based on fork algebras. This interpetability enables us to develop a fork-algebraic formalization of these logics and, as a consequence, to simulate non-classical means of reasoning with equational theories algebras.

Given an ordered fieldK, we compute the natural valuation and skeleton of the ordered multiplicative group (K >0, ·, 1, <) in terms of those of the ordered additive group (K,+,0,<). We use this computation to provide necessary and sufficient conditions on the value groupv(K) and residue field $\bar K$ , for theL ∞ε-equivalence of the above mentioned groups. We then apply the results to exponential fields, and describev(K) in that case. Finally, ifK is countable or a power series field, (...) we derive necessary and sufficient conditions onv(K) and $\bar K$ forK to be exponential. In the countable case, we get a structure theorem forv(K). (shrink)

We study $$\omega $$ ω -categorical MS-measurable structures. Our main result is that a certain class of $$\omega $$ ω -categorical Hrushovski constructions, supersimple of finite SU-rank is not MS-measurable. These results complement the work of Evans on a conjecture of Macpherson and Elwes. In constrast to Evans’ work, our structures may satisfy independent n-amalgamation for all n. We also prove some general results in the context of $$\omega $$ ω -categorical MS-measurable structures. Firstly, in these structures, the dimension in (...) the MS-dimension-measure can be chosen to be SU-rank. Secondly, non-forking independence implies a form of probabilistic independence in the measure. The latter follows from more general unpublished results of Hrushovski, but we provide a self-contained proof. (shrink)

We explore a notion of pseudofinite dimension, introduced by Hrushovski and Wagner, on an infinite ultraproduct of finite structures. Certain conditions on pseudofinite dimension are identified that guarantee simplicity or supersimplicity of the underlying theory, and that a drop in pseudofinite dimension is equivalent to forking. Under a suitable assumption, a measure-theoretic condition is shown to be equivalent to local stability. Many examples are explored, including vector spaces over finite fields viewed as 2-sorted finite structures, and homocyclic groups. Connections are (...) made to products of sets in finite groups, in particular to word maps, and a generalization of Tao's Algebraic Regularity Lemma is noted. (shrink)

Fix a weakly minimal (i.e. superstable U-rank 1) structure M. Let M∗ be an expansion by constants for an elementary substructure, and let A be an arbitrary subset of the universe M. We show that all formulas in the expansion (M∗,A) are equivalent to bounded formulas, and so (M,A) is stable (or NIP) if and only if the M-induced structure AM on A is stable (or NIP). We then restrict to the case that M is a pure abelian group with (...) a weakly minimal theory, and AM is mutually algebraic (equivalently, weakly minimal with trivial forking). This setting encompasses most of the recent research on stable expansions of (Z,+). Using various characterizations of mutual algebraicity, we give new examples of stable structures of the form (M,A). Most notably, we show that if (G,+) is a weakly minimal additive subgroup of the algebraic numbers, A⊆G is enumerated by a homogeneous linear recurrence relation with algebraic coefficients, and no repeated root of the characteristic polynomial of A is a root of unity, then (G,+,B) is superstable for any B⊆A. (shrink)

In this paper we analyze some aspects of the question of using methods from model theory to study structures of functional analysis.By a well known result of P. Lindström, one cannot extend the expressive power of first order logic and yet preserve its most outstanding model theoretic characteristics (e.g., compactness and the Löwenheim-Skolem theorem). However, one may consider extending the scope of first order in a different sense, specifically, by expanding the class of structures that are regarded as models (e.g., (...) including Banach algebras or other structures of functional analysis), and ask whether the resulting extensions of first order model theory preserve some of its desirable characteristics.A formal framework for the study of structures based on Banach spaces from the perspective of model theory was first introduced by C. W. Henson in [8] and [6]. Notions of syntax and semantics for these structures were defined, and it was shown that using them one obtains a model theoretic apparatus that satisfies many of the fundamental properties of first order model theory. For instance, one has compactness, Löwenheim-Skolem, and omitting types theorems. Further aspects of the theory, namely, the fundamentals of stability and forking, were first introduced in [10] and [9].The classes of mathematical structures formally encompassed by this framework are normed linear spaces, possibly expanded with additional structure,e.g., operations, real-valued relations, and constants. This notion subsumes wide classes of structures from functional analysis. However, the restriction that the universe of a structure be a normed space is not necessary. (This restriction has a historical, rather than technical origin; specifically, the development of the theory was originally motivated by questions in Banach space geometry.) Analogous techniques can be applied if the universe is a metric space. Now, when the underlying metric topology is discrete, the resulting model theory coincides with first order model theory, so this logic extends first order in the sense described above. Furthermore, without any cost in the mathematical complexity, one can also work in multi-sorted contexts, so, for instance, one sort could be an operator algebra while another is. say, a metric space. (shrink)

We study classes of modules closed under direct sums, [Formula: see text]-submodules and [Formula: see text]-epimorphic images where [Formula: see text] is either the class of embeddings, RD-embeddings or pure embeddings. We show that the [Formula: see text]-injective modules of theses classes satisfy a Baer-like criterion. In particular, injective modules, RD-injective modules, pure injective modules, flat cotorsion modules and [Formula: see text]-torsion pure injective modules satisfy this criterion. The argument presented is a model theoretic one. We use in an essential (...) way stable independence relations which generalize Shelah’s non-forking to abstract elementary classes. We show that the classical model theoretic notion of superstability is equivalent to the algebraic notion of a noetherian category for these classes. We use this equivalence to characterize noetherian rings, pure semisimple rings, perfect rings and finite products of finite rings and artinian valuation rings via superstability. (shrink)

We study the notion of weak canonical bases in an NSOP $_{1}$ theory T with existence. Given $p=\operatorname {tp}$ where $B=\operatorname {acl}$ in ${\mathcal M}^{\operatorname {eq}}\models T^{\operatorname {eq}}$, the weak canonical base of p is the smallest algebraically closed subset of B over which p does not Kim-fork. With this aim we firstly show that the transitive closure $\approx $ of collinearity of an indiscernible sequence is type-definable. Secondly, we prove that given a total $\mathop {\smile \hskip -0.9em ^| (...) \ }^K$ -Morley sequence I in p, the weak canonical base of $\operatorname {tp}$ is $\operatorname {acl}$, if the hyperimaginary $I/\approx $ is eliminable to e, a sequence of imaginaries. We also supply a couple of criteria for when the weak canonical base of p exists. In particular the weak canonical base of p is the intersection of the weak canonical bases of all total $\mathop {\smile \hskip -0.9em ^| \ }^K$ -Morley sequences in p over B. However, while we investigate some examples, we point out that given two weak canonical bases of total $\mathop {\smile \hskip -0.9em ^| \ }^K$ -Morley sequences in p need not be interalgebraic, contrary to the case of simple theories. Lastly we suggest an independence relation relying on weak canonical bases, when T has those. The relation, satisfying transitivity and base monotonicity, might be useful in further studies on NSOP $_1$ theories. (shrink)

This thesis is concerned with the expansions of algebraic structures and their fit in Shelah’s classification landscape.The first part deals with the expansion of a theory by a random predicate for a substructure model of a reduct of the theory. Let T be a theory in a language $\mathcal {L}$. Let $T_0$ be a reduct of T. Let $\mathcal {L}_S = \mathcal {L}\cup \{S\}$, for S a new unary predicate symbol, and $T_S$ be the $\mathcal {L}_S$ -theory that axiomatises the (...) following structures: $$ consist of a model $\mathscr {M}$ of T and S is a predicate for a model $\mathscr {M}_0$ of $T_0$ which is a substructure of $\mathscr {M}$. We present a setting for the existence of a model-companion $TS$ of $T_S$. As a consequence, we obtain the existence of the model-companion of the following theories, for $p>0$ a prime number: • $\mathrm {ACF}_p$, $\mathrm {SCF}_{e,p}$, $\mathrm {Psf}_p$, $\mathrm {ACFA}_p$, $\mathrm {ACVF}_{p,p}$ in appropriate languages expanded by arbitrarily many predicates for additive subgroups;• $\mathrm {ACF}_p$, $\mathrm {ACF}_0$ in the language of rings expanded by a single predicate for a multiplicative subgroup;• $\mathrm {PAC}_p$ -fields, in an appropriate language expanded by arbitrarily many predicates for additive subgroups.From an independence relation in T, we define independence relations in $TS$ and identify which properties of are transferred to those new independence relations in $TS$, and under which conditions. This allows us to exhibit hypotheses under which the expansion from T to $TS$ preserves $\mathrm {NSOP}_{1}$, simplicity, or stability. In particular, under some technical hypothesis on T, we may draw the following picture : Configuration $T_0\subseteq T$ Generic expansion $TS$ $T_0 = T$ Preserves stability $T_0\subseteq T$ Preserves $\mathrm {NSOP}_{1}$ $T_0 = \emptyset $ Preserves simplicityIn particular, this construction produces new examples of $\mathrm {NSOP}_{1}$ not simple theories, and we study in depth a particular example: the expansion of an algebraically closed field of positive characteristic by a generic additive subgroup. We give a full description of imaginaries, forking, and Kim-forking in this example.The second part studies expansions of the group of integers by p-adic valuations. We prove quantifier elimination in a natural language and compute the dp-rank of these expansions: it equals the number of independent p-adic valuations considered. Thus, the expansion of the integers by one p-adic valuation is a new dp-minimal expansion of the group of integers. Finally, we prove that the latter expansion does not admit intermediate structures: any definable set in the expansion is either definable in the group structure or is able to “reconstruct” the valuation using only the group operation.prepared by Christian d’Elbée.E-mail: [email protected]: https://choum.net/~chris/page_perso. (shrink)

We define a notion of residue field domination for valued fields which generalizes stable domination in algebraically closed valued fields. We prove that a real closed valued field is dominated by the sorts internal to the residue field, over the value group, both in the pure field and in the geometric sorts. These results characterize forking and þ-forking in real closed valued fields (and also algebraically closed valued fields). We lay some groundwork for extending these results to a power-bounded T-convex (...) theory. (shrink)

Assume T is a superstable theory with $ countable models. We prove that any *-algebraic type of M-rank > 0 is m-nonorthogonal to a *-algebraic type of M-rank 1. We study the geometry induced by m-dependence on a *-algebraic type p* of M-rank 1. We prove that after some localization this geometry becomes projective over a division ring F. Associated with p* is a meager type p. We prove that p is determined by p* up to nonorthogonality and that F (...) underlies also the geometry induced by forking dependence on any stationarization of p. Also we study some *-algebraic *-groups of M-rank 1 and prove that any *-algebraic *-group of M-rank 1 is abelian-by-finite. (shrink)

We exhibit a bridge between the theory of cellular categories, used in algebraic topology and homological algebra, and the model-theoretic notion of stable independence. Roughly speaking, we show that the combinatorial cellular categories (those where, in a precise sense, the cellular morphisms are generated by a set) are exactly those that give rise to stable independence notions. We give two applications: on the one hand, we show that the abstract elementary classes of roots of Ext studied by Baldwin–Eklof–Trlifaj are (...) stable and tame. On the other hand, we give a simpler proof (in a special case) that combinatorial categories are closed under 2-limits, a theorem of Makkai and Rosický. (shrink)

We address the classification of the possible finitely-additive probability measures on the Boolean algebra of definable subsets of M which are invariant under the natural action of $\operatorname{Aut}(M)$ . This pursuit requires a generalization of Shelah's forking formulas [8] to "essentially measure zero" sets and an application of Myer's "rank diagram" [5] of the Boolean algebra under consideration. The classification is completed for a large class of ℵ 0 -categorical structures without the independence property including those which are (...) stable. (shrink)

Journal of Mathematical Logic, Ahead of Print. We study classes of modules closed under direct sums, [math]-submodules and [math]-epimorphic images where [math] is either the class of embeddings, RD-embeddings or pure embeddings. We show that the [math]-injective modules of theses classes satisfy a Baer-like criterion. In particular, injective modules, RD-injective modules, pure injective modules, flat cotorsion modules and [math]-torsion pure injective modules satisfy this criterion. The argument presented is a model theoretic one. We use in an essential way stable independence (...) relations which generalize Shelah’s non-forking to abstract elementary classes. We show that the classical model theoretic notion of superstability is equivalent to the algebraic notion of a noetherian category for these classes. We use this equivalence to characterize noetherian rings, pure semisimple rings, perfect rings and finite products of finite rings and artinian valuation rings via superstability. (shrink)

"What can we expect from the study of Chinese philosophy? « In the philosophical systems of the Hindoos and the Chinese there are still hidden treasures, in which the anticipation of scientific discoveries, the results of thousands of years of occidental research, is most striking. Such are the words of Edward von Hartmann, the most famous living German philosopher1. Much labour has been spent in Europe on the Indian Vedanta philosophy, which had such a marked influence on Arthur Schopenhauer. « (...) The Upanishads, says the author of the Parerga and Paralipomena, are the outcome of the highest human wisdom.... They afford the most remunerative and sublime reading possible in this world, which has been the consolation of my life, as it will be that of my death 2. I do not see why the many germs scattered over the vast field of Chinese philosophy should not have a similar fertilizing influence on some philosophical European mind also. The deep impression caused by the Tao-tê-king will support my view. But much work remains to be done before Chinese philosophy will take its proper place in the history of philosophy. The burden of this task lies with us who are living in China and studying her language and literature, for, while great care is bestowed on all her sister languages in Europe and America, Chinese, the oldest of all, but the youngest in the curriculum of our high-schools, is treated as a step-child by public opinion. This paper is meant as a move in the direction just indicated.". (shrink)

This work has been selected by scholars as being culturally important, and is part of the knowledge base of civilization as we know it. This work was reproduced from the original artifact, and remains as true to the original work as possible. Therefore, you will see the original copyright references, library stamps (as most of these works have been housed in our most important libraries around the world), and other notations in the work. This work is in the public domain (...) in the United States of America, and possibly other nations. Within the United States, you may freely copy and distribute this work, as no entity (individual or corporate) has a copyright on the body of the work. As a reproduction of a historical artifact, this work may contain missing or blurred pages, poor pictures, errant marks, etc. Scholars believe, and we concur, that this work is important enough to be preserved, reproduced, and made generally available to the public. We appreciate your support of the preservation process, and thank you for being an important part of keeping this knowledge alive and relevant. (shrink)

This work has been selected by scholars as being culturally important and is part of the knowledge base of civilization as we know it. This work is in the public domain in the United States of America, and possibly other nations. Within the United States, you may freely copy and distribute this work, as no entity (individual or corporate) has a copyright on the body of the work. Scholars believe, and we concur, that this work is important enough to be (...) preserved, reproduced, and made generally available to the public. To ensure a quality reading experience, this work has been proofread and republished using a format that seamlessly blends the original graphical elements with text in an easy-to-read typeface. We appreciate your support of the preservation process, and thank you for being an important part of keeping this knowledge alive and relevant. (shrink)