CSCI 3155: Recitation # 7Set Theory for Understanding ProgrammingLanguagesOctober 15, 20031 Basic ConceptsAs noted in the previous worksheet, Set Theory is a fundamental part of modernmathematics; it also is one of the most frequently used mathematical theories inComputer Science. To a limited extent, we’ve already observed its usefulness inour discussions on grammars and the languages they generate; another examplewhere they are useful is in modelling data types.There are many ways to explain set theory; in here, we choose the approachof defining it (informally) through binary relations.1.1 RelationsA binary relation between two mathematical objects is usually written as aninfix symbol, such as (<). For example, for the mathematical objects 1 and 2,we can validly state 1 < 2; however, the claim 2 < 1 would be false. We callsuch a relation “binary” because it is between precisely two objects; while it iseasily possible to define relations of arbitrary arity (meaning that they relatearbitrarily many mathematical objects to each other), we will stick to binaryones here.Set Theory provides one fundamental binary relation it is centered on: The“is-element-of” relation, usually written (∈). For example, if N is the set ofnatural numbers, we can validly claim 1 ∈ N, whereas apple ∈ N would not betrue.Another example would be a set T with the following defining property:x ∈ T if and only if x ∈ N and 0 ≤ x ≤ 9and now discuss whether ele ments are contained in it, e.g. whether 7 ∈ T (def-initely true) or 11 ∈ T (definitely not true). In some sets, such as the set Pof all prime numbers in existance (an infinite set), actually checking whetherthis is true is very hard computationally; we know that 5 ∈ P, but what about1147710487433? Worse, there are some infinite sets for which checking member-ship is impossible in the general case.Set theory also makes use of another binary relation, the “is-subset-of” re-lation1, written (⊆). We can define this as follows2:S ⊆ T if and only if, for any x ∈ S, x ∈ T holds.So, considering our earlier examples, we can now state the following:• P ⊆ N• T ⊆ N• N ⊆ N• T * NWe usually strike through relations to explain that they do not hold, e.g. 4 /∈ P.In some cases , it may be useful to talk about the equality of two sets S andT . The definition for set equality is as follows:S = T ⇐⇒ (S ⊆ T ) and (T ⊆ S)(where A ⇐⇒ B means that A is true if and only if B is true, in turn meaningthat it also is false if and only if B is false.)1.1.1 SummaryWe have introduced the binary relations (∈) and (⊆), and their inverted counter-parts, ( /∈) and (*). From their definition, we see that, for any two mathematicalobjects A and B, we always have exactly one of A ∈ B or A /∈ B, but not bothat the same time. The same holds for A ⊆ B and A * B. Furthermore, wehave defined set equality (=) as mutual set inclusion.1.1.2 Relations to data typesWe can think of certain sets as being mathematical models for data types. Forexample, some languages, such as Haskell, allow integral numb e rs of arbitrarysize to be represented; for these, we can think of Z, the set of all integral numbers(including the non-negative ones), as being a good model. The general approachfor a given type is to determine the set of all values a variable of that type cantake, and use this as the type’s mathematical model.As an example, the subrange type C3 = [0 TO 3] can be modelled by aset C3= {0, 1, 2, 3}; the subrange typ e C1 = [0 TO 1] by the set C1= {0, 1}1A more precise name would be “is-subset-of-or-equal-to”. There also is a relation for strictor true subsets which excludes the set itself, but we do not consider this here.2While there are compact mathematical languages to express statemtents like the one here,it turns out that almost anything we can unambiguously write in English can be translatedinto the more popular of these.2(subsection 1.2.1 explains this notation for those who are unfamiliar with curlybraces).As we can see, C1⊆ C3– translated back into programming languages, thismeans that any value of type C1 is also a value of type C3. As it turns out, thisworks in a much more general way, so that A ⊆ B for any A and B means thatthe types they model are in a subtype relationship (please refer to the handouton subtyping for details).1.2 Set ConstructionWe have discussed three ways to talk about sets, but one important thing ismissing: We have not discussed how sets c an actually be constructed. SetTheory defines a number of ways in which this can be done, but its axioms onlygive us one pre-existing set:∅ = {}The empty set can be written in two ways; its defining properties are that, forwhichever X we pick out of the universe of mathematical objects, the followingproperties hold:• X /∈ ∅• X ⊆ ∅ in precisely one case, namely if X = ∅.Beyond that, there are a numb er of acceptable methods to construct sets, whichcan b e given arbitrary names (much as a record type be introduced in a pro-gramming language as soon as the need for it arises).1.2.1 Writing down all elementsThe easiest way to write down sets is to list all of their elements explicitly:lunch = {steak, potatoes, vegetables}In here, the set lunch has three elements, listed explicitly. But this does notindicate any special order about these elements– sets are completely unordered,meaning that, withlunch0= {vegetables, steak, potatoes}lunch00= {potatoes, steak, vegetables}it is true that lunch0= lunch, and also that lunch00= lunch, and thus lunch0=lunch00.Writing down all set elements has one notational disadvantage, though: Itseems as if we could include an element in a set more than once, i.e. S ={1, 1, 1} or similar. This does not make mathematical sense– the only thing weknow about this set is that 1 ∈ S (and that nothing else is in there); the “is-element-of” relation does not yield any mechanism for describing “numbers of3occurences”3. As such, there is no such thing as a list that contains an element“more than once”; either the element is contained, or it is not.Note the strong correspondence to enumeration types here– for any enumer-ation type, we also write down explicitly all the values we want variables of thattype to be able to assume as well, e.g. we could defineTYPE lunch type = {vegetables, steak, potatoes};in Modula-3, and use one of the sets above as a model for lunch type.1.2.2 Comprehending