Релација еквиваленције

У математици, релација еквиваленције, која се често означава инфиксно симболима "~" или "≡" је бинарна релација на скупу X која је рефлексивна, симетрична, и транзитивна, то јест, за све елементе a, b, и c из X, следећи искази морају да ва же како би '~' била релација еквиваленције:

Рефлексивност: a ~ a
Симетричност: ако a ~ b онда b ~ a
Транзитивност: ако a ~ b и b ~ c онда a ~ c

Еквиваленција у контексту такве релације (која се тиче елемената скупа X), се разликује од концепта логичке еквиваленције (која се тиче логичких исказа). Релације еквиваленције се могу посматрати као груписање објеката који су слични у неком смислу.

Нотација

У литератури се користе различите ознаке да би се означило да су два елемента $a$ и $b$ скупа еквивалентна у односу еквиваленције $R;$ најчешћи су „ $a\sim b$ ” и „ $a \equiv b$ ”, који се користе када је $R$ имплицитно, а варијације „ $a\sim _{R}b$ ”, „ $a \equiv R b$ ”, или „ ${a\mathop {R} b}$ ” да се $R$ експлицитно. Нееквивалентност се може записати као „ $a ≁ b$ ” или „ $a\not \equiv b$ ”.

Дефиниција

Каже се да је бинарна релација $\,\sim \,$ на скупу $X$ релација еквиваленције, ако и само ако је рефлексивна, симетрична и транзитивна. То јест, за свако $a,b,$ и $c$ у $X:$

$a\sim a.$ (Рефлексивност)
$a\sim b$ ако и само ако је $b\sim a.$ (Симетрија)
Ако је $a\sim b$ и $b\sim c$ онда је $a\sim c.$ (Транзитивност)

$X$ заједно са релацијом $\,\sim \,$ се назива сетоид. Класа еквиваленције $a$ под $\,\sim ,$ означава се са $[a],$ и дефинисана је као $[a]=\{x\in X:x\sim a\}.$ ^[2]^[3]

Алгебарска структура

Велики део математике је заснован на проучавању еквиваленција и односа реда. Теорија решетки обухвата математичку структуру релација реда. Иако су релације еквиваленције једнако свеприсутне у математици као и релације реда, алгебарска структура еквиваленција није у истој мери позната као структура редова. Прва структура се ослања првенствено на теорију група и, у мањој мери, на теорију решетки, категорија и групоида.

Теорија група

Као што су релације поретка утемељене у уређеним скуповима, скупови затворени под упареним супремумом и инфимумом, односи еквиваленције су утемељени у партиционисаним скуповима, који су скупови затворени под бијекцијама који очувавају партициону структуру. Пошто све такве бијекције мапирају класу еквиваленције на саму себе, такве бијекције су такође познате као пермутације. Отуда пермутационе групе (такође познате као трансформационе групе) и сродни појам орбите бацају светло на математичку структуру релација еквиваленције.

Нека '~' означава релацију еквиваленције над неким непразним скупом A, који се назива универзум или основни скуп. Нека G означи скуп бијективних функција над A које презервирају партициону структуру A, што значи за свако $x\in A$ и $g\in G,g(x)\in [x].$ Тада важе следеће три повезане теореме:^[4]

~ дели A на класе еквиваленције. (Ово је Основна теорема релација еквиваленције, поменута горе);
С обзиром на партицију од A, G је трансформациона група под саставом, чије су орбите ћелије партиције;^[8]
С обзиром на трансформациону групу G над A, постоји релација еквиваленције ~ над A, чије класе еквиваленције су орбите G.^[9]^[10]

Све у свему, с обзиром на релацију еквиваленције ~ над A, постоји трансформациона група G над A чије су орбите класе еквиваленције A под ~.

Ова трансформациона групна карактеризација односа еквиваленције суштински се разликује од начина на који решетке карактеришу односе поретка. Аргументи операција теорије решетки обједињавају и спајају елементе неког универзума A. Аргументи композиције и инверзије операција групе трансформације су елементи скупа бијекција, A → A.

Прелазећи на групе у општем случају, нека је H подгрупа неке групе G. Нека је ~ релација еквиваленције на G, таква да је $a\sim b{\text{ ако и само ако }}ab^{-1}\in H.$ Класе еквиваленције ~— такође назване орбите деловања H на G— јесу десни косетови H у G. Заменом a и b добијају се леви косетови.^[11]

