standarddeviationcalculator.net

Updated Free · runs in your browser

Math

Relation calculator

Enter a relation as ordered pairs on a set. The calculator tests the four standard properties, names a counterexample for each one that fails, and builds the closures, with Warshall’s algorithm shown one pass at a time.

Leave blank to use every element that appears in a pair.

Write pairs as (a, b). One "a b" pair per line also works.

R is Reflexive, antisymmetric
ReflexiveYes
SymmetricNo
AntisymmetricYes
TransitiveNo
Equivalence relationNo
Partial orderNo
|A|, |R|4, 6
Transitive closure size7
Relation matrix MR (row a, column b: 1 when (a, b) ∈ R)
1234
11100
20110
30010
40001
PropertyHolds?TestCounterexample
ReflexiveYesevery (a, a) is in R—
IrreflexiveNono (a, a) is in R(1, 1) is in R
SymmetricNo(a, b) ∈ R ⇒ (b, a) ∈ R(1, 2) is in R but (2, 1) is not
AntisymmetricYes(a, b), (b, a) ∈ R ⇒ a = b—
AsymmetricNo(a, b) ∈ R ⇒ (b, a) ∉ R(1, 1) is in R
TransitiveNo(a, b), (b, c) ∈ R ⇒ (a, c) ∈ R(1, 2) and (2, 3) are in R but (1, 3) is not
ClosurePairs addedSize
Reflexive: R ∪ {(a, a)}already closed; nothing to add6
Symmetric: R ∪ R⁻¹add (2, 1), (3, 2)8
Transitive: R⁺ (Warshall)add (1, 3)7
Transitive closure matrix (1* = added by Warshall’s algorithm)
1234
1111*0
20110
30010
40001
Show the working, step by step

  1. List A and R. A has 4 elements; R has 6 pairs.

    A = {1, 2, 3, 4} R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (4, 4)}

  2. Build the matrix: row a, column b holds 1 when (a, b) is in R. Reflexive means the diagonal is all 1s; symmetric means the matrix equals its transpose.

    1 1 1 0 0 2 0 1 1 0 3 0 0 1 0 4 0 0 0 1

  3. Test transitivity by checking every chain a → b → c for the shortcut a → c.

    Fails: (1, 2) and (2, 3) are in R but (1, 3) is not.

  4. Warshall pass k = 1 (through 1): set wij = 1 whenever wi,1 = 1 and w1,j = 1. No new pairs.

    1 1 1 0 0 2 0 1 1 0 3 0 0 1 0 4 0 0 0 1

  5. Warshall pass k = 2 (through 2): set wij = 1 whenever wi,2 = 1 and w2,j = 1. New pairs: (1, 3).

    1 1 1 1 0 2 0 1 1 0 3 0 0 1 0 4 0 0 0 1

  6. Warshall pass k = 3 (through 3): set wij = 1 whenever wi,3 = 1 and w3,j = 1. No new pairs.

    1 1 1 1 0 2 0 1 1 0 3 0 0 1 0 4 0 0 0 1

  7. Warshall pass k = 4 (through 4): set wij = 1 whenever wi,4 = 1 and w4,j = 1. No new pairs.

    1 1 1 1 0 2 0 1 1 0 3 0 0 1 0 4 0 0 0 1

  8. Classify. An equivalence relation is reflexive, symmetric and transitive; a partial order is reflexive, antisymmetric and transitive.

    equivalence: No partial order: No

The four properties

A relation R on a set A is a set of ordered pairs (a, b) with a and b in A. Writing a R b for (a, b) ∈ R:

Reflexive: a R a for every a in A Symmetric: a R b ⇒ b R a Antisymmetric: a R b and b R a ⇒ a = b Transitive: a R b and b R c ⇒ a R c

Two combinations have names. An equivalence relation is reflexive, symmetric and transitive; it sorts the set into equivalence classes, like “has the same remainder mod 3”. A partial order is reflexive, antisymmetric and transitive; it ranks elements, like “divides” or “is a subset of”, though some pairs may be incomparable.

Reading the relation matrix

Row a, column b of the matrix MR holds 1 when (a, b) is in R. Each property then has a quick visual test:

