User:Patrick/relation

The number of binary relations

Binary relations:

Number of n-element binary relations of different types

Elem­ents	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 number of irreflexive relations is the same as that of reflexive relations
• The number of strict partial orders (irreflexive transitive relations) is the same as that of partial orders
• The number of strict weak orders is the same as that of total preorders
• The total orders are the partial orders which are also total preorders. The number of preorders which are neither a partial order nor a total preorder is therefore the number of preorders minus the number of partial orders minus the number of total preorders plus the number of total orders: 0, 0, 0, 3, and 85, respectively.
• the number of equivalence relations is the number of partitions, which is the Bell number.

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.

n=0

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

n=1

There are 2 binary relations on a set of one element (a singleton), both symmetric, antisymmetric, and transitive:

• a reflexive one which is a total order and an equivalence relation
• an irreflexive and asymmetric one, and the corresponding strict total order

n=2

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.

Transitive relations

There are 3 non-transitive relations: those with aRb and bRa but not both aRa and bRb.

Of the 13 transitive relations:

• 4 are reflective (a preorder)
• 3 are irreflexive (asymmetric)
• 5 are symmetric
• 12 are antisymmetric (all except the reflexive relation with aRb and bRa)
• 3 are a partial order (the reflexive relations with aRb, or bRa, or neither)
• 2 are an equivalence relation (with the two elements together in one class or separate)

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.

n=3

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.

Transitive relations

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	$\lesssim$ 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	$\lesssim$ in the case a<b~c
3	3	0	0	0	0	3	3	0	$\lesssim$ 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
$\lesssim$	a~b~c
<	a<b,c
<	a<b~c
=	all
≤	a<b,c
$\lesssim$	a<b~c
$\lesssim$	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.

Preorders

The 29 preorders are the partial orders on partitions:

• 1 partition of 3, giving 1 order
• 3 partitions of 2+1, giving 3 × 3 = 9 orders (because there are 3 partial orders on a set of 2 elements)
• 1 partition of 1+1+1, giving 19 orders (partial orders themselves)

Weak orders

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:

• 1 partition of 3, giving 1 order
• 3 partitions of 2+1, giving 3 × 2 = 6 orders
• 1 partition of 1+1+1, giving 6 orders

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:

• P likes three options equally
• P prefers a particular option, the other two are less attractive and P is indifferent among the two (3 cases)
• P prefers two options equally, the third option is less attractive (3 cases)
• P likes one option best, one is less attractive, and one is worst (6 cases)

(See also Pairwise_comparison#Preference_orders.)

In terms of numbers assigned to three items:

• three equal values
• two equal high values, one low value (3 cases)
• one high values, two equal low values (3 cases)
• three different values (6 cases)

In this case an order-preserving transformation of the numbers counts as the same possibility: the numbers serve as an ordinal scale.

Non-transitive relations

There are 341 non-transitive relations, of which 35 are reflexive and 45 irreflexive.

The 35 reflexive non-transitive relations include:

• 14 non-transitive total relations
  • two of these are antisymmetric but their transitive closure is not (there is an "intransitivity", in some contexts also called "conflict"): the reflexive relation with aRb, bRc, cRa, and the one with a similar cycle in opposite direction

The 45 irreflexive non-transitive relations are:

• the 37 non-antisymmetric irreflexive relations, including:
  • "not equal"
• the 6 simple hierarchies of the form "aRb and bRc"; the transitive closures are the strict total orders
• "aRb, bRc, cRa", and the relation with a similar cycle in opposite direction

Symmetry w.r.t. permutations of elements

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:

• equality
• "not equal"
• "nothing is related"
• "each element is related to each element"

Two relations have a symmetry group of 3 permutations:

• "aRb, bRc, cRa"
• "aRc, cRb, bRa"

n=4

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; 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):

• 1: strict: no related elements; non-strict: each element is only related to itself (equality) (direct product of equality and equality)
• 74 involving four connected elements:
  • 24 strict/non-strict total orders (g: d)
  • 8 of the form aRb aRc aRd and the inverse (direct product of pRq and sRt) (no ub; inv: g: a)
  • 6 of the form aRc aRd bRc bRd (no ub) (subset {a,b} has upper bounds c and d, but no least upper bound)
  • 12 of the form aRb aRc bRd cRd (g: d)
  • 24 of the form aRb bRc bRd and the inverse (no ub; inv: g: a)

There are 144 additional partial orders (together 219) and 144 corresponding strict partial orders:

• 12 of the form aRb (no ub)
• 12 of the form aRb cRd (direct product of pRq and equality) (no ub)
• 48 involving three elements:
  • 24 of the form aRb bRc (no ub)
  • 24 of the form aRb aRc and the inverse (no ub)
• 72 involving four connected elements (together with those above: 146):
  • 48 of the form aRb aRc cRd and the inverse (no ub; inv: g:a)
  • 24 of the form aRb cRb cRd (no ub)

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:

• 189 graphs with 3 or less connected edges
• 12 graphs with 2 unconnected edges
• 14 requiring 4 edges:
  • 8 of the form aRb aRc aRd and the inverse
  • 6 of the form aRc aRd bRc bRd

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:

• with at least one curved edge
• with an additional point where two edges join and another one where they split
• ditto with the two points coinciding, i.e., with four edges joining in this point

Partitions

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:

• 1 partition of 4, giving 1 order
• 4 partitions of 3+1 and 3 of 2+2, giving 7 × 2 = 14 orders
• 6 partitions of 2+1+1, giving 6 × 6 = 36 orders
• 1 partition of 1+1+1+1, giving 24 orders

i.e. together 75 orders.

See also

• Wikipedia:Articles for deletion/Relations on a set of four elements
• Wikipedia_talk:WikiProject_Mathematics#Relations_on_a_set_of_three_elements