Relations - Revision history

Khanh at 21:42, 11 November 2021

2021-11-11T21:42:57Z

Lila: /* Operations on Relations */

2021-09-27T21:31:10Z

Operations on Relations

Lila: /* Equivalence relations */

2021-09-27T21:27:02Z

Equivalence relations

Lila: /* Introduction */

2021-09-27T21:25:38Z

Introduction

Lila: Created page with "== Introduction == This article examines the concepts of a ''function'' and a ''relation''. A '''''relation''''' is any association or link between elements of one set, call..."

2021-09-27T21:24:00Z

Created page with "== Introduction == This article examines the concepts of a ''function'' and a ''relation''. A '''''relation''''' is any association or link between elements of one set, call..."

New page

== Introduction ==

This article examines the concepts of a ''function'' and a ''relation''.

A '''''relation''''' is any association or link between elements of one set, called the '''''domain''''' or (less formally) the ''set of inputs'', and another set, called the '''''range''''' or ''set of outputs''. Some people mistakenly refer to the range as the ''codomain''(range), but as we will see, that really means the ''set of all possible outputs''—even values that the relation does not actually use. (Beware: some authors do not use the term ''codomain''(range), and use the term ''range'' instead for this purpose. Those authors use the term '''''image''''' for what we are calling ''range''. So while it '''is''' a mistake to refer to the ''range'' or ''image'' as the ''codomain''(range), it is '''not necessarily''' a mistake to refer to ''codomain'' as ''range''.)

For example, if the ''domain'' is a set Fruits = {apples, oranges, bananas} and the ''codomain''(range) is a set Flavors = {sweetness, tartness, bitterness}, the flavors of these fruits form a relation: we might say that apples are related to (or associated with) '''both''' sweetness and tartness, while oranges are related to tartness only and bananas to sweetness only. (We might disagree somewhat, but that is irrelevant to the topic of this book.) Notice that "bitterness", although it is one of the possible Flavors (codomain)(range), is not really used for any of these relationships; so it is not part of the ''range'' (or ''image'') {sweetness, tartness}.

Another way of looking at this is to say that a relation is a ''subset of ordered pairs'' drawn from the ''set of all possible ordered pairs'' (of elements of two other sets, which we normally refer to as the ''Cartesian product'' of those sets). Formally, R is a relation if

: <big><math>R \subseteq X \times Y = \{(x, y) | x \in X, y \in Y\}</math></big>

for the domain X and codomain(range) Y. The '''''inverse relation''''' of R, which is written as R-1, is what we get when we interchange the X and Y values:

: <big><math>R^{-1} = \{(y, x) | (x, y) \in R\}</math></big>

Using the example above, we can write the relation in set notation: {(apples, sweetness), (apples, tartness), (oranges, tartness), (bananas, sweetness)}. The inverse relation, which we could describe as "fruits of a given flavor", is {(sweetness, apples), (sweetness, bananas), (tartness, apples), (tartness, oranges)}. (Here, as elsewhere, the order of elements in a set has no significance.)

One important kind of relation is the ''function''. A '''''function''''' is a relation that has '''exactly one output''' for every possible input '''in the domain'''. (The domain does not necessarily have to include all possible objects of a given type. In fact, we sometimes intentionally use a ''restricted domain'' in order to satisfy some desirable property.) The relations discussed above (flavors of fruits and fruits of a given flavor) are '''not''' functions: the first has two possible outputs for the input "apples" (sweetness and tartness); and the second has two outputs for both "sweetness" (apples and bananas) and "tartness" (apples and oranges).

The main reason for not allowing multiple outputs with the same input is that it lets us apply the same function to different forms of the same thing without changing their equivalence. That is, if f is a function with a (or b) in its domain, then a = b implies that f(a) = f(b). For example, z - 3 = 5 implies that z = 8 because f(x) = x + 3 is a function unambiguously defined for all numbers x.

