2 Sets and Relations

Sets

A set is a collection of elements.

We generally use uppercase letters as labels for sets and lowercase letters as labels for their elements. We write $a \in A$ to indicate that $a$ is an element of $A$ .

We may specify a set by enumeration, e.g., ${0, 2, 4}$ is a set of three natural numbers. Alternatively, we may specify the same set by the specification of a condition satisfied by all, and only its elements, e.g., ${x : x$ is an even natural number less than $5}$

Definition 2.1 (Subset) A set $A$ is a subset of another set $B$ , written $A \subseteq B$ , if every element of $A$ is an element of $B$ . A set $A$ is a proper subset of $B$ if $A$ is a subset of $B$ but $B$ is not a subset of $A$ .

Proposition 2.1 (Extensionality) If $A$ is a subset of $B$ and $B$ is a subset of $A$ , then $A$ is the same set as $B$ . That is, $A = B$ .

Example 2.1 ${6} = {x : x$ is perfect number less than $10}$ . A perfect number is the sum of its proper divisors, e.g, 6 is perfect because it is a sum of 1, 2, and 3.

On the one hand,

${6} \subseteq {x : x$ is perfect natural number less than $10}$

because 6 is a perfect natural number, and

On the other,

${a : a$ is perfect natural number less than $10} \subseteq {6}$

because no other natural number less than 10 is perfect.

By Extensionality,

${6} = {a : a$ is perfect natural number less than $10}$

One may think that no mater what objects may be, there is a collection of them. Or, otherwise put, for each condition $\dots x \dots$ , there is a collection of all and only those objects satisfying the condition $\dots x \dots$ . That is, there is a set of the form ${x : \dots x \dots}$ . But that would be a mistake.

There is no set of objects $a$ such that $a \notin a$ . That is, there is no set of the from ${a : a \notin a}$ .

The argument is by indirect proof or reductio at adsurdum, namely, we reach a contradiction from the assumption that such a set exists, call it $R$ . That is, $R = {a : a \notin a}$ .

if $R \in R$ , then $R$ does not satisfy the condition $a \notin a$ , which means that $R \notin R$ .
if $R \notin R$ , then $R$ satisfies the condition $a \notin a$ , which means that $R \in R$ .

We conclude that $R \in R$ if, and only if, $R \notin R$ , which leads to contradiction.

Exercise 2.1 Russell’s paradox relies on the validity of a first-order schema: $\neg \exists y \forall x (R x y \leftrightarrow \neg R x x) .$ Russell substitutes $x \in y$ for $R x y$ , but similar observations result from other substitutions. Justify the observation:

No website links to all and only those websites that do not link to themselves.

That is, some websites are such that there is no way for a website to link to them and only them.

In response to Russell’s paradox, we limit to collections we may construct from given collections in accordance to the axioms of modern set theory.

Proposition 2.2 (Separation) If $A$ is a set and $\dots x \dots$ is a condition on elements of $A$ , then there is a set $B$ of exactly those elements of $A$ which satisfy the condition $\dots x \dots$ . That is, $B = {x \in A : \dots x \dots}$

The axiom of separation yields the existence of certain sets conditional on the existence of a prior set of which they are subsets. To secure the inconditional existence of a set, we require another axiom.

Proposition 2.3 (Empty Set) There is a set without members which we label $\emptyset$ . That is, $\emptyset$ is the set ${a : a \neq a}$ .

We obtain further sets by means of further axioms:

Proposition 2.4 (Pair Set) Given two objects $a$ and $b$ , there is a set whose elements are exactly $a$ and $b$ . We write ${a, b}$ for the pair set of $a$ and $b$ .

Other axioms make sure that sets are closed under other familiar operations.

Relations

We will construe relations as sets of ordered pairs. But an ordered pair is not just a pair set. Instead, we define ordered pairs as special sets from which we can recover the two components of the pair in a certain order.

Definition 2.2 (Ordered Pair) An ordered pair $(a, b)$ is a doubleton set ${{a}, {a, b}}$ . We will write that its first element is $a$ and that its second element is $b$ .

