1

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)$

Leonardo
  • 988
  • 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 '13 at 00: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 '13 at 01: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 '13 at 01:02

1 Answers1

1

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.

Tara B
  • 5,341
  • 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 '13 at 04:00