Math 101 Problem Set 1 Solutions

Thomas Allen and Stefan Karpinski October 14, 1999

Problem N 1.3.1

(a) KA = {x ∈ ℤ : ∃ a ∈ A s.t. a < x}. Not a closure operator: {0} ⊈ K {0} = {1, 2, 3, … } .

(b) KA = {x ∈ ℤ : ∃ a ∈ A s.t. a ≤ x}. A closure operator:

C1. If A has no minimum then KA = ℤ which contains A. If A has a

minimum, a_{0}, then KA = {x ∈ ℤ : a_{0} ≤ x} which also contains A. C2. If either A or B has no minimum (or both) then

KA ∪ KB = K(A ∪ B) = ℤ so we’re done. If both A and B have minima, a_{0} and b_{0}, respectively

K(A ∪ B) = {x ∈ ℤ : min {a_{0}, b_{0}} ≤ x}
= {x ∈ ℤ : a_{0} ≤ x} ∪ {x ∈ ℤ : b_{0} ≤ x}
= KA ∪ KB.

C3. If A has no minimum then KKA = KA = ℤ. If it has a minimum,

a_{0} then KKA and KA both equal

{x ∈ ℤ : a_{0} ≤ x} .

C4. K∅ = ∅ is clear.

(c) KA = {x ∈ ℤ : ∃ a ∈ A, k ∈ ℤ s.t. x = ka}. A closure operator. For A, B ⊆ ℤ denote AB = {x ∈ ℤ : x = yz for some y, z ∈ ℤ}. Observe that

ℤℤ = ℤ  (1)
KA = ℤA  (2)
(AB)C = A(BC)  (3)

for A, B, C ⊆ ℤ.

C1. Use observation (2): KA = ℤA ⊇ {1} A = A. C2. Calculate using observation (2) again

K(A ∪ B) = ℤ(A ∪ B)
= {y ∈ ℤ : y = nx for some n ∈ ℤ, x ∈ A ∪ B}
= {y ∈ ℤ : y = nx for some n ∈ ℤ, x ∈ A} ∪

{y ∈ ℤ : y = nx for some n ∈ ℤ, x ∈ B}

= ℤA ∪ ℤB
= KA ∪ KB

C3. Using observations (1) through (3) we get

KKA = K(ℤA) = ℤ(ℤA) = (ℤℤ)A = ℤA = KA.

C4. K∅ = ∅ is clear.

(d) KA = {x ∈ ℤ : ∃ a_{1}, a_{2} ∈ A s.t. a_{1} ≤ x ≤ a_{2}}. Not a closure operator:

K {1} ∪ K {3} = {1} ∪ {3} , but
K({1} ∪ {3}) = K {1, 3} = {1, 2, 3} .

Problem N 1.3.2

Check that (L, K) satisfies the Kuratowski Axioms: C1. Since both A ⊆ A and A ⊆ A ∪ {∞}, A ⊆ KA for all A. C2. If both A and B are finite then A ∪ B is finite too so

K(A ∪ B) = A ∪ B = KA ∪ KB.

Otherwise, say A is infinite, and thus so is A ∪ B. Then

KA ∪ KB = A ∪ B ∪ {∞} = K(A ∪ B)

C3. If A is finite we have KA = A ⟹ KKA = KA = A. Otherwise we have

KKA = K(A ∪ {∞}) = KA ∪ {∞} = A ∪ {∞} = KA.

C4. K∅ = ∅ is clear.

Problem N 1.4.1

(a) Apply axiom C2. twice:

K(A_{1} ∪ A_{2} ∪ A_{3}) = K(A_{1} ∪ A_{2}) ∪ KA_{3} = KA_{1} ∪ KA_{2} ∪ KA_{3}

(b) Apply axiom C2. three times. (It’s the same.)

(c) The general conjecture is that for n ∈ ℤ

K ⋃_{k=1}^{n} A_{k} = ⋃_{k=1}^{n} KA_{k}.

We could simply say here that we apply axiom C2. n − 1 times but that would be glossing over something very important which is happening here—induction. We’ve already done the base case and now we simply observe that