The converse, that f(a) = f(b) implies a = b, is not always true. When it is, there is never more than one ''input'' x for a certain ''output'' y = f(x). This is the same as the definition of function, but with the roles of X and Y interchanged; so it means the ''inverse relation'' f-1 '''must also''' be a function. In general—regardless of whether or not the original relation was a function—the inverse relation will ''sometimes'' be a function, and sometimes not.

When f and f-1 are both functions, they are called '''''one-to-one''''', '''''injective''''', or '''''invertible functions'''''. This is one of two very important properties a function f might (or might not) have; the other property is called '''''onto''''' or '''''surjective''''', which means, for any y ∈ Y (in the codomain), there is some x ∈ X (in the domain) such that f(x) = y. In other words, a ''surjective'' function f ''maps onto'' every possible output '''at least once'''.

A function can be '''neither''' one-to-one nor onto, '''both''' one-to-one and onto (in which case it is also called '''''bijective''''' or a '''''one-to-one correspondence'''''), or just one and not the other. (As an example which is neither, consider f = {(0,2), (1,2)}. It is a function, since there is only one y value for each x value; but there is more than one input x for the output y = 2; and it clearly does not "map onto" all integers.)

== Relations ==
In the above section dealing with functions and their properties, we noted the important property that all functions must have, namely that if a function does map a value from its domain to its co-domain, it must map this value to only one value in the co-domain.

Writing in set notation, if ''a'' is some fixed value:
: |{f(x)|x=a}| ∈ {0, 1}

The literal reading of this statement is: the ''cardinality'' (number of elements) of the set of all values f(x), such that x=a for some fixed value a, is an element of the set {0, 1}. In other words, the number of ''outputs'' that a function f may have at any fixed ''input'' a is either zero (in which case it is ''undefined'' at that input) or one (in which case the output is unique).

However, when we consider the ''relation'', we relax this constriction, and so a relation may map one value to more than one other value. In general, a relation is '''any''' subset of the Cartesian product of its domain and co-domain.

All functions, then, can be considered as relations also.

=== Notations ===
When we have the property that one value is related to another, we call this relation a ''binary relation'' and we write it as
: x R y
where R is the relation.

For arrow diagrams and set notations, remember for relations we do not have the restriction that functions do and we can draw an arrow to represent the mappings, and for a set diagram, we need only write all the ordered pairs that the relation does take: again, by example
:f = {(0,0),(1,1),(1,-1),(2,2),(2,-2)}
is a relation and not a function, since both 1 and 2 are mapped to two values, (1 and -1, and 2 and -2 respectively)
example let A=2,3,5;B=4,6,9 then
A*B=(2,4),(2,6),(2,9),(3,4),(3,6),(3,9),(5,4),(5,6),(5,9)
Define a relation R=(2,4),(2,6),(3,6),(3,9)
add functions and problems to one another.

=== Some simple examples ===
Let us examine some simple relations.

Say f is defined by
: {(0,0),(1,1),(2,2),(3,3),(1,2),(2,3),(3,1),(2,1),(3,2),(1,3)}

This is a relation (not a function) since we can observe that 1 maps to 2 and 3, for instance.

Less-than, "<", is a relation also. Many numbers can be less than some other fixed number, so it cannot be a function.

=== Properties ===
When we are looking at relations, we can observe some special properties different relations can have.

==== Reflexive ====
A relation is ''reflexive'' if, we observe that for all values a:
: ''a'' R ''a''
In other words, all values are related to themselves.

The relation of equality, "=" is reflexive. Observe that for, say, all numbers a (the domain is '''R'''):
: ''a'' = ''a''
so "=" is reflexive.

In a reflexive relation, we have arrows for all values in the domain pointing back to themselves:
:[[Image:Arrow diagram reflexive.png]]

Note that ≤ is also reflexive (a ≤ a for any a in '''R'''). On the other hand, the relation < is not (a < a is false for any a in '''R''').

==== Symmetric ====
A relation is ''symmetric'' if, we observe that for all values of a and b:
: ''a'' R ''b'' implies ''b'' R ''a''

The relation of equality again is symmetric. If ''x''=''y'', we can also write that ''y''=''x'' also.

