Union And Intersection

Union

Given two sets

A, B \subseteq X

, then the union of

A

and

B

is defined as the set

A \cup B : = {p \in X : p \in A \lor p \in B}

Intersection

Given two sets

A, B \subseteq X

, then the intersection of

A

and

B

is defined as the set

A \cap B : = {p \in X : p \in A \land p \in B}

A set Intersects Another

Suppose that

A, B

are sets, we say that

A

intersects

B

when

A \cap B \neq \emptyset

Arbitrary Union

Suppose that

M

is a family of sets, then

⋃ M

is defined so that

x \in ⋃ M ⟺ \exists A \in M, x \in A

Arbitrary Intersection

Suppose that

M

is a family of sets, then

⋂ M

is defined so that

x \in ⋂ M ⟺ \forall A \in M, x \in A

Arbitrary Union Element of Notation

We define

⋃_{A \in M} A : =

⋃ M

Arbitrary Intersection Element of Notation

We define

⋂_{A \in M} A : =

⋂ M

Arbitrary Union Indexed Notation

Suppose that

I

is an index set for the collection

𝒜 = {A_{α} : α \in I}

where

A_{α}

is a set, then

⋃_{α \in I} A_{α} : =

⋃ 𝒜

. If the index set is known by context, then we may use the shorthand

⋃_{α} A_{α}

Arbitrary Intersection Indexed Notation

Suppose that

I

is an index set for the collection

𝒜 = {A_{α} : α \in I}

where

A_{α}

is a set, then

⋂_{α \in I} A_{α} : =

⋂ 𝒜

. If the index set is known by context, then we may use the shorthand

⋂_{α} A_{α}

Arbitrary Union Finite Counting Notation

Suppose that

a, b \in ℤ

, with

a < b

, and

𝒜 : = {A_{i} : i \in ℤ, a \leq i \leq b}

, then

⋃_{i = a}^{b} A_{i} =

⋃ 𝒜

Arbitrary Intersection Finite Counting Notation

Suppose that

a, b \in ℤ

, with

a < b

, and

𝒜 : = {A_{i} : i \in ℤ, a \leq i \leq b}

, then

⋂_{i = a}^{b} A_{i} =

⋂ 𝒜

Arbitrary Union Infinite Counting Notation

Suppose that

a \in ℤ

, and

𝒜 : = {A_{i} : i \in ℤ, a \leq i}

, where each

A_{i}

is a set. Then

⋃_{i = a}^{\infty} A_{i} : = ⋃ 𝒜 .

Equivalently,

x \in ⋃_{i = a}^{\infty} A_{i} ⟺ \exists i \in ℤ such that a \leq i and x \in A_{i} .

Arbitrary Intersection Infinite Counting Notation

Suppose that

a \in ℤ

, and

𝒜 : = {A_{i} : i \in ℤ, a \leq i}

, where each

A_{i}

is a set. Then

⋂_{i = a}^{\infty} A_{i} : = ⋂ 𝒜 .

Equivalently,

x \in ⋂_{i = a}^{\infty} A_{i} ⟺ \forall i \in ℤ, a \leq i ⟹ x \in A_{i} .

Disjoint Sets

Given two sets

A, B

we say that

A

and

B

are disjoint when

A \cap B

\emptyset

Disjoint Union Notation

Given two sets

A, B

the notation

A ⊔ B

is defined as the set

A \cup B

and also that

A, B

are disjoint.

Sometimes the above can feel confusing, because it allows you to write contradictions, ie, if you write ${1} ⊔ {1}$ then this is a contradiction, just in the same way as writing $1 = 0$ would also be a contradiction, so it's important to remember that the square union notation is making a claim at the same time so whenever it's utilized you should verify that the two sets are indeed disjoint, and sometimes that will also require proof.

pairwise disjoint sets

Suppose that

M

is a family of sets, then we say these sets are pairwise disjoint when given

A, B \in M

such that

A \neq B

, then

A \cap B = \emptyset

partition

Suppose that

X

is a set, then we say that a set

P

is a partition of

X

if and only if the following are true

$\emptyset \notin P$
$⋃ P$ $= X$
P is pairwise disjoint

partition of the integers

The family

{{p \in ℤ : p < 0}, {0}, {p \in ℤ : p > 0}}

is a partition of

ℤ

Note that the integers $- 1, 0, 1$ show that the empty set is not in this family. We'll now prove that it's union equals $ℤ$ , so let $p \in ⋃ P$ , therefore $p$ is in at least one of the sets included in $P$ , since each is a subset of $ℤ$ , then we know $p \in ℤ$ , for the reverse direction, we can assume that $p \in ℤ$ , therefore we know that $p$ is either positive, negative or zero, so that $p \in ⋃ P$ , this shows $⋃ P = ℤ$ .

To show this family is pairwise disjoint, note that $0 \notin {p \in ℤ : p < 0}$ and $0 \notin {p \in ℤ : p > 0}$ , which shows us that ${0} \cap {p \in ℤ : p < 0} = \emptyset$ and ${0} \cap {p \in ℤ : p > 0} = \emptyset$ .

Given any positive integer, we know it cannot be a negative integer, therefore ${p \in ℤ : p < 0} \cap {p \in ℤ : p > 0} = \emptyset$ , thus we know that $P$ is pairwise disjoint, which concludes the proof.

a set intersected with a superset is itself

Let

A, B

be sets such that

A \subseteq B

, then

A \cap B = A

We start by showing $A \cap B \subseteq A$ , so consider $x \in A \cap B$ , so we know that $x \in A$ and $x \in B$ , therefore we trivially know that $x \in A$ , as needed

