Elements | Any | Transitive | Reflexive | Symmetric | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3,994 | 4,096 | 1,024 | 355 | 219 | 75 | 24 | 15 |
n | 2n2 | 2n(n−1) | 2n(n+1)/2 | ∑n k=0 k!S(n, k) |
n! | ∑n k=0 S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Note that S(n, k) refers to Stirling numbers of the second kind.
Notes:
The binary relations can be grouped into pairs (relation, complement), except that for n = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement): part of these are quadruples with reflexive and irreflexive relations: 0, 0, 1, 28, and 2016, respectively.
There is one binary relation on the empty set. It is symmetric, antisymmetric, transitive, reflexive, an equivalence relation, irreflexive, asymmetric, a total order, and the corresponding strict total order.
Note that while the empty relation on a non-empty set is not reflexive, on the empty set it is.
See also Vacuous truth.
this is so true
There are 2 binary relations on a set of one element (a singleton), both symmetric, antisymmetric, and transitive:
There are 16 binary relations on a set of two elements: 4 groups of 4, within which the only differences are in the relations of elements to themselves.
Thus 4 are reflexive, 4 irreflexive, and 8 neither.
The 16 relations form 8 pairs (relation, complement).
There are 8 symmetric relations, i.e. 4 pairs (relation, complement). The 8 non-symmetric relations form 2 quadruples (relation, complement, inverse, inverse complement).
There are 12 antisymmetric relations, of which 3 are asymmetric.
There are 3 total relations, of which all are transitive, and 2 antisymmetric (the total orders): the relation "each element is related to each element" is total but not antisymmetric.
There are 3 non-transitive relations: those with aRb and bRa but not both aRa and bRb.
Of the 13 transitive relations:
There are three strict weak orders; their complements are weak orders, and the inverses of these also.
There are 10 transitive relations with the property that the complement is also transitive (5 pairs). These are the 3 pairs of a weak order and a strict weak order, and 2 more pairs of relations which are neither reflexive nor irreflexive, and which differ from 2 of these 3 pairs only by a relation of an element to itself, added to the strict relation and removed from the complement.
There are 5 symmetric transitive relations, so there are 8 non-symmetric transitive relations. Since the inverse of a transitive relation is also transitive, these form 4 pairs.
There are 2 symmetric transitive relations (one pair) with the property that the complement is also transitive (and symmetric), "each element is related to each element" and "nothing is related", so apart from these there are 2 quadruples (relation, complement, inverse, inverse complement) with all relations transitive. The non-symmetric weak orders and strict weak orders (2 each) form 1 of these quadruples: for a set of numbers like {1, 2} the quadruple is {<, >, ≤, ≥}. The other quadruple consist of neither reflexive nor irreflexive relations: it contains the R given by aRa and aRb, its complement given by bRa and bRb, its inverse given by aRa and bRa, and the complement of its inverse given by aRb and bRb.
There are 512 binary relations on a set of three elements: 64 groups of 8, within which the only differences are in the relations of elements to themselves.
Thus 64 are reflexive, 64 irreflexive, and 384 neither.
The 512 relations form 256 pairs (relation, complement).
There are 64 symmetric relations, i.e. 32 pairs (relation, complement). The 576 non-symmetric relations form 144 quadruples (relation, complement, inverse, inverse complement).
There are 216 antisymmetric relations, of which 27 are asymmetric.
There are 27 total relations, of which 13 are transitive, 8 antisymmetric, and 6 both (the total orders). For the two relations which are total and antisymmetric but not transitive, see below.
The following 48 reflexive and irreflexive relations are transitive:
total | rfl ( pro) | irr ( as; spo) | tpo | swo | ants | symm | eqr | pao | description |
---|---|---|---|---|---|---|---|---|---|
6 | 6 | 0 | 6 | 0 | 6 | 0 | 0 | 6 | ≤ in the case a<b<c ( total order) |
6 | 0 | 6 | 0 | 6 | 6 | 0 | 0 | 0 | < in the case a<b<c ( strict total order) |
1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | < in the case a~b~c < in the case a~b |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | in the case a~b~c |
6 | 0 | 6 | 0 | 6 | 6 | 0 | 0 | 0 | < in the case a<b,c < in the case a<b~c |
1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | = ( equality) |
6 | 6 | 0 | 0 | 0 | 6 | 0 | 0 | 6 | ≤ in the case a<b,c |
6 | 6 | 0 | 6 | 0 | 0 | 0 | 0 | 0 | in the case a<b~c |
3 | 3 | 0 | 0 | 0 | 0 | 3 | 3 | 0 | in the case a~b |
6 | 0 | 6 | 0 | 0 | 6 | 0 | 0 | 0 | < in the case a<b |
6 | 6 | 0 | 0 | 0 | 6 | 0 | 0 | 6 | ≤ in the case a<b |
48 | 29 | 19 | 13 | 13 | 38 | 6 | 5 | 19 | total |
relation | case |
---|---|
≤ | a<b<c |
< | a<b<c |
< | a~b~c |
a~b~c | |
< | a<b,c |
< | a<b~c |
= | all |
≤ | a<b,c |
a<b~c | |
a~b | |
< | a<b |
≤ | a<b |
There are 74 transitive relations with the property that the complement is also transitive (37 pairs). These are the 13 pairs of a weak order and a strict weak order, and 24 more pairs of relations which are neither reflexive nor irreflexive, and which differ from 12 of these 13 pairs only by a relation of an element to itself, added to the strict relation and removed from the complement.
There are 15 symmetric transitive relations, so there are 156 non-symmetric transitive relations. Since the inverse of a transitive relation is also transitive, these form 78 pairs.
There are 2 symmetric transitive relations (one pair) with the property that the complement is also transitive (and symmetric), "each element is related to each element" and "nothing is related", so apart from these there are 18 quadruples (relation, complement, inverse, inverse complement) with all relations transitive. The non-symmetric weak orders and strict weak orders (12 each) form 6 of these quadruples: for a set of numbers like {1, 2, 3} one of the quadruples is {<, >, ≤, ≥}. Two more correspond to taking "1" or "3" as center element. The other three correspond to considering two of the three elements "equivalent". The remaining 12 quadruples consist of neither reflexive nor irreflexive relations.
The 29 preorders are the partial orders on partitions:
The number of pairs of a weak order and a strict weak order, 13, is the Fubini number or ordered Bell number (the number of totally ordered partitions) for n = 3.
We have:
i.e. together 13 orders.
Compare the Bell numbers, here 5: the number of partitions.
In terms of preferences of person P, the possibilities are:
(See also Pairwise_comparison#Preference_orders.)
In terms of numbers assigned to three items:
In this case an order-preserving transformation of the numbers counts as the same possibility: the numbers serve as an ordinal scale.
There are 341 non-transitive relations, of which 35 are reflexive and 45 irreflexive.
The 35 reflexive non-transitive relations include:
The 45 irreflexive non-transitive relations are:
Symmetry with respect to permutations of elements (a relation-preserving automorphism) should not be confused with the concept of a symmetric relation.
Four relations have full symmetry:
Two relations have a symmetry group of 3 permutations:
There are 65536 binary relations on a set P of four elements: 4096 groups of 16, within which the only differences are in the relations of elements to themselves.
Thus 4096 are reflexive and 4096 irreflexive. These form 4096 pairs (relation, complement). 64 of these are pairs of symmetric relations.
The 4032 pairs of non-symmetric reflexive and irreflexive relations form 2016 quadruples (relation, complement, inverse, inverse complement).
There are 24 total order and 24 strict total orders.
There are 51 more strict weak orders S (together 75 [1]; see also below), with which are associated 51 total preorders (together there are 75 total preorders) and 51 corresponding (non-strict) partial orders S ∪ {(a, a) | a in P}. The 75 strict and 75 non-strict relations are given below. Pairs or related elements following from transitivity are not shown , and neither are, for the non-strict version, the relations of elements to itself (i.e, the reflexive and transitive reduction is shown):
There are 144 additional partial orders (together 219 [2]) and 144 corresponding strict partial orders:
The complements and inverse complements of these 288 relations are not transitive.
SEe also Strict_weak_ordering#The_number_of_total_preorders.
Classification of the 219 partial orders based on the graphical representation:
The last 14 can be drawn as a rhombus: in the first case with e.g. downward arrows, in the second case with arrows to the horizontal diagonal. If arrows need to be point to a lower level, the possibilities in the latter case are:
The set of all 15 partitions of the set { 1, 2, 3, 4 }, partially ordered by "refinement", i.e. a finer partition is "less than" a coarser partition, has the Hasse diagram:
These correspond to the 15 equivalence relations among the 64 reflexive symmetric relations. this number 15 is the Bell number for n = 4.
The Fubini number or ordered Bell number, 75, is the number of strict weak orders, with which are associated 75 total preorders:
i.e. together 75 orders.
Elements | Any | Transitive | Reflexive | Symmetric | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3,994 | 4,096 | 1,024 | 355 | 219 | 75 | 24 | 15 |
n | 2n2 | 2n(n−1) | 2n(n+1)/2 | ∑n k=0 k!S(n, k) |
n! | ∑n k=0 S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Note that S(n, k) refers to Stirling numbers of the second kind.
Notes:
The binary relations can be grouped into pairs (relation, complement), except that for n = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement): part of these are quadruples with reflexive and irreflexive relations: 0, 0, 1, 28, and 2016, respectively.
There is one binary relation on the empty set. It is symmetric, antisymmetric, transitive, reflexive, an equivalence relation, irreflexive, asymmetric, a total order, and the corresponding strict total order.
Note that while the empty relation on a non-empty set is not reflexive, on the empty set it is.
See also Vacuous truth.
this is so true
There are 2 binary relations on a set of one element (a singleton), both symmetric, antisymmetric, and transitive:
There are 16 binary relations on a set of two elements: 4 groups of 4, within which the only differences are in the relations of elements to themselves.
Thus 4 are reflexive, 4 irreflexive, and 8 neither.
The 16 relations form 8 pairs (relation, complement).
There are 8 symmetric relations, i.e. 4 pairs (relation, complement). The 8 non-symmetric relations form 2 quadruples (relation, complement, inverse, inverse complement).
There are 12 antisymmetric relations, of which 3 are asymmetric.
There are 3 total relations, of which all are transitive, and 2 antisymmetric (the total orders): the relation "each element is related to each element" is total but not antisymmetric.
There are 3 non-transitive relations: those with aRb and bRa but not both aRa and bRb.
Of the 13 transitive relations:
There are three strict weak orders; their complements are weak orders, and the inverses of these also.
There are 10 transitive relations with the property that the complement is also transitive (5 pairs). These are the 3 pairs of a weak order and a strict weak order, and 2 more pairs of relations which are neither reflexive nor irreflexive, and which differ from 2 of these 3 pairs only by a relation of an element to itself, added to the strict relation and removed from the complement.
There are 5 symmetric transitive relations, so there are 8 non-symmetric transitive relations. Since the inverse of a transitive relation is also transitive, these form 4 pairs.
There are 2 symmetric transitive relations (one pair) with the property that the complement is also transitive (and symmetric), "each element is related to each element" and "nothing is related", so apart from these there are 2 quadruples (relation, complement, inverse, inverse complement) with all relations transitive. The non-symmetric weak orders and strict weak orders (2 each) form 1 of these quadruples: for a set of numbers like {1, 2} the quadruple is {<, >, ≤, ≥}. The other quadruple consist of neither reflexive nor irreflexive relations: it contains the R given by aRa and aRb, its complement given by bRa and bRb, its inverse given by aRa and bRa, and the complement of its inverse given by aRb and bRb.
There are 512 binary relations on a set of three elements: 64 groups of 8, within which the only differences are in the relations of elements to themselves.
Thus 64 are reflexive, 64 irreflexive, and 384 neither.
The 512 relations form 256 pairs (relation, complement).
There are 64 symmetric relations, i.e. 32 pairs (relation, complement). The 576 non-symmetric relations form 144 quadruples (relation, complement, inverse, inverse complement).
There are 216 antisymmetric relations, of which 27 are asymmetric.
There are 27 total relations, of which 13 are transitive, 8 antisymmetric, and 6 both (the total orders). For the two relations which are total and antisymmetric but not transitive, see below.
The following 48 reflexive and irreflexive relations are transitive:
total | rfl ( pro) | irr ( as; spo) | tpo | swo | ants | symm | eqr | pao | description |
---|---|---|---|---|---|---|---|---|---|
6 | 6 | 0 | 6 | 0 | 6 | 0 | 0 | 6 | ≤ in the case a<b<c ( total order) |
6 | 0 | 6 | 0 | 6 | 6 | 0 | 0 | 0 | < in the case a<b<c ( strict total order) |
1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | < in the case a~b~c < in the case a~b |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | in the case a~b~c |
6 | 0 | 6 | 0 | 6 | 6 | 0 | 0 | 0 | < in the case a<b,c < in the case a<b~c |
1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | = ( equality) |
6 | 6 | 0 | 0 | 0 | 6 | 0 | 0 | 6 | ≤ in the case a<b,c |
6 | 6 | 0 | 6 | 0 | 0 | 0 | 0 | 0 | in the case a<b~c |
3 | 3 | 0 | 0 | 0 | 0 | 3 | 3 | 0 | in the case a~b |
6 | 0 | 6 | 0 | 0 | 6 | 0 | 0 | 0 | < in the case a<b |
6 | 6 | 0 | 0 | 0 | 6 | 0 | 0 | 6 | ≤ in the case a<b |
48 | 29 | 19 | 13 | 13 | 38 | 6 | 5 | 19 | total |
relation | case |
---|---|
≤ | a<b<c |
< | a<b<c |
< | a~b~c |
a~b~c | |
< | a<b,c |
< | a<b~c |
= | all |
≤ | a<b,c |
a<b~c | |
a~b | |
< | a<b |
≤ | a<b |
There are 74 transitive relations with the property that the complement is also transitive (37 pairs). These are the 13 pairs of a weak order and a strict weak order, and 24 more pairs of relations which are neither reflexive nor irreflexive, and which differ from 12 of these 13 pairs only by a relation of an element to itself, added to the strict relation and removed from the complement.
There are 15 symmetric transitive relations, so there are 156 non-symmetric transitive relations. Since the inverse of a transitive relation is also transitive, these form 78 pairs.
There are 2 symmetric transitive relations (one pair) with the property that the complement is also transitive (and symmetric), "each element is related to each element" and "nothing is related", so apart from these there are 18 quadruples (relation, complement, inverse, inverse complement) with all relations transitive. The non-symmetric weak orders and strict weak orders (12 each) form 6 of these quadruples: for a set of numbers like {1, 2, 3} one of the quadruples is {<, >, ≤, ≥}. Two more correspond to taking "1" or "3" as center element. The other three correspond to considering two of the three elements "equivalent". The remaining 12 quadruples consist of neither reflexive nor irreflexive relations.
The 29 preorders are the partial orders on partitions:
The number of pairs of a weak order and a strict weak order, 13, is the Fubini number or ordered Bell number (the number of totally ordered partitions) for n = 3.
We have:
i.e. together 13 orders.
Compare the Bell numbers, here 5: the number of partitions.
In terms of preferences of person P, the possibilities are:
(See also Pairwise_comparison#Preference_orders.)
In terms of numbers assigned to three items:
In this case an order-preserving transformation of the numbers counts as the same possibility: the numbers serve as an ordinal scale.
There are 341 non-transitive relations, of which 35 are reflexive and 45 irreflexive.
The 35 reflexive non-transitive relations include:
The 45 irreflexive non-transitive relations are:
Symmetry with respect to permutations of elements (a relation-preserving automorphism) should not be confused with the concept of a symmetric relation.
Four relations have full symmetry:
Two relations have a symmetry group of 3 permutations:
There are 65536 binary relations on a set P of four elements: 4096 groups of 16, within which the only differences are in the relations of elements to themselves.
Thus 4096 are reflexive and 4096 irreflexive. These form 4096 pairs (relation, complement). 64 of these are pairs of symmetric relations.
The 4032 pairs of non-symmetric reflexive and irreflexive relations form 2016 quadruples (relation, complement, inverse, inverse complement).
There are 24 total order and 24 strict total orders.
There are 51 more strict weak orders S (together 75 [1]; see also below), with which are associated 51 total preorders (together there are 75 total preorders) and 51 corresponding (non-strict) partial orders S ∪ {(a, a) | a in P}. The 75 strict and 75 non-strict relations are given below. Pairs or related elements following from transitivity are not shown , and neither are, for the non-strict version, the relations of elements to itself (i.e, the reflexive and transitive reduction is shown):
There are 144 additional partial orders (together 219 [2]) and 144 corresponding strict partial orders:
The complements and inverse complements of these 288 relations are not transitive.
SEe also Strict_weak_ordering#The_number_of_total_preorders.
Classification of the 219 partial orders based on the graphical representation:
The last 14 can be drawn as a rhombus: in the first case with e.g. downward arrows, in the second case with arrows to the horizontal diagonal. If arrows need to be point to a lower level, the possibilities in the latter case are:
The set of all 15 partitions of the set { 1, 2, 3, 4 }, partially ordered by "refinement", i.e. a finer partition is "less than" a coarser partition, has the Hasse diagram:
These correspond to the 15 equivalence relations among the 64 reflexive symmetric relations. this number 15 is the Bell number for n = 4.
The Fubini number or ordered Bell number, 75, is the number of strict weak orders, with which are associated 75 total preorders:
i.e. together 75 orders.