# What kind of algebra is the class of ordered pairs equipped with the binary operation which forms them?

There are many definitions of ordered pair in set theory, but all such definitions have the characteristic property of ordered pair:

$\ \ \ \ \ \ (x, y) = (x', y') \leftrightarrow \ (x = x' \ and \ y = y')\ \ \ \$(*)

The comma in the expression "$(x, y)$" can be treated as a binary operation over sets resulting in an ordered pair. My question is about this operation. The term "$(x, y)$" can be an operation symbol of the language of a set theory T, and my question is easier to be answered for this case, than for the case when this operation is defined by a concrete definition (Kuratowski's, Wiener's, etc.). Thus, what kind of algebra is "$(U, \ (x, y))$", where U denotes the universe of discourse of a set theory T, and "$(x, y)$" is an operation symbol in the language of T?

To make the question correct, I would have to use such terms as "class-algebra", say that $U$ is a Grothendieck universe, or otherwise take care of foundations. But the question is about algebraic properties of this algebra and to keep focus on this, I would keep the aspect of "size" ("set" versus "class") fuzzy for now.

The property (*) is neither an identity, nor a quasi-identity - do algebraists handle such properties of a binary operation?

Here is one reason why this question is interesting. Set theory can be presented algebraically, but then it would be nice that the formulas of such an algebraic set theory are treated on same basis as their interpretations ("within the same universe of discourse"). A formula can be treated as result of multiple applications of the operation $(x, y)$ and, therefore, it would be nice to get an idea of the algebraic properties of this operation - whence my question.

I guess, the AST (Algebraic Set Theory) presented in the language ofcategory theory treats syntax on the same basis as semantics. But can my question be answered in the language of universal algebra?

-
I don't understand. Part of the point of the formation of ordered pairs is that it should satisfy no algebraic identities whatsoever. –  James Cranch Jul 12 '14 at 22:13
But maybe there are other properties, different from identities, of such algebras - properties, which can be expressed in terms of homomorphisms, direct products, subalgebras, etc. I am interested in any study of algebras with such a binary operation satisfying the property (*). –  Ioachim Drugus Jul 12 '14 at 22:25
If you are happy with a set sized universe, there are algebras with decomposition operation that are used to study cartesian products of algebras. Do a web search for details. One of the operations behaves something like (a,b)*(c,d) yields (a,d). –  The Masked Avenger Jul 12 '14 at 22:40
@JamesCranch Your objection applies when one considers the ordered pair $(x,y)$ to have a different type than $x$ or $y$, but here we mix them together in one algebra $U$, and so obviously there will be some instances that have additional structure, as I explain in my answer. For example, some ordered-pair concepts have $U\times U=U$, and others have $U\times U\subsetneq U$. –  Joel David Hamkins Jul 13 '14 at 23:42
@Masked Avenger, the algebras you referred to sound interesting, especially due to the "*" operation. I searched the web, but I could not find anything mentioning this operation. Can you please give me a key word or expression for web search? –  Ioachim Drugus Jul 14 '14 at 1:01

The property (*) is actually equivalent to a set of quasi-identities: $$(x,y)=(x',y')\rightarrow x=x'$$ $$(x,y)=(x',y')\rightarrow y=y'$$ The converse implication you had ($\leftarrow$) is logically valid and hence does not need to be mentioned.

-
And therefore the class of sets equipped with a binary operation which satisfies these conditions is stable under isomorphisms, subalgebras, and products. –  Nik Weaver Jul 13 '14 at 0:12
It is nice to hear that (*) reduces to quasiidentities. So, these algebras form a quasivariety. This reduction is done via the two projections. Interesting, if we add symbols for projections to the signature of this algebra would the theory of new algebras be essentially the same? It seems I sure ask this manner - "would the theory of new algebras be a conservative extension?" –  Ioachim Drugus Jul 13 '14 at 20:32
It depends on how you arrange things. The Jonsson-Tarski algebras mentioned in another answer have a nice equational setup: l(p(x,y))=x=r(p(y,x))= p(l(x),r(x)). This gives trivial or infinite algebras, and is a nice example to use in studying algebras with pairing and projection functions. Gerhard "Ask Me About System Design" Paseman, 2014.07.13 –  Gerhard Paseman Jul 13 '14 at 20:47

Since your algebra mixes together the objects $x$ and $y$ with their pair $(x,y)$ in the same algebra, it has the effect of erasing "ordered-pair" as a separate type in this context, and so there is no reason to expect that condition $(*)$ is all the structure one will expect to find. For example, in your algebra you can form iterated terms like $(x,(y,z))$ and inquire whether $x=(x,y)$ is possible, while in a more highly typed context, such an equation wouldn't even be sensible necessarily. For this reason, there are numerous pairing functions that exhibit all kinds of other extra algebraic structure in the algebra you are considering.

