3
$\begingroup$

An isomorphism from a poset $(S_1,R_1)$ to a poset $(S_2,R_2)$ is a bijection $f: S_1 \rightarrow S_2$ such that, for all $x,y \in S_1$

$(x,y) \in R_1 \leftrightarrow (f(x), f(y)) \in R_2$

When such an isomorphism exists, we say that $(S_1,R_1)$ is isomorphic to $(S_2,R_2)$.

Questions:


  1. Show that every poset is isomorphic to itself.

Attempt: Every poset is isomorphic to itself...it's like the reflexive definition for equivalence relations which is $(\forall x \in S)[(x,x) \in R]$

So maybe I could apply the definition?

$(\forall x \in S)[(x,x) \in (S_1,R_1)]$

$(\forall x \in S)[(x,x) \in (S_2,R_2)]$


2.Prove that if $f$ is an isomorphism then so is $ f^{-1}$

Attempt: Definition 6.3.6 states that we let $R$ be any relation on a set $S$. The inverse relation of R, denoted $R^{-1}$ is defined by the condition $(x,y) \in R \leftrightarrow (y,x) R^{-1}$

Using the definition on $(x,y) \in R_1 \leftrightarrow (f(x),f(y)) \in R_2$, we have

$(x,y) \in R_1 \leftrightarrow (y,x) \in R_1^{-1}$

$(f(x),f(y)) \in R_2 \leftrightarrow f(y),f(x) \in R_2^{-1}$

$(y,x) \in R_1^{-1} \leftrightarrow f(y),f(x) \in R_2^{-1}$

It appears that they're kind of symmetrical in a way.


  1. Prove that the composition of two isomorphisms is an isomorphism.

    Attempt: Definition 6.3.9 states that we let $R_1$ and $R_2$ be relations on a set S. The composition of $R_2$ with $R_1$ is the relation

$R_2 \circ R_1 =[(x,y) \in S \times S:( \exists v \in S)[(x,y) \in R_1 \land (v,y) \in R_2]$

Maybe we should have a composition like $(S_1,R_1) \circ (S_2, R_2)$. Then ,

$(S_2, R_2) \circ (S_1,R_1) =[(x,y) \in S \times S:( \exists v \in S)[(x,y) \in (S_1,R_1) \land (v,y) \in (S_2, R_2)]$

I'm kind of confused and lost...maybe the transitive property would work better?

Definition: R is transitive if $(\forall x, y, z \in S)[((x,y) \in R \land (y,z) \in R) \rightarrow (x,z) \in R]$

so maybe let $x = (S_1,R_1), y = (S_2, R_2)$ and $z = (S_3,R_3)$. Then

$(\forall (S_1,R_1), y, z \in S)[(((S_1,R_1),(S_2, R_2)) \in R \land ((S_2, R_2),(S_3,R_3)) \in R) \rightarrow ((S_1,R_1),(S_3,R_3)) \in R]$...

If the original poset definition was being used here I could understand it a little bit better, but this is a different form. Any hints?

$\endgroup$
0
$\begingroup$

You have some good intuitions, but you apply it to wrong items. The main mistake is that you are trying to apply the properties you are proving to the posets themselves, rather than the isomophism relation.

So let me state it another way: you want to prove that isomophism relation is an equivalence relation, but this is at a one level higher than the posets, i.e. it is a relation about relations.

Hint:

  1. Isomorphism relation is reflexive. That means there exists a bijection from the poset to itself that preserves the poset-relation. There might be many such bijections, but there is one that always works: identity, obviously $$\forall x,y \in S_1.\ (x,y) \in R_1 \leftrightarrow (x, y) \in R_1$$ and so function $\mathrm{id}_{S_1} : S_1 \to S_1$ given by $\mathrm{id}_{S_1}(x) = x$ is a valid isomorhism between $(S_1,R_1)$ and itself.
  2. Isomorphism relation is symmetric. That means that if $f : S_1 \to S_2$ is a valid isomorphism between $(S_1,R_1)$ and $(S_2,R_2)$, then $f^{-1} : S_2 \to S_1$ is a valid isomorphism between $(S_2,R_2)$ and $(S_1,R_1)$. Note, that we don't change or inverse the $R_1$ or $R_2$ relations as you did in your approach. Instead we inverse the isomorphism, which is one level higher. In particular we would like to show $$\Bigg(\forall x,y \in S_1.\ (x,y) \in R_1 \leftrightarrow (f(x), f(y)) \in R_2\Bigg) \!\!\iff\!\! \Bigg(\forall x',y' \in S_2.\ (x',y') \in R_2 \leftrightarrow (f^{-1}(x'), f^{-1}(y')) \in R_1\Bigg)$$ which is true because $f$ and $f^{-1}$ are both bijections and mutual inverses.
  3. Isomorphism relation is transitive. That is, if $f : S_1 \to S_2$ and $g : S_2 \to S_3$ are valid isomorphisms, then so is $(g \circ f) : S_1 \to S_3$. Note that we don't compose the poset relations, but the isomorphisms. Then we would like to show that $$ \Bigg(\forall x,y \in S_1.\ (x,y) \in R_1 \leftrightarrow (f(x), f(y)) \in R_2\Bigg) $$ and $$ \Bigg(\forall x',y' \in S_2.\ (x,y) \in R_2 \leftrightarrow (g(x'), g(y')) \in R_3\Bigg) $$ together imply $$ \Bigg(\forall x'',y'' \in S_1.\ (x'',y'') \in R_1 \leftrightarrow \big((g\circ f)(x''), (g\circ f)(y')\big) \in R_3\Bigg) $$ which is true by transitivity of $\leftrightarrow$.

I hope this helps $\ddot\smile$

$\endgroup$

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.