# How can relations on three-element set have seven elements?

• Eclair_de_XII
In summary: Thus, you would have to eliminate one of them to make the relation not reflexive.Why is that so? You cannot throw away ##(x, t) ## or ##(t,x), t\in\{y,z\} ##, though. If you eliminate ##(x,x) ##, then you must additionally eliminate ##(y,z) ## or ##(z,y) ##, but... since ##(x,x)## and ##(y,y)## do not relate, they cannot both be eliminated. Thus, you would have to eliminate one of
Eclair_de_XII

## Homework Statement

"Determine the max number of elements in a three-element set that is not reflexive, symmetric, or transitive?"

## Homework Equations

##a R b⇔(a,b)∈R##

## The Attempt at a Solution

Basically, my professor has stated that there are a total number of seven possible elements in a relation on a three element set that is not reflexive, symmetric, or transitive.

I began again by listing all possible relations of a three element set: ##A=##{##x,y,z,##}. Let ##R## be a relation on ##A##. Then ##R=##{##(x,x),(x,y),(x,z),(y,x),(y,y),(y,z),(z,x),(z,y),(z,z)##}. There are nine elements in ##R## and by eliminating {##(x,x),(y,y),(z,z)##}, I already have fewer than the maximum number of elements in an ##R## that is not reflexive, symmetric, or transitive. And you kind of must nix those three elements for those three properties, anyway. I feel like I'm missing something... Can anyone point out what it is? Thanks.

I assume the trick is behind the formulation "not or". What is "not (A or B or C)" and what "not A or not B or not C"? Which one is probably meant?

I don't know; I feel like that for all three properties, you would have to remove ##(x,x),(y,y),## and ##(z,z)##. Reflexive is already out. To make it not symmetric, I would still have to deal with the fact that ##(x,x)## implies that its reciprocal (itself) is in the set. Similarly, I would have problems with eliminating the transitive property from my set. If ##aRa## and ##aRa##, then ##aRa##.

I mean, I could just say that ##R## is not reflexive, and add in the null-set...

Last edited:
My interpretation of the question with regard to seven as the answer and a maximum requirement is: "not reflexive or not symmetric or not transitive". An and between them would simply rule out too many relations, as you already observed.

So for the symmetric and transitive properties, does the statement that ##a## R ##b## implies ##b## R ##a## apply when ##a=b##, or no?

What is ##a=b##? You named your elements ##x,y,z## and the relation ##R##. So ##aRb \Rightarrow bRa## for all ##a,b \in A## means ##R## is symmetric. ##a=b## isn't defined anywhere, since it is another relation.

I guess my question is... can ##x## be symmetric or transitive with itself?

Eclair_de_XII said:
I guess my question is... can ##x## be symmetric or transitive with itself?
##xRx## is a possibility and if also ##yRy## and ##zRz## then ##R## is reflexive. It makes no sense to speak of symmetry, if you only compare it with itself, or transitive, for which you also need at least two elements.

I got it; they must be distinct elements of the set the relation is on.

Okay, I ended up nixing ##(x,y)## and ##(y,x)## from the set to yield ##S=##{##(x,x),(x,z),(y,y),(y,z),(z,x),(z,y),(z,z)##}.

Eclair_de_XII said:
Okay, I ended up nixing ##(x,y)## and ##(y,x)## from the set to yield ##S=##{##(x,x),(x,z),(y,y),(y,z),(z,x),(z,y),(z,z)##}.

That is reflexive.

How is one supposed to determine the maximum number of elements of a set whose number of elements is fixed? If you are supposed to construct a so called "maximal relation" that is not reflexive, you merely have to omit one pair ##(x,x) ## or ##(y,y) ## or ##(z,z)## and the maximum number can therefore be?

I mean, I was trying to make it not transitive. But making it not reflexive works even better.

Eclair_de_XII said:
I mean, I was trying to make it not transitive. But making it not reflexive works even better.

The task, it seems to me, is to make it not reflexive, not transitive and not symmetric.

If you begin with a, let's call it complete, relation on a three element set i.e one whose relation matrix is
$$\begin{array}{ccc}1&1&1\\1&1&1\\1&1&1\end{array}$$
By omitting, say ##(x,x)## you will have given up reflexivity, but also relinquished transitivity (why?). All that is left now is to give up symmetry. Therefore, indeed, desired relation can, at most, contain seven elements.

Oh, right. Because in order for a relation ##R## to be reflexive on a set ##A##, ##s## R ##s## must apply for all ##s∈A##. Since eliminating ##(x,x)## would make it so that there exists one element that does not relate to itself, ##R##\##(x,x)## would not be reflexive. Additionally, could you not just remove ##(x,y)## and make it so that ##R## is not symmetric?

