LATTICE THEORY Ordered Sets ^ PARTIAL ORDER ~ Let P be a set. A ___ on P is a binary relation \(\leq\) on P that, for all \(x, y, z \in P\), satisfies the three following conditions: (i) REFLEXIVITY - \(x \leq x\) (ii) ANTISYMMETRY - \(x \leq y\) and \(y \leq x\) implies \(x = y\) (iii) TRANSITIVITY - \(x \leq y\) and \(y \leq z\) implies \(x \leq z\) ^ RELATION ~ A ___ R on a set P is a subset \(R \subset P x P\) (cartesian product). If \(a, b \in R \to a R b\). (PARTIALLY) ORDERED SET (POSET) ~ A set P equipped with an order relation \(\leq\) is said to be an ___. (DISCRETE/(QUASI/PRE)) ORDER ~ On any set, = is an order called the ___. A relation \(\leq\) on a set P which is reflexive and transitive, but not necessarily antisymmetric is called a ___. &&An order relation \(\leq\) on P gives rise to a relation < of STRICT INEQUALITY: x < y in P if and only if \(x \leq y\) and \(x \neq y\).&& NON-COMPARABILITY ~ This is a binary relation \(\parallel\) used to denote ___. We write x \(\parallel\) y if x \(\nleq\) y and y \(\nleq\) x. INDUCED ORDER ~ This is when an order relation on a subset is inherited from its superset. Let P be an ordered set and let Q be a subset of P. Then Q inherits an order relation from P; given x, y ∈ Q, \(x \leq y\) in Q if and only if \(x \leq y\) in P. TOTALLY ORDERED SET ~ Let P be an ordered set. Then P is a ___ if, for all \(x, y \in P\), either \(x \leq y\) or \(y \leq x\). (This is another way of saying any two elements of P are comparable). &&Alternative names for a chain are LINEARLY ORDERED SET and CHAIN.&& &&On the other hand, the ordered set P is an antichain if \(x \leq y\) in P only if \(x = y\).&& &&Clearly, any subset of a chain/antichain is a chain/antichain.&& &&Let P be the n-element set {0, 1, ..., n - 1}. We write N to denote the chain obtained by giving P the order in which 0 < 1 < ... < n - 1 and \(\) for P regarded as an antichain. Any set S may be converted into an antichain \(\) by giving S the discrete order. ORDER-ISOMORPHIC ~ We say that two ordered sets P and Q are ___ and write \(P \cong Q\) if there exists a map \(\psi\) from P onto Q such that \(x \leq y\) in P if and only if \(\psi (x) \leq \psi (y)\) in Q. &&\(\psi\) is called an ORDER-ISOMORPHISM&& COVERED (COVERING RELATION) ~ Let P be an ordered set and let \(x, y \in P\). We say x is ___ by y, and write \(x \prec y y \succ x\) if \(x < y\) and \(x \leq z < y\) implies z = x. The latter condition is demanding that there be no element z of P with x < z < y. ORDER-ISOMORPHIC COVER-RELATION LEMMA ~ Let \(P\) and \(Q\) be finite ordered sets and let \(\varphi: P \to Q\) be a bijective map. Then the following are equivalent: 1. \(\varphi\) is an order-isomorphism. 2. \(x < y\) in \(P\) if and only if \(\varphi(x) < \varphi(y)\) in \(Q\). 3. \(x \prec y\) in \(P\) if and only if \(\varphi(x) \prec \varphi(y)\) in \(Q\). ORDER-ISOMORPHIC DIAGRAM PROPOSITION ~ Two finite ordered sets P and Q are order-isomorphic if and only if they can be drawn with identical diagrams. THE DUALITY PRINCIPLE ~ Given a statement \(\Phi\) about ordered sets which is true in all ordered sets, the dual statement \(\Phi^\delta\) is also true in all ordered sets. BOTTOM AND TOP OF AN ORDERED SET ~ Let P be an ordered set. We say P has a ___ if there exists \(\bot \in P\) with the property that \(\bot R x\) for all \(x \in P\). Dually, P has a ___ element if there exists \(\top \in P\) such that \(x R \top\) for all \(x \in P\). LIFTED ~ Given an ordered set P (with or without \(\bot\), form \(P_\bot\) (called P-___) as follows: Take an element \(0 \not \in P\) and define \(\leq\) on \(P_\bot := P \cup \{0\}\) by \(x \leq y\) if and only if \(x = 0\) or \(x \leq y\) in P. MAXIMAL AND MINIMAL ELEMENT ~ Let P be an ordered set and let \(Q \subseteq P\). Then \(a \in Q\) is a ___ of Q if \(a R x\) and \(x \in Q\) imply \(a = x\). On the other hand, a ___ of \(Q \subseteq P\) is defined dually, by reversing the order. &&We denote the set of maximal elements of Q by max Q. If Q (with order inherited from P) has a top element, \(\top_Q\), then Max Q = {_Q}; in this case \(\top_Q\) is called the MAXIMUM element of Q and we write \(\top_Q\) = max Q. Same thing but for the dual, you get minimal element and the minimum element \(\bot_Q\) = Min Q&& DISJOINT UNION OF ORDERED SETS ~ Suppose P and Q are disjoint ordered sets. The ___ \(P \cup Q\) of \(P\) and \(Q\) is the ordered set formed by defining \(x R y\) in \(P \cup Q\) if and only if either \(x, y \in P\) and \(x R y\) in \(P\) or \(x, y \in Q\) and \(x R y \) in \(Q\). A diagram for \(P \cup Q\) is formed by placing side by side diagrams for \(P\) and \(Q\). LINEAR SUM OF ORDERED SETS ~ Let P and Q be disjoint ordered sets. The ___ \(P \oplus Q\) is defined by taking the following order relation on \(P \cup Q : x R y \) if and only if \({ll}x, y \in P x R y \in P \\ x, y \in Q x R y \in Q \\ x \in P y \in Q\) &&We denote by \(M_n\) the sum \(1 \oplus n \oplus 1\).&& CARTESIAN PRODUCT OF ORDERED SETS ~ Let \(P_1, \ldots, P_n\) be ordered sets. The ___ \(P_1 \times \cdots \times P_n\) can be made into an ordered set by imposing the coordinatewise order defined by \((x_1, \ldots, x_n) R (y_1, \ldots, y_n) \iff (\forall i)x_i R y_i\) in \(P_i\). Given an ordered set \(P\), the notation \(P^n\) is used as shorthand for \(P \times \cdots \times P\). LEXICOGRAPHIC ORDER ~ This is a way to order the product of ordered sets P and Q. This is defined by \((x_1, x_2) R (y_1, y_2)\) if \(x_1 y_1\) or \((x_1 = y_1\) and \(x_2 R y_2)\). DOWN-SET/DECREASING SET/ORDER IDEAL ~ Let \(P\) be an ordered set and \(Q \subseteq P\). \(Q\) is a ___ if, whenever \(x \in Q\), \(y \in P\) and \(y R x\), we have \(y \in Q\). Basically, whenever P has an element that is related to something in Q, it is also in Q. It is nice to think about it as \(Q\) is "closed under going down". UP-SET/INCREASING SET/ORDER FILTER ~ Let \(P\) be an ordered set and \(Q \subseteq P\). \(Q\) is an ___ if, whenever \(x \in Q\), \(y \in P\), and \(x R y\), we have \(y \in Q\). Basically, whenever Q has an element that is related to something in P, it is also in Q. It is nice to think about it as \(Q\) is "closed under going up". PRINCIPAL OF X ~ Let \(P\) be an ordered set and \(x\) be an element \(x \in P\). This is the subset of \(P\) that is a downset in which every element is related to x. \(\downarrow x := \{y \in P \mid y R x\}\) ORDER-PRESERVING ~ Let (P, Q) and (S, R) be ordered sets. A map \(\varphi : P \mapsto S\) is ___ if \(x R y \implies \varphi(x) R \varphi(y)\). ORDER-EMBEDDING ~ Let (P, Q) and (S, R) be ordered sets. A map \(\varphi : P \mapsto S\) is ___ if and only if \(x R y \implies \varphi(x) R \varphi(y)\). POINT-WISE ORDER ~ Let f, g be functions which map sets X to Y. The ___ is defined such that \(f R g\) if and only if \(f(x) R g(x) \in Y \forall x \in X\). CATEGORY ~ A ___ is a class of objects and its morphisms, which are its structure-preserving maps, with an operation of composition of morphisms satisfying a set of natural conditions. Lattices and Complete Lattices Formal Concept Analysis Modular, Distributive, and Boolean lattices Representation: The Finite Case Congruences Complete Lattices and Galois Connections CPOs and Fixpoint Theorems Domains and Information Systems Maximality Principles Representation: The General Case
GENERAL PROBLEM SOLVING - There are three different levels in the problem solving process: STRATEGY ~ These are mathematical and psychological ideas for starting and pursuing problems. TACTICS ~ These are diverse mathematical methods that work in many different settings. TOOLS ~ These are narrowly focused techniques and "tricks" for specific situations. INVESTIGATION ~ Don't try to immediately solve the problem, but instead think about it on a less-focused level. This is when you start by familiarizing yourself with the problem and identifying what the problem is asking you to do. ARGUMENT ~ This is when you convince others of your discoveries. - A good problem solver doesn't give up. He also doesn't just stupidly keep banging his head against a wall, but instead _varies each attempt._ However, an important part of the problem solver's art is knowing when to give up. - _Just because a problem seems impossible does not mean that it is impossible. Never admit defeat after a cursory glance. Begin optimistically; assume that the problem can be solved. Only after several failed attempts should you try to prove impossibility. If you cannot do so, then do not admit defeat. Go back to the problem later._ - Avoid immediate declarations of impossibility; they are dishonest. CREATIVITY ~ This is the elusive receptiveness to new ideas. You should never claim that you "could never have thought of that," but instead think "Nice idea! It's similar to ones I've had. Let's put it to work." _Learn to shamelessly appropriate new ideas and make them your own._ * Many of the times, you are letting self-imposed, unnecessary restrictions limit your thinking. Ask yourself: "Am I imposing rules I don't need to? Can I change or bend the rules to my advantage?" THE FIRST STEP: ORIENTATION ~ These are things that must be done at the beginning of every problem: Read the problem carefully, Begin to classify, Identify the hypothesis and conclusion, brainstorm, and summarize. It's RIBS but there's a C after the R. 1. Read the problem carefully. Pay attention to details such as positive vs. negative, finite vs. infinite, etc. 2. Begin to classify - Is it a "to find" or a "to prove" problem? Is the problem similar to others you have seen? 3. Carefully identify the hypothesis and the conclusion. 4. Try some quick preliminary brainstorming * Think about convenient notation * Does a particular method of argument seem plausible? * Can you guess a possible solution? Trust your intuition! * Are there key words or concepts that seem important? For example, might prime numbers or perfect squares or infinite sequences play an important role? 5. Now that you've understood the problem, can you summarize the problem in its simplest terms? - After you have understood the problem, you may try one or more of the four basic "startup" strategies: penultimate step, get your hands dirty, wishful thinking, and make it easier. THE SECOND STEP: STRATEGIZING ~ These are next steps after orientation and understanding the problem. One of the following may provide insight into how to solve the problem: Get your hands dirty, Penultimate step, Wishful thinking, and Make it easier. It's GPMW (Gold Per Minute, Wealthy). GET YOUR HANDS DIRTY - This is a strategy where you plug in numbers into the problem and play around with them until you see a pattern. If you detect a pattern, try to figure out why the pattern is happening. PENULTIMATE STEP - This is a strategy usable after you find out what the desired conclusion of the problem is. Ask yourself, "What will yield the conclusion in a single step?" For example, if you want to prove that _A_ != _B_, perhaps you could try to show that A is always even and B is always odd. WISHFUL THINKING & MAKE IT EASIER ~ These are strategies where you ask yourself, "What is it about the problem that makes it hard?" Then, make the difficulty disappear. Temporarily avoiding the hard part of the problem could prove insightful on how to solve the harder parts. - _Time spent thinking about a problem is always time worth spent. Even if you seem to make no progress at all._ - _Don't skimp on experimentation! KEep messing around until you think you understand what is going on. Then mess around some more._ - Common Abbreviaions and Stylistic Conventions in Mathematics: 1. Most good mathematical statements start with clear statements of the hypothesis and conclusion. Ending arguments are usually marked with a symbol such as the following three: - QED ~ This means the Latin _quod erat demonstrandum_ ("which was to be demonstrated"), or the English "quite elegantly done." - AWD ~ This means "and we're done." - W^5 ~ This means "which was what we wanted." 2. Like ordinary exposition, mathematical arguments should be complete sentences with nouns and verbs. - COMMON MATHEMATICAL VERBS ~ These include equal to, not equal to, less than or equal to, greater than or equal to, less than, greater than, is an element of, is a subset of, implies, and is equivalent to. \[{l} = & \neq & \leq & \geq & < & > & \subset & \in & \implies & \iff \] 3. Complicated equations should always be displayed on a single line, and labeled if referred to later. \[^\infty e^{-x^2} dx = \] 4. Often, as you explore the penultimate step of an argument, you want to mark this off to your audience clearly. The abbreviation _TS_ and _ISTS_ ("to show" and "it is sufficient to show") are particularly useful for this purpose. 5. A nice bit of notation borrowed from computer science is slowly becoming more common in mathematics and it is ":=" for "is defined to be." For example, we can introduce the variable A as the sum of B and C through "A := B + C." Notice the colon distinguishes between the left and the right side of the expression, indicating which is the new variable. 6. A strictly formal argument may deal with many logically similar cases. Sometimes it is just as clear to single out one illustrative case or example. When this happens, we always alert the audience with _WLOG_ ("without loss of generality"). Just make sure that you really can argue the specific and truly prove the general. DEDUCTION / DIRECT PROOF ~ This is an argument that takes the form "If P, then Q" or "P -> Q" or "P implies Q." If you have isolated the penultimate step, then you have reduced the problem to the simple statement: If (penultimate step), then (conclusion). ARGUMENT BY CONTRADICTION ~ This is an argument that starts by assuming what you are trying to prove to be false and then showing that the assumption leads to a contradiction. MATHEMATICAL INDUCTION ~ This is an argument for proving assertion that are "indexed" by integers. Each assertion can be put in the form P(n) is true for all integers n >= n_0 where P(n) is a statement involving the integer n and n_0 is the "starting point." There are two forms of this: standard and strong. STANDARD INDUCTION ~ This is form of induction that starts by establishing the truth of P(n_0) (the base case). Then it assumes that P(n) is true for some arbitrary integer n, called the inductive hypothesis. Then it shows that the inductive hypothesis implies that P(n + 1) is also true. This is sufficient to prove P(n) for all integers n >= n_0 since P(n_0) is true and P(n_0 + 1) is also true. STRONG INDUCTION ~ This is a form of induction that starts by establishing the truth of P(n_0) (the base case). Then we can assume that for some n, all of the following are true: P(n_0), P(n_0 + 1), P(n_0 + 2), ..., P(n). Then we use this assumption to prove that P(n + 1) is true. Other important strategies: DRAW A PICTURE ~ This is strategy where you translate the problem into a picture to visualize how the problem works. - Instead of drawing a picture, it may be helpful to RECAST THE PROBLEM IN OTHER WAYS, such as with words, colors, or other branches of math. - It may also help to try to CHANGE YOUR POINT OF VIEW. Sometimes a problem is hard only because we chose the "wrong" point of view. Spending a few minutes searching for the "natural" point of view can prove insightful. SYMMETRY ~ This is a way of finding order in a problem. An object has this property if there are one or more non-trivial "actions" that leave the object unchanged. It is important because it gives you "free" information about the object. This property can be geometric (rotational and reflectional), algebraic (pairing), &&Actions that do this are called _symmetries_ of the object.&& THE EXTREME PRINCIPLE ~ This principle says that if possible, assume that the elements of your problem are "in order." Focus on the "largest" and "smallest" elements, as they may be constrained in interesting ways. It is often possible to use this principle with contradiction. THE PIGEONHOLE PRINCIPLE ~ This principle says that if you have more pigeons than pigeonholes, and you try to stuff the pigeons into the holes, then at least one hole must contain at least two pigeons. * Solving pigeonhole principle problems is often a three-part process: 1. Recognize that the problem might require the pigeonhole principle. 2. Figure out what the pigeons will be and what the holes must be. 3. After applying the pigeonhole principle, there is often more work to be done. THE INTERMEDIATE PIGEONHOLE PRINCIPLE ~ This more elaborate version of a previous principle says that if you have p pigeons and h holes, then at least one of the holes contains at least ceil(p/h) pigeons. INVARIANTS ~ This is an aspect of a problem, usually numerical, that does not change, even if many other properties do change. PARITY ~ This is the simplest divisibility invariant and it is whether an integer is even (divisble by 2) or odd. The ___ of a sum of a set of integers is odd if and only if the number of odd elements is odd. The ___ of a product of a set of integers is odd if and if there are no even elements in the set. - Be on the lookout for "easy" invariants. Check to see if you can rearrange your problem to get simple numbers such as zero or one. - Whenever a problem involves integers, ask yourself if there are any parity restrictions. Experiment with different values than the given if necessary. MODULAR ARITHMETIC ~ This is the reductino of our point of view from the infinite set of integers to the finite set of possible remainedrs modulo m, where m is chosen cleverly. MONOVARIANT/SEMIINVARIANT ~ This is a quantity that may or may not change at each step of a problem, but when it does change, it does so in only one direction. These are often used in teh analysis of evolving systems, to show that certain final configurations must occur, and/or to determine the duratino of the system.