3.11 Operations on sets[1YX]

E118

[05R]Let \(X\) be a non-empty set, and \(A ⊆ X\). We will denote with \(A^ c=X⧵ A=\{ x∈ X:x∉ A\} \) the complement of \(A\) in \(X\).

We define the characteristic function \({\mathbb 1}_ A: X→ℤ\) by

\[ {\mathbb 1}_ A(x)= \begin{cases} 1 & \text{if}~ x∈ A\\ 0 & \text{if}~ x∉ A\\ \end{cases} ~ . \]

Prove that

\[ {\mathbb 1}_{A^ c} = 1-{\mathbb 1}_ A ~ ~ ,~ ~ {\mathbb 1}_{A∩ B} = {\mathbb 1}_ A {\mathbb 1}_ B ~ ~ ,~ ~ {\mathbb 1}_{A∪ B} = {\mathbb 1}_ A +{\mathbb 1}_ B - {\mathbb 1}_ A {\mathbb 1}_ B \]

E118

[05S]Now consider instead the characteristic function defined as before, but considered as \({\mathbb 1}_ A: X→ℤ_ 2\) i.e. taking values in the group \(ℤ_ 2\) (more correctly referred to as \(ℤ/2ℤ\)).

In this case the above relations can be written as

\[ {\mathbb 1}_{A^ c} = {\mathbb 1}_ A +1 ~ ~ ,~ ~ {\mathbb 1}_{A∩ B} = {\mathbb 1}_ A {\mathbb 1}_ B ~ ~ ,~ ~ {\mathbb 1}_{A∪ B} = {\mathbb 1}_ A {\mathbb 1}_ B +{\mathbb 1}_ A +{\mathbb 1}_ B~ . \]

Recall the definition of the symmetric difference \( AΔ B= (A⧵ B) ∪ (B⧵ A) \), and then

\[ {\mathbb 1}_{AΔ B} = {\mathbb 1}_ A + {\mathbb 1}_ B ~ ~ . \]

With these rules we show that

\[ AΔ B = B Δ A ~ ~ ,~ ~ (AΔ B)^ c = A Δ (B^ c)=(A^ c) Δ B ~ ~ ,~ ~ AΔ B = C \iff A = B Δ C \]

\[ (AΔ B)∩ C = (A∩ C) Δ (B∩ C) ~ ~ ,~ ~ A∪ (BΔ C) = (A∪ B)Δ (A^ c ∩ C) \]

E118

[05T]Let \(A,B,C\) sets, then

\begin{eqnarray*} A× (B∪ C) = (A× B)∪ (A× C)~ ~ ,\\ A× (B∩ C) = (A× B)∩ (A× C)~ ~ .\\ \end{eqnarray*}

Therefore the Cartesian product operation is distributive on the union and intersection.

E118

[05V]If \(A,B,C\) are non-empty sets and

\[ (A\times B) \cup (B\times A) = (C\times C) \]

then \(A=B=C\).

Hidden solution: [UNACCESSIBLE UUID ’05W’]

E118

[05X]Given four sets \(X,Y,A,B\) with \(A⊂ X,B⊂ Y\), write

\[ (X× Y)⧵ (A× B) \]

as a union of three sets, pairwise disjoint, each a Cartesian product.

Hidden solution: [UNACCESSIBLE UUID ’05Y’]

E118

[05Z]We want to rewrite the tautologies seen in 3 in the form of set relations.

Let \(X\) be a set and let \(𝛼,𝛽,𝛾⊆ X\) be subsets. Let \(x∈ X\). If we define \(A=(x∈ 𝛼)\), \(B=(x∈ 𝛽)\), \(C=(x∈ 𝛾)\) in the tautologies, we can then rewrite each tautology as a formula between sets \(𝛼,𝛽,𝛾,X,∅\), that use connectives \(=,∩,∪\) and the complement.