In a symmetric relation, for each arrow we have also an opposite arrow, i.e. there is either no arrow between ''x'' and ''y'', or an arrow points from ''x'' to ''y'' and an arrow back from ''y'' to ''x'':
:[[Image:Arrow diagram symmetric.png]]

Neither ≤ nor < is symmetric (2 ≤ 3 and 2 < 3 but neither 3 ≤ 2 nor 3 < 2 is true).

==== Transitive ====
A relation is ''transitive'' if for all values ''a'', ''b'', ''c'':
: ''a'' R ''b'' and ''b'' R ''c'' implies ''a'' R ''c''

The relation ''greater-than'' ">" is transitive. If ''x'' > ''y'', and ''y'' > ''z'', then it is true that ''x'' > ''z''. This becomes clearer when we write down what is happening into words. ''x'' is greater than ''y'' and ''y'' is greater than ''z''. So ''x'' is greater than both ''y'' and ''z''.

The relation ''is-not-equal'' "≠" is not transitive. If ''x'' ≠ ''y'' and ''y'' ≠ ''z'' then we might have ''x'' = ''z'' or ''x'' ≠ ''z'' (for example 1 ≠ 2 and 2 ≠ 3 and 1 ≠ 3 but 0 ≠ 1 and 1 ≠ 0 and 0 = 0).

In the arrow diagram, every arrow between two values ''a'' and ''b'', and ''b'' and ''c'', has an arrow going straight from ''a'' to ''c''.
:[[Image:Arrow diagram transitive.png]]

==== Antisymmetric ====
A relation is ''antisymmetric'' if we observe that for all values ''a'' and ''b'':
: ''a'' R ''b'' and ''b'' R ''a'' implies that ''a''=''b''
'''Notice that antisymmetric is not the same as "not symmetric."'''

Take the relation ''greater than or equal to'', "≥"
If ''x'' ≥ ''y'', and ''y'' ≥ x, then ''y'' must be equal to ''x''.
a relation is anti-symmetric if and only if a∈A, (a,a)∈R

==== Trichotomy ====
A relation satisfies ''trichotomy'' if we observe that for all values ''a'' and ''b'' it holds true that:
''a''R''b'' ''or'' ''b''R''a''

The relation ''is-greater-or-equal'' satisfies since, given 2 real numbers ''a'' and ''b'', it is true that whether ''a'' ≥ ''b'' or ''b'' ≥ ''a'' (both if ''a'' = ''b'').

==== Problem set ====
Given the above information, determine which relations are reflexive, transitive, symmetric, or antisymmetric on the following - there may be more than one characteristic. (Answers follow.)
''x'' R ''y'' if
# x = y
# x < y
# x2 = y2
# x ≤ y

===== Answers =====
#Symmetric, Reflexive, and transitive
#Transitive, Trichotomy
#Symmetric, Reflexive, and transitive (x2 = y2 is just a special case of equality, so all properties that apply to x = y also apply to this case)
#Reflexive, Transitive and Antisymmetric (and satisfying Trichotomy)

=== Equivalence relations ===
We have seen that certain common relations such as "=", and congruence (which we will deal with in the next section) obey some of these rules above. The relations we will deal with are very important in discrete mathematics, and are known as ''equivalence relations''. They essentially assert some kind of equality notion, or ''equivalence'', hence the name.

==== Characteristics of equivalence relations ====
For a relation R to be an ''equivalence relation'', it must have the following properties, viz. R must be:
* symmetric
* transitive
* reflexive
(A helpful mnemonic, S-T-R)

In the previous problem set you have shown equality, "=", to be reflexive, symmetric, and transitive. So "=" is an equivalence relation.

We denote an equivalence relation, in general, by <math>x \sim y</math>.

==== Example proof ====
Say we are asked to prove that "=" is an equivalence relation.
We then proceed to prove each property above in turn (Often, the proof of transitivity is the hardest).

