Sets and Maps

1Introduction

This lecture defines the basic operations on sets and the principal properties of maps. These concepts provide the language for specifying algorithmic input and output and for defining the vertex set of a graph.

2Sets and inclusion

A set is a collection of objects called its elements. The notation $$x\in A$$x\in A states that $$x$$x is an element of $$A$$A, whereas $$x\notin A$$x\notin A states that it is not. The empty set, denoted by $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing, has no elements.

A set $$A$$A is a subset of a set $$B$$B, written $$A\subseteq B$$A\subseteq B, if $$x\in A$$x\in A implies $$x\in B$$x\in B for every $$x$$x. The conjunction of $$A\subseteq B$$A\subseteq B and $$B\subseteq A$$B\subseteq A is equivalent to $$A=B$$A=B.

3Operations on sets

For sets $$A$$A and $$B$$B, their union, intersection, and difference are defined by

A complement requires a specified universal set $$U$$U containing the objects under consideration. For $$A\subseteq U$$A\subseteq U, the complement of $$A$$A is

Changing the universal set can therefore change the complement.

The Cartesian product of sets $$A$$A and $$B$$B is the set of ordered pairs

Order matters: in general, $$(a,b)\ne (b,a)$$(a,b)\ne(b,a).

4Relations

A binary relation $$R$$R from a set $$A$$A to a set $$B$$B is a subset $$R\subseteq A\times B$$R\subseteq A\times B of their Cartesian product. If $$(a,b)\in R$$(a,b)\in R, we say that $$a$$a is related to $$b$$b by $$R$$R and may write $$aRb$$aRb. When $$A=B$$A=B, this is called a relation on $$A$$A.

The edge set $$E\subseteq V\times V$$E\subseteq V\times V of a directed graph is a binary relation on its vertex set $$V$$V. In an undirected graph, the order of endpoints is ignored, and a two-element subset $$\{u,v\}$${\{u,v\}} is used as an edge. The following graph lecture defines this distinction precisely.

5Maps

For sets $$A$$A and $$B$$B, a map $$f:A\to B$$f:A\to B is a rule that assigns exactly one element of $$B$$B to every element $$a$$a of $$A$$A. The set $$A$$A is the domain, the set $$B$$B is the codomain, and the assigned element is denoted by $$f\left(a\right)$$f(a). Thus every domain element must receive a value, and that value must be unique.

For $$S\subseteq A$$S\subseteq A and $$T\subseteq B$$T\subseteq B, the image of $$S$$S and the preimage of $$T$$T are

In particular, $$f\left(A\right)$$f(A) is the image of the map. Although $$f\left(A\right)\subseteq B$$f(A)\subseteq B, the image need not equal the codomain. The notation $$f^{-1}\left(T\right)$$f^{-1}(T) for a preimage remains valid even when $$f$$f has no inverse map.

6Injective, surjective, and bijective maps

A map $$f:A\to B$$f:A\to B is injective if

for all $$a_1,a_2\in A$$a_1,a_2\in A. Equivalently, distinct inputs have distinct outputs.

The map is surjective if, for every $$b\in B$$b\in B, there exists $$a\in A$$a\in A such that $$f\left(a\right)=b$$f(a)=b. This condition is equivalent to $$f\left(A\right)=B$$f(A)=B. A map that is both injective and surjective is bijective. Exactly for a bijection, there is an inverse map $$f^{-1}:B\to A$$f^{-1}:B\to A that assigns each $$b\in B$$b\in B its unique preimage.

7Example

Let $$A=\{1,2,3\}$$A=\{1,2,3\} and $$B=\{a,b,c,d\}$$B=\{a,b,c,d\}, and define

Then $$f\left(A\right)=\{a,b\}$$f(A)=\{a,b\} and $$f^{-1}\left(\right\{b,c\left\}\right)=\{2,3\}$$f^{-1}(\{b,c\})=\{2,3\}. Because $$f\left(2\right)=f\left(3\right)$$f(2)=f(3), the map is not injective. Because $$c$$c and $$d$$d do not belong to its image, it is not surjective either.

8Connections to computer science

An array of length $$n$$n can be represented as a map from the index set $$\{0,1,\dots ,n-1\}$$\{0,1,\ldots,n-1\} to a codomain of values. A deterministic algorithm whose output is uniquely determined for every input can be specified as a map from its set of admissible inputs to its set of outputs. When a problem permits more than one correct output, its output specification can instead be represented as a relation between inputs and admissible outputs. A graph $$G=(V,E)$$G=(V,E) is described by a vertex set $$V$$V and an edge set $$E$$E whose elements are ordered pairs in a Cartesian product or two-element subsets of $$V$$V.

9Summary

• A set is determined by element membership, and $$A\subseteq B$$A\subseteq B means that $$x\in A\Rightarrow x\in B$$x\in A\Rightarrow x\in B holds for every $$x$$x.
• A complement requires a universal set, while a Cartesian product distinguishes the order of its coordinates.
• A map assigns exactly one codomain element to every domain element.
• Under an injective map, distinct inputs have distinct outputs; under a surjective map, every codomain element lies in the image; and a bijection gives a one-to-one correspondence.