Functions

So, a binary relation is a set of ordered pairs, any such set. A binary relation on a set \(X\) is a binary relation which is a subset of \(X\times X\). A binary relation between sets \(X\) and \(Y\) is a binary relation which is a subset of \(X\times Y\). Now, I want to say what is a function: a function will be a special kind of a binary relation.

Let us fix a binary relation \(R\). This just means that \(R\) is a set of ordered pairs. Two natural sets assigned to \(R\) are its domain and its range: 

\[\mathrm{dom}(R):=\{x : \exists y, \langle x,y \rangle\in R\},\]

\[\mathrm{ran}(R):=\{y : \exists x, \langle x,y \rangle \in R\}.\]

Of course, it's not immediate that these are sets, but there is no doubt that they are classes. In order for a class to be a set, it suffices for it to be contained in a set. More precisely, if a class \(C\) is contained in a set \(X\), then \(C\) is equal to the intersection \(X\cap C\). The intersection of a set and a class is a set by Axiom of Comprehension. Hence, \(C\) is a set. Back to the case of \(R\), in order to show that \(\mathrm{dom}(R)\) is a set, we just need to pinpoint one of its supersets. Here's what works:

\[\mathrm{dom}(R)\subseteq\bigcup\bigcup R.\]

To understand this, you'll just need to remind yourself of the definition of an ordered pair. The reasoning here is similar to the one that we had with \(\times\). We can see in a similar fashion that \(\mathrm{ran}(R)\) is a set.

Now, these two sets are very special when the relation \(R\) is concerned. To begin with,

\[R\subseteq\mathrm{dom}(R)\times\mathrm{ran}(R),\]

or in other words, \(R\) is a binary relation between \(\mathrm{dom}(R)\) and \(\mathrm{ran}(R)\). However, more is true: if \(A\) and \(B\) are any sets and if it is true that \(R\) is a binary relation between \(A\) and \(B\), then we necessarily have that \(\mathrm{dom}(R)\subseteq A\) and \(\mathrm{ran}(R)\subseteq B\). Said differently, \(\mathrm{dom}(R)\) and \(\mathrm{ran}(R)\) are the least sets \(A\) and \(B\) such that \(R\) is a binary relation between \(A\) and \(B\).

If \(x\in\mathrm{dom}(R)\), then by definition, there exists \(y\) such that \(\langle x,y \rangle\in R\). Of course, there can be more then one such \(y\). For example, if \(R=<\) is the standard order of natural numbers, then \(0\in \mathrm{dom}(<)\) because \(\langle 0,1 \rangle\in <\). However, it is also true that \(\langle 0,2 \rangle\in <\). This means that if \(x=0\) we can take both \(y=1\) and \(y=2\) and get \(\langle x,y \rangle\in <\).

Functions are a special kind of binary relations where this doesn't happen. More precisely, \(R\) is a function if and only if \(R\) is a binary relation and in addition, for every \(x\in\mathrm{dom}(R)\), there exists a unique \(y\) such that \(\langle x,y \rangle\in R\).

Here is an example of a function. Let us define that \(\langle x,y \rangle \in S\) if and only if \(x\) is a natural number and \(y=x\cup\{x\}\). If \(n\) is a natural number, then we said that \(n\cup\{n\}\) is its successor. So, \(x S y\) just means "\(x\) and \(y\) are two consecutive natural numbers (in that order)". However, since every natural number has a unique successor, the relation \(S\) meets the requirement to be a function!

A function will very often be denoted by \(f\). We also frequently write 

\[f:A\longrightarrow B,\]

by which we mean "\(f\) is a function, \(\mathrm{dom}(f)=A\), and \(\mathrm{ran}(f)\subseteq B\)". For the set \(A\) we require it to be exactly equal to the domain of \(f\), while for the set \(B\) we just require that all the points in the range of \(f\) are contained in it. For example, 

\[S:\omega\longrightarrow\omega,\]

while \(\mathrm{ran}(S)=\omega-\{0\}\) (\(0\) is not a successor of anything!).

One more piece of standard notation. So, if \(f\) is a function and \(x\in\mathrm{dom}(f)\), then there is a unique \(y\) such that \(\langle x,y \rangle\in f\). Thus, it makes sense to name this unique \(y\): we name it \(f(x)\). Here are examples:

\[S(0)=1,\ S(2)=3,\ S(S(3))=5.\]

Comments

Post a Comment

Popular posts from this blog

Axiom of Powerset

So far, I listed Axioms of the Empty Set, Extensionality, Pairing, Union, Comprehension, Induction, Replacement, and Infinity. This is not the complete list making up the Mathematical Theory of Everything, we have to add two more axioms to the list. These axioms are called Powerset  and Choice . Axiom of Powerset is relatively easy to state: for every set \(x\) in the universe, there exists a set whose elements are exactly all subsets of \(x\) . As usual, Extensionality implies that such object must be unique and we denote it by \(P(x)\). So, the defining characteristic of the set \(P(x)\) is that a given set \(y\) belongs to \(P(x)\) if and only if \(y\) is a subset of \(x\). The other axioms don't imply existence of the powerset. More precise explanation of this will have to wait, but for now, we can kind of see that the set \(P(x)\) is "larger" than \(x\). If \(a\) is an element of \(x\), than \(\{a\}\) is a subset of \(x\), so an element of \(P(x)\). But there are oth...
Read more

Wellorderings

I've already told you what is an ordering, but let me give a quick reminder. A ( strict) ordering  on some set \(X\) is a a binary relation, usually denoted by some variation on the symbol \(<\), which is  irreflexive,  that is for all \(x\in X\), it is not  the case that \(x<x\), transitive, that is for all \(x,y,z\in X\), if \(x<y\) and \(y<z\), then \(x<z\). One very important example is the standard ordering on natural numbers. In that case, we have that \(X=\omega\) and \(<=\in\). To understand the second thing, recall that in Set Theory, natural numbers are coded as \(0=\emptyset\), \(1=\{0\}\), \(2=\{0,1\}\), \(3=\{0,1,2\}\), and so on. Hence, for example, \(1<3\) because \[1\in \{0,1,2\}=3.\] In addition to the irreflexivity and transitivity, this relation satisfies some other important properties. One of them is being total, that is for all \(x,y\in X\), one of the options is true: \(x<y\) or \(x=y\) or \(x>y\). The orderings which...
Read more

Relations

I'll write this post in form of a dialogue between Master (M) and Apprentice (A). A: Say, O Noble Teacher, what are those "relations" that mathematicians always talk about? M: Why, my dear Apprentice, you have already seen one kind of relations! A: How so, O Exalted One? M: Well, \(\in\) is a relation and \(V\) is also a relation! These are class-sized relations. A: Oh, I see! But how does their "relation-ness" manifest? M: In the case of \(\in\), it divides pairs of sets \((x,y)\) into those for which \(x\) belongs to \(y\) and into those for which \(x\) does not belong to \(y\). So, it tells us whether the statement ''\(x\in y\)" is true or false for any particular pair of sets \((x,y)\). In this sense, they are no different from predicates or classes. Class-sized relations are the same thing as predicates. A: I seem to understand now! \(\in\) is a binary predicate, so a class-sized relation. \(V\) is a class, which is the same thing as a unary pr...
Read more