Binary Relations - Stanford University
Binary RelationsPart One
Outline for Today Binary Relations Equivalence Relations Reasoning about connections betweenobjects.Reasoning about clusters.A Fundamental Theorem How do we know we have the “right”defnition for something?
Relationships In CS103, you've seen examples of relationships between sets:A B between numbers:x y x ₖ yx ybetween people:p loves q Since these relations focus on connectionsbetween two objects, they are called binaryrelations. The “binary” here means “pertaining to two things,”not “made of zeros and ones.”
What exactly is a binary relation?
RabaRb
RabaR̸b
Binary Relations A binary relation over a set A is a predicateR that can be applied to pairs of elementsdrawn from A.If R is a binary relation over A and it holds forthe pair (a, b), we write aRb.3 3 5 7Ø ℕIf R is a binary relation over A and it does nothold for the pair (a, b), we write aR̸b.4 34 3ℕ Ø
Properties of Relations Generally speaking, if R is a binary relation overa set A, the order of the operands is signifcant. For example, 3 5, but 5 3.In some relations order is irrelevant; more on thatlater.Relations are always defned relative to someunderlying set. It's not meaningful to ask whether 15, forexample, since is defned over sets, not arbitraryobjects.
Visualizing Relations We can visualize a binary relation R over a set A bydrawing the elements of A and drawing a line betweenan element a and an element b if aRb is true.Example: the relation a b (meaning “a divides b”) overthe set {1, 2, 3, 4} looks like this:4231
Visualizing Relations We can visualize a binary relation R over a set A bydrawing the elements of A and drawing a line betweenan element a and an element b if aRb is true.Example: the relation a b over the set {1, 2, 3, 4}looks like this:4231
Visualizing Relations We can visualize a binary relation R over a set A bydrawing the elements of A and drawing a line betweenan element a and an element b if aRb is true.Example: the relation a b over the set {1, 2, 3, 4}looks like this:4231
Visualizing Relations We can visualize a binary relation R over a set A bydrawing the elements of A and drawing a line betweenan element a and an element b if aRb is true.Example: below is some relation over {1, 2, 3, 4} that'sa totally valid relation even though there doesn'tappear to be a simple unifying rule.4231
lationrelationRRoveroverthethesetset{1,{1,2,2, , nrelationR?R?A.A. xRyxRy ifif xx 33andandyy 55B.B. xRyxRy ifif yy xx 22C.C. yRxyRx ifif yy xx 22D.D. RR 2 2E.E. NoneNoneofofthesetheseF.F. thenthenA,A,B,B,C,C,D,D,E,E,ororF.F.
Capturing Structure
Capturing Structure Binary relations are an excellent way forcapturing certain structures that appear incomputer science.Today, we'll look at one of them(partitions), and next time we'll seeanother (prerequisites).Along the way, we'll explore how to writeproofs about defnitions given in frst-orderlogic.
Partitions
Partitions A partition of a set is a way of splitting the setinto disjoint, nonempty subsets so that everyelement belongs to exactly one subset. Two sets are disjoint if their intersection is theempty set; formally, sets S and T are disjointif S T Ø.Intuitively, a partition of a set breaks the setapart into smaller pieces.There doesn't have to be any rhyme or reason towhat those pieces are, though often there is one.
Partitions and Clustering If you have a set of data, you can oftenlearn something from the data by fndinga “good” partition of that data andinspecting the partitions. Usually, the term clustering is used in dataanalysis rather than partitioning.Interested to learn more? Take CS161 orCS246!
What's the connection between partitionsand binary relations?
a A. aRa a A. b A. (aRb bRa) a A. b A. c A. (aRb bRc aRc)
Refexivity Some relations always hold from any element toitself.Examples: x x for any x. A A for any set A. x ₖ x for any x.Relations of this sort are called refexive.Formally speaking, a binary relation R over a set A isrefexive if the following frst-order statement is true: a A. aRa(“Every element is related to itself.”)
Refexivity Visualized a A. aRa(“Every element is related to itself.”)
ortextCS103to22333oncetojoin,then0,1,text CS103 to 22333 once to join, then 0, e?R,R,,,,,,, a A. aRa(“Every element is related to itself.”)
ttrue.true. a A. aRa(“Every element is related to itself.”)
dualindividualobjects.objects. a ?. aa
Symmetry In some relations, the relative order of the objectsdoesn't matter.Examples: If x y, then y x. If x ₖ y, then y ₖ x.These relations are called symmetric.Formally: a binary relation R over a set A is calledsymmetric if the following frst-order statement is trueabout R: a A. b A. (aRb bRa)(“If a is related to b, then b is related to a.”)
Symmetry Visualized a A. b A. (aRb bRa)(“If a is related to b, then b is related to a.”)
Is This Relation Symmetric?ba a A. b A. (aRb bRa)(“If a is related to b, then b is related to a.”)
oin,thenthenYYororN.N. a A. b A. (aRb bRa)(“If a is related to b, then b is related to a.”)
Transitivity Many relations can be chained together. Examples: If x y and y z, then x z. If R S and S T, then R T. If x ₖ y and y ₖ z, then x ₖ z.These relations are called transitive.A binary relation R over a set A is called transitive if thefollowing frst-order statement is true about R: a A. b A. c A. (aRb bRc aRc)(“Whenever a is related to b and b isrelated to c, we know a is related to c.)
Transitivity Visualized a A. b A. c A. (aRb bRc aRc)(“Whenever a is related to b and b isrelated to c, we know a is related to c.)
Is This Relation Transitive? a A. b A. c A. (aRb bRc aRc)(“Whenever a is related to b and b isrelated to c, we know a is related to c.)
,join,thenthenYYororN.N. a A. b A. c A. (aRb bRc aRc)(“Whenever a is related to b and b isrelated to c, we know a is related to c.)
Is This Relation Transitive?abc a A. b A. c A. (aRb bRc aRc)(“Whenever a is related to b and b isrelated to c, we know a is related to c.)
Equivalence Relations An equivalence relation is a relationthat is refexive, symmetric andtransitive.Some examples: x y x ₖ y x has the same color as y x has the same shape as y.
Binary relations give us a commonlanguage to describe commonstructures.
Equivalence Relations Most modern programming languages include somesort of hash table data structure. Java: HashMap C : std::unordered map Python: dictIf you insert a key/value pair and then try to look up akey, the implementation has to be able to tell whethertwo keys are equal.Although each language has a diferent mechanism forspecifying this, many languages describe them insimilar ways.
Equivalence Relations“The equals method implements an equivalencerelation on non-null object references: It is refexive: for any non-null reference value x,x.equals(x) should return true.It is symmetric: for any non-null reference values x andy, x.equals(y) should return true if and only ify.equals(x) returns true.It is transitive: for any non-null reference values x, y,and z, if x.equals(y) returns true and y.equals(z) returnstrue, then x.equals(z) should return true.”Java 8 Documentation
Equivalence Relations“Each unordered associative container isparameterized by Key, by a function object typeHash that meets the Hash requirements(17.6.3.4) and acts as a hash function forargument values of type Key, and by a binarypredicate Pred that induces an equivalencerelation on values of type Key. Additionally,unordered map and unordered multimap associatean arbitrary mapped type T with the Key.”C 14 ISO Spec, §23.2.5/3
Time-Out for Announcements!
Interpreting your Pset 1 )(92.5%)(92.5%)
Research Info Session CURIS (Undergraduate ResearchInstitute “in” CS—har har har) is asummer research experience in our dept Unbelievable cutting-edge projects See if grad school might be of interest Learn more:Tuesday, 1/30 at 5:30pm in Gates 219
Back to CS103!
Equivalence Relation Proofs Let's suppose you've found a binaryrelation R over a set A and want to provethat it's an equivalence relation.How exactly would you go about doingthis?
An Example Relation Consider the binary relation defned over the set ℤ:a b a b is evenSome examples:0 4 if1 92 65 5Turns out, this is an equivalence relation! Let's see how toprove inggivingaarule,rule,likelikethis:this:a bififsomea g“if”ratherthan“if”here,Although we're using “if” rather than “if” fordetails.details.
What properties must have to be anequivalence relation?RefexivitySymmetryTransitivityLet's prove each property independently.
a bifa b is evenLemma 1: The binary relation is refexive.Proof: Consider an arbitrary a ℤ. We need toprove that a a. From the defnition of the relation, this means that we need to prove thatisis thea a isWhateven.Whatthe formalformal defiitioidefiitioi ofof refexivity?refexivity?To see this, notice that a a 2a, so the sum a a a ℤ.aa aa aℤ. can be written as 2k for some integer k (namely,a),Therefore,so a a iswe'lleven.Therefore,a aholds,aschooseaiarbitraryiitegera,Therefore, we'll choose ai arbitrary iiteger a, theitheirequired. gogo proveprove thatthat aa aa.
a bifa b is evenLemma 1: The binary relation is refexive.Proof: Consider an arbitrary a ℤ. We need toprove that a a. From the defnition of the relation, this means that we need to prove thata a is even.To see this, notice that a a 2a, so the sum a acan be written as 2k for some integer k (namely,a), so a a is even. Therefore, a a holds, asrequired.
a bifa b is evenLemma 2: The binary relation is symmetric.Proof: Consider any integers a and b where a b.We need to show that b proof?Since a b, we know that a b is even. BecauseA.Consideranyaaandwillprovea bandA.a bConsideranyintegersintegersandb.b.WeWewillb aproveisa bandb a.b a. b a,thismeansthateven.SinceB.Pick a ℤand b ℤ.Wewillprovea b b a.B. Pick a ℤ and b ℤ. We will prove a b b a.is even,we knowasb a.required. C.Consideranyaaandwherea bC.b aConsideranyintegersintegersandbbthatwhereb a,a bandandb a.D.D. ConsiderConsideranyanyintegerintegeraawherewherea a.a a.E.Therelation issymmetricifforE. The relation is symmetric if foranyanya,a,bb ℤ,ℤ,wewehavehavea ba b b a.b a.F.F. Consideranyintegersaandbwherea b.Wewillproveb a.Consider any integers a and b where a b. We will prove b in,join,thenthenA,A,B,B,C,C,D,D,E,E,ororF.F.
a bifa b is evenLemma 2: The binary relation is symmetric.Proof: Consider any integers a and b where a b.We need to show that b a.Since a b, we know that a b is even. BecauseWhattheformalofsymmetry?What isisthemeansformal defiitioidefiitioiofissymmetry?a b b a,thisthat b aeven. Sinceb a is even, we know that b a, as required. a a ℤ.ℤ. b b ℤ.ℤ.(a(a bb bb a)a)Therefore,Therefore, we'llwe'll choosechoose arbitraryarbitrary iitegersiitegers aa aidaidbb wherewhere aa bb,, theithei proveprove thatthat bb aa.
a bifa b is evenLemma 2: The binary relation is symmetric.Proof: Consider any integers a and b where a b.We need to show that b a.Since a b, we know that a b is even. Becausea b b a, this means that b a is even. Sinceb a is even, we know that b a, as required.
a bifa b is evenLemma 3: The binary relation is transitive.Proof: Consider arbitrary integers a, b and c where a b andb c. We need to prove that a c, meaning that we need toshow that a c is even.Since a b and b c, we know that a b and b c are even.This means there are integers k and m where a b 2kand b c 2m. Notice thatWhatformaldefiitioioftraisitivity?What isis thetheformaldefiitioiof(a b) (b c) 2k traisitivity?2m.Rearranging,weseethat a ℤ. b ℤ. c a ℤ. b ℤ. c ℤ.ℤ.(a(a bb bb cc aa c)c)a c 2b 2k 2m,soTherefore,Therefore, we'llwe'll choosechoose arbitraryarbitrary iitegersiitegers aa,, bb,, aidaid ccwherebb aidcc,,–theiprovethatwhere aa aid 2mtheiprovethat aa cc.a c 2kbb 2b 2(k m–b).So there is an integer r, namely k m–b, such thata c 2r. Thus a c is even, so a c, as required.
a bifa b is evenLemma 3: The binary relation is transitive.Proof: Consider arbitrary integers a, b and c where a b andb c. We need to prove that a c, meaning that we need toshow that a c is even.Since a b and b c, we know that a b and b c are even.This means there are integers k and m where a b 2kand b c 2m. Notice that(a b) (b c) 2k 2m.Rearranging, we see thata c 2b 2k 2m,soa c 2k 2m – 2b 2(k m–b).So there is an integer r, namely k m–b, such thata c 2r. Thus a c is even, so a c, as required.
An Observation
a bifa b is evenLemma 1: The binary relation is refexive.Proof: Consider an arbitrary a ℤ. We need toprove that a a. From the defnition of the relation, this means that we need to prove thata a is even.To see this, notice that a a 2a, so the sum a acan be written as 2k for some integer k (namely,a), so a a is even. Therefore, a a holds, asrequired. TheThe formalformal defiitioidefiitioi ofof refexivityrefexivityisis giveigivei iiii frst-orderfrst-order logic,logic, butbutthisthis proofproof doesdoes notnot containcontain anyanyfrst-orderfrst-order logiclogic symbols!symbols!
a bifa b is evenLemma 2: The binary relation is symmetric.Proof: Consider any integers a and b where a b.We need to show that b a.Since a b, we know that a b is even. Becausea b b a, this means that b a is even. Sinceb a is even, we know that b a, as required. TheThe formalformal defiitioidefiitioi ofof symmetrysymmetryisis giveigivei iiii frst-orderfrst-order logic,logic, butbutthisthis proofproof doesdoes notnot containcontain anyanyfrst-orderfrst-order logiclogic symbols!symbols!
a bifa b is evenLemma 3: The binary relation is transitive.Proof: Consider arbitrary integers a, b and c where a b andb c. We need to prove that a c, meaning that we need toshow that a c is even.Since a b and b c, we know that a b and b c are even.This means there are integers k and m where a b 2kand b c 2m. Notice that(a b) (b c) 2k 2m.Rearranging, we see thata c 2b 2k 2m,soTheformaldefiitioia c 2k 2m– 2b 2(k m–b).Theformaldefiitioi ofof traisitivitytraisitivityisis giveigivei iiii frst-orderfrst-order logic,logic, butbutnamelyk m–b,suchthatthisthis proofproof doesdoes notnot containcontain anyanySo there is an integer r,a c 2r. Thus a c is even, so a c, as required. frst-orderfrst-order logiclogic symbols!symbols!
First-Order Logic and Proofs First-order logic is an excellent tool for givingformal defnitions to key terms.While frst-order logic guides the structure ofproofs, it is exceedingly rare to see frst-orderlogic in written proofs.Follow the example of these proofs: Use the FOL defnitions to determine what to assumeand what to prove.Write the proof in plain English using the conventionswe set up in the frst week of the class.Please, please, please, please, pleaseinternalize the contents of this slide!
Binary Relations A binary relation over a set A is a predicate R that can be applied to pairs of elements drawn from A. If R is a binary relation over A and it holds for the pair (a, b), we write aRb.3 3 5 7 Ø ℕ If R is a binary relation over A and it does not hold
Binary prices Binary prices rautmann (2013 Binary no price Epstein (2002 Binary prices al. (2014 Binary maximis- seek- er- t al. (2010 Binary individ- price al. 2014 Binary prices Binary sset prices Halevy (2019 Auction y Binary diffi- sig- nals Liang (2019 sm y Binary erreac- news al. (2012 Auction y Binary under- signals et y Gaussian erreac .
SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity Qingyuan Zhao Stanford University qyzhao@stanford.edu Murat A. Erdogdu Stanford University erdogdu@stanford.edu Hera Y. He Stanford University yhe1@stanford.edu Anand Rajaraman Stanford University anand@cs.stanford.edu Jure Leskovec Stanford University jure@cs.stanford .
2D Membership functions : Binary fuzzy relations (Binary) fuzzy relations are fuzzy sets A B which map each element in A B to a membership grade between 0 and 1 (both inclusive). Note that a membership function of a binary fuzzy relation can be depicted with a 3D plot. (, )xy P Important: Binary fuzzy relations are fuzzy sets with two dimensional
Computer Science Stanford University ymaniyar@stanford.edu Madhu Karra Computer Science Stanford University mkarra@stanford.edu Arvind Subramanian Computer Science Stanford University arvindvs@stanford.edu 1 Problem Description Most existing COVID-19 tests use nasal swabs and a polymerase chain reaction to detect the virus in a sample. We aim to
Domain Adversarial Training for QA Systems Stanford CS224N Default Project Mentor: Gita Krishna Danny Schwartz Brynne Hurst Grace Wang Stanford University Stanford University Stanford University deschwa2@stanford.edu brynnemh@stanford.edu gracenol@stanford.edu Abstract In this project, we exa
Stanford University Stanford, CA 94305 bowang@stanford.edu Min Liu Department of Statistics Stanford University Stanford, CA 94305 liumin@stanford.edu Abstract Sentiment analysis is an important task in natural language understanding and has a wide range of real-world applications. The typical sentiment analysis focus on
Binary compounds are those that are composed of only two elements. There are three types of binary compounds: binary covalent compounds, binary ionic compounds and binary acids. Examples of binary covalent compounds include water (H 2O), carbon monoxide (CO), and carbon dioxide CO 2. The naming convention for bina
ANALISIS PENERAPAN AKUNTANSI ORGANISASI NIRLABA ENTITAS GEREJA BERDASARKAN PERNYATAAN STANDAR AKUNTANSI KEUANGAN NO. 45 (STUDI KASUS GEREJA MASEHI INJILI DI MINAHASA BAITEL KOLONGAN) KEMENTERIAN RISET TEKNOLOGI DAN PENDIDIKAN TINGGI POLITEKNIK NEGERI MANADO – JURUSAN AKUNTANSI PROGRAM STUDI SARJANA TERAPAN AKUNTANSI KEUANGAN TAHUN 2015 Oleh: Livita P. Leiwakabessy NIM: 11042103 TUGAS AKHIR .
