Релација еквиваленције — разлика између измена
Садржај обрисан Садржај додат
м ispravke |
. |
||
Ред 1:
{{Short description|Математички концепт за поређење објеката}}{{rut}}
[[File:Set partitions 5; matrices.svg|right|thumb|The [[Bell number|52]] equivalence relations on a 5-element set depicted as <math>5 \times 5</math> [[Logical matrix|logical matrices]]<ref name=GS>{{cite book | doi=10.1017/CBO9780511778810 | isbn=9780511778810 | author=Gunther Schmidt | page=91 | title=Relational Mathematics | chapter=6: Relations and Vectors | publisher=Cambridge University Press | year=2013 | author-link=Gunther Schmidt }}</ref> (colored fields, including those in light gray, stand for ones; white fields for zeros.) The row and column indices of nonwhite cells are the related elements, while the different colors, other than light gray, indicate the equivalence classes (each light gray cell is its own equivalence class).]]
У [[математика|математици]], '''релација еквиваленције''', која се често означава [[инфиксна нотација|инфиксно]] симболима "~" или "≡" је [[бинарна релација]] на [[скуп]]у ''-{X}-'' која је ''рефлексивна'', ''симетрична'', и ''транзитивна'', то јест, за све елементе ''-{a}-'', ''-{b}-'', и ''-{c}-'' из ''-{X}-'', следећи искази морају да ва же како би '~' била релација еквиваленције:
*[[Рефлексивна релација|Рефлексивност]]: ''-{a}-'' ~ ''-{a}-''
Линија 5 ⟶ 8:
Еквиваленција у контексту такве релације (која се тиче елемената скупа ''-{X}-''), се разликује од концепта [[логичка еквиваленција|логичке еквиваленције]] (која се тиче логичких исказа). Релације еквиваленције се могу посматрати као груписање објеката који су слични у неком смислу.
== Нотација ==
Various notations are used in the literature to denote that two elements <math>a</math> and <math>b</math> of a set are equivalent with respect to an equivalence relation <math>R;</math> the most common are "<math>a \sim b</math>" and "{{math|''a'' ≡ ''b''}}", which are used when <math>R</math> is implicit, and variations of "<math>a \sim_R b</math>", "{{math|''a'' ≡<sub>''R''</sub> ''b''}}", or "<math>{a\mathop{R}b}</math>" to specify <math>R</math> explicitly. Non-equivalence may be written "{{math|''a'' ≁ ''b''}}" or "<math>a \not\equiv b</math>".
== Дефиниција ==
A [[binary relation]] <math>\,\sim\,</math> on a set <math>X</math> is said to be an equivalence relation, [[if and only if]] it is reflexive, symmetric and transitive. That is, for all <math>a, b,</math> and <math>c</math> in <math>X:</math>
* <math>a \sim a.</math> ([[Reflexive relation|Reflexivity]])
* <math>a \sim b</math> if and only if <math>b \sim a.</math> ([[Symmetric relation|Symmetry]])
* If <math>a \sim b</math> and <math>b \sim c</math> then <math>a \sim c.</math> ([[Transitive relation|Transitivity]])
<math>X</math> together with the relation <math>\,\sim\,</math> is called a [[setoid]]. The [[equivalence class]] of <math>a</math> under <math>\,\sim,</math> denoted <math>[a],</math> is defined as <math>[a] = \{x \in X : x \sim a\}.</math><ref>{{Cite web|last=Weisstein|first=Eric W.|title=Equivalence Class|url=https://mathworld.wolfram.com/EquivalenceClass.html|access-date=2020-08-30|website=mathworld.wolfram.com|language=en}}</ref><ref name=":0">{{Cite web|date=2017-09-20|title=7.3: Equivalence Classes|url=https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Book%3A_Mathematical_Reasoning__Writing_and_Proof_(Sundstrom)/7%3A_Equivalence_Relations/7.3%3A_Equivalence_Classes|access-date=2020-08-30|website=Mathematics LibreTexts|language=en}}</ref>
== Алгебарска структура ==
Much of mathematics is grounded in the study of equivalences, and [[order relation]]s. [[Lattice (order)|Lattice theory]] captures the mathematical structure of order relations. Even though equivalence relations are as ubiquitous in mathematics as order relations, the algebraic structure of equivalences is not as well known as that of orders. The former structure draws primarily on [[group theory]] and, to a lesser extent, on the theory of lattices, [[Category theory|categories]], and [[groupoid]]s.
===Group theory===
Just as [[order relation]]s are grounded in [[Partially ordered set|ordered sets]], sets closed under pairwise [[supremum]] and [[infimum]], equivalence relations are grounded in [[Partition of a set|partitioned sets]], which are sets closed under [[bijection]]s that preserve partition structure. Since all such bijections map an equivalence class onto itself, such bijections are also known as [[permutation]]s. Hence [[permutation group]]s (also known as [[Group action (mathematics)|transformation groups]]) and the related notion of [[Orbit (group theory)|orbit]] shed light on the mathematical structure of equivalence relations.
Let '~' denote an equivalence relation over some nonempty set ''A'', called the [[Universe (mathematics)|universe]] or underlying set. Let ''G'' denote the set of bijective functions over ''A'' that preserve the partition structure of ''A'', meaning that for all <math>x \in A</math> and <math>g \in G, g(x) \in [x].</math> Then the following three connected theorems hold:<ref>Rosen (2008), pp. 243–45. Less clear is §10.3 of [[Bas van Fraassen]], 1989. ''Laws and Symmetry''. Oxford Univ. Press.</ref>
* ~ partitions ''A'' into equivalence classes. (This is the {{em|Fundamental Theorem of Equivalence Relations}}, mentioned above);
* Given a partition of ''A'', ''G'' is a transformation group under composition, whose orbits are the [[Partitions of a set|cells]] of the partition;{{#tag:ref|
''Proof''.<ref>Bas van Fraassen, 1989. ''Laws and Symmetry''. Oxford Univ. Press: 246.</ref> Let [[function composition]] interpret group multiplication, and function inverse interpret group inverse. Then ''G'' is a group under composition, meaning that <math>x \in A</math> and <math>g \in G, [g(x)] = [x],</math> because ''G'' satisfies the following four conditions:
* ''G is closed under composition''. The composition of any two elements of ''G'' exists, because the [[Domain of a function|domain]] and [[codomain]] of any element of ''G'' is ''A''. Moreover, the composition of bijections is [[bijective]];<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. Springer-Verlag: 22, Th. 6.</ref>
* ''Existence of [[identity function]]''. The [[identity function]], ''I''(''x'') = ''x'', is an obvious element of ''G'';
* ''Existence of [[inverse function]]''. Every [[bijective function]] ''g'' has an inverse ''g''<sup>−1</sup>, such that ''gg''<sup>−1</sup> = ''I'';
* ''Composition [[Associativity|associates]]''. ''f''(''gh'') = (''fg'')''h''. This holds for all functions over all domains.<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. Springer-Verlag: 24, Th. 7.</ref>
Let ''f'' and ''g'' be any two elements of ''G''. By virtue of the definition of ''G'', [''g''(''f''(''x''))] = [''f''(''x'')] and [''f''(''x'')] = [''x''], so that [''g''(''f''(''x''))] = [''x'']. Hence ''G'' is also a transformation group (and an [[automorphism group]]) because function composition preserves the partitioning of <math>A. \blacksquare</math>}}
* Given a transformation group ''G'' over ''A'', there exists an equivalence relation ~ over ''A'', whose equivalence classes are the orbits of ''G''.<ref>Wallace, D. A. R., 1998. ''Groups, Rings and Fields''. Springer-Verlag: 202, Th. 6.</ref><ref>Dummit, D. S., and Foote, R. M., 2004. ''Abstract Algebra'', 3rd ed. John Wiley & Sons: 114, Prop. 2.</ref>
In sum, given an equivalence relation ~ over ''A'', there exists a [[transformation group]] ''G'' over ''A'' whose orbits are the equivalence classes of ''A'' under ~.
This transformation group characterisation of equivalence relations differs fundamentally from the way [[Lattice (order)|lattices]] characterize order relations. The arguments of the lattice theory operations [[Meet (mathematics)|meet]] and [[Join (mathematics)|join]] are elements of some universe ''A''. Meanwhile, the arguments of the transformation group operations [[Function composition|composition]] and [[Inverse function|inverse]] are elements of a set of [[bijections]], ''A'' → ''A''.
Moving to groups in general, let ''H'' be a [[subgroup]] of some [[Group (mathematics)|group]] ''G''. Let ~ be an equivalence relation on ''G'', such that <math>a \sim b \text{ if and only if } a b^{-1} \in H.</math> The equivalence classes of ~—also called the orbits of the [[Group action (mathematics)|action]] of ''H'' on ''G''—are the right '''[[coset]]s''' of ''H'' in ''G''. Interchanging ''a'' and ''b'' yields the left cosets.<ref>Related thinking can be found in Rosen (2008: chpt. 10).</ref>
===Categories and groupoids===
Let ''G'' be a set and let "~" denote an equivalence relation over ''G''. Then we can form a [[groupoid]] representing this equivalence relation as follows. The objects are the elements of ''G'', and for any two elements ''x'' and ''y'' of ''G'', there exists a unique morphism from ''x'' to ''y'' [[if and only if]] <math>x \sim y.</math>
The advantages of regarding an equivalence relation as a special case of a groupoid include:
*Whereas the notion of "free equivalence relation" does not exist, that of a [[Free object|free groupoid]] on a [[directed graph]] does. Thus it is meaningful to speak of a "presentation of an equivalence relation," i.e., a presentation of the corresponding groupoid;
* Bundles of groups, [[Group action (mathematics)|group action]]s, sets, and equivalence relations can be regarded as special cases of the notion of groupoid, a point of view that suggests a number of analogies;
*In many contexts "quotienting," and hence the appropriate equivalence relations often called [[Congruence relation|congruences]], are important. This leads to the notion of an internal groupoid in a [[Category (mathematics)|category]].<ref>Borceux, F. and Janelidze, G., 2001. ''Galois theories'', Cambridge University Press, {{ISBN|0-521-80309-8}}</ref>
== Примери релација еквиваленције ==
Линија 15 ⟶ 61:
* „Је паралелно“, на скупу афиних потпростора [[афини простор|афиног простора]].
== Референце ==
==Спољашње везе==▼
{{reflist|}}
*[http://www.cut-the-knot.org/blue/equi.shtml Релације еквиваленције]▼
== Литература ==
{{refbegin|30em}}
*Brown, Ronald, 2006. ''[http://arquivo.pt/wayback/20160514115224/http://www.bangor.ac.uk/r.brown/topgpds.html Topology and Groupoids.]'' Booksurge LLC. {{ISBN|1-4196-2722-8}}.
*Castellani, E., 2003, "Symmetry and equivalence" in Brading, Katherine, and E. Castellani, eds., ''Symmetries in Physics: Philosophical Reflections''. Cambridge Univ. Press: 422–433.
*[[Robert Dilworth]] and Crawley, Peter, 1973. ''Algebraic Theory of Lattices''. Prentice Hall. Chpt. 12 discusses how equivalence relations arise in [[lattice (order)|lattice]] theory.
*Higgins, P.J., 1971. ''[http://www.emis.de/journals/TAC/reprints/articles/7/tr7abs.html Categories and groupoids.]'' Van Nostrand. Downloadable since 2005 as a TAC Reprint.
*[[John Lucas (philosopher)|John Randolph Lucas]], 1973. ''A Treatise on Time and Space''. London: Methuen. Section 31.
*Rosen, Joseph (2008) ''Symmetry Rules: How Science and Nature are Founded on Symmetry''. Springer-Verlag. Mostly chapters. 9,10.
*[[Raymond Wilder]] (1965) ''Introduction to the Foundations of Mathematics'' 2nd edition, Chapter 2-8: Axioms defining equivalence, pp 48–50, [[John Wiley & Sons]].
* {{citation|first=Carol|last=Avelsgaard|title=Foundations for Advanced Mathematics|publisher=Scott Foresman|year=1989|isbn=0-673-38152-8}}
* {{citation|last=Devlin|first=Keith|title=Sets, Functions, and Logic: An Introduction to Abstract Mathematics|year=2004|publisher=Chapman & Hall/ CRC Press|edition=3rd|isbn=978-1-58488-449-1}}
* {{citation|last=Maddox|first=Randall B.|title=Mathematical Thinking and Writing|year=2002|publisher=Harcourt/ Academic Press|isbn=0-12-464976-9}}
* {{citation|last=Wolf|first=Robert S.|title=Proof, Logic and Conjecture: A Mathematician's Toolbox|year=1998|publisher=Freeman|isbn=978-0-7167-3050-7}}
* {{citation|last=Sundstrom|title=Mathematical Reasoning: Writing and Proof|year=2003|publisher=Prentice-Hall}}
* {{citation|last1=Smith|last2=Eggen|last3=St.Andre|title=A Transition to Advanced Mathematics |edition=6th |year=2006|publisher=Thomson (Brooks/Cole)}}
* {{citation|last=Schumacher|first=Carol|author-link= Carol Schumacher |title=Chapter Zero: Fundamental Notions of Abstract Mathematics|year=1996|publisher=Addison-Wesley|isbn=0-201-82653-4}}
* {{citation|last=O'Leary|title=The Structure of Proof: With Logic and Set Theory|year=2003|publisher=Prentice-Hall}}
* {{citation|last=Lay|title=Analysis with an introduction to proof|year=2001|publisher=Prentice Hall}}
* {{citation|last=Morash|first=Ronald P.|title=Bridge to Abstract Mathematics|publisher=Random House|year=1987|isbn=0-394-35429-X}}
* {{citation|last1=Gilbert|last2=Vanstone|title=An Introduction to Mathematical Thinking|year=2005|publisher=Pearson Prentice-Hall}}
* {{citation|last1=Fletcher|last2=Patty|title=Foundations of Higher Mathematics|publisher=PWS-Kent}}
* {{citation|last1=Iglewicz|last2=Stoyle|title=An Introduction to Mathematical Reasoning|publisher=MacMillan}}
* {{citation|last1=D'Angelo|last2=West|title=Mathematical Thinking: Problem Solving and Proofs|year=2000|publisher=Prentice Hall}}
* {{citation|last=Cupillari|author-link= Antonella Cupillari |title=The Nuts and Bolts of Proofs|publisher=Wadsworth}}
* {{citation|last=Bond|title=Introduction to Abstract Mathematics|publisher=Brooks/Cole}}
* {{citation|last1=Barnier|last2=Feldman|title=Introduction to Advanced Mathematics|year=2000|publisher=Prentice Hall}}
* {{citation|last=Ash|title=A Primer of Abstract Mathematics|publisher=MAA}}
* {{cite book |last= Brualdi |first= Richard A. |title= Introductory Combinatorics |edition= 4th |year= 2004 |publisher= Pearson Prentice Hall |isbn= 0-13-100119-1}}
* {{cite book |last= Schechter |first= Eric |title= Handbook of Analysis and Its Foundations |year= 1997 |publisher= Academic Press |isbn= 0-12-622760-8}}
* {{Citation | last1=Hogben | first1=Leslie|author1-link= Leslie Hogben | title=Handbook of Linear Algebra (Discrete Mathematics and Its Applications) | publisher=Chapman & Hall/CRC | location=Boca Raton | isbn=978-1-58488-510-8 | year=2006}}, § 31.3, Binary Matrices
* {{Citation | last1=Kim | first1=Ki Hang | title=Boolean Matrix Theory and Applications |year=1982| isbn=978-0-8247-1788-9}}
* [[H. J. Ryser]] (1957) "Combinatorial properties of matrices of zeroes and ones", [[Canadian Journal of Mathematics]] 9: 371–7.
* Ryser, H.J. (1960) "Traces of matrices of zeroes and ones", ''Canadian Journal of Mathematics'' 12: 463–76.
* Ryser, H.J. (1960) "Matrices of Zeros and Ones", [[Bulletin of the American Mathematical Society]] 66: 442–64.
* [[D. R. Fulkerson]] (1960) "Zero-one matrices with zero trace", [[Pacific Journal of Mathematics]] 10; 831–6
* D. R. Fulkerson & H. J. Ryser (1961) "Widths and heights of (0, 1)-matrices", ''Canadian Journal of Mathematics'' 13: 239–55.
* [[L. R. Ford Jr.]] & D. R. Fulkerson (1962) § 2.12 "Matrices composed of 0's and 1's", pages 79 to 91 in ''Flows in Networks'', [[Princeton University Press]] {{mr|id=0159700}}
{{refend}}
▲== Спољашње везе ==
{{Commons category|Equivalence relation}}
* {{springer|title=Equivalence relation|id=p/e036030}}
* [[Alexander Bogomolny|Bogomolny, A.]], "[http://www.cut-the-knot.org/blue/equi.shtml Equivalence Relationship]" [[cut-the-knot]]. Accessed 1 September 2009
* [https://web.archive.org/web/20130509233055/http://planetmath.org/equivalencerelation Equivalence relation] at PlanetMath
* {{OEIS el|1=A231428|2=Binary matrices representing equivalence relations}}
▲* [http://www.cut-the-knot.org/blue/equi.shtml Релације еквиваленције]
{{Authority control}}
[[Категорија:Математичке релације]]
| |||