September 3 * Partial Orders One way to identify a partial ordering is to prove that a relation is reflexive, transitive, and has no "nontrivial cycles". A "chain" in a binary relation R is a sequence (a1, ..., an) such that each (ai, ai+1) in R. If all ai are distinct and (an, a1) in R, the chain is also a "cycle". If n=1 the cycle is "trivial", otherwise the cycle is "nontrivial". Problem 1.4.8 a) Prove that if S is any collection of sets, then R_S = {(A,B): A,B in S and A<=B} is a partial order. To prove that R_S is a partial order it is sufficient to show that R_S is reflexive, transitive, and has no nontrivial cycles. Reflexive: A includes all of the elements of itself, so by definition of subset, A<=A. Transitive: Show that if A<=B and B<=C, then A<=C. If B<=C, then every element of B is also an element of C. Because A<=B, every element of A is an element of B which is also an element of C, so A<=C. No nontrivial cycles: for (a1, ..., an) to form a nontrivial cycle all ai must be distinct, (ai, ai+1) must be in R_S, and (an, a1) must be in R_S. Note that for ai<=ai+1, either ai must equal ai+1 or ai has fewer elements than ai+1. Since all of the ai components are distinct, we know that ai neq ai+1 so |a1| < |a2| < ... < |an|. By the transitive property of "<", |a1| < |an|, and thus (an, a1) cannot be in R_S. Thus R_S has no nontrivial cycles. b) Let S = 2**{1,2,3}. Draw directed graph representing the partial order defined in (a). What element or elements are minimal? A "minimal" element of a partial order R is an element a such that (b,a) in R only if b = a. We can spot minimal elements in the directed graph if there are no arrows pointing to a node or nodes in the graph except from themselves (these are minimal elements). Every finite partial order has at least one minimal element. One final note on binary relations: we can use the notation (a,b) in R or the "infix notation" aRb. * Closures Let D be a set, n>=0, and let R<=D**{n+1} be a (n+1)ary relation on D. D**n here means a group of size n where each component is an element of D. A subset B of D is said to be "closed under" relation R if b_{n+1} in B whenever b1, ..., bn in B and (b1, ..., b_{n+1}) in R. Any property of the form "the set B is closed under relations R1, ..., Rm" is called a "closure property" of B. The set of natural numbers is closed under "one less than". A closure property maps elements of a set onto an element of the same set. Functions can also have closures. If D is a set, n>=0, and f is a function from D**n to D, then a subset B of D is "closed under f" if f(b1, ..., bn) in B for all b1, ..., bn in B. The natural numbers are closed under addition. - Are odd integers closed under multiplication? Yes. The product of two odd integers is always an odd integer. - Are negative integers closed under subtraction? No. -5 - -8 = 3, which is not a negative integer. What is the minimal set, of which negative integers is a subset, which is closed under subtraction? Integers are closed under subtraction. - Are negative integers closed under multiplication? No. -5 * -8 = 40, which is not a negative integer. What is the minimal set, of which negative integers is a subset, which is closed under subtraction? Integers are closed under subtraction. If A<=D and P is a closure property defined by relations R1, ..., Rm on D, then there is a unique minimal set B, A<=B, and B has property P. B is the "closure" of A under relations R1, ..., Rm. In particular, the "reflexive, transitive closure" of a binary relation R <= AxA, notated R*, is the closure of R under relations Q = {((a,b), (b,c), (a,c)): a,b,c in A} transitive Q' = {((a,a)): a in A} reflexive Include the original relation pairs and all other ordered pairs transitively reachable from the original pairs. R = {(a,b), (b,c) (c,1), (1,3)} R* = {(a,b), (b,c), (c,1), (1,3), (a,c), (a,1), (a,3), (b,1), (b,3), (c,3)} R* = R v {(a,b): there is a chain in R from a to b} Similarly, R+ = {(a,b): there is a chain in R from a to b} R+ is the transitive closure of R. R+ need not be reflexive. * FINITE AND INFINITE SETS We know how to compare the size of finite sets A = {1,2,3}, B = {4,5,6,7}, |A| = 3, |B| = 4, |A| < |B| We know that if A<=B then |A| <= |B|. if AB. Remember this is one-to-one and onto, so the sets must have an equal number of elements. A set is finite if it is equinumerous with the set {1, 2, ..., n}, for a given natural number n. If A and {1, ..., n} are equinumerous, then the "cardinality" of A is n. The sets N and R are infinite, but they are not equinumerous. How can we distinguish between sizes of infinite sets? A set is "countably infinite" if it is equinumerous with N, and "countable" if it is finite or countably infinite. A set that is not countable is "uncountable". How do we prove that a set is countable? - define a bijection between the set and a known countably infinite set (often N is used for this purpose) - prove that the set is a subset of a known countably infinite set How can we prove that A = {x: x is even} is countable? A is a subset of N which is countably infinite. Key: you want to show that for any element bi in the set, you can visit the element in finite time (i steps) Consider a bijection f:N->B as a way of listing the elements of the countably infinite set B, where bi = f(i). Thus any element bi is listed on the ith step. If A is a subset of B, we can list the elements of A the same way as the elements of B, only omitting the elements not included in A. Show the "dovetailing" method for listing elements of a union of a finite number of countably infinite sets. Visit first element of first set, first element of second set, and so forth, then second element of each set, etc. a0 a1 | /| | / | b0 / b1 ... | / | |/ | c0 c1 Another example of dovetailing. Show union of countably infinite number of countability infinite sets is countably infinite. Try to define bijection between this set and N (define an ordering on the elements of the set such that element i of the set is visited on the ith step). Let us refer to the ith element from the jth set as (i,j). First round: visit one element from first set (0,0) Second round: visit second element from first set (0,1), then visit first element from second set (1,0) Third round: visit third element from first set (0,2), then visit second element from second set (1,1), then visit first element from third set (2,0) nth round: visit nth element of first set (0,n-1), then visit n-1st element of second set (0,n-2), then ..., then visit first element of the nth set (n-1,1) In each round we visit all pairs (i,j) s.t. i+j = n-1. In each round there is a finite number of elements to visit (because we visit one element of each set and there is a finite number of sets). Thus for any given element (x,y) we will visit the element in a finite amount of time. ...| 7| 6| Element 5| 4| 3| 2| 1| 0| +------------------- Show dovetailing 0 1 2 3 4 5 6 7 ... Set How can we use this method to show that the set of rational numbers is countably infinite? B = {x: x is rational}, x is of the form N+/N+, represent x as (numerator, denominator) - Interesting Example A program can be viewed as a function: INPUT -> OUTPUT, where I/O are represented a binary strings representing natural numbers. A program is thus f:N->N. Each such function f also suggests a program. How many such functions are there? f:N->{0,1} is smaller than f:N->N, let's consider that. There are as many f:N->{0,1} as there are elements in the power set of N. This is shown by the function f called the "characteristic function" of X (X represents a subset of N), f:N->{0,1}, defined as +--- f(n) = |1 if n in X |0 if n not in X +--- There are at least as many functions from N to N as |P(N)|. We know that P(N) is uncountable, so there are uncountably many functions for which we may want to write programs. Consider your favorite programming language. There are a finite number of symbols in the language. We can count all programs in this language by first alphabetizing the symbols, listing all programs of length on in order, then of length two in order, etc. Such a listing would ultimately contain any program that can be written in the language. This the set of all programs that can be written in the language is countable. Because programs are countable and the functions they generate are uncountable, there are more functions than program and there are some problems you might want to solve for which no program can be written in a given programming language. Can these ever be solved? We will address some of these questions throughout the semester.