There are alternative definitions of ordered pair, but what matters in all of them is to have the means to encode the fact that $a$ is the first element of the pair by the fact that it is the member of the singleton in the unordered pair.

Proposition 2.5 An ordered pair $(a, b)$ is the same as the ordered pair $(c, d)$ if, and only if, $a$ is the same object as $c$ and $b$ is the same object as $d$ .

Proof. We first unfold the definition of $(a, b)$ as $\{\{a\}\,{a, b\}\}$ and $(c, d)$ as ${{c}, {c, d}}$ . We now argue that if ${{a}, {a, b}}$ is the same set as ${{c}, {c, d}}$ , then $a = c$ and $b = d$ .

We distinguish two cases:

If $a = b$ , then ${{a}, {a, b}}$ is ${{a}, {a, a}}$ , which is just ${a}}$ . So, if ${{a}, {a, b}}$ is the same set as ${{c}, {c, d}}$ , then ${{a}}$ is the same set as ${{c}, {c, d}}$ , which means that $c = d$ and $a = c$ and $b = d$ .
If $a \neq b$ , then the singleton ${a}$ and the doubleton ${a, b}$ must correspond to ${c}$ and ${c, d}$ , respectively, which requires that $a = c$ and $b = d$ .

We can now identify a relation with a set of ordered pairs.

Proposition 2.6 The Cartesian Product $A \times B$ of two sets $A$ and $B$ is the set of ordered pairs whose first element belongs to $A$ and whose second element belongs to $B$ . That is, the Cartesian Product of two sets $A$ and $B$ is: $A \times B = {(a, b) : a \in A \land b \in B}$

Definition 2.3 (Relation) If $A$ is a set, $R$ is a binary relation on $A$ if, and only if, $R$ is a subset of $A \times A$ .

Exercise 2.2 How many binary relations $R$ are there on a given set $A$ ?

If $R$ is a relation on $A$ , we sometimes write $R x y$ or $x R y$ for $(x, y) \in R$ .

Properties of Relations

We now specify a variety of properties a relation may exemplify.

Definition 2.4 If $R$ is a binary relation on a set $A$ ,

$R$ is reflexive on $A$ iff for every element $x \in A$ , $R x x$
$R$ is irreflexive on $A$ iff for every element $x \in A$ , $\neg R x x$ for every element $x$ in $A$ .
$R$ is non-reflexive on $A$ iff for some element $x \in A$ , $\neg R x x$ .

Example 2.2 Consider the set of English words $W$ . Then:

${(u, v) \in W \times W : u$ shares at least one letter with $v}$ is a reflexive relation on $W$ .
${(u, v) \in W \times W : u$ is an antonym of $v}$ is an irreflexive relation on $W$ .
${(u, v) \in W \times W : u$ is $v$ backwards $}$ is a non-reflexive relation on $W$ .22 Consider the word ‘radar’ for example.

Definition 2.5 If $R$ is a binary relation on a set $A$ ,

$R$ is symmetric on $A$ iff for all elements $x, y \in A$ , if $R x y$ , then $R y x$ .
$R$ is asymmetric on $A$ iff for all elements $x, y \in A$ , if $R x y$ , then $\neg R y x$ .
$R$ is non-symmetric on $A$ iff for some elements $x, y \in A$ , $R x y$ and $\neg R y x$ .
$R$ is antisymmetric on $A$ iff for all elements $x, y \in A$ , if $R x y$ , then $R y x$ only if $x = y$

Example 2.3 Consider the set of English words $W$ . Then:

${(u, v) \in W \times W : u$ shares at least one letter with $v}$ is a symmetric relation on $W$ .
${(u, v) \in W \times W : u$ has fewer letters than $v}$ is an asymmetric relation on $W$ .
${(u, v) \in W \times W : u$ is no later than $v$ in the lexicographical order $}$ is an anti-symmetric relation on $W$ .

Definition 2.6 If $R$ is a binary relation on a set $A$ ,

