Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
5  
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 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 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 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 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 at 1:01

3 Answers 3

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.

share|improve this answer
2  
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 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 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 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.

share|improve this answer
    
Out of curiosity: is there an ordered-pair definition which does not raise the rank? –  Mariano Suárez-Alvarez Jul 13 at 1:50
1  
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 at 1:56
    
From your answer, it sound correct to name the algebras which I described, "pairing algebras". –  Ioachim Drugus Jul 13 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 at 0:41
    
I would go along with that. –  Joel David Hamkins Jul 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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