Surprisingly, rewriting can be done algorithmically and in a purely syntactic manner. Pick a tautology seen in 3. In the following \(𝜑,𝜓\) indicate subparts of tautology that are well-formed formulas.

• Replace \(((𝜑) ⇒ (𝜓))\) with \(((¬(𝜑)) ∨ (𝜓))\) (you will get another tautology).

• Then syntactically replace \(¬ (𝜑)\) with \((𝜑)^ c\), \(∨\) with \(∪\) and \(∧\) with \(∩\); replace \(A\) with \(𝛼\), \(B\) with \(𝛽\), \(C\) with \(𝛾\), \(V\) with \(X\), and \(F\) with \(∅\).

• Finally, if the formula contains at least one ”\(\iff \)”, transform them all in ”\(=\)”; otherwise add ”\(=X\)” at the end.

Check that this ”algorithm” really works!

E118

[060] Let \(X\) be a set. Let \(I,J\) families not empty of indexes, and for every \(i∈ I\) let \(J_ i⊆ J\) a family not empty of indexes. For each \(i∈ I, j∈ I_ j\) let \(A_{i,j}⊆ X\). Show that

\[ ⋂_{i∈ I}⋃_{j∈ J_ i}A_{i,j}= ⋃_{𝛽∈ B} ⋂_{i∈ I} A_{i,𝛽(i)} \]

where \(B=∏_{i∈ I} J_ i\) and remember that every \(𝛽∈ B\) is a function \(𝛽:I→ J\) for which for every \(i\) you have \(𝛽(i)∈ J_ i\). Then formulate a similar rule by exchanging the role of intersection and union. (use the complements of the sets \(A_{i,j}\) and the rules of de Morgan). Hidden solution: [UNACCESSIBLE UUID ’061’]

[UNACCESSIBLE UUID ’27B’]

Limsup and liminf of sets

We suppose that \(A_ n\subseteq X\) for every \(n\). (We can set \(X=\bigcup _ n A_ n\)).

[UNACCESSIBLE UUID ’062’]

E125

[063] Recall that

\[ A^ c=X⧵ A=\{ x∈ X:x∉ A\} \]

is the complement of \(A\) in \(X\) (as defined in 33). Show that

\[ (\limsup _{n\to \infty } A_ n)^ c=\liminf _{n\to \infty } (A_ n ^ c)~ ~ . \]

E125

[064] Prerequisites:160. Show that

\begin{eqnarray} \label{eq:limsup_ insiemi_ freq} \limsup _{n→∞} A_ n & =& \{ x∈ X : x∈ A_ n \text{ frequently in~ }n\} ~ ~ ,\\ \label{eq:liminf_ insiemi_ defn} \liminf _{n→∞} A_ n & =& \{ x∈ X : x∈ A_ n \text{ eventually in~ }n\} ~ ~ . \end{eqnarray}

(”Frequently” and ”eventually” are discussed in Sec. 4.7).

E125

[065]Prerequisites:2, 4. Given sets \(A_ 1,A_ 2\ldots \) and \(B_ 1,B_ 2\ldots \) , for \(n∈ℕ\), say if there is a relation (of equality or containment) between

\begin{eqnarray} \label{eq:liminf_ insiemi_ intersezione} (\liminf _{n→∞} A_ n) ∩ (\liminf _{n→∞} B_ n) & \stackrel{?}{=} & \liminf _{n→∞} (A_ n∩ B_ n)\quad ,\\ {} \label{eq:liminf_ insiemi_ unione} (\liminf _{n→∞} A_ n) ∪ (\liminf _{n→∞} B_ n) & \stackrel{?}{=} & \liminf _{n→∞} (A_ n∪ B_ n)\quad . \end{eqnarray}

If equality does not hold, show an example. Then use 1 to establish similar rules for \(\limsup _{n→∞} A_ n\).

Hidden solution: [UNACCESSIBLE UUID ’066’]