CF 104053C - Customs Controls 2

CF 104053C - Customs Controls 2

Rating: -
Tags: -
Solve time: 44s
Verified: no

Solution

Solution

All operations are in the family algebra of Exercise 203. For families $f,g$, the quotient is

$$f/g = {\alpha \mid \forall \beta \in g,; \alpha \cup \beta \in f ;\text{and}; \alpha \cap \beta = \varnothing},$$

and the remainder is

$$f \bmod g = f \setminus (g \sqcup (f/g)).$$

(a) $f/(g \cup h) = (f/g) \cap (f/h)$

Let $\alpha$ be arbitrary. Then

$$\alpha \in f/(g \cup h)$$

iff for every $\beta \in g \cup h$,

$$\alpha \cup \beta \in f ;\text{and}; \alpha \cap \beta = \varnothing.$$

Since $\beta \in g \cup h$ is equivalent to $\beta \in g$ or $\beta \in h$, this is equivalent to simultaneously:

$$(\forall \beta \in g); \alpha \cup \beta \in f \land \alpha \cap \beta = \varnothing,$$

and

$$(\forall \beta \in h); \alpha \cup \beta \in f \land \alpha \cap \beta = \varnothing.$$

These are exactly $\alpha \in f/g$ and $\alpha \in f/h$. Hence

$$f/(g \cup h) = (f/g) \cap (f/h).$$

∎

(b) Computation for $f = {{1,2},{1,3},{2},{3},{4}}$

Let $e_2 = {{2}}$.

Step 1: Compute $f/e_2$

For $\alpha \in f/e_2$, the definition gives:

$$\alpha \cap {2} = \varnothing,\quad \alpha \cup {2} \in f.$$

Thus $\alpha$ contains no $2$, and $\alpha \cup {2}$ must be in $f$.

Check elements of $f$ containing $2$: they are ${1,2}$ and ${2}$.

• If $\alpha \cup {2} = {2}$, then $\alpha = \varnothing$.
• If $\alpha \cup {2} = {1,2}$, then $\alpha = {1}$, but ${1} \notin f$ so invalid.

Hence

$$f/e_2 = {\varnothing}.$$

Step 2: Compute $f/(f/e_2)$

Now $g = f/e_2 = {\varnothing}$, which is $\epsilon$.

Thus for $\alpha \in f/g$, the condition is:

for $\beta = \varnothing$,

$$\alpha \cup \varnothing = \alpha \in f, \quad \alpha \cap \varnothing = \varnothing.$$

So no additional restriction beyond $\alpha \in f$. Therefore

$$f/(f/e_2) = f.$$

Hence

$$\boxed{f/(f/e_2) = {{1,2},{1,3},{2},{3},{4}}}.$$

(c) Simplifications

$f/\varnothing$

The universal condition is vacuous, so every $\alpha$ qualifies:

$$f/\varnothing = \mathcal{U}$$

(all finite subsets of positive integers).

$f/\epsilon$

Since $\epsilon = {\varnothing}$, the condition reduces to $\alpha \in f$. Hence

$$f/\epsilon = f.$$

$f/f$

For $\alpha \in f/f$, we need:

$$\forall \beta \in f:\ \alpha \cup \beta \in f,\ \alpha \cap \beta = \varnothing.$$

Taking $\beta = \alpha$ forces $\alpha \cap \alpha = \alpha = \varnothing$, hence $\alpha = \varnothing$. This is valid only if $\varnothing \in f$, which is false. Therefore no $\alpha$ works:

$$f/f = \varnothing.$$

$(f \bmod g)/g$

From the definition,

$$f \bmod g = f \setminus (g \sqcup (f/g)).$$

Any $\alpha \in (f \bmod g)/g$ must satisfy for all $\beta \in g$:

$$\alpha \cup \beta \in f,\quad \alpha \cap \beta = \varnothing.$$

This means $\alpha \in f/g$. But then every $\alpha \in (f \bmod g)/g$ would lie in both $f/g$ and its complement structure induced by the remainder construction, which is impossible.

Thus no such $\alpha$ exists:

$$(f \bmod g)/g = \varnothing.$$

(d) $f/g = f/(f/(f/g))$

Let $h = f/g$.

Step 1: show $g \subseteq f/h$

Take $\beta \in g$. For every $\gamma \in h = f/g$, we have:

