Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

Does this help?  Write back if you'd like to talk about this 
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 
question. Please help.


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)

and, adding these relations together:

  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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/