Link Search Menu Expand Document
Introduction to Proofs

Lesson (II)

Table of contents

  1. Families of Sets
  2. Power Sets
  3. Cartesian Products of Sets
  4. Binary Relations
  5. Partially Ordered Sets

Families of Sets

We might be interested at time to consider not one set but a bunch of them at the same time.

For example, we might be interested in a sequence
\[ A_0, A_1, A_2, \ldots \] of sets indexed by the natural numbers. Here the numbers $0,1,2,\ldots$ are the indices, whereas the sets $A_n$ might or might not have any natural numbers in them: For each natural number $n$, we can define the set $A_n$ to be the set of people alive today that are of age $n$.

More generally, if $I$ is a set, we sometimes wish to consider a family \(\set{ A_i \mid i \in I } \) of sets indexed by elements of $I$. Here the member of the set \(\set{ A_i \mid i \in I } \) are themselves sets, indexed by elements of $I$.

Union and intersection of indexed families

Given a family $\set{ A_i \mid i \in I }$ of sets indexed by $I$, we can form its union: \[ \bigcup_{i \in I} A_i = \set{ x \mid x \in A_i \text{ for some $i \in I$} } \] We can also form the intersection of this family: \[ \bigcap_{i \in I} A_i = \set{ x \mid x \in A_i \text{ for every $i \in I$} } \]

So an element $x$ is in $\bigcup_{i \in I} A_i$ if and only if $x$ is in $A_i$ for some $i$ in $I$, and $x$ is in $\bigcap_{i \in I} A_i$ if and only if $x$ is in $A_i$ for every $i$ in $I$.

The operations of union and intersection of families of sets are represented in symbolic logic by the existential and the universal quantifiers. We have: \[ \forall x \; (x \in \bigcup_{i \in I} A_i \iff \exists i \in I \; (x \in A_i)) \] \[ \forall x \; (x \in \bigcap_{i \in I} A_i \iff \forall i \in I \; (x \in A_i)) \]

Challenge

The operations of indexed union and intersection have a particularly simple nature when the indexing set has finite number of elements:

  1. Describe these operations when indexing set is empty.
  2. Describe these operations when indexing set is a singleton.
  3. Describe these operations when indexing set has exactly two elements.

Challenge (Disjoint Unions for Families of Sets)

We defined the disjoint union of two sets by $A \times \set{0} \cup B \times \set{1}$. Can you extend this definition for a family of sets $\set{A_i \mid i \in I}$? (Note that by extension here we mean that your definition of the disjoint union of a family of sets should agree with the usual disjoint union of sets when the family has only two members.)

The following theorem states that the usual intersection and union distributes over indexed unions and intersections:

Theorem. Let $\set{ B_i \mid i \in I }$ be a family of sets. We have

  1. \( A \cap \bigcup_{i \in I} B_i = \bigcup_{i \in I} (A \cap B_i) \)
  2. \( A \cup \bigcap_{i \in I} B_i = \bigcap_{i \in I} (A \cup B_i) \)

Challenge

Prove the theorem above.

We can have a family of sets indexed by many sets: for instance, a family $\set{A_{i,j} \mid i\in I, j \in J}$.

For every such family, consider the family $\set{ B_i \mid i \in I}$ where $B_i = \bigcup_{j \in J} A_{i,j}$ (here we fix $i \in I$, and let $j$ range over $J$).

We define $\bigcup_{i \in I} \bigcup_{j \in J} A_{i,j}$ to be $\bigcup_{i \in I} B_i$.

Challenge

Prove the following equalities of sets:

  1. $\bigcup_{i \in I} \bigcup_{j \in J} A_{i,j} = \bigcup_{j \in J} \bigcup_{i \in I} A_{i,j} $
  2. $\bigcap_{i \in I} \bigcap_{j \in J} A_{i,j} = \bigcap_{j \in J} \bigcap_{i \in I} A_{i,j} $.

Challenge

  1. Prove that for every family $\set{ A_{i,j} \mid i \in I, j \in J}$ of sets we have \[ \bigcup_{i \in I} \bigcap_{j \in J} A_{i,j} \subseteq \bigcap_{j \in J} \bigcup_{i \in I} A_{i,j} \]
  2. Find the indexing sets $I$ and $J$ and a family $\set{ A_{i,j} \mid i \in I, j \in J}$ such that \[ \bigcap_{j \in J} \bigcup_{i \in I} A_{i,j} \nsubseteq \bigcup_{i \in I} \bigcap_{j \in J} A_{i,j} \]

Power Sets

Let $X$ be a set. The power set of $X$, written $\mathcal{P}(X)$ is the set of all subsets of $X$. Formally, \[ \mathcal{P}(X) \defeq \set{ U \mid U \subseteq X } \] Note that the predicate we use to form the set above is $Sub_X$, that is $Sub_X (U)$ is the sentence that $U$ is a subset of $X$.

