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