Relacija ekvivalencije

U matematici, relacija ekvivalencije, koja se često označava infiksno simbolima "~" ili "≡" je binarna relacija na skupu X koja je refleksivna, simetrična, i tranzitivna, to jest, za sve elemente a, b, i c iz X, sledeći iskazi moraju da va že kako bi '~' bila relacija ekvivalencije:

Refleksivnost: a ~ a
Simetričnost: ako a ~ b onda b ~ a
Tranzitivnost: ako a ~ b i b ~ c onda a ~ c

Ekvivalencija u kontekstu takve relacije (koja se tiče elemenata skupa X), se razlikuje od koncepta logičke ekvivalencije (koja se tiče logičkih iskaza). Relacije ekvivalencije se mogu posmatrati kao grupisanje objekata koji su slični u nekom smislu.

Notacija[uredi | uredi izvor]

U literaturi se koriste različite oznake da bi se označilo da su dva elementa $a$ i $b$ skupa ekvivalentna u odnosu ekvivalencije $R;$ najčešći su „ $a\sim b$ ” i „ $a \equiv b$ ”, koji se koriste kada je $R$ implicitno, a varijacije „ $a\sim _{R}b$ ”, „ $a \equiv R b$ ”, ili „ ${a\mathop {R} b}$ ” da se $R$ eksplicitno. Neekvivalentnost se može zapisati kao „ $a ≁ b$ ” ili „ $a\not \equiv b$ ”.

Definicija[uredi | uredi izvor]

Kaže se da je binarna relacija $\,\sim \,$ na skupu $X$ relacija ekvivalencije, ako i samo ako je refleksivna, simetrična i tranzitivna. To jest, za svako $a,b,$ i $c$ u $X:$

$a\sim a.$ (Refleksivnost)
$a\sim b$ ako i samo ako je $b\sim a.$ (Simetrija)
Ako je $a\sim b$ i $b\sim c$ onda je $a\sim c.$ (Tranzitivnost)

$X$ zajedno sa relacijom $\,\sim \,$ se naziva setoid. Klasa ekvivalencije $a$ pod $\,\sim ,$ označava se sa $[a],$ i definisana je kao $[a]=\{x\in X:x\sim a\}.$ ^[2]^[3]

Algebarska struktura[uredi | uredi izvor]

Veliki deo matematike je zasnovan na proučavanju ekvivalencija i odnosa reda. Teorija rešetki obuhvata matematičku strukturu relacija reda. Iako su relacije ekvivalencije jednako sveprisutne u matematici kao i relacije reda, algebarska struktura ekvivalencija nije u istoj meri poznata kao struktura redova. Prva struktura se oslanja prvenstveno na teoriju grupa i, u manjoj meri, na teoriju rešetki, kategorija i grupoida.

Teorija grupa[uredi | uredi izvor]

Kao što su relacije poretka utemeljene u uređenim skupovima, skupovi zatvoreni pod uparenim supremumom i infimumom, odnosi ekvivalencije su utemeljeni u particionisanim skupovima, koji su skupovi zatvoreni pod bijekcijama koji očuvavaju particionu strukturu. Pošto sve takve bijekcije mapiraju klasu ekvivalencije na samu sebe, takve bijekcije su takođe poznate kao permutacije. Otuda permutacione grupe (takođe poznate kao transformacione grupe) i srodni pojam orbite bacaju svetlo na matematičku strukturu relacija ekvivalencije.

Neka '~' označava relaciju ekvivalencije nad nekim nepraznim skupom A, koji se naziva univerzum ili osnovni skup. Neka G označi skup bijektivnih funkcija nad A koje prezerviraju particionu strukturu A, što znači za svako $x\in A$ i $g\in G,g(x)\in [x].$ Tada važe sledeće tri povezane teoreme:^[4]