Therefore, \[ \forall U \, \big( U \subseteq X \Leftrightarrow U \in \mathcal{P}(X) \big) \] Note that the power set of every set is inhabited since for a set $X$ we have $\varnothing \in \mathcal{P}(X)$ and $X \in \mathcal{P}(X)$.

Challenge

Suppose $A$ is a set with $3$ elements. How many elements does the set $\mathcal{P}\set{\emptyset,A}$ have?

With the definition of power set, let us observe that

  • $\mathcal{P} \emptyset = \set{\emptyset} $
  • $\mathcal{P}\mathcal{P} \emptyset= \set{ \emptyset, \set{\emptyset} }$

Challenge

Let us define \[ \mathcal{P}^n A = \mathcal{P}\mathcal{P} \ldots \mathcal{P}\mathcal{P} A\] where we have applied the power set operation $n$ times.

  1. How many elements does $\mathcal{P}^3 \emptyset$ have?
  2. How many elements does $\mathcal{P}^n \emptyset$ have? Your answer should depend on $n$.

Challenge

Let $X$ be a set. We define the family $(S_x)_{x \in X}$ where $S_x$ is the set of all subsets of $X$ which contain $x$. In other words: [ S_x = \set{ U \subseteq X \mid x \in U } \, . ] Show that

  1. $ \bigcup_{x \in X} S_x = \mathcal P (X) \setminus { \emptyset} $
  2. $ \bigcap_{x \in X} S_x = { X } $

Challenge

Prove that if $A \subseteq B$ then $\mathcal{P} A \subseteq \mathcal{P} B$. Is the converse true as well? Justify your answer.

Cartesian Products of Sets

With the tools we have developed we can define the cartesian product $A \times B$ of sets $A$ and $B$ to be the set containing exactly ordered pairs $(a,b)$ where the first component $a$ belongs to the set $A$ and the second component $b$ belongs to $B$. We have expressed the idea of the new object $(a,b)$ but have not defined it so far. Since in set theory, everything is a set we should be able to define $(a,b)$ as a set. Consider the following definition:

\[ (a, b) \defeq \set{ \set{a}, \set{ a, b } } \in \mathcal{P}(\mathcal{P}(A \cup B)) \, \] where $a \in A$ and $b \in B$.

In other words,
\[ A \times B \defeq \set{ (a, b) \; \mid a \in A \text{ and } b \in B } \, . \]

Notice that if $a = b$, the set $(a, b)$ has only one element:

\[ (a, a) = \set{ \set{a},\set{a, a} } = \set{ \set{a},\set{a} } = \set{\set{a}} \, . \]

Challenge

Show that if $a$ and $b$ are distinct then $(a,b) \neq (b,a)$.

The following theorem shows that the definition of cartesian product of sets is reasonable.

Theorem

For all elements $a,b,c,d$ of the universe, we have $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$.

Challenge

Prove the theorem above.

Binary Relations

In this lesson our goal is to make the idea of relation and relationship mathematically precise, using the concepts of set theory.

First, consider the following examples of relations:

  • The relation on days on the calendar, given by days $x$ and $y$ fall on the same day of the week. For instance, 24 Jan 2022 and 31 Jan 2022 are related with this relationship.
  • The relation on vegetable produce in a farmers market, given by price of $x$ is less than price of $y$.
  • The relation on people currently alive on the planet, given by $x$ and $y$ have the same home address.
  • The relation on people in the world, given by $x$ is a brother of $y$.
  • The relation on cities of the world, given by $x$ and $y$ are in the same country.
  • The relation on people in the world, given by person $x$ is influenced by person $y$.
  • The relation on lines on a 2-dimensional plane, given by line $l$ and line $m$ are parallel to each other.
  • The relation on points and lines on a 2-dim plane, given by point $p$ is on line $l$.
  • The relation on natural numbers, given by number $m$ is less than $n$.

Now, we will introduce a precise mathematical concept which encompasses all the instance of our informal idea of relation in above. A binary relation $R$ on sets $A$ and $B$ (or from $A$ to $B$) is a two-variable predicate $R$ on the set $A \times B$; Alternatively, we can think of $R$ as a two-variable predicate where the first variable ranges over $A$ and the second over $B$. For every $(a,b) \in A \times B$, the expression $R(a,b)$ is the proposition “$a$ is related to $b$ through $R$”.

In mathematics, we often use infix notation, writing $a \mathrel{R} b$ instead of $R(a, b)$, e.g. $a = b$, $a \leq b$, $f \pitchfork g$, etc.

We call $A$ the domain and $B$ the codomain of the relation $R$.

