1. přednáška a cvičení/1st lecture and tutorial, pondělí/Monday 25. 2. 2019. A. Pultr: kapitoly/chapters I.1-I.6 v/in
skriptech .
2. přednáška a cvičení/2nd lecture and tutorial, pondělí/Monday 4. 3. 2019. A. Pultr: kapitoly/chapters I.6-I.7 v/in
skriptech. M. Klazar: kapitoly/chapters II.1-I.II.2 v/in
skriptech but I also mentioned Higman's ordering, Higman's theorem and Sperner's theorem.
Problem 1.
yes or no: a) (P, <) is an order => (P^*, <_H) (the Higman
ordering on words over P) is an order too, b) (P, <) is an order
=> (P^N, <_H) (the Higman ordering on infinite sequences
over P) is an order too, of course justify your answers.
Problem 2. Prove
that for any preorder (P, <), a~b iff a <= b and b <= a is an
equivalence relation, and that we get an order on P/~.
Problem 3. We
defined two orders (X, <_X) and (Y, <_Y) to be isomorphic, if
there are two monotonous maps (called isomorphisms), one from X to Y
and the other from Y to X, which compose in both ways to identical
maps, on X and on Y. Prove that a map f from X to Y is an isomorphism
if and only if f is onto and a <=_X b iff f(a) <=_Y f(b).
Problem 4. Prove
that for linear orders the condition "(ii) if M is a subset of the
downset of t then s is less or equal than t" (in the definition that s
is a supremum of a subset M of an ordered set) is equivalent to the
condition "(ii') if t < s then there is a u in M such that t < u"
and explain why for general orders these two conditions are not
equivalent. The problems are due by March 18, preferably by e-mail.
3. přednáška a cvičení/3rd lecture and tutorial, pondělí/Monday 11. 3. 2019. A. Pultr: kapitoly/chapters I.7 a II.3, II.6 a částečně/partially II.7 v/in
skriptech. M. Klazar: kapitola/chapter II.7 (theorems on fixed points for monotonous selfmaps of ordered sets) v/in
skriptech.
Additionaly (to the fixed point proof) I gave a combinatorial proof of
the Cantor--Bernstein theorem, based on types of components of the
arrow graph of the given injections X -> Y and Y -> X.
Problem 1. Why is the map in Thm. 7.1 (Bourbaki's thm on fixed point) monotonous?
Problem 2. Why is the map F in the fixed point proof of the Cantor--Bernstein theorem (7.4.1, p. 43) monotonous?
Problem 3. Why we can assume that the sets X and Y in the Cantor--Bernstein theorem are disjoint?
Problem 4.
(See p. 44) Show in detail that the strategy S_I is a persistent
strategy for the 1st player. Problems are due by March 25, preferably
by e-mail (sorry for posting them here after almost 1 week, next time I
will try to be faster).
4. přednáška a cvičení/4th lecture and tutorial, pondělí/Monday 18. 3. 2019. A.
Pultr: ... . M. Klazar: still chapter II.7, an application of
Bourbaki's theorem to Kleene's 1st recursion theorem. Chapter III.2: we
are heading to the proof of Theorem III.2.6 characterizing distributive
lattices by two forbidden configurations C_5 and D_3, and are in the
middle of the proof of Lemma 2.5 on the symmetric identity.
Problem 1. Find on the Internet information on
Kleene's 1st recursion theorem.
Problem 2. Show that if L has C_5 as a sublattice then it is not modular.
Problem 3. Show that (when a lattice
L is not modular) if
u join (v meet w) < (u join v) meet w (for some three elements
u, v and
w in
L) then with
a=v, x=u join (v meet w) and
b=v meet w we have
a meet x = b. The three problems are due by April 2, preferably by e-mail.
5. přednáška a cvičení/5th lecture and tutorial, pondělí/Monday 25. 3. 2019. A.
Pultr: Pseudocomplements. M. Klazar: Completing the proof of Theorem
III.2.6 characterizing distributive lattices by two forbidden
configurations C_5 and D_3. I followed in this proof
this and
this
text of mine (lecture notes for the lecture 2 years ago). Basic notions
of universal algebra: kapitola/chapter IV.1 (especially Propositions
1.3.1 and 1.3.2) ve
skriptech.
Problem 1. Show that if a lattice L contains D_3 then it is not distributive.
Problem 2. Explain in detail the argument by symmetry in the proof of Theorem III.2.6 (top of p. 52 ve
skriptech). The two problems are due by April 16 (since I am posting them here too late), preferably by e-mail.
6. přednáška a cvičení/6th lecture and tutorial, pondělí/Monday 1. 4. 2019. A.
Pultr: Complements, Heyting algebras and their relation to logics,
Boolean algebras, ultrafilters. M. Klazar: kapitola/chapter IV.2
(especially Proposition 2.5 on p. 72) ve
skriptech. The graph reconstruction problem (Harary, 1964) and Müller's theorem (1977) on it, after
this and
this text of mine.
Problem 1.
Prove the edge reconstruction conjecture for graphs with four edges
(i.e., if G and H have four edges and after deleting one edge produce
the same - up to isomorphism and reordering - collection of graphs,
then they are isomorphic).
Problem 2. Prove the PIE (inclusion-exclusion formula) by double-counting. The two problems are due by April 16, preferably by e-mail.
7. přednáška a cvičení/7th lecture and tutorial, pondělí/Monday 8. 4. 2019. Only M. Klazar: completing the proof of Muller's theorem on graph reconstruction
(
here and
here). Then Chapter IV. 9 in
skripta.
Problem 1. The formula
inj_D(G, bar{H}) = sum_{A subset of E \ D} ... - what are the sets X_1, ..., X_n in this application of PIE? (bottom of p. 1
here).
Problem 2. Why does the second displayed equation at p. 2 in
here hold?
Problem 3. Exercise at the top of p. 3 in
here.
Problem 4. Prove
that the (commutative) monoid (N, *, 1) (the natural numbers with
standard multiplication) is isomorphic to the free (commutative) monoid
(F(P), +, emptyset) of finite multisets of prime numbers.
(I complete this tomorrow, Apr. 10. Well, sorry, I completed it on Apr 15. The four problems are therefore due by April 29).
8. přednáška a cvičení/8th lecture and tutorial, pondělí/Monday 15. 4. 2019. A.
Pultr: ... . M. Klazar: An ideal
I (in a commutative unitary ring
R) is maximal (resp. prime) iff
R / I is a field (resp. an integral domain), proof. Theorem: for every prime p and integer k>0 there is a finite field
F with p^k elements, proof by constructing
F as the quotient field
Z_p[x] / (r(x)) where
r(x) is an irreducible polynomial with degree
k. We get
r(x) from the Theorem: the number of such monic irreducible polynomials in
Z_p[x] with degree
k is
(1 / k)sum_{d | k}m(d)*p^{k / d} where
m(.) is the Moebius function, conclusion of the proof next time.
Problem 1. Prove directly (without using the quotient ring) that every maximal ideal is prime.
Problem 2. Prove that every finite integral domain is a field.
Problem 3. Prove that every finite field has p^k elements, for some prime number
p and positive integer
k.
The three problems are due by April 29.
9. přednáška a cvičení/9th lecture and tutorial, pondělí/Monday 29. 4. 2019. A.
Pultr: ... . M. Klazar: Proof of the formula for the number of monic irreducible polynomials in
Z_p[x] with given degree. Proof of the Moebius inversion formula and some remarks on the logaritmic differentiation.
Topology. Up to Chapter V.1.5.5 in the
lecture notes, proof of the Fact 1.1.1 next time.
Problem 1. Prove the formal logaritmic differentiation identity: If F_1(x), F_2(x),
... are formal power series in C[[x]]
such
that their orders ord(F_n) (indices of the first nonzero term) go to
infinity with n, then the infinite product F(x) = (1 + F_1(x)).(1 +
F_2(x))... formally converges and F' / F = F_1' / (1 + F_1) +
F_2' / (1 + F_2) + ... (in the lecture I forgot these 1 + in the
denominators).
Problem 2. Prove the four properties of closure in a topological space given in Chapter V.1.5.2 (page 98) in the
lecture notes.
The two problems are due by May 13.
10. přednáška a cvičení/10th lecture and tutorial, pondělí/Monday 6. 5. 2019. A.
Pultr: ... . M. Klazar: Proof of of the Fact 1.1.1. Then continuing in
topology up to before the 5 equvalent definitions of continuity of a
mappig.
Problem 1. Let
(X, =<) be a preorder, a subset U of X is increasing if a in U, b in
X, a=<b implies that b is in U. Similarly for decreasing
subsets. Prove that increasing subsets satisfy the axioms of open
sets and that decreasing subsets satisfy the axioms of closed sets.
Problem 2. Prove
that Zariski topology is a topology: for a field F the set system of
subsets A of F^n such that A is the common zeros of a set of
polynomials in F[x_1, ..., x_n] (i.e., there is a subset P of F[x_1,
..., x_n] such that a is in A iff p(a) = 0 for every p(x) in P)
satisfies the axioms of closed sets.
Problem 3. Prove
that a subset S of exp(X) is a base for a topology on X iff (i) the
union (sum) of S is X and (ii) for every A and B in S their
intersection equals to the union of some elements of S.
The three problems are due by May 26.
11. přednáška a cvičení/11th lecture and tutorial, pondělí/Monday 13. 5. 2019. A.
Pultr: both lectures .
12. přednáška a cvičení/9th lecture and tutorial, pondělí/Monday 6. 5. 2019. M. Klazar: both lectures. Solution of
Problem 1 from Monday 29. 4. 2019. Properties of compact spaces (Chapter V.6 in
skripta) and properties of connected spaces (Chapter V.7 in
skripta).
květen/May 2019