1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

As with all math, you have to be sensitive to the context - different fields are going to use slightly different terms depending on their needs, and will often use terminology from other fields imprecisely via metaphor. You shouldn't assume that every mathematician means the exact same formal definition as every other mathematician by such terms, especially when it comes down to small details like domain/codomains, and distinctions like those between objects like "a boolean valued function on a set" and "a subset of a set" where mathematicians often differ in the precise details (and may even just treat them as interchangeable).

This said, I think all the evidence you need is in your question: subsets of $A\times B$ are most commonly known as relations from $A$ to $B$ (with this "from _ to _" phrasing mostly coming from the category Rel - in some contexts where order doesn't matter you'll hear "between _ and _" instead). There are some other terms that sometimes get used (e.g. "binary predicate" which is subtly different, but interchangeable in most classical contexts - note that predicates commonly take any number of arguments, so "binary" is important here) as well as some qualifiers (e.g. "binary relation" to clarify that two sets are involved in the product). In my experience, this term is very widespread (and Wikipedia would not invent a name for a concept like this!), but not so technical as to have everyone in agreement about the specifics - sort of like how $\mathbb N$ might include $0$ or might not, but it's should never be hard to figure out which convention the author meant or if it matters.

The definition of an equivalence relation does not contradict this definition of a relation. An equivalence relation is a (binary) relation, but the properties of symmetry, transitivity, and reflexivity all implicitly assume that it is a relation from a set to itself. This is in the same way that an endomorphism is a kind of function where the domain and codomain are equal.

$\endgroup$
9
  • $\begingroup$ What mathematical term distinguishes recursive/endormorphic binary relations from others? Recursive? Endomorphic? $\endgroup$ – fundagain Feb 19 '20 at 17:49
  • $\begingroup$ @fundagain It's not a sufficiently common mathematical idea to have a universally understood term. The clearest thing to say is "a relation from a set to itself" or occasionally you'll hear "a relation on a set" (which is imprecise, but easily understood) or, in the category Rel "an endomorphism." Sometimes those objects might be thought of as directed graphs. It's an issue of language and intuition - you seem to be after rigorous answers, but it's important to know that common mathematical language is not itself rigorous - it is merely meant to convey rigorous ideas. $\endgroup$ – Milo Brandt Feb 19 '20 at 18:00
  • $\begingroup$ I would just like to check that I have got you right. Binary relations as subsets of $A^2$ are universally understood. Binary relations as subsets of $A \times B$ are not a universally understood term. Hence I should not expect a universal term for the latter notion. This is consistent with everything I have read over my life. I was hoping there was a term, because it would make my life easier. But a term for subsets of $A \times B$ that is not "relation". $\endgroup$ – fundagain Feb 19 '20 at 20:31
  • 1
    $\begingroup$ @fundagain It's the other way around: a binary relation from $A$ to $B$ is a subset of $A\times B$ - just like Wikipedia says. Subsets of $A\times A$ are a special case of this more general definition and are often called relations on $A$ (...or spoken of in entirely different terms, e.g. in the language of directed graphs or binary predicates). $\endgroup$ – Milo Brandt Feb 19 '20 at 20:54
  • $\begingroup$ No you are right. It is used that way. $\endgroup$ – fundagain Feb 19 '20 at 21:04
4
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Am I to take from your answer that it is well-known that binary relations are defined as subsets of $A\times B$, and that subsets of $A^2$ are special cases called [what]? What is the term that distinguishes the latter from the former. Is it "recursive" as in computer science? $\endgroup$ – fundagain Feb 19 '20 at 17:37
  • $\begingroup$ No! How do you define reflexive over $A\times B$? $\endgroup$ – fundagain Feb 19 '20 at 17:39
  • $\begingroup$ No I mean functor. The algebraization of a logic, if it exists, take a point/formula to a set of points/formulae. These point-set functions give rise to binary relations rather than functions. $\endgroup$ – fundagain Feb 19 '20 at 18:00
  • $\begingroup$ 1. "reflexive", when applied to a relation, also requires that the two sets be the same. 2. What you mean by "functor" is apparently not what category theorists, for example, mean by "functor," for the "domains" in category may be too large to be sets. 3. Is it well known that (binary) relations are subsets of cartesian products. Well, that's how the much-cited Halmos book defines them. A random discrete math book I just grabbed (Maurer and Ralston) has that definition on page 18. The more widely used book by Rosen delays that to page 355, but says the same thing. So....yeah. Well-known. $\endgroup$ – John Hughes Feb 19 '20 at 21:00
  • $\begingroup$ As for relations on $A,A$ (i,e, a subset of $A \times A$) I'd call that a "binary relation on $A$", and I'd expect no one to be confused by it, but I've been wrong before. :) $\endgroup$ – John Hughes Feb 19 '20 at 21:02