Категорије и групоиди

Нека је G скуп и нека „~” означава релацију еквиваленције над G. Тада се може формирати гроупоид који представља ову релацију еквиваленције на следећи начин. Објекти су елементи G, а за било која два елемента x и y из G постоји јединствени морфизам од x до y ако и само ако је $x\sim y.$

Предности посматрања релације еквиваленције као посебног случаја групноида укључују:

Док појам „слободне релације еквиваленције” не постоји, појам слободног групноида на усмереном графу постоји. Стога је смислено говорити о „презентацији релације еквиваленције”, тј. о презентацији одговарајућег групноида;
Скупови група, групне акције, скупови и релације еквиваленције могу се сматрати посебним случајевима појма групноида, што је тачке гледишта која сугерише бројне аналогије;
У многим контекстима је важно „квоцијентирање“, а тиме и одговарајуће релације еквиваленције које се често називају конгруенције. Ово доводи до појма унутрашњег групноида у категорији.^[12]

Примери релација еквиваленције

Очигледан пример релације еквиваленције је једнакост ("="), релација између елемената сваког скупа. Следи још примера:

„Рођен је истог дана као и“ на скупу свих људских бића.
„Је сличан“ или „је подударан“ на скупу свих троуглова.
Логичка еквиваленција исказа у логици.
Нека a, b, c, d ∈ 'N', и (a, b) и (c, d) су уређени парови. Релације (a, b)~(c, d) ако a+d = b+c, и (a, b)~(c, d) ако ad = bc, су релације еквиваленције, чијим класама еквиваленције се могу сматрати цели бројеви и позитивни рационални бројеви, редом.
„Је конгруентно по модулу n" за скуп целих бројева.
„Је паралелно“, на скупу афиних потпростора афиног простора.

Референце

^ Gunther Schmidt (2013). „6: Relations and Vectors”. Relational Mathematics. Cambridge University Press. стр. 91. ISBN 9780511778810. doi:10.1017/CBO9780511778810.
^ Weisstein, Eric W. „Equivalence Class”. mathworld.wolfram.com (на језику: енглески). Приступљено 2020-08-30.
^ „7.3: Equivalence Classes”. Mathematics LibreTexts (на језику: енглески). 2017-09-20. Приступљено 2020-08-30.
^ Rosen (2008), pp. 243–45. Less clear is §10.3 of Bas van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press.
^ Bas van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press: 246.
^ Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 22, Th. 6.
^ Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 24, Th. 7.
^
Proof.^[5] Let function composition interpret group multiplication, and function inverse interpret group inverse. Then G is a group under composition, meaning that $x\in A$ and $g\in G,[g(x)]=[x],$ because G satisfies the following four conditions:
- G is closed under composition. The composition of any two elements of G exists, because the domain and codomain of any element of G is A. Moreover, the composition of bijections is bijective;^[6]
- 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⁻¹, such that gg⁻¹ = I;
- Composition associates. f(gh) = (fg)h. This holds for all functions over all domains.^[7]
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 $A.\blacksquare$
^ Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 202, Th. 6.
^ Dummit, D. S., and Foote, R. M., 2004. Abstract Algebra, 3rd ed. John Wiley & Sons: 114, Prop. 2.
^ Related thinking can be found in Rosen (2008: chpt. 10).
^ Borceux, F. and Janelidze, G., 2001. Galois theories, Cambridge University Press, ISBN 0-521-80309-8

Литература

