Unformatted text preview:

CS/Math 240: Introduction to Discrete Mathematics 2/1/2011Lecture 4 : SetsInstructor: Dieter van Melkebeek Scribe: Dalibor Zelen´yDRAFTLast time we discussed how to precisely express statements using propositions and predicates.We mentioned there was a connection between predicates and se t s in the sense that the elementsof the domain for which the predicate holds form a set. Today we discus s sets in great e r detail asthey are the bui l di n g blocks for other concepts such as relations, functions, and gr aphs.4.1 SetsWe start by defining what a set is.Definition 4.1. A set is a collecti on of elements from some domain. A set must be well-defined,which means that for every element of the domain, we can tell whether it belongs to the set or not.Let A be a set. We use the notation x ∈ A to mean that x is an element of A. When x is notan element of the set A, we write x /∈ A.The next definition captures the notion of containment.Definition 4.2. If all elements of s o me set A also belong to another set B, we say that A is asubset of B. Furthermore, if B contains s o me element that is not in A, we say that A is a strictsubset of B.We write A ⊆ B to mean that A is a subset of B, and use A ⊂ B to say that the containment isstrict. Notice that the set containment symbols ⊆ and ⊂ resemble the inequality symbols ≤ and <.This is not a coincidence. Both of these symbols express that one object is, in some sense, “smaller”than some other object. Saying A ⊂ B means that A is “less than” B in terms of containment.When we list elements of a set, the order in which we list them does not matter. Thus, the setB = {true, false} is the same as the set {false , true}. If or der does not matter, we use curly braceswhen listing the elements. We will use other notation to indicate that order of elements in somecollection matters.Sometimes t he set has too many elements for us to list them all. In most cases, the set hassome defining property. For example, t o describe the set A of all positive integers between 100 and1000 inclusive, we could write A = {x ∈ N | 100 ≤ x ≤ 1000} or A = {x | x ∈ N ∧ 100 ≤ x ≤ 1000}.The part of such definition before the | symbol tells us what an element is called, and the par t afterthe | symbol tells us what properties this element must have in order to be in the set. Some waysto read the | symbol is “such that” or “having the property that”. For example, we could read ourdescription of A as “the set of integers x such that 100 ≤ x ≤ 1000.”The sets A and B we just defined are examples of a finite sets. A finite set contains a finitenumber of elements, which means that we can write them all down, give n enough time.Let’s now write the set B, which i s sometimes called the Bool ean domain, i n two differentways. This may sound redundant, but it is often convenie nt to represent the e l e me nts in differentways. One instance where multiple rep re se ntations of sets are helpful is when we want to express1Lecture 4: Sets 4.1. Setsoperations on their elements in a different way. For example, suppose we represent t he Booleandomain using the set B′= {0, 1} whe r e 0 means fal se and 1 means true. The conjunction operat or∧ on elements of B corresponds to multiplication of elements of B′. Yet another way to representB i s as B′′= {−1, 1} where −1 r e pr es ents true and 1 represents false. Multiplication of elementsof B′now corresponds to exclusive or, which captures the noti on that exactly one of two values istrue. Thus, an exclusive or is different from the or we used e arl i e r because an or of two values istrue even if they are both true.Very often, we are inte r es te d in counting how many elements a set has. For example, we countedthe number of possible paths through a graph when analyzing the complexity of t he thread methodfor solving mazes. If P is the set of all possible paths through a maze, then we were asking howmany elements were in the set P .Definition 4.3. The cardinality of a set S is the number of distinct elements in S.We use the notation |S| to denote the cardinality of a set S.For e x ample, the cardinality of the Boolean domai n B defined earlier is 2 because B has twodistinct elements, true and false. Simi l ar l y, we have |B′| = |B′′| = 2.It may also happen that a set has no elements. If this is t he case, we cal l it an empty set, anduse the symbol ∅ to denote it. Note that |∅| = 0.4.1.1 Countable SetsWe said at the beginning of this course that di s cr e t e structures were the opposite of continuous.We also mentioned that we could somehow say that something is the first element, something isthe second element, and so on. We now make this notion more precise.Definition 4.4. A set is countable if there is an enumeration consisti ng exactly of all elements ofA. Every element of A appears at some point in this enumeration, and no element outside of Aappears in it.Think of an enumeration as a possibly infinite list of elements of A. This is pr obabl y bestexplained on examples.Example 4.1: Every finite set is countable. For example, one enumeration of the set B ={true, false} is: true, false. Another enumeration is: false, true. The properties of an enumer-ation are satisfied. Every element of B appeared in both of our enumerations, and no elementsoutside of B appeared in them. ⊠Example 4.2: The natural numbers N = {0, 1, 2, . . .} are countable. Note that the natural numbersare not a finit e set, which shows that cou ntable sets are not limited to finite sets. One enumerationof the natural numbers is 0, 1, 2, 3, . . . . Notice that number i appears in the (i + 1)-th posi t i on inthe enumeration, and, conversely, the i-th position in the enumerati on is i − 1 which is a naturalnumber. Thus, all natural numbers are listed in the enumeration, and no other elements are. Itfollows that the natural numbers are a countable set. ⊠Here we should warn the reader that one should be careful when using ellipsis (. . . ) as part ofa description of a list. It is important that the use of ellipsis is unambiguous and allows for onlyone logical way of continuing the sequence. Anothe r problem with ellipsis is if we use them at thebeginning of a list, as is illustrated in the next ex ampl e .Example 4.3: The integers Z = {. . . , −2, −1, 0, 1, …


View Full Document

UW-Madison CS 240 - Sets

Download Sets
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sets and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sets 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?