Is it correct that — opposed to general relations and functions — equivalence relations and bijective functions can be defined without reference to ordered pairs? Especially, do the following definitions capture the usual notions of equivalence and bijection?

Definition: $X$ is an equivalence relation on set $Y$ if

  1. $X \subset \mathcal{P}(Y)$

  2. $(\forall x \in X)\ |x| = 1 \vee |x| = 2$

  3. $(\forall y \in Y)\ \lbrace y \rbrace \in X$

  4. $(\forall x,y,z \in Y)\ \lbrace x,y \rbrace \in X \wedge \lbrace y,z \rbrace \in X \rightarrow \lbrace x,z \rbrace \in X$

Definition: $X$ is a bijection between sets $Y$ and $Z$ if

  1. $(\forall x \in X)(\exists y \in Y)(\exists z \in Z)\ \lbrace y,z\rbrace = x$

  2. $(\forall y \in Y)(\forall z \in Z)(\exists x \in X)\ \lbrace y,z\rbrace = x$

Or is there a mistake in one of these definitions?

  • 1
    $\begingroup$ Your definition of bijection is incorrect as stated: part 2 requires that for every $y\in Y$ and every $z\in Z$ you have $\{y,z\}\in X$. You are just saying that $X$ is the collection of all subsets that contains exactly one element from $Y$ and one element from $Z$ (possibly the same element). So, for example, the only set that satisfies your definition of "bijection" with $Y=\{a,b\}$ and $Z=\{a,1,2\}$ is $X=\{ \{a\}, \{a,1\}, \{a,2\}, \{a,b\}, \{b,1\}, \{b,2\}\}$. This satisfies your definition, and is not what you really want to call a "bijection", is it? $\endgroup$ – Arturo Magidin Oct 16 '11 at 20:20

The "equivalence" definition looks okay (and the same technique can encode every symmetric relation), but the "bijection" one has trouble.

It can only begin to work if $Y$ and $Z$ are disjoint. And even so, the second condition must be replaced with two:

  • $(\forall y \in Y)(\exists_1 z \in Z)\ \lbrace y,z\rbrace \in X$
  • $(\forall z \in Z)(\exists_1 y \in Y)\ \lbrace y,z\rbrace \in X$

where $\exists_1$ is the "there exists exactly one" quantifier.

  • $\begingroup$ Together with Arturo's comment I understand that my definition is flawn and yours is much better and appropriate. But why do $Y$ and $Z$ have to be disjoing? $\endgroup$ – Hans-Peter Stricker Oct 16 '11 at 22:18
  • $\begingroup$ Otherwise you don't know, when you see $\{a,b\}$ and $a$ and $b$ are both in $X\cap Y$ whether $a$ maps to $b$ or vice versa. For example there is a bijection $\mathbb Z\to\mathbb Z$ that adds 1 to every number, and a different bijection that subtracts 1 from every number. But your scheme would attempt to represent both as $\{\{0,1\},\{0,-1\},\{1,2\},\{-1,-2\},\{2,3\},\ldots\}$. $\endgroup$ – Henning Makholm Oct 16 '11 at 22:22
  • $\begingroup$ So I should not call it "bijection" or "bijective function". Could you propose something if I would like to capture only the concept of "being equipollent"? $\endgroup$ – Hans-Peter Stricker Oct 16 '11 at 22:27
  • 1
    $\begingroup$ I don't think trying to patch it up will give you anything that is simpler than the usual ordered-pair based definition. For example, you'll want to have a witness for $\mathbb N\simeq\mathbb Z$, and for that you need to have some natural numbers map to negatives and themselves be images of other naturals. Getting the bookkeeping right there will require you to invent something that is essentially as strong as ordered pairs. $\endgroup$ – Henning Makholm Oct 16 '11 at 22:33
  • $\begingroup$ I'm not looking for something simpler but for something more natural and less ambiguous than any specific definition of "ordered pair" (like Kuratowski's). Especially I try to define "equipollent" without ordered pairs. $\endgroup$ – Hans-Peter Stricker Oct 16 '11 at 22:37

Every equivalence relation on a set $X$ defines a (unique) partition on said set, so you can conversely define an equivalence relation using not ordered pairs, but partitions.


I would say that a bijection is, in particular, a function, and therefore must have a specified domain and codomain. How would you define the inverse of a bijection in your definition?

In other words, your bijections are not in bijection with my bijections, because for any such set $X$ in your definition, there are two bijections in my definition, namely, $f_X:Y\to Z$ and $f_X^{-1}:Z\to Y$.


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.