Convention

Whenever the domain and codomain of a relation $R$ are the same set, say $A$, instead of saying $R$ is a relation from $A$ to $A$ we say $R$ is a relation on $A$ (or that $A$ is equipped with a relation $R$).

An extension of a relation $R$ on sets $A$ and $B$ is a subset $[R]$ of $A \times B$ consisting of the pairs $(a,b)$ where $R(a,b)$ holds. Formally,

\[ [R] \defeq \set{ (a,b) \in A \times B \mid R(a,b)} \]

Challenge

  1. Prove that any subset of $A \times B$ is obtained as an extension of some relation on $A$ and $B$.
  2. Use the previous fact to prove that the sets of all relations on $A$ and $B$ coincide with $\mathcal{P} (A \times B)$.

For any set $A$, there there are three trivial relation from $A$ to $A$:

  • The maximal relation $\mathrm{m}_A$ which relates every element $a$ of $A$ to every element $a’$ of $A$.
  • The identity relation $\mathrm{id}_A$ relates every element of $A$ to itself and nothing else.
  • The empty relation $\mathrm{e}_A$ which does not relate any element to any element.

Inverse of Relations

If we have a relation $R$ from $A$ to $B$ we can form another relation $R^{-1}$, called the inverse of $R$, from $B$ to $A$ defined as follows: \[ R^{-1}(b,a) \iff R(a,b) \, .\]

Note the extension $[R^{-1}]$ is a subset of $B \times A$

Composition of Relations

Given a relation $R$ from $A$ to $B$ and a relation $S$ from $B$ to $C$ we can compose them to get a a relation $S \circ R$ from $A$ to $C$ defined as follows: \[ a (S \circ R) c \iff \exists b \in B \, (a R b \land b R c) \]

Challenge

Draw a picture conveying the idea behind the composition operation of relations.

Challenge

Let $B$ be the “brotherhood’’ relation ($x B y$ means $x$ is a brother of $y$) and $S$ be the “sisterhood’’ relation. Show that the composite relation $S \circ B$ is not equivalent to $B$.1

Challenge

Show that for any relation $R$ from $A$ to $B$ we always have $R \circ R^{-1} = \mathrm{id}_B$ and $R^{-1} \circ R = \mathrm{id}_A$ as sets.

Associated Graph of Relations

Suppose a set $A$ comes equipped with a relation $R$. We can associate a directed graph (aka a digraph) whose vertices are elements of $A$ and whose directed edges determined by ordered pairs $(a, b) \in A \times A$ such that $a R b$.

  1. Incidentally, I wonder why we use in English “ship” in “relationship”, “kinship”, “friendship”, etc, and “hood” in “sisterhood”, “brotherhood”, “personhood”, “neighbourhood”, etc? ↩

Partially Ordered Sets

A binary relation $R$ on a domain $A$ is a partial order if it has the following three properties:

  • Reflexivity: $a R a$, for every $a$ in $A$.
  • Transitivity: If $a R b$ and $b R c$, then $a R c$, for every $a$, $b$, and $c$ in $A$.
  • Antisymmetry: If $a R b$ and $b R a$ then $a = b$, for every $a$ and $b$ in $A$.

The Partial Order of Propositions

An natural example of partial order is the partial order on the collection of propositions defined by the relation $ P \leq Q $ if $Q$ can be derived from $P$ using the derivation of rules of intuitionistic logic (see here).

Challenge

Think why the conditions of reflexivity, transitivity, and antisymmetry hold for this relation.

A partial order $R$ on a domain $A$ is a total order (also called a linear order) if it additionally has the following property: For every $a$ and $b$ in $A$, either $a R b$ holds or $b R a$ holds.

Challenge

Express the conditions of reflexivity, transitivity, symmetry, antisymmetry, and totality of order in terms of more familiar connectivity conditions on the associated graph.

The Partial Order of Propositions

There is a partial order on the power set $\mathcal{P} (X)$ of a set $X$ given by the subset relation:

Challenge

  1. Check that all the axioms of partial order are satisfied.
  2. Show that this partial order is not total.

A non-empty partially ordered set $(S,\leq)$ is filtered (or is said to be a filtered set) if for each $a, b \in S$, there is a element $c$ such that $a \leq c$ and $b \leq c$.

Theorem

Every total order is a filtered.

Proof

Suppose $A$ is a set equipped with a total order $\leq$. Suppose $a,b \in A$. We want to find an element $c \in A$ for which both $a \leq c$ and $b \leq c$. By totality, either $a \leq b$ or $b \leq a$. If $a \leq b$, then we take $c$ to be $b$, and if $b \leq a$ we take $c$ to be $a$.

Challenge

Show that the power set $\mathcal{P}(X)$ with the subset relation is filtered.