Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-19T03:48:47.628Z Has data issue: false hasContentIssue false
  • English
  • Français

Note on Carnap's relational asymptotic relative frequencies1

Published online by Cambridge University Press:  12 March 2014

Frank Harary
Frank Harary*
Affiliation:
The University of Michigan, and The Institute for Advanced Study
Get access Rights & Permissions [Opens in a new window]

Extract

A (binary) relation is a collection of ordered couples. Two relations are isomorphic if there is a 1–1 correspondence between their fields which preserves the ordered couples. Isomorphism between relations is itself an equivalence relation, and a structure is an isomorphism class of binary relations.

Carnap ([1], p. 124) asks certain questions concerning (both the exact and) the asymptotic value of the relative frequency that a relation on p objects satisfies certain properties. Among the most interesting special cases are the asymptotic value of the relative frequency that a binary relation on p objects be (a) symmetric, (b) reflexive, (c) transitive irreflexive anti-symmetric, and (d) symmetric irreflexive. These results already appear either in, or almost in, the literature, in various disguises. The object of this expository note is to bring them to light, especially since some of the references may not be generally known to logicians.

Carnap ([1], p. 124) points out explicitly the correspondence between binary relations and linear graphs. Davis [2] and Harary [4] obtains precise results for the number of structures with certain properties using the language of relations and graphs respectively; but these do not supply the asymptotic values directly. The asymptotic results which are most useful here are either contained in, or are straight-forward extensions of, the formulas presented in Ford and Uhlenbeck [3], which in turn are based on unpublished work of G. Pólya. In addition, we utilize a result of L. Moser on transitive relations, which appears in Wine and Freund [5].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 23 , Issue 3 , September 1958 , pp. 257 - 260
Copyright
Copyright © Association for Symbolic Logic 1958

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

This work was supported by a grant from the National Science Foundation.

References

REFERENCES

[1]Carnap, R., Logical foundations of probability, Chicago, 1950.Google Scholar
[2]Davis, R. L., The number of structures of finite relations, Proceedings of the American Mathematical Society, vol. 4 (1953) 486–495.CrossRefGoogle Scholar
[3]Ford, G. W. and Uhlenbeck, G. E., Combinatorial problems in the theory of graphs, IV Proceedings of the National Academy of Sciences, vol. 43 (1957) 163–167.CrossRefGoogle ScholarPubMed
[4]Harary, F., The number of linear, directed, rooted, and connected graphs, Transactions of the American Mathematical Society, vol. 78 (1955) 445–463.CrossRefGoogle Scholar
[5]Wine, R. L. and Freund, J. E., On the enumeration of decision patterns involving n means, Annals of mathematical statistics, vol. 28 (1957) 256–259.CrossRefGoogle Scholar