nuuskur
Eclair_de_XII said:
Oh, right. Because in order for a relation ##R## to be reflexive on a set ##A##, ##s## R ##s## must apply for all ##s∈A##. Since eliminating ##(x,x)## would make it so that there exists one element that does not relate to itself, ##R\(x,x)## would not be reflexive. Additionally, could you not just remove ##(x,y)## and make it so that ##R## is not symmetric?
Almost, but in this case, when you give up reflexivity, you also give up transitivity. Why is that so? You cannot throw away ##(x, t) ## or ##(t,x), t\in\{y,z\} ##, though. If you eliminate ##(x,x) ##, then you must additionally eliminate ##(y,z) ## or ##(z,y) ##, but why?

I'm guessing that since ##x## R ##x## is no longer in ##R##, there is no relation ##x## R ##x## to transition ##(x,x)## to ##(x,y)## or ##(x,z)##.

And why is the max number of elements seven when I have eliminated only one element from my nine-element relation?

It is seven, because you cannot kill all three birds with one stone i.e, if you give up any diagonal pair ##(a,a) ##, you can't omit symmetry with it. Therefore, it's also necessary to remove another pair.

Can you state precisely why giving up ##(x,x) ## removes transitivity property? A relation on the set ##S ##, ##R\subseteq S\times S ##, is transitive if for all ##a,b,c\in S,\ aRb ## and ##bRc\Longrightarrow aRc ##. By removing ##(x,x)##, how is this implication violated?

nuuskur said:
Can you state precisely why giving up ##(x,x)## removes transitivity property?

It removes the transition from ##x## to itself, then to ##y## or ##z##?

Indeed, which also explains why, when you remove ##(x,x)##, you cannot remove ##(x,y), (x,z), (y,x) ## or ##(z,x) ##. If you did, then you give up symmetry, yes, but not transitivity.

Even if I removed either ##(y,z)## or ##(z,y)##, there would still be ##(z,x)## and ##(y,x)## to transition into ##(y,x)## and ##(z,x)## respectively, though.

I'm guessing that even if that were so, there would be no ##(x,x)## for ##(y,x)## to transition from ##(x,z)## to ##(y,z)##?

Your expression is incredibly ambiguous to me, which is why I asked you to state precisely the reason that so and so.

When you remove, say, ##(x,x) ## and nothing else, you omit reflexivity and transitivity. The reason for that is, because ##xRy \mbox{ and } yRx ##, but there is no ##xRx##. Now, if you removed, say, ##(x,y)##, you merely exchange symmetry for transitivity. You don't want that.
Remove, say, ##(y,z)##, instead. You still have ##zRy ##, but no ##yRz ##, therefore symmetry is gone.

nuuskur said:
The reason for that is, because ##xRy## ##\mbox{ and } yRx## , but there is no ##xRx##.

Oh, so that's why the transitive property is removed... So why does removing ##(x,y)## reintroduce transitivity into ##R##? Is it something to do with vacuous truth? Like, the transitive property states that if ##xRy##, and ##yRx##, then ##xRx##. If there is no ##(x,y)##, then that would make the statement that ##R## is transitive vacuously true, I think?

Oh snap, you are right. It doesn't, that's a mistake on my part. Removing ANY non diagonal pair will remove symmetry and problem is solved.

There still is ##xRz, zRx ##, but no ##xRx##. For some reason, I forgot about it

## 1. How can a relation on a three-element set have seven elements?

This is possible because a relation on a set is defined as a collection of ordered pairs, and each ordered pair consists of two elements. Therefore, a relation on a three-element set can have up to six elements. However, it is also possible for a relation to have additional elements that are not part of the original set, making it possible for a three-element set to have a relation with seven elements.

## 2. Can a relation on a three-element set have more than seven elements?

Yes, it is possible for a relation on a three-element set to have more than seven elements. As mentioned earlier, a relation can have additional elements that are not part of the original set. Therefore, a three-element set can have a relation with any number of elements greater than seven.

## 3. What is the significance of relations on three-element set having seven elements?

The significance of relations on a three-element set having seven elements lies in the fact that it showcases the versatility and complexity of mathematical concepts. It also highlights the importance of understanding the fundamental definitions and principles of relations.

## 4. How can we visualize a relation on a three-element set with seven elements?

A relation on a three-element set with seven elements can be visualized using a directed graph. Each element in the three-element set can be represented by a vertex, and the ordered pairs in the relation can be represented by directed edges connecting the vertices. This visualization helps to understand the nature and properties of the relation.

## 5. What are some real-life examples of relations on a three-element set with seven elements?

Real-life examples of relations on a three-element set with seven elements can include relationships between three individuals, such as a group of friends, where each person has a different level of closeness to the other two individuals. This can be represented by a relation on a three-element set with seven elements, where each element represents a person and the ordered pairs represent the level of closeness between them.

• Calculus and Beyond Homework Help
Replies
3
Views
693
• Calculus and Beyond Homework Help
Replies
5
Views
3K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
806
• Calculus and Beyond Homework Help
Replies
9
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
35
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
950