Relations

Better Representing WaterWorld We have been using propositions to represent our problem. This is not entirely natural; for instance the only way the rules recognize that locations a and b are near each other is because there are several axioms involving A-has-2 and B-unsafe, in just the right way to result in our idea of the concept "neigbhor". In fact, we had no way of mentioning about the location a directly; we only had propositions which dealt with its properties (whether or not it neighbored exactly two pirates, etc.). If writing a program about WaterWorld, our program should of course reflect our conception of the problem, and as it stands, our conception corresponds to having many many boolean variables named A-has-2, B-unsafe, etc. Even worse, the rules would be encodings of the hundreds of axioms. A long enouration of the axioms is probably not how you think of the rules -- when explaining the game to your friend, you probably say "if a location contains a 2, then two of its neighbors are pirates". (Rather than droning on for half an hour about how "if location a contains a two, then either location bis unsafe or ...".) And the current rules only pertained to a fixed-size board; inventing a new game played on a 50x50 grid would require a whole new set of rules! -- clearly not how we humans conceptualize the game! Relations are the way we'll improve this situation Later, introducing quantifiers later will finish our upgrade. We'll start by adding a way to determing if any two locations are adjacent: The relation neighbor will encode the board's geography as follows: neighbor( a, b ) is true, while neighbor( a, d ) is false. That is, neighbor is a function which takes in two locations, and returns either true or false. Showing a picture of the board is tantamount to specifying this function. Note that the function can represent an arbitrarily weird map, such as locations that look adjacent on the map but actually aren't, maps which wrap around (e.g. equivalent to playing on a round or toroidal planet), and a locations a with a tunnel connecting it to a location clear across the board (like the harrowing sub trip in The Phantom Menace, through the planet ..??..) Note that encoding this information lets us play on different size boards: we can have one rule, saying that if location a has zero, then any neighboring location is safe. Thus the exact details of the neighbor relation might change from game to game as we play on different boards (just as which locations are contain pirates changes from game to game). ...Which brings us to the next question: how to express the notion "location a is safe"? Again, we'll use a relation, but this time one which only takes one input: safe(a) is true if and only if ("iff") location a is safe. For a particular game of WaterWorld we are given a set of locations and we are given a binary relation to be used as neighbor. Hmm, for the WaterWorld gui, all locations are named, so the model has only named constants, blurring the line between the vocabulary and the model. [flesh out:] We like relations better because it helps separate the rules from the data (from the particular board). relation A binary relation is a function which takes in two elements of the domain, and returns true or false (indicating that those two have the desired relation, or that they don't). A unary relation takes in only one input instead of two. You can have ternary and quaternary relations, etc.; however any given relation has a fixed arity (number of inputs). How shall we encode concepts such as "location a has 3 dangerous neighbors", using relations? A good first guess might be to say we have a function which returns the number of pirates next to a given location. That is, "piratesNear(a) = 3". However, "piratesNear" doesn't qualify as a relation -- why not? To work around this, we could propose a binary relation along the lines of "piratesNear(a, 3) = true". This is better, but it requires our domain to be not only board locations, but also numbers (and, our axioms might suddenly need to include many axioms just about numbers, and other relations such as ">" Hmmm, what is the arity of >?) While this approach is feasible -- and ultimately might be what we want -- for now, let's stick with relations involving only locations, not numbers. Okay, the third time's the charm: we can implement concepts like "a neighbors three pirates" as shows3(a) being true. We'll have a seperate relation shows2; presumably shows2(a) is false on any board where shows3(a) is true.

Relations in other settings; Subsets For the domain of types-of-vegetables, the relation yummy is a useful one to know, when cooking. In case you weren't sure, yummy(brussel sprouts) = false, and yummy(carrots) = true. Supose we had a second relation, yucky. Is it conceivable that we could model a vegetable that's neither yucky nor yummy, using these relations? Sure! (Iceburg Lettuce is an example, even.) In fact, we could even have a vegetable which is both yummy and yucky -- radishes, perhaps!) A quick digression on a philosophical nuance: the domain for the above problem is not vegetables; it's types-of-vegetables. That is, we talk about whether or not carrots are yummy; this is different than talking the yumminess of whether the carrot i dropped under the couch yesterday, or the carrot underneath the chocolate sauce. In computer science, this often manifests itself as the difference between values and types of values -- that is, we distinguish between 3 and the set of all integers; we distinguish between particular carrots and the abstract idea of carrots. (Some languages even include types as values.) Philosophers enjoy debating how particular instances shape the abstract generalization, but for our purposes we'll take each both vegetables and types-of-vegetables as given. Unary relations correspond to subsets of the domain -- e.g., the set of yummy vegetables. Or, for instance, knowing the relation hasPirate is the same as knowing the set P = {locations containing pirates}. We might say the relation hasPirate is an "indicator function" for the set P -- given any location "loc", you can find out whether it's in P by knowing whether or not hasPirate(loc). (And vice versa, of course -- if you know exactly what's in the set P, you can predict what hasPirate will answer for any input.) Same concept, different representations. A relation with a whole website devoted to it is "has starred in a movie with". We'll call this relation hasStarredWith; the relevant domain is people. Some sample points in this relation: hasStarredWith(Ewan McGregor, Cameron Diaz) (as witnessed by the movie "beautiful things??", 199?) hasStarredWith(Cameron Diaz, John Cusack). One reason why the relation includes this pair is "Being John Malkovich" (1999). You can think of each actor being a "location", and one actor being "adjacent" to each other if they have ever starred in a movie together; two of these locations, even if not adjacent might have a multi-step path between them (e.g. there is path of length 3 from ... to ..., using the adjacencies just mentioned. (There is also a shorter path; can you think of it? The (in)famous Kevin Bacon game asks to find a shortest path from one location to the location Kevin Bacon. Make a guess, as to the longest shortest path leading from (some obscure) location to Kevin Bacon.) A binary relation is equivalent to a set of pairs -- You might have objected to the idea of the unary relation yummy, since different people have different tastes. How could you model this, with a binary relation? We can use the binary relation thinksIsYummy: In particular, thinksIsYummy(ian, brusselSprouts) = false, but thinksIsYummy(phokion, brusselSprouts ) = true, Use anchovies (domain = pizza toppings), instead?. What set are we using, as the domain for this? Really, the domain is the union of people and vegetables. So thinksIsYummy(radishes, brusselSprouts) is a valid thing to write down; it would be false. Note that if working with such a domain, having unary predicates isVegetable and isPerson. Ternary relations Note that propositions can be modeled by 0-ary relations.

Reasoning with Relations connectives follow the same rules as in propositional logic Proofs otherwise unchanged. Note that we might express our rules as "for any locations x and y, we have the following axiom: shows3(x), neighbor(x y) → ¬ safe(y)" Really, note that there's something else going on here: x and y are symbols which can represent any location: they are variables, whose value can be any element of the domain. side link: prolog, w/o mentioning quantifiers. Then, prolog; mentioning quantifiers.

Properties of Relations

Reflexive ..

Transitive ..

Symmetric ..

anti-Symmetric ..

Modeling functions with relations What about adding functions, to our language, in addition to relations? Well, we can just use relations to implement functions! (functions are a special case; what can you say about them? We'll get some tools later, to be able to express formally "the relation R is a (actually a disguised) function, iff ...".)