# Thread: Very simple Binary Relation definition needed

1. ## Very simple Binary Relation definition needed

Everywhere I look, binary relation is defined as the set of ordered pairs containing elements from 2 sets.

But then I get a a problem that says

How many binary relations are there on the set (1, 2, 3}?

This doesn't make sense to me. How can you have a relation with only 1 set?

2. Phrase "R is a binary relation on a set A" is commonly used to mean that R is a subset of the cartesian product A x A. That is, R is a collection of ordered pairs of elements of A.

3. Do you understand the following calculations?
$\begin{gathered}
X = \left\{ {1,2,3} \right\}\; \Rightarrow \;\left| X \right| = 3 \hfill \\
X \times X = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,2} \right),\left( {2,1} \right),\left( {2,3} \right),\left( {3,3} \right),\left( {3,1} \right),\left( {3,2} \right)} \right\} \hfill \\
\left| {X \times X} \right| = 9\; \Rightarrow \;\left| {P(X \times X)} \right| = 2^9 \hfill \\
\end{gathered}$

Because a binary relation on $X$ is any subset of pairs in $X\times X$ there are $2^9$ possible binary relations on $X$.
(Some authors say $2^9-1$ because of not liking an empty relation.)

4. Yes, that makes sense to me. I had actually tried 9 as an answer, and I was wrong.

.... any idea why this was wrong?

5. I believe Plato has already answered that! Could you tell us why you thought it was 9?

6. I just took the cartesian product and found that there were 9 results. It was more of a guess than anything else.

It took a few times reading to figure this out a little more.

May I present you with another example, and maybe you could help me figure out what I'm doing wrong?

I am presented with the set {1,2}
So, the product is {(1,1), (1,2), (2,1), (2,2)}
and there would be 16 relations?

I am then asked a series of questions such as "How many relations are reflexive? Symmetrical?"

I know I need to set up a matrix showing all the possible relations, but... aren't they all possible? Wouldn't the matrix be all "1"s?

7. Think about what the definition is.

A relation on a set is a subset of the Cartesian product.

So you have to think about all the possible subsets of:
$\{(1, 1), (1, 2), (2, 1), (2, 2)\}$

A reflexive relation is one which includes (1,1) and (2,2). (By looking hard at the definition of "reflexive", ask yourself: why?)

A symmetric relation is one where, if (a, b) is in the relation, then (b, a) is also in that relation.

So as there's only 16 possible relations, it's feasible to list them all out and examine them one by one for whether they have all these properties.

For example, $\{(1, 1), (1, 2), (2, 2)\}$ is reflexive, because it has (1, 1) and (2, 2), but not symmetric - because it has (1, 2) but not (2, 1).

And so on. As I say, list them all out and look at them - it's an instructional exercise in its own right.

8. Originally Posted by JTG2003
I am then asked a series of questions such as "How many relations are reflexive? Symmetrical?"
Suppose that $|X|=n$ then there are $2^n$ binary relations on $X$.

The are $2^{n^2-n}$ reflexive relations on $X$

The are $2^{\frac{n(n+1)}{2}}$ symmetric relations on $X$