Go BackDaily Calendar - Math 3312
What I hear, I forget; what I see, I remember; what I do, I understand.
Click on a date for a class: 1 - 22, 1 - 20, 1 - 27, 1 - 29, 2 - 3, 2 - 5, 2 - 10, 2 - 12, 2 - 17, 2 - 19, 2 - 24, 2 - 26, 3 - 2, 3 - 4, 3 - 9,
3 - 23, 3 - 25, 3 - 30, 4 - 1, 4 - 6, 4 - 8, 4 - 13, 4 - 15, 4 - 20, 4 - 22, 4 - 27, 4 - 29, 5 - 11
|
Date |
Read & Study Sections |
Discussion Topics |
Exercises |
| Final Exam, 11:30 am- 2 pm, Comprehensive | |||
|
8.5 8.7 8.8 |
Let A be a well-ordered set. (1) A is linearly ordered; (2) if B is order-isomorphic to A, then B is well-ordered; (3) A is order-isomorphic to the collection of all initial segments of A ordered by set containment, see Theorem 8.6; (4) any other well-ordered set B is similar to A, or one of them is order-isomorphic to an initial segment of the other, see Theorem 8.10; (5) A is assigned a symbol called the ordinal number of A, ord(A), so that two well-ordered sets have the same ordinal number if and only the sets are order-isomorphic, see definitions 8.3, 8.4, 8.5. | Study the examples. | |
|
7.8 7.9 8.1 |
If posets S and T are order-isomorphic, they share many common
properties: (1)
S is linearly ordered if and only if
T is linearly ordered (Theorem 7.2); (2)
S and T are equipotent (Theorem 7.4); (3) First, last, minimal and
maximal elements of S are mapped respectively to first, last, minimal and
maximal elements of T (Theorem 7.3). Moreover, the relation of
order-isomorphism between ordered sets is an equivalence relation (Theorem 7.5).
Hence, start with a collection of linearly ordered sets and define two of these sets to be related provided they are order-isomorphic: the collection is then partitioned into equivalence classes and to each set in the same equivalence class assign a symbol called its order type. See page 176. Let A be a poset. A is well-ordered if and only if every subset of A contains a first element. See definition 8.1, page 204. |
For Practice Chapter 7 # 7.67, 7.68, 7.69, 7.70, 7.71, 7.72, 7.73, 7.74, 7.75 |
|
|
|
Test 2 (6.5, 6.6, 6.7, 7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7) | ||
|
7.5 7.6 7.8 |
Note: (1) problem 7.17 uses the Principle of Mathematical Induction II, page 13; (2) the predecessor set of an element is defined in problem 7.31 and used in 7.32; (3) from problems 7.47 and 7.52, we may conclude that an ordered set with one maximal (minimal) element may not have a last (first) element. | ||
|
7.5 7.7 7.8 |
Be certain that you go through the
practice exercises regarding minimal and maximal elements, first and last
elements, and infimum and supremum.
An important difference between the real numbers and the rational numbers is the Completeness Axiom of the Real Numbers, see page 174. We say a one-to-one function between ordered sets X and Y is a similarity mapping provided that for all a,b in X: [a<b in X if and only if f(a)<f(b) in Y]. See page 175. |
For Practice Chapter 7 # 7.24, 7.25, 7.26 |
|
|
7.5 7.6 7.7 |
Note: (1) if S is a finite
ordered set, then S has at least one minimal element and at least one
maximal element; (2) S can have at most one first element which must
be a minimal element; (3) S
can have at most one last element which must be a maximal element; (4) If
S is linearly ordered
and has a minimal element then it must also be a first element; (5)
If S is linearly ordered and
has a maximal element then it must also be a last element. Study the definition of a consistent enumeration on page 172. Study the definitions of: upper bound, supremum or least upper bound; lower bound; infimum or greatest lower bound. Study the examples in section 7.7. |
For Practice Chapter 7 # 7.16, 7.17, 7.19, 7.20, 7.21, 7.22, 7.23 |
|
|
7.3 7.4 7.5 |
Note in the definition of the product order and lexicographical
order for S×T
that the order relations for S
and T may be different. Study the definitions of immediate predecessor and immediate successor. A Hasse diagram is a graphical representation of a finite ordered set. Study examples 7.3 and 7.4. Study the definitions of minimal elements and maximal elements. Note that an ordered set may have no minimal element, or may have more than one minimal element; this is also true for maximal elements. |
For Practice Chapter 7 # 7.4, 7.5, 7.6, 7.7, 7.13, 7.41, 7.46, 7.56, 7.58, 7.59, 7.60 |
|
|
7.2 7.3 |
A quasi-order is a relation
on a set that satisfies the irreflexive and transitive properties; see page
167. Note that there is a one-to-one correspondence between the partial
orders and the quasi-orders on a given set.
There are different ways of creating new ordered sets from given ordered sets. Study the definitions of: the product order on S×T when S and T are ordered sets (page 168); the lexicographical or dictionary order on S×T when S and T are linearly ordered sets (page 168); the concatenation or sum order on a linearly ordered collection of disjoint linearly ordered sets (page 169). |
For Practice Chapter 7 # 7.9, 7.10, 7.11, 7.12, 7.15 |
|
|
7.1 7.2 |
Review the definition of a partially ordered set. In section 7.2, become familiar with all the new notation and terminology: a precedes b; a strictly precedes b; b succeeds a; b strictly succeeds a; dual order; induced order; comparable elements; noncomparable elements; totally ordered set; linearly ordered set; a chain. Study the examples in section 7.2. |
For Practice
Chapter 7 # 7.1, 7.2, 7.3, 7.8 |
|
|
6.7 |
By Theorem 6.15, (א-nought)(c)
= c. Study the proof of this statement
in problem 6.26
that uses the set definition of product of
cardinal numbers. Study problem 6.13: removing a denumerable subset from
uncountable set does not change the set's cardinality. Study Theorem
6.16 (laws of exponents for cardinal numbers). Study problem 6.7: For any
set X, the power set of X is equipotent with C(X), the
family of characteristic functions of X.
A handout of HW 3 was given in class today. |
For Practice Chapter 6 # 6.7, 6.9, 6.48 |
|
|
6.7 |
Study definition 6.7 of the sum of two cardinal numbers; note that the corresponding sets must be disjoint. Study definition 6.8 of the product of two cardinal numbers; note that the corresponding sets do not have to be disjoint. Study the properties of cardinal number addition and multiplication given in Theorem 6.14. Note from Theorem 6.15, that if you have two nonzero cardinal numbers at least one of which is infinite, then the sum or product is simply the larger of the two. Also, note the special notation AB is the set of all functions from B, the exponent, into A. Study the examples in section 6.7. |
For Practice Chapter 6 # 6.13, 6.25, 6.26, 6.27 |
|
|
6.2 6.6 6.7 |
Study example 6.2, page 143: For any two sets A and B,
there exists sets
A' and B' such that
A is equipotent with A' , B is equipotent with B'
, and A' and B' are disjoint. The Schroeder-Bernstein Theorem, page 149, shows that the relation < on the cardinal numbers is antisymmetric. Theorem 6.12 (Law of Trichotomy) shows that given any two cardinal numbers α and β, then either (1) α < β, (2) α = β, or (3) α > β. The famous Continuum Hypothesis in given on page 149. Study definition 6.7 (the sum of cardinal numbers). Some web sites that you may useful for your writing project are: MathWorld, Wikipedia, and the MacTutor History of Math. |
For Practice Chapter 6 # 6.12, 6.16, 6.21, 6.23 |
|
| Test 1 (Chapters 1, 3, 4, 6.1-6.4) | |||
|
6.6 |
Problem 4.47 was discussed. It was noted that there is a mistake
in the statement of the problem. The second sentence should read: Show that
gof :A→C
is invertible, and (gof
) -1 = f -1 o
g -1 . One possible proof uses the associative property of
composition of functions. A different possible proof involves the action of
the functions on the elements of the appropriate domain. By Definition 6.6, |A|<|B| if A has the same cardinality as a subset of B, or, equivalently, if there exists a one-to-one (injective) function f :A→B. How can you justify that 0<1 as cardinal numbers? Note that as cardinal numbers, we have that 0<1<2<3<...<aleph-nought<c Study example 6.4. |
||
|
6.3 6.4 6.5 6.6 |
Study problem 6.8: for any infinite set A and
finite subset F of A that A\F is equipotent with
A. In section 6.6, study (1) definition 6.6 of the inequality relation for cardinal numbers on page 147. (2) Cantor's theorem 6.9 states that the cardinal number of A is strictly less than the cardinal number of the power set of A, for any set A. The proof is outlined in problem 6.18. (3) Theorem 6.13 answers the question about the relationship between aleph-nought and the power of the continuum. |
See below. | |
|
6.2 6.3 6.4 |
Remember that two sets A and B are equipotent if and only if there is a function between A and B that is one-to-one and onto. Study the function rules in problems 6.2, 6.3 and 6.15. | See below. | |
|
6.3 6.4 6.5 |
In section 6.4, study: (1) definition of a set that has the
power of the continuum; (2) any interval of numbers has the power of the
continuum; (3) the set of real numbers has the power of the continuum-verify
that the given function is one-to-one and onto. In section 6.5, study: (1) the cardinal number of a set A; (2) finite cardinal numbers; (3) transfinite cardinal numbers aleph-nought and c. |
For practice, Chapter 6 # 6.18, 6.20 |
|
|
6.2 6.3 6.4 |
In section 6.3, study: (1) the definition of a denumerable
set; (2) the definition of a countable set; (3) examples 6.3 of
denumerable sets such as P×P;
(4) theorems 6.2 (every infinite set has a subset which is countable), 6.3
(subsets of denumerable sets are finite or denumerable), 6.4 (subsets of
countable sets are countable), 6.5 (the union of a sequence of pairwise
disjoint denumerable sets is denumerable), 6.6 (countable union of countable
sets is countable), 6.7 (the set of rational numbers is denumerable). In section 6.4, study theorem 6.8 and its proof in problem 6.15. |
For practice,
Chapter 6 # 6.8, 6.15, 6.28, 6.29, 6.31, 6.32 |
|
|
3.6 6.1 6.2 |
Keep reviewing definitions. Sets A and B have the same cardinality if and only if there is a one-to-one and onto function from A to B, see page 142. Study Theorem 6.1: the relation of being equipotent (same cardinality) is an equivalence relation on any collection of sets. Study example 6.1: (c) any two closed intervals have the same cardinality; (d) the set of positive integers has the same cardinality as the set of even positive integers. |
For practice Chapter 6 # 6.1, 6.2, 6.3, 6.4, 6.5, 6.6 |
|
|
4.3 4.4 |
See the definition of equal functions on page 95. Study the relationships between 1-1 and onto functions. Let f:A→B and g:B→C: (1) if f is 1-1 and g is 1-1 then gof is 1-1; (2) if f is onto and g is onto then gof is onto; (3) if gof is 1-1 then f is 1-1; (4) if gof is onto then g is onto. Study problems 4.21 and 4.22. Study the relationships between invertible functions and bijective functions. (1) A function f:A→B is invertible if and only if f -1 is a function. [by definition ] (2) A function f:A→B is invertible if and only if f is both 1-1 and onto. [study Theorem 4.2 and problem 4.23] (3) f:A→B is an invertible function if and only if f -1:B→A is an invertible function. |
See below. | |
|
4.2 4.3 4.4 |
Study the definitions and examples: a function f from set A into set B; a function f is one-to-one (injective); a function f is onto (surjective); a function f is invertible; a function f is a one-to-one correspondence between set A and set B (bijective). Compare the solution of problem 4.22 to that done in class. | See below. | |
|
3.9 3.10 4.1 |
Pay close attention to the organization of proofs given in the
solutions. If there are alternate proofs to a problem, try comparing them
for the advantages and disadvantages that each has. For example, study the
proof of Theorem 3.5 (iii).
Review the definition of a partially ordered set; see page 75. Are you familiar with any well-known examples of posets? A function is a special type of relation; see page 95. |
For practice Chapter 4 # 4.9, 4.10, 4.13, 4.15, 4.16, 4.21, 4.22, 4.23, 4.28, 4.30, 4.38, 4.46, 4.47 |
|
|
3.8 3.9 3.10 |
Intuitively, a partition of a nonempty set S is a
subdivision of S into nonoverlapping, nonempty subsets. The subsets
are called cells. See the formal definition on page 73. A relation R on a set S is an equivalence relation if R is reflexive, symmetric, and transitive. See the definition on page 73. Also, study the related concepts of equivalence class and quotient set of S by R (S/R) on page 74. There is a one-to-one correspondence between the set of partitions of a set S and the set of equivalence relations on S. See Theorems 3.5 and 3.6. |
See the practice exercises listed below. Turn-in assignment: Hw 2. |
|
|
3.6 3.7 3.8 3.9 |
Keep reviewing all definitions until you can state each from
memory, as well as its negation! Become familiar with examples that satisfy
a definition as well as examples that do not satisfy a definition. Corollary to Theorems 3.2 and 3.4: Let R be a relation on a set A. (1) R is reflexive if and only if ΔA Í R . (2) R is symmetric if and only if R-1 = R. (3) If |A|=n, then R is transitive if and only if R = R ÈR2 ÈR3 … ÈRn . Study the properties of a partition of a set, section 3.8, and the properties of an equivalence relation, section 3.9. |
See the practice exercises listed below. | |
|
3.6 3.7 |
Carefully read the definition of a transitive relation on a set A,
as well as its negation.
Study the examples in sections 3.6 and 3.7. Note in section 3.7 that there are close relationships between: the diagonal relation on a set A and a reflexive relation on A; the inverse relation R-1 and a symmetric relation R on A; higher order products of a relation R on A, denoted Rn , and a transitive relation R. |
For Practice Chapter 3 3.22 - 3.30, 3.49, 3.50, 3.52, 3.55, 3.56, 3.58 - 3.61 |
|
|
1.12 3.1 3.2 3.3 3.4 3.5 3.6 |
Carefully read the definitions of: equality of an ordered pair; the cartesian product of sets A and B; a (binary) relation from set A to set B; the universal relation; the empty relation; the inverse of a relation; the composition of relations R and S; a reflexive relation; a symmetric relation; and an antisymmetric relation There is special notation for a cross product, page 64; a relation, page 65; and an inverse relation, page 66. Relations may also be represented pictorially, page 68; or by a directed graph, page 68; or by a matrix, page 69. Study the examples to learn to recognize special properties. |
For Practice Chapter 3 # 3.3 - 3.5, 3.8, 3.10, 3.11, 3.13 - 3.17 Turn-in assignment: Hw 1. |
|
|
1.6 1.7 1.9 |
Definitions of some familiar set operations: union of two
sets; intersection of two sets; complement of a set;
difference of one set with respect to another set; symmetric
difference of two sets. An equation of set algebra consists of a finite
number of sets and set operations. Review Table 1-1 for a list of some
well-known algebra equations that are identities (true for all sets). Study
the Theorems in sections 1.6, 1.7 and 1.9. Get in the habit of logically
breaking down the organization of a proof; for example, describe the
organization of the solution to problem 1.13. See the definition of a class of sets on page 11, as well as the special notation for a class of sets. |
For Practice Chapter 1 # 1.16 - 1.19, 1.27 - 1.29, 1.64 - 1.66 |
|
|
1.1 1.2 1.3 1.4 |
Meaning of a set; universal set U; meaning of set equality A=B and its negation A¹B; meaning of subset and its negation AËB; the empty set φ; indirect proof of φÍA for any set A. |
For Practice Chapter 1 # 1.1, 1.4, 1.5, 1.6, 1.11, 1.12, 1.13 |