```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.
```