Now consider the other direction, we need to show that $A \subseteq A \cap B$ , so consider that $x \in A$ , then we want to show that $x \in A$ and $x \in B$ , which really just simplifies to showing $x \in B$ , but we know that $A \subseteq B$ , therefore since $x \in A$ , we know that $x \in B$ finishing the proof

A Set Union a Subset is Itself

Let

A, B

be sets such that

B \subseteq A

, then

A \cup B = A

We start by showing $A \cup B \subseteq A$ , so consider $x \in A \cup B$ , so we know that $x \in A$ or $x \in B$ , if $x \in A$ we are done, on the other hand if $x \in B$ , then since $B \subseteq A$ , then $x \in A$ as needed.

Supposing that $x \in A$ , then we know that $x \in A \cup B$ is true.

Subset of an Intersection

Suppose that

A, B, C

are sets then

A \subseteq (B \cap C)

iff

A \subseteq B

and

A \subseteq C

Suppose that $A \subseteq (B \cap C)$ , suppose $x \in A$ , therefore $x \in B$ and $x \in C$ showing $A \subseteq B$ and $A \subseteq C$

Now suppose that $A \subseteq B$ and $A \subseteq C$ , therefore given $x \in A$ , we can see that $x \in B \cap C$ as needed.

intersection factors from union

Suppose that

U_{α}

is an indexed family of sets, and

Y

is any set, then

⋃_{α \in I} (U_{α} \cap Y) = (⋃_{α \in I} U_{α}) \cap Y

Suppose that $x \in ⋃_{α \in I} (U_{α} \cap Y)$ , therefore there is some $β \in I$ such that $x \in U_{β} \cap Y$ , so that $x \in U_{β}$ and $x \in Y$ . Since there is some $β \in I$ such that $x \in U_{β}$ then $x \in ⋃_{α \in I} U_{α}$ , additionally we had that $x \in Y$ so that $x \in (⋃_{α \in I} U_{α}) \cap Y$ as needed

Now suppose that $x \in (⋃_{α \in I} U_{α}) \cap Y$ , therefore $x \in (⋃_{α \in I} U_{α})$ and $x \in Y$ , due to this we have some $β \in I$ , such that $x \in U_{β}$ and thus $x \in U_{β} \cap Y$ which by definition shows that $x \in ⋃_{α \in I} (U_{α} \cap Y)$

intersection factors from intersection

Suppose that

U_{α}

is an indexed family of sets, and

Y

is any set, then

⋂_{α \in I} (U_{α} \cap Y) = (⋂_{α \in I} U_{α}) \cap Y

Suppose that $x \in ⋂_{α \in I} (U_{α} \cap Y)$ , therefore for every $α \in I$ we have: $x \in U_{α} \cap Y$ , so that $x \in U_{α}$ and $x \in Y$ . Since it's true for every $α \in I$ then $x \in ⋂_{α \in I} U_{α}$ , additionally we had that $x \in Y$ so that $x \in (⋂_{α \in I} U_{α}) \cap Y$ as needed

Now suppose that $x \in (⋂_{α \in I} U_{α}) \cap Y$ , therefore $x \in (⋂_{α \in I} U_{α})$ and $x \in Y$ , due to this, for every $α \in I$ , we know $x \in U_{α}$ and thus $x \in U_{α} \cap Y$ which by definition shows that $x \in ⋂_{α \in I} (U_{α} \cap Y)$

Union of Subsets is Still a Subset

Suppose that

𝒞

is a collection of subsets of

X

, then

⋃ 𝒞 \subseteq X

Let

x \in ⋃_{C \in 𝒞} C

, then

x \in U

for some

U \in 𝒞

, since

U

must be a subset of

X

then x is also in

X

. As needed

Intersection of Subsets is Still a Subset

Suppose that

𝒞

is a collection of subsets of

X

, then

⋂ 𝒞 \subseteq X

Let

x \in ⋂_{C \in 𝒞} C

, then

x \in U

for each

U \in 𝒞

, focusing on a single such set

M \in 𝒞

since

M

must be a subset of

X

then x is also in

X

. As needed

An Intersection of Supersets is still a Superset

Suppose that

𝒞

is a collection of supersets of

X

, then

⋂ 𝒞 \supseteq X

Let

x \in X

, suppose that

C \in 𝒞

, thus by definition

C \supseteq X

, and since

x \in X

we must deduce

x \in C

, therefore

x \in ⋂ 𝒞

as needed.

Intersection Decreases as It Intersects More Things

Suppose that

N, M

are families of sets such that

N \subseteq M

, then

⋂ M \subseteq ⋂ N

Let

x \in ⋂ M

, then for every

S \in M, x \in S

. Now consider any

K \in N

, then

K \in M

therefore

x \in K

which shows that

x \in ⋂ N

as needed.

The Intersection of a Collection of Sets Is a Subset of Any Set Part of the Intersection

Suppose that

𝒞

is a collection of sets, then for any

C \in 𝒞

we have:

⋂ 𝒞 \subseteq C

Note that

𝒞 \supseteq {C}

therefore we know

⋂ 𝒞 \subseteq ⋂ {C} = C

as needed.

A set Covered in Subsets is a Union

Suppose

A

is a set and that for each

a \in A

, there is a

B_{a}

such that

a \in B_{a} \subseteq A

, then

A = ⋃_{a \in A} B_{a}

We can see that $𝒞 = {B_{a} : a \in A}$ is a collection of subsets of $A$ , so since a union of a subsets is still a subset we have $⋃_{a \in A} B_{a} \subseteq A$ .

But also given $p \in A$ we know that $p \in B_{p}$ so $p \in ⋃_{a \in A} B_{a}$ which shows $A \subseteq ⋃_{a \in A} B_{a}$ , so we can conclude $A = ⋃_{a \in A} B_{a}$ .