MATH 318, Assignment 4

MATH 318, Assignment 4

1. (2 points) Let B be the Lindenbaum–Tarski algebra with three
variables p, q, r
(1) Find all the atoms of B
(2) How many elements does B have?
2. (2 points)
(1) Does there exist an infinite Boolean algebra B such that
for every nonzero b ∈ B there is an atom a ∈ B with a ≤ b?
Justify your answer.
(2) Does there exist an infinite Boolean algebra which contains
exactly one atom? Justify your answer.
A preorder is a binary relation that is reflexive and transitive.
3. (2 points) Suppose  is a preorder on a set X. Define the
relation ≡ on X by x ≡ y if x  y and y  x. Show that ≡
is an equivalence relation. Define ≤ on X/ ≡ by [x]≡ ≤ [y]≡ if
x  y. Show that this definition is correct (does not depend on
the choice of representatives of equivalence classes) and that ≤
is a partial order.
Below, N stands for the set of natural numbers {0, 1, 2, . . .}.
4. (3 points) Consider the following binary relation | on N: n|m if
n divides m (i.e. there exists k ∈ N such that m = n · k).
(1) Is | a partial order on N?
(2) Does (N, |) have the least element?
(3) Does (N, |) have the greatest element?
Justify your answers.
2
5. (2 points) Consider P = {1, 2, 3, 4} and let | be defined on P
as in the previous problem: i|j if there exists k ∈ N such that
j = k · i. Find the minimal number n such that there exists
chains C1, . . . , Cn in P with P =
Sn
i=1 Ci
. Justify your answer.
6. (1 point) Consider the powerset P({1, 2, 3}) with the relation
of inclusion ⊆. Find a linear order on P({1, 2, 3}) that extends
the inclusion relation ⊆.
7. (1 point) Let P = {A ⊆ N : A is nonempty, finite and has an
even number of elements}. Consider X = {A ∈ P : 1 ∈ A}.
Does X have a lower bound in (P, ⊆)? Justify your answer.
8. (2 points) Write {0, 1}
∗
for S
n∈N
{0, 1}
n
. Elements of {0, 1}
∗ are
called words and subsets of {0, 1}
∗ are called formal languages
(over the two-element alphabet {0, 1}). Write  for the empty
word (of length 0). Consider the function f : P({0, 1}
∗
) →
P({0, 1}
∗
) defined as follows:
f(X) = X ∪ {w01 : w ∈ X} ∪ {}
Find the least fixed point of f on P({0, 1}
∗
) ordered by inclusion. Justify your answer.
The following problem is for extra credit.
9*. (4 points) Let f : A → B and g : B → A be arbitrary functions.
Show that there are subsets A1, A2 ⊆ A and B1, B2 ⊆ B such
that A1 ∪ A2 = A, A1 ∩ A2 = ∅, B1 ∪ B2 = B, B1 ∩ B2 = ∅ and
f(A1) = B1, g(B2) = A2.
Use this to give an alternative proof of the Schr¨oder–Bernstein
theorem.
hint: use the Knaster-Tarski fixed point theorem.