Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-22T20:37:42.330Z Has data issue: false hasContentIssue false
  • English
  • Français

On transitive subrelations of binary relations

Published online by Cambridge University Press:  12 March 2014

Christopher S. Hardin
Christopher S. Hardin*
Affiliation:
Department of Mathematics, Union College,807 Union Street, Schenectady, NY 12308, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The transitive closure of a binary relation R can be thought of as the best possible approximation of R “from above” by a transitive relation. We consider the question of approximating a relation from below by transitive relations. Our main result is that every thick relation (a relation whose complement contains no infinite chain) on a countable set has a transitive thick subrelation. This allows for a solution to a problem arising from previous work by the author and Alan Taylor. We also exhibit a thick relation on an uncountable set with no transitive thick subrelation.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 4 , December 2011 , pp. 1429 - 1440
Copyright
Copyright © Association for Symbolic Logic 2011

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.)

References

REFERENCES

[Buh02]Buhler, Joe P., Hat tricks, Mathematical Intelligencer, vol. 24 (2002), no. 4, pp. 44–49.CrossRefGoogle Scholar
[BHKL08]Butler, Steve, Hajiaghayi, Mohammad T., Kleinberg, Robert D., and Leighton, Tom, Hat guessing games, SIAM Journal on Discrete Mathematics, vol. 22 (2008), pp. 592–605.CrossRefGoogle Scholar
[EHMR84]Erdȍs, Paul, Hajnal, András, Maté, Attila, and Rado, Richard, Combinatorial set theory: partition relations for cardinals, North-Holland, Amsterdam, 1984.Google Scholar
[FR95]János C., Fodor and Roubens, Marc, Structure of transitive valued binary relations, Mathematical Social Sciences, vol. 30 (1995), pp. 71–94.Google Scholar
[GPR08]González-Pachón, Jacinto and Romero, Carlos, A method for obtaining transitive approximations of a binary relation, Annals of Operations Research, vol. 163 (2008), pp. 197–208.CrossRefGoogle Scholar
[HT08a]Hardin, Christopher S. and Taylor, Alan D., An introduction to infinite hat problems. Mathematical Intelligencer, vol. 30 (2008), no. 4, pp. 20–25.CrossRefGoogle Scholar
[HT08b]Hardin, Christopher S., A peculiar connection between the axiom of choice and predicting the future, American Mathematical Monthly, vol. 115 (2008), no. 2, pp. 91–96.CrossRefGoogle Scholar
[HT09]Hardin, Christopher S., Limit-like predictability for discontinuous functions, Proceedings of the American Mathematical Society, vol. 137 (2009), pp. 3123–3128.CrossRefGoogle Scholar
[HT10]Hardin, Christopher S., Minimal predictors in hat problems, Fundamenta Mathematicae, vol. 208 (2010), pp. 273–285.CrossRefGoogle Scholar
[Heu69]Heuchenne, C., Sous-relations transitives maxima, Bulletin de la Société Royale des Sciences de Liège, vol. 38 (1969), pp. 435–449.Google Scholar
[Hod97]Hodges, Wilfrid, A shorter model theory, Cambridge University Press, New York, 1997.Google Scholar
[SS00]Shelah, Saharon and Stanley, Lee, Filters, Cohen sets and consistent extensions of the Erdȍs–Dushnik–Miller theorem, this Journal, vol. 65 (2000), pp. 259–271.Google Scholar