Associated Topics || Dr. Math Home || Search Dr. Math

### Set and Element Relations

```Date: 03/23/2003 at 15:24:36
From: John
Subject: Discrete Maths, specifically, relations

On a set of n elements, how many relations are there that are

- reflexive and antisymmetric?
- irreflexive and symmetric?

First, I'm having trouble understanding what relation is. When you say
relation do you just mean a relationship between a and b? e.g. (a,b)
belong to R and so do (e,f). Are (a,b) and (e,f) two relations or the
same one (since they both belong to R)?
```

```
Date: 03/24/2003 at 04:48:21
From: Doctor Jacques
Subject: Re: Discrete Maths, specifically, relations

Hi John,

A relation on a set A is just a set of pairs of elements of A, i.e.
expressions (x,y) where x and y are elements of A (possibly the same).
Note that we consider ordered pairs - (x,y) is not the same as (y,x).

An important point is that you can define relations quite arbitrarily.
For every possible pair (x,y), you can decide whether or not you
include it in the relation - a relation has nothing to do with
properties or "logical relationships." A relation is just a set.

In the case of a finite set A (say of n elements), there is a simple
interpretation of a relation. We simply draw an n by n table,
representing all the possible pairs (x,y), and we put a '*' in a cell
when the corresponding pair belongs to the relation. For example, with
the set A = {a,b,c}, we could have the following relation:

| a | b | c |
--+---+---+---+
a |   | * |   |
b |   |   |   |
c | * |   | * |
--+---+---+---+

In this case, the relation contains the pairs (a,b), (c,a), and (c,c).

In general, for every way you can put stars in the above table
(including none at all), you get a relation on A.

Before tackling your question, we will first examine a few simpler
problems.

All relations
-------------

As a first exercise, let us count how many relations are possible on
this set.

We have 3*3 = 9 squares to fill. For each square, we can decide either
to include it (put a '*' in it), or not. This makes two possibilities
for each square. When you combine the nine squares, you have a total
of 2^9 = 512 possibilities - there are 512 possible relations on A.
In general, for a set of n elements, there are n^2 squares in the
table, and 2^(n^2) possible relations.

Reflexive relations
-------------------

A relation is reflexive if it contains all the pairs (x,x) for every
x in A. In the example above, this means that we must have '*' in all
squares of the main diagonal - the smallest possible reflexive
relation is:

| a | b | c |
--+---+---+---+
a | * |   |   |
b |   | * |   |
c |   |   | * |
--+---+---+---+

In a reflexive relation, the three squares of the diagonal are fixed.
You are still free to include or not any of the 6 remaining squares -
this gives a total of 2^6 = 64 possibilities. For a set of n
elements, you would have:

2^(n^2 - n) = 2^(n*(n-1))

possible reflexive relations.

Irreflexive relations
---------------------

A relation is irreflexive if it contains none of the pairs (x,x).
This means that you must have no '*' on the main diagonal, and you
are still free to do whatever you want with the other squares. The
number of irreflexive relations is therefore the same as the number
of reflexive relations.

Note that "irreflexive" is not the same as "not reflexive."
"Irreflexive" means you have no squares on the diagonal; "not
reflexive" means you don't have all the squares on the diagonal. The
very first example of this message is neither reflexive (since it does
not contain (a,a)) nor irreflexive (since it contains (c,c)).

Symmetric relations
-------------------

A relation is symmetric if, whenever it contains the pair (x,y), it
also contains the pair (y,x). This means that the table must be
symmetric with respect to the main diagonal. For example, the
following is a symmetric relation:

| a | b | c |
--+---+---+---+
a |   | * |   |
b | * |   | * |
c |   | * | * |
--+---+---+---+

We note that the off-diagonal elements come in pairs: (a,b) and
(b,a), (b,c) and (c,b). The diagonal elements are not taken into
account.

To build a symmetric relation, we can freely choose all the squares
on and above the diagonal. There are n(n+1)/2 such squares, and two
possibilities for each of them, so the number of symmetric relations
is:

2^(n(n+1)/2)

Antisymmetric relations
-----------------------

A relation is antisymmetric if, whenever it contains both (x,y) and
(y,x), x = y (x and y are the same element). This is equivalent to
saying that, if x and y are distinct elements, you cannot have at the
same time (x,y) and (y,x) in the relation.

The following is an example of an antisymmetric relation:

| a | b | c |
--+---+---+---+
a | * | * |   |
b |   |   |   |
c | * |   | * |
--+---+---+---+

Note that the relation contains (a,b) but not (b,a), and (c,a) but
not (a,c). Also, it contains neither of (b,c) and (c,b). Elements on
the diagonal can be selected freely.

How many antisymmetric relations are there? We count separately the
possibilities for diagonal and off-diagonal elements.

For diagonal elements, there are two possibilities for each of them,
and there are n such elements. This gives 2^n possibilities.

For each pair of off-diagonal elements x and y, we have three
possibilities:

(x,y) (y,x)
-----------
out    out
in     out
out    in

since we cannot have both (x,y) and (y,x) in the relation. The number
of pairs of distinct elements is "n choose 2":

C(n,2) = n(n-1)/2

and, as there are three possibilities for each pair, we have
3^(n(n-1)/2) possibilities for off-diagonal elements.

The total number of antisymmetric relations is thus:

2^n * 3^(n(n-1)/2)

Note that "antisymmetric" is not the same as "not symmetric." For
example, the following relation is neither symmetric nor
antisymmetric:

| a | b | c |
--+---+---+---+
a |   | * | * |
b |   |   |   |
c | * |   | * |
--+---+---+---+

It is not symmetric, because it contains (a,b) but not (b,a), and it
is not antisymmetric because it contains both (a,c) and (c,a).

Now, let us come to your specific questions - they are, in fact, a
little easier.

Reflexive and antisymmetric
---------------------------

If you compare that with the antisymmetric case, the only difference
is that you must have '*' in all diagonal squares - you are no longer
free to select them. You still have 3 possibilities for each of the
n(n-1)/2 pairs of distinct elements (off-diagonal squares), and the
the total number is therefore:

3^(n(n-1)/2)

Irreflexive and symmetric
-------------------------

In this case, you cannot include any square on the diagonal, and you
can still select freely all the squares strictly above the diagonal;
the squares below the diagonal will be their mirror images. You should
now be able to compute the number of such relations using the
technique outlined above.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 03/24/2003 at 07:55:11
From: John
Subject: Discrete Maths, specifically, relations

First of all, I just like to thank you for a speedy and helpful
response. I find it very clear and helpful.

Second, while we are on the subject of relations, I have another
somewhat related question.

Let S be the set of all character strings made from lower case
letters. For two strings a and b we say that (a,b) belong to R if
b=p.a.q where p and q are (possibly empty) character strings.
Determine if the relation R is reflexive, symmetric, antisymmetric
and transitive.

The problem I'm having with this question is that most of the
properties seem to hold if p and q are empty. For example, if p and
q are empty then the statement b=p.a.q simply says that b = a which
makes it reflexive, symmetric, (possible also antisymmetric) and
transitive. Surely this can't be how I'm supposed to do this
```

