0
$\begingroup$

Let the relation $R$ on $P(\mathbb{N})$ betrue for $A,B ∈ P(\mathbb{N})$ exactly if there is a surjection $f : A → B$. Is $R$ reflexiv, symmetrical, anti-symmetrical and/or transitive?

I know it is reflexive, because of the identity function.

I think it is not symmetrical but I can't really prove it. The solutions says: "there is a surjection: $\{{0, 1}\} → \{{0}\}$ but not in the other direction". Can someone explain that to me.

The solution continues and says that it is not anti-symmetrical either because of: " there are surjections between $\{{0}\} → \{{1}\}$, but they are different sets" It just mentioned that $\{{0, 1}\} → \{{0}\}$, how can they give this as an example, $\{{0}\} → \{{1}\}$. Doesn't that make the previous invalid?

$\endgroup$
1
  • $\begingroup$ Do you understand what "surjection" means? It seems you do not. $\endgroup$
    – BrianO
    Commented Feb 21, 2016 at 23:27

2 Answers 2

2
$\begingroup$

A relation is symmetric iff:

$\forall a, b \in X\ (a R b \Rightarrow b R a)$.

Thus, for $\{ 0,1 \}, \{ 0 \} \in \mathcal P(\mathbb N)$ we have the surjection $f : \{ 0,1 \} \to \{ 0 \}$ defined by: $f(0)=f(1)=0$.

But we cannot "invert" it to find a function $f' : \{ 0 \} \to \{ 0,1 \}$.

Thus, we have no sutjection from $\{ 0 \}$ to $\{ 0,1 \}$ and this means, applying the definition of $R$, that $( \{ 0 \}, \{ 0,1 \}) \notin R$.

Having found two sets $A, B \in \mathcal P(\mathbb N)$ such that: $(A, B) \in R$ but $(B, A) \notin R$, we have to conclude that $R$ is not symmetric.


Regarding antisymmetry, there is a simple surjection $s_1: \{ 0 \} \to \{ 1 \}$ with $s_1(0)=1$ and another simple one $s_2 : \{ 1 \} \to \{ 0 \}$ with $s_2(1)=0$.

Thus, again by definition of $R$, we have $(\{ 0 \}, \{ 1 \}) \in R$ and $(\{ 1 \}, \{ 0 \}) \in R$ but $\{ 0 \} \ne \{ 1 \}$.

$\endgroup$
3
  • $\begingroup$ How do you know $f(0) = f(1) = 1$? What function are you using? $\endgroup$ Commented Feb 21, 2016 at 18:17
  • 1
    $\begingroup$ Shouldn't it be $f(0)=f(1)=0$ instead of $1$? Or doesn't it matter since you have defined it? $\endgroup$ Commented Feb 21, 2016 at 18:21
  • $\begingroup$ I get it now! Thanks :) $\endgroup$ Commented Feb 21, 2016 at 18:25
1
$\begingroup$

To say that the relation is symmetrical in this case means that if you have a surjection from A to B then you must be able to find a surjection from B to A. The counterexample given in the solution is telling you that if you take the set $A= \lbrace 0,1 \rbrace$ and the set $B= \lbrace 0 \rbrace$ you have a surjection from A to B (the zero function) so the pair (A,B) is in the relation but you can't have a surjection in the other direction because you can only send 0 to 1 or to 0 but not to both of them (otherwise it wouldn't be a function). In general a function can't be surjective if the cardinality of the codomain is greater than the cardinality of the domain, in the case of finite sets thjs means that if the codomain has more elements than the domain there will be no surjection.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .