2. Families of sets, relations and functions

Part 1.: problems, solutions.

Families of sets

A family of sets is simply a set of sets. For example: \mathcal{A}=\{\{\varnothing\},\{\varnothing,\{\varnothing\},\{\{\varnothing\}\}\},\{\varnothing,\{\{\varnothing\}\}\}\}.

A union of a family of sets consists of all elements of all its elements. \bigcup\mathcal{A}=\{a\colon \exists_{A\in\mathcal{A}}a\in A\}. In our example: \bigcup\mathcal{A}=\{\varnothing,\{\varnothing\},\{\{\varnothing\}\}\}.

An intersection of a family of sets consists of all elements appearing in every its element. \bigcap\mathcal{A}=\{a\colon \forall_{A\in\mathcal{A}}a\in A\}. In our example: \bigcap\mathcal{A}=\{\varnothing\}.

We can define an ordered pair of elements a,b as \left<a,b\right>=\{\{a\},\{a,b\}\}. A product of two given sets A,B is the set A\times B=\{\left<a,b\right>\colon a\in A,b\in B\}. Set A\times A is usually denoted as A^2.

For a given set A, the family \mathcal{P}(A) consists of all subsets of A. E.g. for A=\{1,2,3\}, we get \mathcal{P}(A)=\{\varnothing, \{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}.


A subset r\subseteq A^2 is called a relation on A. The fact that \left<a,b\right>\in r is usually denoted as a r b. As for any other sets we can consider a union or intersection of two relations. We often also consider some properties of relations. E.g. a relation r on A is reflexive, if for any a\in A, a r a. Notice that giver two reflexive r, r', their intersection r\cap r' is also reflexive, because for all a\in A, a r a and a r' a, so also \left<a,a\right>\in r\cap r'.

Given a relation r\subseteq A\times B, the set of those elements of A which appear on the left side is called its left-side domain, in other words it is the set \{a\in A\colon \exists_{b\in B} a r b\}. Similarly its right-side domain is \{b\in B\colon \exists_{a\in A} a r b\}. Therefore if, for example, r=\{\left<n,5n\right>\colon n\in\mathbb{N}\}, \mathbb{N} is the left-side domain of r the set of natural numbers divisible by 5 is the right-side domain.

The field of a relation is the union of its left- and right-side domains. In the above example the whole set of natural numbers is the field of r.

The inverse of a relation r is the relation r^{-1}=\{\left<b,a\right>\in B\times A\colon \left<a,b\right>\in r\}.


A relation f\subseteq A\times B will be called a function, if for every argument a\in A it assigns at most one element (value) from B, in other words if:

    \[\forall_{a\in A} \forall_{b,b'\in B}\left<a,b\right>,\left<a,b'\right>\in f\rightarrow b=b'.\]

Sometimes we additionally request that every element of A is used:

    \[\forall_{a\in A}\exists_{b\in B} \left<a,b\right>\in f\]

and then relations which satisfy the first condition but may not satisfy the second are called partial functions. But often (especially when studying mathematical analysis) we ignore the second condition and call all relations satisfying the first condition functions and studying instead their domains.

If f is a function and \left<a,b\right>\in f, we write f(a)=b. The set of all functions f\colon A\to B will be denoted B^A.

E.g. F=\{\left<x,y\right>\colon y^3=x^2\} is a function, because if \left<x,y'\right>,\left<x,y\right>\in F, then y=\sqrt[3]{x^2}=y'.

Meanwhile: F=\{\left<x,y\right>\colon y^2=x\} is not a function, because \left<1,1\right>,\left<1,-1\right>\in F.

One-to-one functions and onto functions

A function is one-to-one (or monomorphism, injection), if different argument always give different values:

    \[\forall_{a,a'\in A} f(a)=f(a')\rightarrow a=a'.\]

A function f\colon A\to B is onto (or epimorphism, surjection), if every value is used:

    \[\forall_{b\in B}\exists_{a\in A} f(a)=b.\]

A bijection is a function which is both onto and one-to-one.

E.g. function f\colon \mathbb{R}\to\mathbb{R}, f(x)=x^2 is not one-to-one, because f(-1)=f(1). It is also not onto, because there does not exist r\in\mathbb{R} such that f(r)=-1.

On the other hand function F\colon\mathbb{N}\to\mathcal{P}{\mathbb{N}}, F(n)=\{n\} is one-to one, because if \{n\}=\{n'\}, then n=n'. It is not onto, because there does not exist n such that F(n)=\{1,2\}.

Function g\colon\mathbb{Z}\to\mathbb{N}, g(a)=|a| is not one-to-one, because g(-1)=g(1). It is onto, since for any n\in\mathbb{N}, we have g(n)=n.

Function G\colon\mathbb{N}^2\to\mathbb{N}^2, G(\left<n,m\right>)=\left<m,n\right> is one-to-one, because if G(\left<n,m\right>)=G(\left<n',m'\right>), then \left<m,n\right>=\left<m',n'\right>, so n=n',m=m'. It is also onto, because for any \left<n,m\right>\in\mathbb{N}^2 we have G(\left<m,n\right>)=\left<n,m\right>. Therefore G is a bijection.

Reverse function

If a function f\colon X\to Y is a bijection, then its reverse relation is also a function, called the reverse function f^{-1}\colon Y\to X. We can also consider the reverse function for a 1-1 function, but it will be defined on its image only.

Function g\colon Y\to X is the reverse function of f\colon X\to Y, if and only if f\circ g =id_Y and g\circ f=\id_X. It is if for all y\in Y, f(g(y)=y and for all x\in X, g(f(x))=x.

E.g.: let f\colon [0,\infty)\to [0,\infty), f(x)=x^2. Then f^{-1}=g, where g\colon [0,\infty)\to [0,\infty), g(y)=\sqrt{y}.