Part 05- Discrete Mathematics for computer science- Anti Symmetric Relation with core Cocept

Part 05- Discrete Mathematics for computer science- Anti Symmetric Relation with core Cocept

Here is Part 05 of Discrete Mathematics for Computer Science, focused on the Anti-Symmetric Relation, explained with core concepts, examples, and logic — especially useful for GATE, CS/IT, and university-level understanding.

What is an Anti-Symmetric Relation?

A binary relation $R$ on a set $A$ is said to be anti-symmetric if:

$$\text{If }(a,b)\in R\text{ and }(b,a)\in R,\text{ then }a=b$$

In simple terms:
If both $a$ is related to $b$ and $b$ is related to $a$**, then they must be the same element.

Formal Definition

Let $A$ be a set and $R\subseteq A\times A$.
$R$ is anti-symmetric if:

$$\forall a,b\in A,(a,b)\in R\wedge (b,a)\in R\Rightarrow a=b$$

Key Concept:

• Anti-symmetric does not mean symmetric = false.

• It is allowed to have both $(a,b)$ and $(b,a)$ only when $a=b$.

• Reflexive elements like $(a,a)$ are fine.

Examples of Anti-Symmetric Relations

Example 1: “Less than or equal to” (≤) on real numbers

If $a\le b$ and $b\le a$, then $a=b$

→ Anti-symmetric

Example 2: Subset relation (⊆) on sets

If $A\subseteq B$ and $B\subseteq A$, then $A=B$

→ Anti-symmetric

Example 3: Divisibility Relation on Natural Numbers

Let $aRb⟺a\mid b$ (a divides b)

If $a\mid b$ and $b\mid a$, then $a=b$

→ Anti-symmetric

Non-Anti-Symmetric Example

Let $A=\{1,2\}$, and $R=\{(1,2),(2,1)\}$

Here, both $(1,2)$ and $(2,1)$ exist but 1≠21 \ne 21=2

→ Not anti-symmetric

Summary Table of Relations

Relation Property	Reflexive	Symmetric	Anti-symmetric	Transitive
$=$ (Equality)
$\le$
Subset (⊆)
“Friend of” Relation	(maybe)

Quick Check: How to Test Anti-Symmetry

Given relation $R$ on set $A$:

1. List all pairs (a,b) in $R$

2. For each pair, check if (b,a) also exists.

3. If yes, then ensure $a=b$. If even one pair violates this, it’s not anti-symmetric.

Key Takeaways:

• Anti-symmetric ≠ Not symmetric

• Reflexive relations can be anti-symmetric.

• Useful in partial orders, posets, and hierarchical data.

Would you like practice questions (MCQs or reasoning-based) on anti-symmetric relations for GATE or university exams?

Part 05- Discrete Mathematics for computer science- Anti Symmetric Relation with core Cocept

DISCRETE MATHEMATICS