Search results for "Equivalence relation"
showing 7 items of 27 documents
On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations
2009
We show that every finitely satisfiable two-variable first-order formula with two equivalence relations has a model of size at most triply exponential with respect to its length. Thus the finite satisfiability problem for two-variable logic over the class of structures with two equivalence relations is decidable in nondeterministic triply exponential time. We also show that replacing one of the equivalence relations in the considered class of structures by a relation which is only required to be transitive leads to undecidability. This sharpens the earlier result that two-variable logic is undecidable over the class of structures with two transitive relations.
Left-Right Equivalence and Stability
2020
We introduce the key equivalence relations on germs of maps, which play an important role throughout the book—right-equivalence and left-right equivalence (A-equivalence). These are induced by groups of diffeomorphisms, so equivalence classes have tangent spaces, and we calculate many examples, including some multi-germs. We introduce the notions of stability and finite determinacy, and prove Mather’s infinitesimal criterion for stability.
A note on maximal subgroups and conjugacy classes of finite groups
2021
Given a finite group G, two elements are ≡m-related if they lie in exactly the same maximal subgroups of G. This equivalence relation was introduced by P. J. Cameron, A. Lucchini and C. M. Roney-Do...
Harnack and Shmul'yan pre-order relations for Hilbert space contractions
2015
We study the behavior of some classes of Hilbert space contractions with respect to Harnack and Shmul'yan pre-orders and the corresponding equivalence relations. We give some conditions under which the Harnack equivalence of two given contractions is equivalent to their Shmul'yan equivalence and to the existence of an arc joining the two contractions in the class of operator-valued contractive analytic functions on the unit disc. We apply some of these results to quasi-isometries and quasi-normal contractions, as well as to partial isometries for which we show that their Harnack and Shmul'yan parts coincide. We also discuss an extension, recently considered by S.~ter~Horst [\emph{J. Operato…
Algebraic Structures of Rough Sets
1994
This paper deals with some algebraic and set-theoretical properties of rough sets. Our considerations are based on the original conception of rough sets formulated by Pawlak [4, 5]. Let U be any fixed non-empty set traditionally called the universe and let R be an equivalence relation on U. The pair A = (U, R) is called the approximation space. We will call the equivalence classes of the relation R the elementary sets. We denote the family of elementary sets by U/R. We assume that the empty set is also an elementary set. Every union of elementary sets will be called a composed set. We denote the family of composed sets by ComR. We can characterize each set X ⊆ U using the composed sets [5].
A NOTE ON THE CATEGORICAL NOTIONS OF NORMAL SUBOBJECT AND OF EQUIVALENCE CLASS
2021
In a non-pointed category E, a subobject which is normal to an equivalence relation is not necessarily an equivalence class. We elaborate this categorical distinction, with a special attention to the Mal'tsev context. Moreover, we introduce the notion of fibrant equipment, and we use it to establish some conditions ensuring the uniqueness of an equivalence relation to which a given subobject is normal, and to give a description of such a relation.
Equivalence classes of Dyck paths modulo some statistics
2015
International audience; We investigate new equivalence relations on the set $\mathcal{D}_n$ of Dyck paths relatively to the three statistics of double rises, peaks and valleys. Two Dyck paths ar $r$-equivalent (resp. $p$-equivalent and $v$-equivalent) whenever the positions of their double rises (res. peaks and valleys) are the same. Then, we provide generating functions for the numbers of $r$-, $p$- and $v$-equivalence classes of $\mathcal{D}_n$.