```
Date: 03/24/2003 at 09:05:37
From: Doctor Jacques
Subject: Re: Discrete Maths, specifically, relations

Hi John,

Indeed, you cannot assume that p and q are empty. Given any strings a
and b, you have to ask if there exist strings p and q that verify the
relation - these strings will depend on the particular strings a and
b.

We must assume that S is the set of _finite_ strings over the given
alphabet, because, if we allow infinite strings, we can no longer
concatenate them. (What would it mean to write a string at the end of
an infinite string?)

It may be useful to try to see if the relation has an intuitive
meaning. As I explained before, this will not always be the case
(relations can be defined arbitrarily). However, in this case and in
plain English, (a,b) in R means that a is a substring of b. You would
not use that as such in a formal proof (well, maybe...), but it helps
understanding what one is talking about.

Is R reflexive? We must check that, for every string a, we can find
strings p and q such that a = paq. Of course, we may take p and q as
the empty string, and this shows that R is reflexive.

R is not symmetric. To prove it, it is sufficient to exhibit two
strings a and b such that (a,b) is in R and (b,a) is not. We can take,
for example, a = x and b = xy.

To check for transitivity, we assume that R contains (a,b) and (b,c).
This means that there exist strings p,q,r,s such that:

b = paq
c = rbs

and we must check that R contains (a,c), i.e. that there exist
strings u and v such that

c = uav

This is indeed the case, as we can write c = rpaqs, and we can take
u = rp and v = qs.

Let us now check for antisymmetry.

Each string has a length, i.e. an integer >= 0 and equal to the number
of characters in the string.

If R contains (a,b), we have b = paq. This shows that length(b) >=
length(a). More precisely, we can write:

L(b) = L(paq) = L(p) + L(a) + L(q)

Assume that R contains (a,b) and (b,a), i.e. we have:

b = paq
a = rbs

This shows that:

L(b) = L(p) + L(a) + L(q)
L(a) = L(r) + L(b) + L(s)

0 = L(p) + L(q) + L(r) + L(s)

and, as lengths are non-negative, this shows that all lengths are 0,
i.e. p, q, r, s are empty strings, and a = b.

To summarize, we have shown that, if R contains (a,b) and (b,a), then
a = b; i.e. R is antisymmetric.

Does this make sense?

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search