Let R be a binary relation on a set X

[barneygumble742]

i have a statement: Let R be a binary relation on a set X. R is reflexive if (x, x) belongs to R for each x belongs to X.

what is a binary relation? what does the (x, x) mean? how can x be both the input and output? and finally...i see the book i have has IdX where X is a subscript. and sometimes replaced with the notation for real numbers. what does the Id. mean?

thanks,
barneygumble742

 

[quasar987]

Given a set X, a binary relation R on X is a subgroup of the cartesian product X x X. So elements of R are ordered couple, i.e. they are of the form (a,b), where a and b are in X. If (a,b) is in R, we'll say that a is in relation with b.

Relations are vague until we've seen an exemple. Here's one: Define the set R as follow:

$$R = \{(a,b) \in X \times X | a=b\}$$

In this case, every element in R is of the form (x,x), and R says that a is in relation with b iff a=b. Of course, this relation is reflexive. It is also symetric, anti-symetric and transitive.

 

[quasar987]

Here's another exemple that'll make thing even more tangible. Suppose S is a set containing sets. Define

$$R = \{(a,b) \in S \times S | a \subseteq b \}$$

then R is reflexive, anti-symetric and transitive. A relation satisfying those 3 properties is called a "partial ordering" and we denote the fact that a is in relation with b by well known notation $a\leq b$. .

 

[matt grime]

Id means the identity map, and the subscript tells you on what set it is the identity map (often used if there are two sets and we want to make it clear which map has which set as its domain and range) Id_X is the map from X to X satisfying Id_X(x)=x for all x in X.

example of usage: suppose f is a map fro X to Y, then f is invertible if there is a map g from Y to X satisfying gf=Id_X and fg=Id_Y.

i think people get too bothered about the set notation for relations. firstly just think about relations, then think about ways to represent them.

a relation on a set is simply some way of taking some elements of a set and deciding if they satisfy a rule. it is binary if we compare two elements. so we take two elements, decide if the property is true or false for this pair. if it's true we say they are related (and if it's false they are not related).

examples as indicated include < on the real numbers, or "is a subset of" on a set of sets.

let's just stick to the real numbers. another example would be we say a is related to b if ab>1, or a is related to b if a^2+b^2=1

now, the set notation thing. this is a formal way of writing a relation. say we have a relation on A, some set, then we can form a set like this:

for a in A create the set { (a,b) : a is related to b}

then take the union of these for each a in A. this is a subset of AxA. sometimes people call this the relation on A. basically a relates b if and only if (a,b) is in that set we just created.

quasar then started talking about the properties a relation may have. i suggest coming back to those later.

other notation you need is that we say all of the following and mean the same thing

a is related to b
aRb
(a,b) is in R

and we refer to R as the relation. notice that R is used in two different but equivalent ways.

 

[barneygumble742]

thank you both very much. i understand it very well now.

regarding the relations, i understand transitive and symmetric but i don't understand the rest such as reflexive, irreflexive, and antisymmetric.

the way my teacher does transitive is understandable. for example i can see how he's getting {(1, 3)} from {(1, 2), (2, 3)} but i don't follow how he sees the other relations.

 

[matt grime]

reflexie is if xRx, ie everything is related to itself, thus <= is refelxive, < is not. in set terms it states that (x,x) is in R. I wish i could get all the people who think that teaching relations as subsets of cartesian products is good and knock their heads together. it's stupid.


i guess irreflexive just means "not reflexive". not sure about antisymmetric to be honest since antisymmetic has a specific meaning in other parts of mathematics that is not applicable here.

right, antisymmetric means xRy and yRx implies y=x.

or if you must, if (x,y) is in R, and x doesn't equal y, then (y,x) cannot be in R.


and irreflexive means that x is never related to x, which is different from "not reflexive", in set terms (x,x) is not in R for any x