What are subsets of $A\times B$ called

notationrelations

What are subsets of $A\times B$ called in mathematics?

  • In logic (algebra and analysis), a binary relation on/over $A$ is a subset of $A^2$. Abstractions of $=$, $\leq$, etc. While using subsets of $A\times B$ extensively in the role of functor, logicians have no term for these objects. I have always called a subset of $A\times B$ a binary relationship, but always explain that this is just my term.

  • In the computer science ER Model, a binary relation is a subset of $A\times B$, with a subset of $A^2$ being called a recursive binary relation.

Wikipedia currently makes a complete mess of the situation, by defining a binary relation as

In mathematics, a binary relation over two sets $X$ and $Y$ is a set of
ordered pairs $(x, y)$ consisting of elements $x\in X$ and $y\in Y$. That
is, it is a subset of the Cartesian product $X ร— Y$.

yet defining an equivalence relation, via reference to the above definition, as

In mathematics, an equivalence relation is a binary relation that is
reflexive, symmetric and transitive.

The latter definition is complete nonsense for subsets of $A\times B$, only making sense for subsets of $A^2$. Reflexivity cannot be defined for subsets of $A\times B$.

  • What are subsets of $๐ดร—๐ต$ called in mathematics?
  • I have never encountered these being called binary relations in mathematics, except for Wikipedia. I thought this might be my algebra-logic bias, but have checked Analysis books, and yes, (binary) relations are as we have known them from primary school, subsets of $A^2$. Abstraction of $=$, $\leq$, etc.
  • Unary operations ($o:A\rightarrow A$) are to binary relations ($r\subseteq A^2$) as functions ($f:A\rightarrow B$) are to ??? ($R\subseteq A\times B$)?

I am not looking for a proposed term, nor asking for reference back to Wikipedia, rather, I am asking if there is some term already in widespread use in the literature, and ideally with reference.

Based on answers received so far, an additional question would then be,

  • in the context that binary relations are subsets of $A\times B$, what term distinguishes the $A^2$ case? Endomorphic? Recursive?

Some have argued that the Wikipedia definition of equivalence relation is correct as stands. It is not. The definition of an equivalence relation cannot be phrased for subsets of $A\times B$. Reflexivity is impossible to define for subsets of $A\times B$. Further, no one would define an equivalence relation as a subset of $A\times B$ such that…, and then expect the reader to deduce that $A$ must equal $B$. No. That is not how equivalence relations are defined. Currently Wikipedia is wrong.

@TheEmptyFunction has drawn my attention to the fact that Wikipedia currently defines an $n$-ary operation as a function $A_1\times…\times A_n\rightarrow B$, rather than the mathematicians $A^n\rightarrow A$. This definition strips the notion of operation of all its logical/algebraic/analytic meaning. Homomorphisms no longer make sense. The same is true for calling a subset of $A\times B$ a binary relation.

Best Answer

"Wikipedia makes a complete mess ... " is just a trifle arrogant, because Wikipedia, as quoted, gets it exactly right.

A binary relation on $A, B$ cannot be symmetric unless $A = B$, so "equivalence relations" (as defined) are all on products of the form $A \times A$; they are exactly those relations that are symmetric, transitive, and reflexive.

"While using subsets of ๐ดร—๐ต extensively in the role of functor," ... I certainly hope you mean "function"; functors are defined on categories (or at least they were back in the 1980s, when I learned this stuff).

"I have never encountered these being called binary relations in mathematics, except for Wikipedia." says more about the extent of your exposure to mathematics than it does about Wikipedia.

Halmos's "Naive Set Theory" does a pretty good job getting this stuff laid out without too much fuss. Of course it doesn't mention functors, but that's because it's a naive-set-theory book.

Related Question