17
$\begingroup$

If someone asks me how to prove that two order structures $\langle A,\leq \rangle$ and $\langle B,\preceq \rangle$ are isomorphic I would immediately suggest: try to find a function $f:A\to B$ such that $a \leq b$ iff $f(a) \preceq f(b)$, for all $a,b \in A$. Because given the definitions, this is the natural way the proof goes.

But if the same person asks me to show that $\langle A,\leq \rangle$ and $\langle B,\preceq \rangle$ aren't isomorphic, then I'm in trouble. I would start suggesting him: (1) pick up an arbitrary function $f:A\to B$ such that $a \leq b$ iff $f(a) \preceq f(b)$, for all $a,b \in A$, (2) try to find a contradiction. Then most of the times this is where I get stuck. Because I don't find any further information than this generic assumption, and I simply cannot check all possible functions.

This started with my (failed) attempt to show that $\langle \mathbb{N},< \rangle$ and $\langle \mathbb{Z},< \rangle$ aren't isomorphic.

Then I googled for some answers and I realize most people prove such "$X$ and $Y$ aren't isomorphic" statements by showing a property of $X$ (or $Y$) that is not satisfied by $Y$ (or $X$). Like:

$\langle \mathbb{N},< \rangle$ is well-ordered, $\langle \mathbb{Z},< \rangle$ isn't. QED.

Question: Why is this a legitimate approach? Why is it enough? As a logician, and looking at the definitions, my natural approach to show that two structures aren't isomorphic, is to assume a generic order-preserving mapping and then deriving a contradiction. How is this "property approach" in harmony with that?

$\endgroup$
  • 1
    $\begingroup$ Note that in your first paragraph you need to require that $f$ is a bijection; if not all bets are off. $\endgroup$ – Marc van Leeuwen Jul 22 '15 at 13:49
  • $\begingroup$ See Ehrenfeucht–Fraïssé game. $\endgroup$ – Pål GD Jul 22 '15 at 15:20
28
$\begingroup$

The "property approach" does generate a contradiction. The full proof tends to follow these lines:

Suppose the structures $X$ and $Y$ are isomorphic. Then there exists an isomorphism $f : X \rightarrow Y$ between them. Property $P$ is preserved under isomorphism (due to some other proof), so because $X$ has property $P$, so must $Y$. But $Y$ does not have property $P$. Therefore, $X$ and $Y$ are not isomorphic.

$\endgroup$
  • 11
    $\begingroup$ +1. Note to OP that this is extremely common in many different areas of math, and often the step where one verifies that "property $P$ is preserved under isomorphism" is omitted from proofs (even when it's not obvious!) $\endgroup$ – hunter Jul 22 '15 at 8:56
  • $\begingroup$ @hunter: I don't completely agree. See also my answer. $\endgroup$ – Martin Brandenburg Jul 22 '15 at 9:03
  • $\begingroup$ @MartinBrandenburg "I don't completely agree" doesn't seem to add any useful information: Can you explain what you disagree with, and why, instead of just stating there is something you disagree with? Is this approach not common in different areas of math? Is that phrase not often omitted from proofs? $\endgroup$ – Yakk Jul 22 '15 at 14:03
  • 2
    $\begingroup$ I don't agree that this is a bunch of isolated phenomena in different areas of math with usually omitted proofs. As I've explained in my answer, this is a single phenomen and you can prove it in general. And in my opinion this is absolutely obvious. Or can you state an example where it's not obvious? $\endgroup$ – Martin Brandenburg Jul 22 '15 at 14:54
8
$\begingroup$

I think contrapositive is nicer than contradiction.

\begin{align*}[\text{isomorphism}] &\implies [\text{some property}],\text{ so}\\ [\text{lack of that property}] &\implies [\text{no isomorphisms}].\end{align*}

I personally had trouble separating the two: I would mistakenly think I had argued by contradiction, when in fact it was a contrapositive argument. Or, worse still, I would sully a nice contrapositive argument so it became a convoluted argument by contradiction.

So, rather than argue $$[\text{isomorphism}] \implies \text{contradiction},$$

it's mathematically 'cleaner' (less confusing, more fulfilling) in my opinion to use a property preserved by isomorphism in a contrapositive argument.


To elaborate, some proofs by contradiction are not ideal because they're unnecessarily bloated, as they already contain enough logic for a free-standing proof of the contrapositive. This is what I didn't realize for several years.

For example, examine a possible contradiction argument. You begin by assuming that the objects are isomorphic, hence at least one isomorphism exists and you pick one. This isomorphism must preserve certain properties. But you notice that a certain preserved-by-isomorphisms property holds for only one of the two objects! This clearly contradicts the existence of your chosen isomorphism, hence no isomorphisms exist, hence the two are not isomorphic.

That which was to be demonstrated has been beaten like a dead horse, because we observed that

  • Any isomorphism preserve certain properties

  • One such property is not shared by both objects.

These two observations alone are enough for a contrapositive argument; it didn't need to be wrapped in a proof by contradiction.

$\endgroup$
  • 3
    $\begingroup$ +1: And if you did want to seek a contradiction, you could show that $$\text{[isomorphism]}\implies\text{[property]}$$ and that $$\text{[property]}\implies\text{[contradiction]},$$ so that, indeed, $$\text{[isomorphism]}\implies\text{[contradiction]}.$$ For example, we suppose that $f:\Bbb N\to\Bbb Z$ is an order isomorphism. Thus, $f(0)$ is the least element of $\Bbb Z.$ But $f(0)-1$ is then not less than $f(0),$ whence $0\le-1,$ which is absurd. $\endgroup$ – Cameron Buie Jul 22 '15 at 17:18
  • 1
    $\begingroup$ Thank you, @CameronBuie, we're thinking the same thing! I realized, after answering, that my main point is that many contradiction arguments already contain enough for a free-standing argument by the contrapositive, but include extra logical features that aren't necessary. This is what I failed to notice and utilize for several years. $\endgroup$ – pjs36 Jul 22 '15 at 17:40
6
$\begingroup$

This is because isomorphic structures are elementary equivalent (in fact, every isomorphism is an elementary embedding). Notice that the converse is not true. For example, there are many orders which are elementary equivalent, but not isomorphic, to $(\mathbb{N},<)$.

Another important method to prove the non-existence of an isomorphism is the usage of functors in the sense of category theory. It is a general fact that functors preserve isomorphic objects. This is especially useful in algebraic topology, where one uses several functors $\mathsf{Top} \to \mathsf{Ab}$ (and similar) in order to distinguish topological spaces.

$\endgroup$
  • 6
    $\begingroup$ I don't think this quite captures the idea. The non-existence of isomorphisms can be witnessed by properties which aren't necessarily first order expressible. E.g., OPs wellordered example serves to show that there is no isomorphism between two structures, but isn't expressible in a first order way in the language of orders. $\endgroup$ – Miha Habič Jul 22 '15 at 9:30
  • 1
    $\begingroup$ Of course there is also the notion of elementary equivalence in higher order languages, and isomorphisms are elementary equivalences. $\endgroup$ – Martin Brandenburg Jul 22 '15 at 10:24
  • 3
    $\begingroup$ Although I like the spirit behind this answer, i.e. formalizing the notion of structure and property, I don't think this quite captures it. For example, the sphere and the torus are not homeomorphic because one is simply connected and the other is not, but I'm not aware of any way to formalize this argument using any kind of elementary equivalence. $\endgroup$ – Jim Belk Jul 22 '15 at 17:27
  • $\begingroup$ @JimBelk: I've added a paragraph about this. $\endgroup$ – Martin Brandenburg Jul 22 '15 at 18:49

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.