Brown, Ronald, 2006. 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 theory.
Higgins, P.J., 1971. Categories and groupoids. Van Nostrand. Downloadable since 2005 as a TAC Reprint.
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.
Avelsgaard, Carol (1989), Foundations for Advanced Mathematics, Scott Foresman, ISBN 0-673-38152-8
Devlin, Keith (2004), Sets, Functions, and Logic: An Introduction to Abstract Mathematics (3rd изд.), Chapman & Hall/ CRC Press, ISBN 978-1-58488-449-1
Maddox, Randall B. (2002), Mathematical Thinking and Writing, Harcourt/ Academic Press, ISBN 0-12-464976-9
Wolf, Robert S. (1998), Proof, Logic and Conjecture: A Mathematician's Toolbox, Freeman, ISBN 978-0-7167-3050-7
Sundstrom (2003), Mathematical Reasoning: Writing and Proof, Prentice-Hall
Smith; Eggen; St.Andre (2006), A Transition to Advanced Mathematics (6th изд.), Thomson (Brooks/Cole)
Schumacher, Carol (1996), Chapter Zero: Fundamental Notions of Abstract Mathematics, Addison-Wesley, ISBN 0-201-82653-4
O'Leary (2003), The Structure of Proof: With Logic and Set Theory, Prentice-Hall
Lay (2001), Analysis with an introduction to proof, Prentice Hall
Morash, Ronald P. (1987), Bridge to Abstract Mathematics, Random House, ISBN 0-394-35429-X
Gilbert; Vanstone (2005), An Introduction to Mathematical Thinking, Pearson Prentice-Hall
Fletcher; Patty, Foundations of Higher Mathematics, PWS-Kent
Iglewicz; Stoyle, An Introduction to Mathematical Reasoning, MacMillan
D'Angelo; West (2000), Mathematical Thinking: Problem Solving and Proofs, Prentice Hall
Cupillari, The Nuts and Bolts of Proofs, Wadsworth
Bond, Introduction to Abstract Mathematics, Brooks/Cole
Barnier; Feldman (2000), Introduction to Advanced Mathematics, Prentice Hall
Ash, A Primer of Abstract Mathematics, MAA
Brualdi, Richard A. (2004). Introductory Combinatorics (4th изд.). Pearson Prentice Hall. ISBN 0-13-100119-1.
Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. ISBN 0-12-622760-8.
Hogben, Leslie (2006), Handbook of Linear Algebra (Discrete Mathematics and Its Applications), Boca Raton: Chapman & Hall/CRC, ISBN 978-1-58488-510-8 , § 31.3, Binary Matrices
Kim, Ki Hang (1982), Boolean Matrix Theory and Applications, 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 (језик: маратхи)

Спољашње везе

Hazewinkel Michiel, ур. (2001). „Equivalence relation”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
Bogomolny, A., "Equivalence Relationship" cut-the-knot. Accessed 1 September 2009
Equivalence relation at PlanetMath
OEIS sequence A231428 (Binary matrices representing equivalence relations)
Релације еквиваленције

[GS-1] Gunther Schmidt (2013). „6: Relations and Vectors”. Relational Mathematics. Cambridge University Press. стр. 91. ISBN 9780511778810. doi:10.1017/CBO9780511778810.

[2] Weisstein, Eric W. „Equivalence Class”. mathworld.wolfram.com (на језику: енглески). Приступљено 2020-08-30.

[:0-3] „7.3: Equivalence Classes”. Mathematics LibreTexts (на језику: енглески). 2017-09-20. Приступљено 2020-08-30.

[4] Rosen (2008), pp. 243–45. Less clear is §10.3 of Bas van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press.

[5] Bas van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press: 246.

[6] Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 22, Th. 6.

[7] Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 24, Th. 7.

[8] Proof.^[5] Let function composition interpret group multiplication, and function inverse interpret group inverse. Then G is a group under composition, meaning that $x\in A$ and $g\in G,[g(x)]=[x],$ because G satisfies the following four conditions:
G is closed under composition. The composition of any two elements of G exists, because the domain and codomain of any element of G is A. Moreover, the composition of bijections is bijective;^[6]

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⁻¹, such that gg⁻¹ = I;

Composition associates. f(gh) = (fg)h. This holds for all functions over all domains.^[7]
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 $A.\blacksquare$

[9] G is closed under composition. The composition of any two elements of G exists, because the domain and codomain of any element of G is A. Moreover, the composition of bijections is bijective;^[6]

[10] Existence of identity function. The identity function, I(x) = x, is an obvious element of G;

[11] Existence of inverse function. Every bijective function g has an inverse g⁻¹, such that gg⁻¹ = I;

[12] Composition associates. f(gh) = (fg)h. This holds for all functions over all domains.^[7]

[9] Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 202, Th. 6.

[10] Dummit, D. S., and Foote, R. M., 2004. Abstract Algebra, 3rd ed. John Wiley & Sons: 114, Prop. 2.

[11] Related thinking can be found in Rosen (2008: chpt. 10).

[12] Borceux, F. and Janelidze, G., 2001. Galois theories, Cambridge University Press, ISBN 0-521-80309-8

[1]

[2]

[3]

[4]

[8]

[9]

[10]

[11]

[12]

[5]

[6]

[7]