Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

Given some set $X$ and relation $R$

If $R = \{(x,x) | x \in X\}$ then we have a relation which is reflexive, transitive, symmetric, and anti-symmetric. Now can I add any elements to the relation which are members of X crossed with X, such that the relation still has these properties? I am not sure if I need to require they be members of $X$ cross $X$, would it no longer be a relation if I added $(1,5)$ to $R$, since $5 \notin X$ ?

Example $X = \{1,2,3\} R = \{(1,1),(2,2),(3,3)\}$ are there any elements that I can add such that $R$ is still a relation with the four properties?

This question is strange enough that I can explain where I am coming from. Taking discrete mathematics my instructor says that being able to determing symmetry/transitive/etc properties are very very important. So, I am writing a computer program in Python such that the computer will randomly choose whether or not these properties are in a relation, and then build a set and a relation for the user to practice determining such things on their own. Now I do not want the computer to make it extremely easy for the user, such that when it decides to make a relation with all 4 propeties, it simply spits out each element in $X$ paired with itself in $R$. I want to know if I can throw in elements like $(1,5)$ in the example above, and will I still have a relation or is this unfair? Currently the program claims it has all four properties even when I add $(1,5)$

share|improve this question
A relation with non-diagonal elements can't preserve both symmetry and anti-symmetry. Intuitive examples: the total relation $"T"$ consists of all pairs in $X \times X$ and is reflexive, transitive, and symmetric but not anti-symmetric. The upper-triangle relation $"U"$ is reflexive, transitive, and anti-symmetric but not symmetric. – alancalvitti Feb 22 at 0:57
@alancalvitti I understand, so if I added an element $(1,5)$ to the relation would it no longer be a relation, of X? – Leonardo Feb 22 at 1:00
In your original Q, you defined an endorelation (or "hom" relation) on $X \times X$. You can also define general binary (or "het") relations on $X \times Y$ where $X$ and $Y$ are distinct sets. But the latter don't have a diagonal hence can't be reflexive. (1,5) is not in $X \times X$ because 5 is not in $X$. – alancalvitti Feb 22 at 1:02

1 Answer

up vote 1 down vote accepted

Your program will find that all four properties hold, because it is only checking them for elements of $X$. If you add a pair $(x,y)$ to your relation and $y\notin X$, then you need to also add $y$ to the set your new relation is defined on.

Just to expand on alancalvitti's first comment: Suppose $R$ is a relation on a set $X$ which is both symmetric and anti-symmetric. Then if $(x,y)\in R$, then by symmetry $(y,x)\in R$, and therefore by anti-symmetry $x=y$. Thus $R$ is the diagonal relation on $X$.

I'd also like to point out that you're probably more likely to be given 'natural' relations to check the properties of - that is, ones which can be defined by some kind of rule - rather than just an arbitrary list of ordered pairs.

share|improve this answer
Right now I am introducing "rules" that define the relation, along with the ability to randomly generate a relation with specified attributes. – Leonardo Feb 23 at 4:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.