Mathematical Structures, NMAI064, summer term 2019/20
Lectures are on Monday 9:00 - 10:30 and Tuesday 17:20 - 18:50 in the lecture room S221 (corridor KAM) at the
2nd floor in the Malostranske namesti building. Lecturers are doc. Martin Klazar and prof. Ales Pultr. You get the
``zapocet'' for solving at least 1/2 of the problems posted.
On ``zapocet'', exam and exam questions. I decided to grant ``zapocet'' to all who sent solutions to at least
some of the homeworks. Exam is in Czech or English and is preferably in contact form (oral with written preparation) but distant form is possible on
request, see SIS for terms.
1. Outline the (Cantor) construction of real numbers.
2. State and prove the Cantor--Bernstein theorem (on injections and bijections between two sets).
3. State and prove the prophet paradox (an application of the axiom of choice).
4. State Harary's edge-reconstruction conjecture, Muller's theorem on it and give main ideas of the proof.
5. Prove that for a ring R and a proper ideal I in R, (i) the factor-ring R/I is an integral domain iff
I is prime and (ii) the factor-ring R/I is a field iff I is maximal.
6. State and prove the division algorithm in the ring of polynomials F[x] (where F is a field). Prove that
F[x] is a an integral domain and a principal ideal domain.
7. Define topological space, state basic properties of open and closed sets in it, and state the separation
axioms T_0 -- T_4.
8. Define compact topological spaces, state their basic properties and prove some of them.
1st lecture on February 24, 2020 (M. Klazar). Chapters I.1.1-I.2.3 of the
Czech LN of A. Pultr,
equivalences and partitions, begining of the construction of real numbers. Lecture notes for the 1st lecture.
Problem 1.1. Let (a, b) := { {a}, {a, b} }. Prove that (a, b) = (c, d) iff a = c and b = d.
Problem 1.2. Prove the trichotomy law for the relation < on R: if neither (a_n) < (b_n) nor (b_n) < (a_n) then
(a_n) ~ (b_n) (R, < and ~ were defined in the lecture).
2nd lecture on February 25, 2020 (M. Klazar). Chapters I.3.1-I.3.5 of the
Czech LN of A. Pultr,
conclusion of the construction of real numbers, The Cantor - Bernstein theorem and beginning of its proof.
Lecture notes for the 2nd lecture.
Problem 2.1. (concerning the construction of real numbers) Prove that the coordinate-wise multiplication
is an operation on R (i.e., the result is always in R).
Problem 2.2. (concerning the construction of real numbers) Show that if (a_n) in R is non-equivalent to s_0
(constant 0 sequence) then (1/a_n) is in R. What do you do if, for some n, a_n=0?
3rd lecture on March 2, 2020 (M. Klazar). Conclusion of the proof of the C.-B. thm. Chapters I.3.6-I.4.3
of the Czech LN of A. Pultr,
an application of the AC (axiom of choice): existence of non-measurable sets.
Lecture notes for the 3rd lecture.
Problem 3.1. Prove that the the AC (as formulated in the LN)
is equivalent with: for every set A that does not contain empty set there is a map f from A to the union of A such that (for every X in A) f(X) is in X.
Problem 3.2. Prove that the relation ~ on the unit circle S (defined in the lecture) is an equivalence relation.
Deadline: till March 10 (included).
4th lecture on March 3, 2020 (A. Pultr).
Chapters II.1-II.3.3 (Order) of the Czech LN of A. Pultr.
5th lecture on March 9, 2020 (M. Klazar). Another paradoxical corollary of the AC: The prophet
paradox. Chapters I.4.4-I.5.3 of the Czech LN of A. Pultr.
Lecture notes for the 5th lecture.
Problem 5.1. Prove that a countable union of countable sets is a countable set.
Problem 5.2. Prove that every well ordered (w.r. to the standard ordering) set of real numbers is
at most countable. (See the LN for a hint.)
Problem 5.3. Prove that a map from X to Y is an isomorphisms to M-ary relations R in X^M and S in Y^M
(by the definition in the LN) if and only if f is a bijection and for every map s from M to X, the composition fs is in S iff s is in R.
Deadline: till March 17 (included).
6th lecture on March 10, 2020 (A. Pultr). Chapters II.3.4.-II.6 (Order) of the
Czech LN of A. Pultr.
Starting March 11 classes in person are cancelled because of the coronavirus quarantine.
I will post my scanned handwritten lecture notes + problems (deadline 1 week) here as before on each Monday.
As for the lectures of prof. A. Pultr, I will post here on each Tuesday reference to precise chapters
covered by him in his LN, as before. The form of the exam will be determined later.
March 16, 2020 (M. Klazar). Chapters I.6-I.7 of the Czech
LN of A. Pultr (abridged). The edge-reconstruction conjecture (ERC) of F. Harary (1964), graph homomorphisms,
Muller's theorem (the ERC holds for graphs with no too few edges), proof next time.
study text replacing the 7th lecture.
Problem 7.1. Prove that the ERC holds for graphs with exactly one edge (see the study text for precise definitions).
Problem 7.2. Prove that the ERC does not hold for the two pairs of graphs G and H given in the study text.
Problem 7.3. Prove that a graph G has chromatic number at most k iff there exists a homomorphism from G to the
complete graph K_k. Deadline: it will be good if you send in your solutions by March 24 (included) but because
of the current situation I will not be strict.
March 17, 2020 (A. Pultr). Chapters of the Czech
LN of A. Pultr corresponding to: Vety o pevnem bode (Knaster-Tarski, Bourbaki, a par dusledku) (Kapitola 2) Binarni suprema a infima
jako algebraicke operace, Modularni a distributivni svazy a jejich charakteristika Idealy a filtry (Kapitola 3).
March 23, 2020 (M. Klazar). Proof of Muller's theorem: any graph with
n>5 vertices and at least 1 + n(log_2(n) - 1) edges can be reconstructed from its one-edge-deleted spanning subgraphs, to be finished in the next lecture.
study text replacing the 9th lecture (corrections: on p. 1 in the theorem I forgot to state the assumption that
the common number of edges is at leat 1 + n(log_2(n) - 1)).
Problem 9.1. Prove that if G, H and L are graphs where G and H are isomorphic, then the number of L-copies in G
(the number of subgraphs of G that are isomorphic to L) is the same as the number of L-copies in H.
Problem 9.2. Prove the principle of inclusion and exclusion (see the study text for its precise formulation),
double counting arguments are preferred.
Problem 9.3. Prove the last equality in the study text (bottom of page 4).
Deadline: it will be good if you send in your solutions by March 31 (included) but because
of the current situation I will not be strict.
March 24, 2020 (A. Pultr). Specialni idealy a filtry (prvo- a maximalni). Birkhoffova veta o prvoidealech a
prvofiltrech. Heytingovy algebry, poznamky o Boolovych algebrach.
March 30, 2020 (M. Klazar). Conclusion of the proof of Muller's theorem. In fact, its author
Vladimir Muller is a researcher in the Mathematical Institute of the Czech
Academy of Sciences. When we are at these personalia, I must sadly mention that the great Czech, or Czech-American, combinatorialist and graph theorist
Robin Thomas (graduate of the MFF UK and a doctoral student of J. Nesetril) passed
away four days ago. A jump to commutative algebra (but I promise I will return to combinatorics and generating functions later): basic definitions related
to rings, definition of a field.
study text replacing the 11th lecture
Problem 11.1. Why is inj(H, H) > 0?
Problem 11.2. Why do the equalities ...=...=n! at the top of page 3 in the study text hold?
Problem 11.3. Prove by induction (or other method) that n! < (n/2)^n for every n > 5.
Deadline: it will be good if you send in your solutions by April 7 (included) but because
of the current situation I will not be strict.
March 31, 2020 (A. Pultr). V tomto tydnu: Heytingovy algebry podrobneji, nektere Heytingovske identity.
Role adjunkce (zejmena silnejsi distributivita $(\bigvee a_i)\wedge b=\bigvee(a_i\wedge b)$ (ktera se nedualizuje). Pseudokomplementy v
Heytingovealgebre. Booleovy algebry, proc jsou specialni pripad Heytingovych.
April 6, 2020 (M. Klazar). Integral domains. Remark(s) on the Wedderburn theorem. Quaternions.
Proposition/Definition on characteristic of an integral domain, proof. I forgot to mention in the study text that
every field is an integral domain. Ideals I in a ring R, maximal and prime ideals. Definition of the factor-ring R/I. study
text replacing the 13th lecture
Problem 13.1. Prove that every finite integral domain is a field, for a hint see the study text.
Problem 13.2. Prove that Z_m = Z/mZ is a field iff m is a prime number, for a hint see the study text.
Problem 13.3. Prove that every finite field has p^k elements (k>0 is
an integer and p is a prime), for a hint see the study text. Deadline: it will be good if you send
in your solutions by April 14 (included) but because of the current situation I will not be strict.
April 7, 2020 (A. Pultr). K prednasce: Booleovy algebry a booleanizace, ultrafiltry. Prvni poznamky k
universalni algebre: Operace, systemy operaci, typ. Priklady. Pojem homomorfismu.
April 13, 2020 (M. Klazar). Easter Monday - no lecture.
April 14, 2020 (A. Pultr). Homomorfismy algeber, rozdily mezi chovanim homomorfismu algeber a relacnich
homomorrfismu ("trojuhelnikova lemmata") Podalgebry, srovnani s podobjekty relacnich systemu. Pruniky podalgeber, generovani. Zvlastnost u algeber
finitarniho typu.
April 20, 2020 (M. Klazar). I am sorry for the delay, the study text will be posted here tomorrow on April 21.
Here it is: study text replacing the 16th lecture. Correctness of operations on R/I.
Theorem on R/I: I is a prime ideal iff R/I is an i. domain, and I is maximal iff R/I is a field, proof. PIDs.
Proposition: If F is a field then F[x] is a PID, proof. Irreducibles. Proposition:
If R is a PID and a in R is irreducible then the ideal (a) is maximal, proof. Problem 16.1. Prove that if a is an
element of R and I is an ideal in R then {x + ra | x in I, r in R} is an ideal in R.
Problem 16.2. Prove that 0_R+I and 1_R+I (I is a proper ideal in R) are different elements of R/I which are
neutral to addition and multiplication in R/I, respectively.
Problem 16.3. Prove that if F is a field then F[x] (the ring of polynomials with coefficients in F) is an integral
domain. Does it hold if we assume that F is only an integral domain? Deadline: it will be good if you send in your solutions
by April 28 (included) but because of the current situation I will not be strict.
April 21, 2020 (A. Pultr). Postoupili jsme do generovani podalgebry podmnozinou.
Dale, specialni pripad algeber finitarniho typu (rozsirovani mnoziny vysledky operaci se saturuje po spocetne krocich. Faktorove
algebry a homomorfismy na. Prvni kroky ve volnych algebrach.
April 27, 2020 (M. Klazar). See May 4.
April 28, 2020 (A. Pultr). Themata jsou: Volne algebry, obecna veta o existenci pro tridy finitarnich algeber.
Volna algebra a slozene operace.
May 4, 2020 (M. Klazar). I am sorry but I could only post the study text replacing
the 18th lecture with a week delay. Theorem: For every field F the integral domain F[x] of polynomials in x with
coefficients in F is a UFD (unique factorization domain), proof but first the definition of UFD. Theorem: For
every prime number p and every integer k>0 there exists a field with p^k elements, beginning of the proof.
Problem 18.1. Prove that the relation that two elements a, b of an i. domain are associated (a=bc where c is a unit)
is an equivalence relation.
Problem 18.2. Prove that if F is a field then F[x] is a PID (every ideal is generated by one element). Hint: the next
problem.
Problem 18.3. Prove the division algorithm for F[x]: if a, b are in F[x] and b is nonzero, then there are c, d
in F[x] such that a = bc + d and deg(d) < deg(b) or d is the zero polynomial. Deadline: it will be good if you send
in your solutions at the last two weeks from now but because of the current situation I will not be strict.
study text replacing the 20th lecture. Continuation and conclusion of the proof of the last theorem. The proof uses
two, in fact three, interesting results. Theorem: If a_k is the number of monic and degree k irreducible polynomials in Z_p[x]
then (1 - px)^{-1} = prod_{k=1}^{infinity}(1 - x^k)^{-a_k}, proof. Proposition (the Moebius inversion): If f, g
are functions from N to R such that for every n we have f(n) = sum_{d divides n}g(d), then g(n) = sum_{d divides n}mju(d)*f(n/d), where mju(n) is the
Moebius function, without proof. The desired formula: the number of monic degree k irreducible polynomials in Z_p[x]
equals (1/k)sum_{d divides k}mju(d)*p^{n/d}, proof.
Problem 20.1. Prove that if f is any degree k polynomial in Z_p[x] then the elements of the factor-ring
Z_p[x]/(f) bijectively correspond to the polynomials in Z_p[x] with degree less than k (and the zero polynomial).
Problem 20.2. Prove that two polynomials f and g in Z_p[x] are associated iff f=gh where h is a nonzero constant.
Problem 20.3. Prove that the number of monic degree k polynomials in Z_p[x] is p^k.
Deadline: it will be good if you send in your solutions at the last two weeks from now but because of the
current situation I will not be strict.
May 5 2020 (A. Pultr).
Rovnice jako axiomy, variety algeber, jejich zakladni vlastnosti. Birkhoffova veta (bez dukazu).
May 11, 2020 (M. Klazar).
study text replacing the 22nd lecture (updated on May 13). Topology. Metric
spaces and their open sets. Introducing topology by open sets and by neighborhoods, transitions between both approaches. The operation of closure and
its properties. Example of a non-metrisable topology. Base and subbase of a topology, Proposition: Characterization
of bases and subbases, without proof. The Sorgenfrey line.
Problem 22.1. Prove the basic properties of open sets in a metric space, see the study text for details.
Problem 22.2. Deduce (from the axioms (ot1) - (ot3)) and prove the axioms (uz1) - (uz3) for closed sets in
an abstract topological space, see the study text for details.
Problem 22.3. Prove that the axioms (ok1) - (ok4) for neighborhoods imply the axiom (ok4'), see the study text
for details. Deadline: it will be good if you send in your solutions at the last a week from now (i.e. May 20)
but because of the current situation I will not be strict. This is the last batch of problems to solve.
May 12 2020 (A. Pultr). Kapitola V.3 Spojita zobrazeni a Kapitola V.4 Zakladni konstrukce, str. 101 - 105.
May 18, 2020 (M. Klazar).
study text replacing the 22nd lecture (updated on May 20). Separation axioms T_0, T_1, T_2, T_3, T_{3.5} and T_4.
Proposition: every metric space is normal (T_4 space), proof. Definition of compact
(topological) spaces.
May 19 2020 (A. Pultr). Zbytek kapitoly V.6 Kompaktnost, bez V.6.8 Cechova--Stoneova kompaktifikace.
May 2020