K ⋃_{k=1}^{n} A_{k} = K ⋃_{k=1}^{n−1} A_{k} ∪ A_{n}

and by the induction hypothesis (= the assumption that what you’d like to prove is true for smaller n) we already know that

K ⋃_{k=1}^{n−1} A_{k} = ⋃_{k=1}^{n−1} KA_{k},

so we’re done.

If we replace unions with intersections then the resulting conjecture is blatantly false already in the case n = 2. (Consider e.g. on the real line ℝ with the standard Euclidean topology: K([0, 1) ∩ (1, 2]) = K(∅) = ∅ but K[0, 1) ∩ K(1, 2] = [0, 1] ∩ [1, 2] = {1}.) However, Theorem N 1.10 says that we do have K(A ∩ B) ⊆ KA ∩ KB and using induction as before we get the more general result

K ⋂_{k=1}^{n} A_{k} ⊆ ⋂_{k=1}^{n} KA_{k}.

Problem N 1.4.2

(a) Let X = ℤ, let K be the closure operator defined in Problem N 1.3.1(b) (which we showed was in fact a closure operator) and let A = {1} and B = {2}. Then KA = {1, 2, 3, … } and KB = {2, 3, 4, … } so

K(A − B) = KA = {1, 2, 3, … } ⊈ {1} = KA − KB.

(b) Begin with the following lemma:

Lemma. C − D ⊆ E ⟺ C ⊆ D ∪ E.

Proof. Suppose C − D ⊆ E. If x ∈ C then x ∈ E or x ∈ D (and x ∉ C − D). This in turn implies x ∈ D ∪ E. So, C ⊆ D ∪ E. Now, if C − D ⊈ E, then there exists x ∈ C − D such that x ∉ E. Furthermore, x ∈ C but x ∉ D implies x ∉ D ∪ E and finally C ⊈ D ∪ E.

Now clearly A ⊆ A ∪ B = B ∪ (A − B). By Theorem N 1.9 (that C ⊆ D implies KC ⊆ KD), we therefore have that

KA ⊆ K(B ∪ (A − B)) = KB ∪ K(A − B),

which—by the Lemma—happens if and only if

KA − KB ⊆ K(A − B).

Problem N 1.4.3

Recall the following definitions.

Ext A =^{def} (KA)^{c} = X − KA
Int A =^{def} (KA^{c})^{c} = X − K(X − A)
∂A =^{def} KA ∩ KA^{c} = KA ∩ K(X − A)

For brevity we denote the complement of a set S by S^{c} = X − S.

(a) There are four properties to verify:

X = Ext A ∪ Int A ∪ ∂A  (4)
∅ = Ext A ∩ Int A  (5)
∅ = Ext A ∩ ∂A  (6)
∅ = Int A ∩ ∂A.  (7)

First we verify (4) using De Morgan’s Law repeatedly and cancelling as we go:

Ext A ∪ Int A ∪ ∂A = (KA)^{c} ∪ (KA^{c})^{c} ∪ (KA ∩ KA^{c})
= (KA)^{c} ∪ [[(KA^{c})^{c} ∪ KA] ∩ [(KA^{c})^{c} ∪ KA^{c}]]
= (KA)^{c} ∪ [[(KA^{c})^{c} ∪ KA] ∩ X]
= (KA)^{c} ∪ (KA^{c})^{c} ∪ KA
= X ∪ (KA^{c})^{c}
= X.

Next we verify (5) by noting that for any set B ⊆ X we have

(KB^{c})^{c} ⊆ B.

Using this twice, first with B = A and second with B = A^{c}, we get

Ext A ∩ Int A = (KA)^{c} ∩ (KA^{c})^{c}
⊆ (KA)^{c} ∩ A
⊆ A^{c} ∩ A
= ∅.

Finally we verify (6) and (7) by simply cancelling in the obvious fashion:

Ext A ∩ ∂A = (KA)^{c} ∩ KA ∩ KA^{c} = ∅,
Int A ∩ ∂A = (KA^{c})^{c} ∩ KA ∩ KA^{c} = ∅.