Relation and its properties

Subjects to be Learned

  • reflexive relation
  • irreflexive relation
  • symmetric relation
  • antisymmetric relation
  • transitive relation

Contents

Certain important types of binary relation can be characterized by properties they have. Here we are going to learn some of those properties binary relations may have. The relations we are interested in here are binary relations on a set.

Definition(reflexive relation): A relation R on a set A is called reflexive if and only if < a, a > R for every element a of A.

Example 1: The relation on the set of integers {1, 2, 3} is {<1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3>} and it is reflexive because <1, 1>, <2, 2>, <3, 3> are in this relation. As a matter of fact on any set of numbers is also reflexive. Similarly and = on any set of numbers are reflexive. However, < (or >) on any set of numbers is not reflexive.

Example 2: The relation on the set of subsets of {1, 2} is { < , > , < , {1} > , < , {2} > , < , {1, 2} > , < {1} , {1} > , < {1} , {1, 2} > , < {2} , {2} > , < {2} , {1, 2} > , < {1, 2} , {1, 2} > }
and it is reflexive. In fact relation on any collection of sets is reflexive.

Definition(irreflexive relation): A relation R on a set A is called irreflexive if and only if <a, a> R for every element a of A.

Example 3: The relation > (or <) on the set of integers {1, 2, 3} is irreflexive. In fact it is irreflexive for any set of numbers.

Example 4: The relation {< 1, 1 >, < 1, 2 >, < 1, 3 >, < 2, 3>, < 3, 3 > } on the set of integers {1, 2, 3} is neither reflexive nor irreflexive.

Definition(symmetric relation): A relation R on a set A is called symmetric if and only if for any a, and b in A, whenever <a, b> R , <b, a> R .

Example 5: The relation = on the set of integers {1, 2, 3} is {<1, 1> , <2, 2> <3, 3> } and it is symmetric. Similarly = on any set of numbers is symmetric. However, < (or >), (or on any set of numbers is not symmetric.

Example 6: The relation "being acquainted with" on a set of people is symmetric.

Definition(antisymmetric relation): A relation R on a set A is called antisymmetric if and only if for any a, and b in A, whenever <a, b> R , and <b, a> R , a = b must hold. Equivalently, R is antisymmetric if and only if whenever <a, b> R , and a b , <b, a> R . Thus in an antisymmetric relation no pair of elements are related to each other.

Example 7: The relation < (or >) on any set of numbers is antisymmetric. So is the equality relation on any set of numbers.

Definition(transitive relation): A relation R on a set A is called transitive if and only if for any a, b, and c in A, whenever <a, b> R , and <b, c> R , <a, c> R .

Example 8: The relation on the set of integers {1, 2, 3} is transitive, because for <1, 2> and <2, 3> in , <1, 3> is also in , for <1, 1> and <1, 2> in , <1, 2> is also in , and similarly for the others. As a matter of fact on any set of numbers is also transitive. Similarly and = on any set of numbers are transitive.

The following figures show the digraph of relations with different properties.
(a) is reflexive, antisymmetric, symmetric and transitive, but not irreflexive.
(b) is neither reflexive nor irreflexive, and it is antisymmetric, symmetric and transitive.
(c) is irreflexive but has none of the other four properties.
(d) is irreflexive, and symmetric, but none of the other three.
(e) is irreflexive, antisymmetric and transitive but neither reflexive nor symmetric.

Comments

Post a Comment

Popular posts from this blog

Intelligent Agents(Algorithms for Intelligent Systems)

    Unit II: Intelligent Agents   Intelligent Agents: Agents and Environments, The Concept of Rationality, The Nature of Environments (PEAS), The Structure of Agents: Simple Reflex Agents, Model-Based Reflex Agents, Goal-Based Agents, Utility-Based agents, Learning Agents. Agents and Environments: Agent An  agent  is an entity that perceives its environment through sensors and acts upon that environment through actuators. Agents can be anything from simple programs to complex systems like robots or humans. The key characteristic of an agent is its ability to take actions based on its perceptions to achieve specific goals. Environment The  environment  is the external context or world in which the agent operates. It includes everything the agent can perceive and interact with. The environment provides the agent with inputs (percepts) and receives outputs (actions) from the agent. Example Consider a  self-driving car : ...
Read more

2D-Transformations

Image
Transformation means changing some graphics into something else by applying rules. We can have various types of transformations such as translation, scaling up or down, rotation, shearing, etc. When a transformation takes place on a 2D plane, it is called 2D transformation. Transformations play an important role in computer graphics to reposition the graphics on the screen and change their size or orientation. Homogenous Coordinates To perform a sequence of transformation such as translation followed by rotation and scaling, we need to follow a sequential process − Translate the coordinates, Rotate the translated coordinates, and then Scale the rotated coordinates to complete the composite transformation. To shorten this process, we have to use 3×3 transformation matrix instead of 2×2 transformation matrix. To convert a 2×2 matrix to 3×3 matrix, we have to add an extra dummy coordinate W. In this way, we can represent the point by 3 numbers instead of 2 numbers, wh...
Read more

3D-Transformations(Including projections)

Image
In the 2D system, we use only two coordinates X and Y but in 3D, an extra coordinate Z is added. 3D graphics techniques and their application are fundamental to the entertainment, games, and computer-aided design industries. It is a continuing area of research in scientific visualization. Furthermore, 3D graphics components are now a part of almost every personal computer and, although traditionally intended for graphics-intensive software such as games, they are increasingly being used by other applications. Parallel Projection Parallel projection discards z-coordinate and parallel lines from each vertex on the object are extended until they intersect the view plane. In parallel projection, we specify a direction of projection instead of center of projection. In parallel projection, the distance from the center of projection to project plane is infinite. In this type of projection, we connect the projected vertices by line segments which correspond to connections o...
Read more