* '''Reflexive''': Clearly, it is true that ''a'' = ''a'' for all values a. Therefore, = is reflexive.
* '''Symmetric''': If ''a'' = ''b'', it is also true that ''b'' = ''a''. Therefore, = is symmetric
* '''Transitive''': If ''a'' = ''b'' and ''b'' = ''c'', this says that ''a'' is the same as ''b'' which in turn is the same as ''c''. So ''a'' is then the same as ''c'', so ''a'' = ''c'', and thus = is transitive.

Thus = is an equivalence relation.

==== Partitions and equivalence classes ====
It is true that when we are dealing with relations, we may find that many values are related to one fixed value.

For example, when we look at the quality of ''congruence'', which is that given some number ''a'', a number congruent to ''a'' is one that has the same remainder or ''modulus'' when divided by some number ''n'', as ''a'', which we write
:a &equiv; b (mod n)
and is the same as writing
:''b'' = ''a''+''kn'' for some integer k.
(We will look into congruences in further detail later, but a simple examination or understanding of this idea will be interesting in its application to equivalence relations)

For example, 2 &equiv; 0 (mod 2), since the remainder on dividing 2 by 2 is in fact 0, as is the remainder on dividing 0 by 2.

We can show that congruence is an equivalence relation (This is left as an exercise, below '''Hint''' use the equivalent form of congruence as described above).

However, what is more interesting is that we can group all numbers that are equivalent to each other.

With the relation congruence ''modulo'' 2 (which is using n=2, as above), or more formally:
: x ~ y if and only if x &equiv; y (mod 2)
we can group all numbers that are equivalent to each other. Observe:
: <math>0 \equiv 2 \equiv 4 \equiv \ldots \pmod{2}</math>
: <math>1 \equiv 3 \equiv 5 \equiv \ldots \pmod{2}</math>
This first equation above tells us all the ''even'' numbers are equivalent to each other under ~, and all the ''odd'' numbers under ~.

We can write this in set notation. However, we have a special notation.
We write:
:[0]={0,2,4,...}
:[1]={1,3,5,...}

and we call these two sets ''equivalence classes''.

All elements in an equivalence class by definition are equivalent to each other, and thus note that we do not need to include [2], since 2 ~ 0.

We call the act of doing this 'grouping' with respect to some equivalence relation ''partitioning'' (or further and explicitly ''partitioning a set S into equivalence classes under a relation ~''). Above, we have partitioned '''Z''' into equivalence classes [0] and [1], under the relation of congruence modulo 2.

==== Problem set ====
Given the above, answer the following questions on equivalence relations (Answers follow to even numbered questions)
# Prove that congruence is an equivalence relation as before (See hint above).
# Partition {x | 1 ≤ x ≤ 9} into equivalence classes under the equivalence relation
<math> x \sim y\ \mbox{iff}\ x \equiv y \pmod{6}</math>

===== Answers =====
2. [0]={6}, [1]={1,7}, [2]={2,8}, [3]={3,9}, [4]={4}, [5]={5}

=== Partial orders ===
We also see that "≥" and "≤" obey some of the rules above. Are these special kinds of relations too, like equivalence relations? Yes, in fact, these relations are specific examples of another special kind of relation which we will describe in this section: the ''partial order''.

As the name suggests, this relation gives some kind of ordering to numbers.

==== Characteristics of partial orders ====
For a relation R to be a partial order, it must have the following three properties, viz R must be:
* reflexive
* antisymmetric
* transitive
(A helpful mnemonic, R-A-T)

We denote a partial order, in general, by <math>x \preceq y</math>.

'''Question:'''
# Suppose R is a relation on a set of integers Z then prove that R is a partial order relation on Z iff a=b raise to power r.

==== Example proof ====
Say we are asked to prove that "≤" is a partial order.
We then proceed to prove each property above in turn (Often, the proof of transitivity is the hardest).

===== Reflexive =====
Clearly, it is true that ''a'' ≤ ''a'' for all values a.
So ≤ is reflexive.

===== Antisymmetric =====
If ''a'' ≤ ''b'', and ''b'' ≤ ''a'', then a ''must'' be equal to ''b''.
So ≤ is antisymmetric