For example, many of the usual ordered-pair definitions in set theory have the property that $(x,y)$ has higher rank than $x$ and $y$, and in particular, $x\neq (x,y)\neq y$.

Similarly, for most of the pairing functions, $\emptyset\neq (x,y)$, and so these pairing function are never a bijection of $U\times U$ with $U$.

But there are other pairing functions that do constitute a bijection between $U\times U$ and $U$, and in this sense it would be correct to write $U\times U=U$. This would include some of the usual flat pairing functions one sees in set theory, where actually every set $x$ is $(y,z)$ for some $y$ and $z$, and so the pairing function is a bijection of $U\times U$ with $U$. Indeed, with the flat pairing functions I have in mind, $V_\theta\times V_\theta=V_\theta$ for any infinite ordinal $\theta$, and this includes all the Grothendieck universes you were considering.

One can easily design artificial pairing functions that have other extra properties, such as having fixed-point objects $x$ for which $x=(x,x)$ and hence $x=(x,(x,x))=(((x,x),x),x)$ and so on, or having no such fixed-points $x$. One could also make pairing functions that had various instances of finite cycles $x=(x,y)$, $y=(y,z)$ and $z=(z,x)$ and so on. One can easily arrange crazy stuff, since of course the only requirement that $(*)$ imposes is that $(\cdot,\cdot)$ is injective.

If $(x,y)$ is a pairing function and $\pi:U\to U$ is any injective function, then $(x,y)_\pi:=\pi((x,y))$ is another pariing function. And indeed, all pairing functions arise this way from any given surjective pairing function.

-
Out of curiosity: is there an ordered-pair definition which does not raise the rank? –  Mariano Suárez-Alvarez Jul 13 '14 at 1:50
Yes, that is precisely what "flat" means for the flat pairing functions. They don't raise ranks on any infinite set. Another way to say this is that every $V_\theta$ for infinite $\theta$ is closed under pairs. (It is impossible to never increase rank, since the finite ranks $V_k$ cannot be closed under pairing (for $k>1$) on finite cardinality grounds, since $n^2$ is larger than $n$ for $n>1$. –  Joel David Hamkins Jul 13 '14 at 1:56
From your answer, it sound correct to name the algebras which I described, "pairing algebras". –  Ioachim Drugus Jul 13 '14 at 23:56
Thus, an ordered pair can be defined in such a manner that it encrypts not only order but also some additional information. This is very interesting because (1) this justifies using pairing algebras in encoding formulas as sets as I described their intended use in my question (2) Some properties of sets can be expressed in the language of pairing algebra and equality, which is useful for an algebraic set theory. –  Ioachim Drugus Jul 14 '14 at 0:41
I would go along with that. –  Joel David Hamkins Jul 14 '14 at 0:51

I am not sure but I believe up to isomorphism this kind of structure is indistinguishable from arbitrary embedding $A\times A\hookrightarrow A$.

Sort of related are the s. c. Jónsson-Tarski algebras --- when one requires that the above is actually a bijection. The latter are equational in the well known way, and play important rôles in various fields, being source of many interesting counterexamples.

-
Jónsson-Tarski algebras seem to be a sub-class of pairing algebras - "well-behaved pairing algebras". –  Ioachim Drugus Jul 14 '14 at 0:48

Universal algebra prefers to use a language in which the class of algebras under investigation is equationally defined (in other words: is a variety). This is why groups are often not written as structures $(G,*)$ but rather as structures $(G,*, 1, {}^{-1})$. (Or, rarely, as structures $(G,/)$, where $x/y:= x*y^{-1}$.)

I think the situation is similar here. If you do not require the pairing function to be onto, then the (in my opinion) natural way to represent your structures as algebras is to equip them with unary functions $l$ and $r$, and require $l(x*y)=x$, $r(x*y)=y$. (I use $*$ rather than the comma as the pairing operation.)

This makes your family of "sets with a pairing function" into an equationally defined class.

Every algebra $(A,*)$ with a pairing function in your sense can be expanded to an algebra $(A,*,l,r)$ in my sense. This implies that the first order theory of "my" algebras (the consequences of the two laws I gave) is a conservative extension of the theory of "your" algebras. (However, I think that this theory is quite trivial.)

An even more natural way would be to declare $l$ and $r$ to be partial functions, but it seems to me that partial functions are not popular in universal algebra.

Of course, if you do require the pairing function to be onto, you have to add the axiom $l(z)*r(z) = z$, and get a Jónsson-Tarski algebra, as remarked in previous answers.

-
Maybe, my question should have sounded like this: Can the ordered pair concept serve as foundation of (finitary) mathematics, and if it can, then can this foundation be algebraic? In such presentation, I would not regard the algebra above, with or without projections, as a "trivial algebra". It might be "trivial" only same manner as the free algebras are "trivial". It would be great to hear comments on this more general question from @Joel and others who gave here so useful answers, once I probably cannot ask again my question in a more general form. –  Ioachim Drugus Mar 13 at 0:25