Question

state the relations in sets

Answer 1

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.

NotationsEdit

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 examplesEdit

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.

PropertiesEdit

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

ReflexiveEdit

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:

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).

SymmetricEdit

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 fromx to y and an arrow back from y to x:

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

TransitiveEdit

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.

AntisymmetricEdit

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

TrichotomyEdit

A relation satisfies trichotomy if we observe that for all values a and b it holds true that: aRb or bRa

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 setEdit

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 = yx < yx2 = y2x ≤ yAnswersEditSymmetric, Reflexive,and transitiveTransitive, TrichotomySymmetric, 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, and Antisymmetric (and satisfying Trichotomy)Equivalence relationsEdit

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.