1
$\begingroup$

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
    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?2011-10-16

3 Answers 3

4

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.

  • 0
    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?2011-10-16
  • 0
    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\}$.2011-10-16
  • 0
    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"?2011-10-16
  • 1
    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.2011-10-16
  • 0
    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.2011-10-16
  • 0
    I still think the best thing you can hope for is to replace Kuratowski pairs with "Stricker pairs" of an equally arbitrary anatomy.2011-10-16
  • 0
    Sounds bad (for my intention).2011-10-16
5

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.

4

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