===== Transitive =====
If ''a'' ≤ ''b'' and ''b'' ≤ ''c'', this says that ''a'' is less than ''b'' and ''c''. So ''a'' is less than ''c'', so ''a'' ≤ ''c'', and thus ≤ is transitive.

Thus ≤ is a partial order.

==== Problem set ====
Given the above on partial orders, answer the following questions
# Prove that divisibility, |, is a partial order (a | b means that a is a factor of b, i.e., on dividing b by a, no remainder results).
# Prove the following set is a partial order: (''a'', ''b'') <math>\preceq</math> (''c'', ''d'') implies ''ab''≤''cd'' for ''a'',''b'',''c'',''d'' integers ranging from 0 to 5.

===== Answers =====
2. Simple proof; Formalization of the proof is an optional exercise.
:Reflexivity: (''a'', ''b'') <math>\preceq</math> (''a'', ''b'') since ''ab''=''ab''.
:Antisymmetric: (''a'', ''b'') <math>\preceq</math> (''c'', ''d'') and (''c'', ''d'') <math>\preceq</math> (''a'', ''b'') since ''ab''≤''cd'' and ''cd''≤''ab'' imply ''ab''=''cd''.
:Transitive: (''a'', ''b'') <math>\preceq</math> (''c'', ''d'') and (''c'', ''d'') <math>\preceq</math> (''e'', ''f'') implies (''a'', ''b'') <math>\preceq</math> (''e'', ''f'') since ''ab''≤''cd''≤''ef'' and thus ''ab''≤''ef''

==== Posets ====
A partial order imparts some kind of "ordering" amongst elements of a set. For example, we only know that 2 ≥ 1 because of the partial ordering ≥.

We call a set A, ordered under a general partial ordering <math>\preceq</math>, a ''partially ordered set'', or simply just ''poset'', and write it (A, <math>\preceq</math>).

===== Terminology =====
There is some specific terminology that will help us understand and visualize the partial orders.

When we have a partial order <math>\preceq</math>, such that ''a'' <math>\preceq</math> ''b'', we write <math>\prec</math> to say that a <math>\preceq</math> but ''a'' ≠ ''b''. We say in this instance that a ''precedes'' b, or ''a'' is a predecessor of ''b''.

If (A, <math>\preceq</math>) is a poset, we say that ''a'' is an immediate predecessor of ''b'' (or ''a'' immediately precedes ''b'') if there is no ''x'' in A such that ''a'' <math>\prec</math> ''x'' <math>\prec</math> ''b''.

If we have the same poset, and we also have ''a'' and ''b'' in A, then we say ''a'' and ''b'' are ''comparable'' if ''a'' <math>\preceq</math> ''b'' or ''b'' <math>\preceq</math> ''a''. Otherwise they are ''incomparable''.

==== Hasse diagrams ====
''Hasse diagrams'' are special diagrams that enable us to visualize the structure of a partial ordering. They use some of the concepts in the previous section to draw the diagram.

A Hasse diagram of the poset (A, <math>\preceq</math>) is constructed by
* placing elements of A as points
* if ''a'' and ''b'' ∈ A, and ''a'' is an immediate predecessor of b, we draw a line from ''a'' to ''b''
* if ''a'' <math>\prec</math> ''b'', put the point for ''a'' lower than the point for ''b''
* not drawing loops from ''a'' to ''a'' (this is assumed in a partial order because of reflexivity)

=== Operations on Relations ===

There are some useful operations one can perform on relations, which allow to
express some of the above mentioned properties more briefly.

==== Inversion ====
Let R be a relation, then its inversion, R-1 is defined by

R-1 := {(a,b) | (b,a) in R}.

==== Concatenation ====
Let R be a relation between the sets A and B, S be a relation between B and C. We can concatenate
these relations by defining

R • S := {(a,c) | (a,b) in R and (b,c) in S for some b out of B}

==== Diagonal of a Set ====
Let A be a set, then we define the diagonal (D) of A by

D(A) := {(a,a) | a in A}

==== Shorter Notations ====
Using above definitions, one can say (lets assume R is a relation between A and B):

R is ''transitive'' if and only if R • R is a subset of R.

