Equivalence relations & classes.html (2054B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.0.3 (456341)"/><meta name="keywords" content="sets"/><meta name="altitude" content="-1.320224285125732"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-03-08 15:42:52 +0000"/><meta name="latitude" content="52.33416412555773"/><meta name="longitude" content="4.867464486884508"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-03-08 16:00:56 +0000"/><title>Equivalence relations & classes</title></head><body><div><b>Equivalence relation in V</b></div><div>relation R of type V × V that satisfies:</div><div><ul><li>reflexivity: x R x</li><li>transitivity: x R y ∧ y R z ➝ x R z</li><li>symmetry: x R y ➝ y R x</li></ul><div><br/></div></div><div><b>Equivalence classes</b></div><div>an equivalence relation ≡ in a set V partitions the set into equivalence classes</div><div><br/></div><div>equivalence class of p:</div><div>[p] = { x ∈ V: p ≡ x },<span> p ∈ V</span></div><div><span><br/></span></div><div><span>all elements of equivalence class relate to each other</span></div><div><span>elements of different equivalence classes are unrelated</span></div><div><span><br/></span></div><div><span>equivalence classes lead to a partition:</span></div><div><span>{ [p] : p ∈ V }</span></div><div><span><br/></span></div><div><span><b>Complete system of representatives</b></span></div><div>for ≡ in V is a set S ⊆ V that contains <i>exactly one </i>element from each equivalence class</div><div>in other words:</div><div><ol><li>every v ∈ V is equivalent to some s ∈ S</li><li>two different elements of S are not equivalent</li></ol><div><br/></div></div><div><br/></div><div><br/></div></body></html>