The number of structures of finite relations
Robert L. Davis · Proceedings of the American Mathematical Society · 1953
1. Preliminaries. Let A be a dyadic relation defined on a finiteset of n elements. It is convenient to regard A as an n Xn matrix over the two-element Boolean algebra, so that a,j=1 if and only if iAj. There is then an obvious correspondence of relational concepts [1; 2]2 with matrix notions, interpreting conjunction as coordinatewise multiplication, relative product as matrix product, etc. In this paper, however, matrix notation and Boolean I's and 0's are adopted merely for convenient reference. If A and B are two relations defined over the set N= {1, * * , n}, then they are isomorphic just when there is a permutation 7r of N such that A has the same matrix with respect to N as B with respect to 7r(N) [cf. 3, *151.01]. Formally, for every relation A defined on N and every 7r in S,) (the symmetric group of n letters), define a transformation tr of A by