$R$ is transitive on $A$ iff for all elements $x, y, z \in A$ , if $R x y$ and $R y z$ , then $R x z$ .
$R$ is intransitive on $A$ iff for all elements $x, y, z \in A$ , if $R x y$ and $R y z$ , then $\neg R x z$ .
$R$ is non-transitive on $A$ iff for some elements $x, y, z \in A$ , if $R x y$ and $R y z$ , then $\neg R x z$ .

Example 2.4 Consider the set of English words $W$ . Then:

${(u, v) \in W \times W : u$ is no later than $v$ in the lexicographical order $}$ is a transitive relation on $W$ .
${(u, v) \in W \times W : u$ is an antonym of $v}$ is an intransitive relation on $W$ .
${(u, v) \in W \times W : u$ is $v$ backwards $}$ is a non-transitive relation on $W$ .33 Consider the words ‘flow’ and ‘wolf’, for example.

Definition 2.7 (Equivalence Relation) A binary relation on a set $A$ is an equivalence relation on $A$ iff

$R$ is reflexive on $A$ ,
$R$ is symmetric on $A$ , and
$R$ is transitive on $A$ .

Exercise 2.3 Which of the following binary relations on the set of English words $W$ is an equivalence relation on $W$ ?

${(u, v) \in W \times W : u$ is a synonym for $v}$
${(u, v) \in W \times W : u$ is an antonym of $v}$

Given an equivalence relation $R$ on a set $A$ , we will write that two elements $x, y \in A$ are $R$ -equivalent when $R x y$ . Equivalence relations induce a partition of the relevant set $A$ into equivalence classes.

Definition 2.8 (Equivalence Class) If a binary relation $R$ is an equivalence relation on a set $A$ , for each $x \in A$ , the equivalence class of $x$ , written $[x]_{R}$ is the set of elements of $A$ that are $R$ -equivalent to it: $[x]_{R} := {y \in A : R x y} .$ The quotient of $A$ under $R$ is the set of equivalence classes induced by $A$ : $A / R := {[x]_{R} : x \in A} .$

Example 2.5 Given a set $A$ of undergraduate students enrolled at USC, consider the following binary relation $R$ on $A$ :

$R = {(x, y) \in A \times A : x$ is in the same year as $y}$ .

$R$ is an equivalence relation on $A$ : $R$ is reflexive, symmetric, and transitive on $S$ .

Given a student $a$ , the equivalence class $[a]_{R}$ is the set of students in the same year as $a$ . If $a$ is a freshman, then $[a]_{R}$ will be the set of freshman students, if $a$ is a sophomore, then $[a]_{R}$ will be the set of sophomore students, etc.

The quotient of $S$ under $R$ , $S / R$ , consists of four sets: freshman, sophomore, junior, and senior students.

It will later prove important to note that there is a further characterization of equivalence relations in terms of an alternative structural feature of binary relations:

Definition 2.9 If $R$ is a binary relation on a set $A$ , then:

$R$ is euclidean on $A$ iff for all elements $x, y, z \in A$ , if if $R x y$ and $R x z$ , then $R y z$ .

Here is the alternative characterization of an equivalence relation we seek:

Proposition 2.7 If $R$ is a binary relation on a set $A$ , then $R$ is an equivalence relation on $A$ if, and only if, $R$ is reflexive on $A$ and $R$ is euclidean on $A$ .

This is one of the goals for your first assignment. We close with three more structural features of binary relations we will eventually consider:

Definition 2.10 If $R$ is a binary relation on a set $A$ , then:

$R$ is serial on $A$ iff for every $x \in A$ , there is some $y \in A$ such that $R x y$ .
$R$ is convergent on $A$ iff for every $x, y, z \in A$ , if $R x y$ and $R x z$ , then for some $w \in A$ , $R y w$ and $R z w$ .
$R$ is connected on $A$ iff for every $x, y, z \in A$ , if $R x y$ and $R x z$ , then $R y z$ or $R z y$ .