~ deli A na klase ekvivalencije. (Ovo je Osnovna teorema relacija ekvivalencije, pomenuta gore);
S obzirom na particiju od A, G je transformaciona grupa pod sastavom, čije su orbite ćelije particije;^[8]
S obzirom na transformacionu grupu G nad A, postoji relacija ekvivalencije ~ nad A, čije klase ekvivalencije su orbite G.^[9]^[10]

Sve u svemu, s obzirom na relaciju ekvivalencije ~ nad A, postoji transformaciona grupa G nad A čije su orbite klase ekvivalencije A pod ~.

Ova transformaciona grupna karakterizacija odnosa ekvivalencije suštinski se razlikuje od načina na koji rešetke karakterišu odnose poretka. Argumenti operacija teorije rešetki objedinjavaju i spajaju elemente nekog univerzuma A. Argumenti kompozicije i inverzije operacija grupe transformacije su elementi skupa bijekcija, A → A.

Prelazeći na grupe u opštem slučaju, neka je H podgrupa neke grupe G. Neka je ~ relacija ekvivalencije na G, takva da je $a\sim b{\text{ ако и само ако }}ab^{-1}\in H.$ Klase ekvivalencije ~— takođe nazvane orbite delovanja H na G— jesu desni kosetovi H u G. Zamenom a i b dobijaju se levi kosetovi.^[11]

Kategorije i grupoidi[uredi | uredi izvor]

Neka je G skup i neka „~” označava relaciju ekvivalencije nad G. Tada se može formirati groupoid koji predstavlja ovu relaciju ekvivalencije na sledeći način. Objekti su elementi G, a za bilo koja dva elementa x i y iz G postoji jedinstveni morfizam od x do y ako i samo ako je $x\sim y.$

Prednosti posmatranja relacije ekvivalencije kao posebnog slučaja grupnoida uključuju:

Dok pojam „slobodne relacije ekvivalencije” ne postoji, pojam slobodnog grupnoida na usmerenom grafu postoji. Stoga je smisleno govoriti o „prezentaciji relacije ekvivalencije”, tj. o prezentaciji odgovarajućeg grupnoida;
Skupovi grupa, grupne akcije, skupovi i relacije ekvivalencije mogu se smatrati posebnim slučajevima pojma grupnoida, što je tačke gledišta koja sugeriše brojne analogije;
U mnogim kontekstima je važno „kvocijentiranje“, a time i odgovarajuće relacije ekvivalencije koje se često nazivaju kongruencije. Ovo dovodi do pojma unutrašnjeg grupnoida u kategoriji.^[12]

Primeri relacija ekvivalencije[uredi | uredi izvor]

Očigledan primer relacije ekvivalencije je jednakost ("="), relacija između elemenata svakog skupa. Sledi još primera:

„Rođen je istog dana kao i“ na skupu svih ljudskih bića.
„Je sličan“ ili „je podudaran“ na skupu svih trouglova.
Logička ekvivalencija iskaza u logici.
Neka a, b, c, d ∈ 'N', i (a, b) i (c, d) su uređeni parovi. Relacije (a, b)~(c, d) ako a+d = b+c, i (a, b)~(c, d) ako ad = bc, su relacije ekvivalencije, čijim klasama ekvivalencije se mogu smatrati celi brojevi i pozitivni racionalni brojevi, redom.
„Je kongruentno po modulu n" за скуп целих бројева.
„Је паралелно“, на скупу афиних потпростора афиног простора.

Референце[uredi | uredi izvor]

^ 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$ $x\in A$ and $g\in G,[g(x)]=[x],$ $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$ $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

Literatura[uredi | uredi izvor]

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 izd.), 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 izd.), 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 izd.). 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 (jezik: marathi)

Spoljašnje veze[uredi | uredi izvor]

Hazewinkel Michiel, ur. (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)
Relacije ekvivalencije

[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]

Normativna kontrola
Državne	Nemačka Izrael Sjedinjene Države
Ostale	Enciklopedija Britanika 2