PropertyWhat to look for in the matrix
ReflexiveEvery diagonal entry is 1
IrreflexiveEvery diagonal entry is 0
SymmetricThe matrix equals its transpose
AntisymmetricNo off-diagonal pair of 1s mirrored across the diagonal
TransitiveThe Boolean square M ⊙ M has no 1 where M has a 0

A worked example

The default is A = {1, 2, 3, 4} with R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (4, 4)}.

  1. Reflexive: yes. All four loops (1, 1) to (4, 4) are present.
  2. Symmetric: no. (1, 2) is in R, but (2, 1) is not.
  3. Antisymmetric: yes. No two different elements are related in both directions.
  4. Transitive: no. (1, 2) and (2, 3) are in R, but (1, 3) is not.

So R is neither an equivalence relation nor a partial order. The closures show the least that would fix each failure. The reflexive closure adds nothing, because R is already reflexive. The symmetric closure adds (2, 1) and (3, 2), giving 8 pairs. For the transitive closure, Warshall’s pass through 1 adds nothing; the pass through 2 sees 1 → 2 → 3 and adds (1, 3); the passes through 3 and 4 add nothing more. The closure has 7 pairs and is a partial order, whose Hasse diagram is the chain 1 → 2 → 3, with 4 on its own.

Closures

The closure of R under a property is the smallest relation that contains R and has that property. The reflexive closure adds the missing loops (a, a), and the symmetric closure adds the reverse of each pair, R ∪ R⁻¹. The transitive closure R⁺ adds (a, c) whenever there is any chain from a to c, however long, which is why it needs an algorithm rather than a single pass. In graph terms, R⁺ records which vertices can reach which.

Typing the relation

  • Write pairs in brackets: (1,2), (2,3). Angle brackets <1,2> also work, and so does one pair per line as 1 2.
  • Leave the set blank to use every element that appears in a pair. Fill it in when some elements appear in no pair: such an element makes a relation fail reflexivity.
  • Elements can be words or letters: (a, b), (b, c).

Common mistakes

  • Forgetting elements with no pairs. On A = {1, 2, 3}, R = {(1, 1), (2, 2)} is not reflexive, because (3, 3) is missing. Enter the set so the calculator knows 3 is there.
  • Treating “not symmetric” as “antisymmetric”. They are different properties. {(1, 2), (2, 1), (2, 3)} is neither.
  • Stopping transitivity after one round. Adding the missing shortcuts can create new chains. Warshall’s algorithm handles this, and a single round of fixes by hand often does not.

Common questions

How do I check whether a relation is transitive?

Look at every pair of pairs that chain together, (a, b) and (b, c), and check that the shortcut (a, c) is also in R. One missing shortcut is enough to fail. In the default relation, (1, 2) and (2, 3) are in R but (1, 3) is not, so R is not transitive. Pairs with a = b, such as (1, 1) followed by (1, 2), chain to a pair that is already there, so they never cause a failure.

Can a relation be both symmetric and antisymmetric?

Yes. Antisymmetric only forbids two different elements being related both ways. A relation whose pairs are all of the form (a, a), such as the identity relation {(1, 1), (2, 2)}, is symmetric and antisymmetric at once. The empty relation is too.

What is the difference between antisymmetric and asymmetric?

Asymmetric means (a, b) ∈ R rules out (b, a) ∈ R for every pair, including a = b, so an asymmetric relation has no loops (a, a). Antisymmetric allows loops and only rules out both directions between different elements. “Less than or equal to” is antisymmetric; “less than” is asymmetric.

What are equivalence classes?

For an equivalence relation, the class of a is [a] = {x : (a, x) ∈ R}, the set of everything related to a. The classes do not overlap and together they cover the whole set, so they form a partition. For R = {(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)} on {1, 2, 3, 4}, the classes are {1, 2} and {3, 4}.

What does Warshall’s algorithm do?

It builds the transitive closure of a relation from its matrix in n passes. In pass k it allows element k as a stepping stone: wherever row i has a 1 in column k and row k has a 1 in column j, it sets entry (i, j) to 1. After all n passes, (i, j) is 1 exactly when there is a chain from i to j. It takes n³ steps, so it is quick for any set you would type by hand.

Written and reviewed by our editorial team. Last updated . Method and sources: how these numbers are computed.