R is ''reflexive'' if and only if D(A) is a subset of R.

R is ''symmetric'' if R-1 is a subset of R.

R is ''antisymmetric'' if and only if the intersection of R and R-1 is D(A).

R is ''asymmetric'' if and only if the intersection of D(A) and R is empty.

R is a ''function'' if and only if R-1 • R is a subset of D(B).

In this case it is a function A → B.
Let's assume R meets the condition of being a function, then

R is ''injective'' if R • R-1 is a subset of D(A).

R is ''surjective'' if {b | (a,b) in R} = B.

← Older revision		Revision as of 21:42, 11 November 2021
Line 239:		Line 239:

	R is ''surjective'' if {b \| (a,b) in R} = B.		R is ''surjective'' if {b \| (a,b) in R} = B.
		+
		+	== Licensing ==
		+	Content obtained and/or adapted from:
		+	* [https://en.wikibooks.org/wiki/Discrete_Mathematics/Functions_and_relations Functions and relations, Wikibooks: Discrete Mathematics] under a CC BY-SA license

← Older revision		Revision as of 21:25, 27 September 2021
Line 1:		Line 1:
	== Introduction ==		== Introduction ==
−
−	~~This article examines the concepts of a ''function'' and a ''relation''.~~

	A '''''relation''''' is any association or link between elements of one set, called the '''''domain''''' or (less formally) the ''set of inputs'', and another set, called the '''''range''''' or ''set of outputs''. Some people mistakenly refer to the range as the ''codomain''(range), but as we will see, that really means the ''set of all possible outputs''—even values that the relation does not actually use. (Beware: some authors do not use the term ''codomain''(range), and use the term ''range'' instead for this purpose. Those authors use the term '''''image''''' for what we are calling ''range''. So while it '''is''' a mistake to refer to the ''range'' or ''image'' as the ''codomain''(range), it is '''not necessarily''' a mistake to refer to ''codomain'' as ''range''.)		A '''''relation''''' is any association or link between elements of one set, called the '''''domain''''' or (less formally) the ''set of inputs'', and another set, called the '''''range''''' or ''set of outputs''. Some people mistakenly refer to the range as the ''codomain''(range), but as we will see, that really means the ''set of all possible outputs''—even values that the relation does not actually use. (Beware: some authors do not use the term ''codomain''(range), and use the term ''range'' instead for this purpose. Those authors use the term '''''image''''' for what we are calling ''range''. So while it '''is''' a mistake to refer to the ''range'' or ''image'' as the ''codomain''(range), it is '''not necessarily''' a mistake to refer to ''codomain'' as ''range''.)

@@ Line 197: / Line 197: @@
 * not drawing loops from ''a'' to ''a'' (this is assumed in a partial order because of reflexivity)
-=== Operations on Relations ===
+== Operations on Relations ==
 There are some useful operations one can perform on relations, which allow to
 express some of the above mentioned properties more briefly.
-==== Inversion ====
+=== Inversion ===
 Let R be a relation, then its inversion, R<sup>-1</sup> is defined by
 R<sup>-1</sup> := {(a,b) | (b,a) in R}.
-==== Concatenation ====
+=== Concatenation ===
 Let R be a relation between the sets A and B, S be a relation between B and C. We can concatenate
 these relations by defining
@@ Line 213: / Line 213: @@
 R &bull; S := {(a,c) | (a,b) in R and (b,c) in S for some b out of B}
-==== Diagonal of a Set ====
+=== Diagonal of a Set ===
 Let A be a set, then we define the diagonal (D) of A by
 D(A) := {(a,a) | a in A}
-==== Shorter Notations ====
+=== Shorter Notations ===
 Using above definitions, one can say (lets assume R is a relation between A and B):

@@ Line 128: / Line 128: @@
 #Symmetric, Reflexive, and transitive (x<sup>2</sup> = y<sup>2</sup> is just a special case of equality, so all properties that apply to x = y also apply to this case)
 #Reflexive, Transitive and Antisymmetric (and satisfying Trichotomy)
 === Partial orders ===