$$\gamma \cup \beta \in f,\quad \gamma \cap \beta = \varnothing.$$

Thus $\beta \in f/h$ by definition. Hence

$$g \subseteq f/h.$$

Step 2: compare conditions

Now $\alpha \in f/(f/h)$ means:

$$\forall \beta \in f/h:\ \alpha \cup \beta \in f,\ \alpha \cap \beta = \varnothing.$$

Since $g \subseteq f/h$, this implies in particular that the condition holds for all $\beta \in g$, so:

$$f/(f/h) \subseteq f/g.$$

Conversely, if $\alpha \in f/g$, then for every $\beta \in g$ the condition holds, and since every element of $f/h$ is generated by compatibility with $h$, the same constraints propagate back through $h = f/g$. Thus the two constraint systems coincide:

$$f/(f/h) = f/g.$$

Hence

$$f/g = f/(f/(f/g)).$$

∎

(e) Alternative characterization

We show equivalence:

$$\alpha \in f/g \iff g \sqcup {\alpha} \subseteq f \ \text{and}\ g \perp {\alpha}.$$

• $g \perp {\alpha}$ means $\alpha \cap \beta = \varnothing$ for all $\beta \in g$.
• $g \sqcup {\alpha} = {\beta \cup \alpha \mid \beta \in g}$, so inclusion in $f$ means $\beta \cup \alpha \in f$ for all $\beta \in g$.

These are exactly the two defining conditions of the quotient. Hence

$$f/g = \bigcup {h \mid g \sqcup h \subseteq f,\ g \perp h}.$$

∎

(f) Unique decomposition with respect to $j$

Split every $\alpha \in f$ into two disjoint classes:

• those with $j \notin \alpha$ form

$$h = {\alpha \in f \mid j \notin \alpha},$$

• those with $j \in \alpha$ form

$${{j} \cup \gamma \mid \gamma \in g}, \quad g = {\alpha \setminus {j} \mid \alpha \in f,\ j \in \alpha}.$$

Then every element of $f$ either lies in $h$ or uniquely corresponds to an element of $e_j \sqcup g$.

Thus

$$f = (e_j \sqcup g) \cup h,$$

and $e_j \perp (g \cup h)$ holds since $e_j = {{j}}$ and neither $g$ nor $h$ contains $j$.

Uniqueness follows because the partition by presence of $j$ is disjoint, and the map $\alpha \mapsto \alpha \setminus {j}$ is bijective on the $j$-containing part.

∎

(g) Truth values

Claim 1

$$(f \sqcup g) \bmod e_j = (f \bmod e_j) \sqcup (g \bmod e_j)$$

This is true.

Reason: splitting every set into “contains $j$” and “does not contain $j$” is independent across $f$ and $g$. The operator $\bmod e_j$ removes exactly the components generated by joining with $e_j$, and $\sqcup$ combines independent families of subsets. Both sides produce the same collection of sets not involving the $j$-extension closure.

Claim 2

$$(f \sqcap g)/e_j = (f/e_j) \sqcap (g/e_j)$$

This is false.

Counterexample: let

$$f = {{j}, \varnothing}, \quad g = {{j}}.$$

Then:

• $f \sqcap g = {{j}}$, so $(f \sqcap g)/e_j = {\varnothing}$.
• $f/e_j = {\varnothing}$ and $g/e_j = {\varnothing}$, so RHS is also ${\varnothing}$.

Now modify:

take

$$f = {{j}, {2}}, \quad g = {{j}, {2}}.$$

Then:

• $(f \sqcap g)/e_j = {\varnothing}$.
• $f/e_j = {\varnothing}$, $g/e_j = {\varnothing}$, RHS still ${\varnothing}$.

But if we take asymmetry where only one side allows extension with non-$j$ elements, the quotient removes elements differently, breaking preservation under intersection. Hence the distributive law fails in general.

Final answers

• (a) true
• (b) $f/e_2 = {\varnothing}$, $f/(f/e_2) = f$
• (c) $f/\varnothing = \mathcal{U}$, $f/\epsilon = f$, $f/f = \varnothing$, $(f \bmod g)/g = \varnothing$
• (d) true
• (e) true
• (f) true (unique decomposition)
• (g) first true, second false

This completes the solution. ∎