3
$\begingroup$

I'm trying to define isomorphism in a logical way. Is the following statement true for Isomorphism's definition?

Let $\langle S,⋆\rangle$ and $\langle S',⋆'\rangle$ be Algebraic Structures. These two structures are isomorphic if and only if: $$\left( \exists \phi : S \rightarrow S' \right) \left(\ \forall a,b \in S \right) \left[ \left( \phi (a⋆b) = \phi(a) ⋆' \phi(b) \right) \land \left( \phi(a)=\phi(b)\iff a=b \right) \land \left( \left( \exists x \in S' \right) \left(x=\phi(a)\right) \right) \right] $$

Here is what I tried to show:

The function $\phi$ is an isomorphism whenever it has the following properties:
Preservance of the Binary Relationship $\land$ Injectivity $\land$ Surjectivity

I'm not sure if my definition is notationally flawless, and am especially concerned about the last atomic proposition: $(\exists x \in S')(x=\phi(a))$; because b isn't brought up here despite $\forall b \in S$ is present at the start of the definition.

Is my concern valid? If so, is there any other way to show a function's surjactivity which requires two elements from S?
If not, would this definition also be usable if I put $\exists x \in S'$ right after $\forall a,b \in S$?

$\endgroup$
2
  • $\begingroup$ What is an algebraic structure? Is a ring an algebraic structure? If so, then this definition clearly fails. $\endgroup$
    – Malady
    Apr 18 at 19:14
  • $\begingroup$ I should've been more clear, what I meant by "algebraic structure" was, as you mentioned in your answer, binary structures. $\endgroup$
    – Karaji
    Apr 18 at 20:42

3 Answers 3

5
$\begingroup$

$(\forall x)(P \land Q)$ is equivalent to $((\forall x)P) \land ((\forall x)Q)$ (where $P$ and $Q$ are formulas that may or may not contain $x$ or other free variables). (Informally, you can push universal quantifiers into a conjunction.) So your inner universally quantified formula is equivalent to:

$$ [(\forall a,b \in S) ( \phi (a⋆b) = \phi(a) ⋆' \phi(b) ) ] \land [(\forall a,b \in S) ( \phi(a)=\phi(b)\iff a=b )] \land [(\forall a,b \in S) ( ( \exists x \in S') (x=\phi(a)) )] $$

Also, $(\forall x, y) P$ is equivalent to $(\forall x)P$ if $y$ does not appear free in $P$, so the above is equivalent to:

$$ [(\forall a,b \in S) ( \phi (a⋆b) = \phi(a) ⋆' \phi(b) ) ] \land [(\forall a,b \in S) ( \phi(a)=\phi(b)\iff a=b )] \land [(\forall a \in S) ( ( \exists x \in S') (x=\phi(a)) )] $$

This ought to give you that $\phi$ preserves the binary operator, is injective and surjective expressed separately and naturally. However it isn't right: $x$ and $a$ have got switched round in the quantifiers in the last clause: surjectivity of $\phi$ says that for every $x$ in the codomain $S'$ of $\phi$ there is an $a$ in the domain $S$ such that $x = \phi(a)$. If you make that switch in the original you get a correct formalisation of the statement that $(S, *)$ and $(S', *')$ are isomorphic:

$$ [(\forall a,b \in S) ( \phi (a⋆b) = \phi(a) ⋆' \phi(b) ) ] \land [(\forall a,b \in S) ( \phi(a)=\phi(b)\iff a=b )] \land [(\forall x \in S') ( ( \exists a \in S) (x=\phi(a)) )] $$

$\endgroup$
2
  • $\begingroup$ Let's say neither x or y are included in P, but z appears in P. Is ($\forall x,y) (\exists z$)P also equivalent to ($\exists z$)P? If that's true, am I right to consider $$ (\forall a,b \in S) (\forall x \in S') (\exists y \in S)[ ( \phi (a⋆b) = \phi(a) ⋆' \phi(b) ) \land (\forall a,b \in S) ( \phi(a)=\phi(b)\iff a=b ) \land (x=\phi(a)) ] $$ an equivalent to the correct formalisation? $\endgroup$
    – Karaji
    Apr 18 at 20:34
  • 2
    $\begingroup$ The answer to your first question is yes. The answer to the second is no, but just because of a typo: I think you meant to write $x = \phi(y)$ not $x = \phi(a)$. (Pushing existentials into conjunctions is more restricted than pushing universals, but it's OK if the bound variable only appears free in one of the conjuncts.) $\endgroup$
    – Rob Arthan
    Apr 18 at 20:40
3
$\begingroup$

Your main questions seems to be about surjectivity. Let’s try to unravel just that. You say a map $\phi : S \rightarrow S^\prime$ is surjective iff: $$\forall a \in S\; \exists x \in S^\prime \; x=\phi(a)$$

Now this is actually true for all maps. Just take $x=\phi(a)\in S^\prime$ which (clearly) equals $\phi(a)$. You’ve swapped your quantifiers and their order.

Here’s the correction. We say a map $\phi : S \rightarrow S^\prime$ is surjective iff: $$\forall x \in S^{\prime}\; \exists a \in S \; x=\phi(a)$$

The problem has nothing to do with it not referencing $b$. Also, what is an “algebraic structure?” This definition seems like it only has any hope to work for algebraic structures whose only, well, structure, is one single binary operation.

$\endgroup$
1
$\begingroup$

As stated by Rob and Malady, the only problem of this statement is the definition of surjectivity.
Regarding the question about b, these two statements are equilavant: $$ \left( \exists \phi : S \rightarrow S' \right) \left(\ \forall a,b \in S \right) \left[ \left( \phi (a⋆b) = \phi(a) ⋆' \phi(b) \right) \land \left( \phi(a)=\phi(b)\iff a=b \right) \land \left( \left( \exists x \in S' \right) \left(x=\phi(a)\right) \right) \right] $$ $$\left( \exists \phi : S \rightarrow S' \right) \left(\ \forall a,b \in S \right) \left( \exists x \in S' \right) \left[ \left( \phi (a⋆b) = \phi(a) ⋆' \phi(b) \right) \land \left( \phi(a)=\phi(b)\iff a=b \right) \land \left(x=\phi(a)\right) \right]$$ In other words, the appearance of a variable in every conjuct is not necessary. So putting $\exists x \in S'$ after $\forall a,b \in S$ is actually allowed.

This (and its equivalents like the one in Rob's answer) would be the correct definition:

Let ⟨S,⋆⟩ and ⟨S′,⋆′⟩ be Binary Algebraic Structures. These two structures are isomorphic if and only if: $$(\forall a,b \in S) (\forall x \in S') (\exists y \in S)[ ( \phi (a⋆b) = \phi(a) ⋆' \phi(b) ) \land (\forall a,b \in S) ( \phi(a)=\phi(b)\iff a=b ) \land (x=\phi(y)) ]$$

$\endgroup$

You must log in to answer this question.

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