# Logical Definition of Isomorphism

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

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

$$(\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)) )]$$

• 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? Apr 18 at 20:34
• 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.) Apr 18 at 20:40

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.

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)) ]$$