1
$\begingroup$

Let A & B be sets. Then, a subset of $A \times B$ is referred to in different ways depending on what you're trying to accomplish.

For example, a relation is any subset of $A \times B$. Unless I'm blanking and missing out on something, that's the coarsest structure that you're working with. Just plain old subsets of $A \times B$. We just call those relations.

Then, you could take it one step higher and say that a function is a subset of $A \times B$ such that $\forall a \in A: \exists! b \in B: (a,b) \in f$, where $f:A \to B$ is the function.

Notice that we have created an entirely new term based on an additional property that we've imposed on the specific subset of $A \times B$ that we pick out. These are just additional properties that would make them interesting to study.

For example, Linear Transformations are specific functions that map elements from one vector space to another vector space such that an additional number of conditions hold. In this case, the function itself has to specify certain properties and the sets also have to satisfy specific properties.

Definition: A binary operation on a set $S$ is a function $\circ: S \times S \to S$

In other words, a binary operation is nothing but a function of a specific type. It takes two elements from S, does something to them and spits out something that belongs to S.

To put it very simply, they are referred to in different ways depending on the context.

References:

Fundamentals of Mathematics by Bernd Schroder

$\endgroup$
2
  • $\begingroup$ Might e.g. call $[0, 1] \times [0, 1]$ "the unit square".... or "the limits of our integal", or a whole lot of other names $\endgroup$ – vonbrand Feb 19 '20 at 20:47
  • $\begingroup$ Indeed. Context dictates the name of a given set. $\endgroup$ – Abhi Feb 20 '20 at 3:44
1
$\begingroup$

Depending on the context, a subset of $A\times B$ may be called a binary relation or simply referred to as a subset of $A\times B$.

For example, if I am referring to a particular subset $U\subseteq \mathbb{R}\times \mathbb{R}$ then I might want to think of it more geometrically as opposed to being a relation on $\mathbb{R}$ (although it is technically a binary relation). For example, the unit circle is the subset $\{(x,y)\in \mathbb{R}^2: x^2+y^2=1\}$. But I could equivalently think of it as a relation $x\sim y$ if and only if $x^2+y^2=1$.

The way that we can go back and forth between subsets $R\subseteq A\times B$ and binary relations is by the correspondence $(a,b)\in R\Longleftrightarrow a\sim b$.

As for your comment about equivalence relations, you are correct. The reflexivity requirement forces $A=B$. But there's nothing contradictory about that. It just means that if $A\neq B$, no subset of $A\times B$ is an equivalence relation.

I really do not understand what you are asking by saying "Operations are to binary relations as functions are to ???." Operations are functions $O:A_1\times\cdots\times A_n\to B$

$\endgroup$
13
  • $\begingroup$ I have corrected that to unary operations are to binary relations as functions are to ???. $\endgroup$ – fundagain Feb 19 '20 at 17:30
  • $\begingroup$ A unary operation $O$ is just a function $O:A\to B$. Operations and functions are the same thing. Every operation is a function, and every function $f:X\to Y$ is a unary operation on $X$ with values in $Y$. $\endgroup$ – TheEmptyFunction Feb 19 '20 at 18:32
  • $\begingroup$ Yes. So unary operation is to binary relation as function is to ??? Or unary operation is to ??? as function is to binary relation. $\endgroup$ – fundagain Feb 19 '20 at 18:37
  • $\begingroup$ Unary operations are the same thing as functions. And a function is just a specific type of binary relation. So unary operation is to binary relation as function is to binary relation. If P=Q, then P is to X as Q is to X (no matter what X is) $\endgroup$ – TheEmptyFunction Feb 19 '20 at 19:00
  • $\begingroup$ No. Unary operations are special functions. $\endgroup$ – fundagain Feb 19 '20 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.