3
$\begingroup$

I was asked to determine whether the following statement is true:

If every function $F : P \to P$ is a homomorphism from $(P, \leq)$ to $(P, \leq)$, with $\leq$ an arbitrary order, then $|P| = 1$.

It is straightforward to observe that $|P| \not> 1$. However, $|P| = 0$ seems to satisfy the first part of the predicate.

If $P = \emptyset$ there is one and only one function over $\emptyset^2$ that maps from the empty set to itself; namely, $\emptyset$. The definition of a homomorphism $F$ involves statements of the form: for all $x, y$ in $P$ occurs this and that involving $F$... So to refute that $F$ is a homomorphism one is to find a counter-example to these properties. Of course, such counter examples cannot be found in the empty set. So $\emptyset : \emptyset \to \emptyset$ is a homomorphism from $(\emptyset, \leq)$ to $(\emptyset, \leq)$.

The notation $\emptyset : \emptyset \to \emptyset$ is odd but seems formally correct, because $\emptyset$ is a function and it does have itself as domain and range. However, I'd incidentally like to know if this notation is correct indeed.

Now, my question is the following. Is $\emptyset : \emptyset \to \emptyset$ an isomorphism between $(\emptyset, \leq)$ and $(\emptyset, \leq)$? It seems to be the case that $\emptyset$ thus considered is not only a function, but that it is its own inverse ($\emptyset^{-1} = \emptyset$).

$\endgroup$
2
  • 2
    $\begingroup$ It is an isomorphism for a silly reason: $\emptyset$ is one-to-one and onto (both vacuously) and preserves an order (which will be empty, of course). $\endgroup$
    – Hanul Jeon
    Mar 4 at 23:08
  • 1
    $\begingroup$ If you are taking some sort of logic course including discussion of e.g. first-order logic, it's possible that in this course, models of a first-order theory are by definition always non-empty, and "$\le$ is an order on $P$" means "$(P, \le)$ is a model of the theory of partial/linear orders". If so, then the statement is true. I think pretty much any combination of "the statement was intended to be true/false, and it is true/false" is possible, depending on the definitions and whether whoever wrote the question was absent-mindedly thinking of a different definition or not :) $\endgroup$ Mar 5 at 3:18

2 Answers 2

6
$\begingroup$

As you surmise, the empty set, $\emptyset$, can be be viewed as a function $\emptyset \to \emptyset$ and it preserves the only possible ordering, $\le$, that you can put on its range $\emptyset$. So, yes, the statement in the title of your question is true, and the statement you that you have been asked to determine is false.

$\endgroup$
1
  • $\begingroup$ Thanks for answering my question. $\endgroup$
    – lafinur
    Mar 5 at 19:16
3
$\begingroup$

Note that $\mathrm{id}_{\varnothing}=\varnothing$; that is, the empty set is also the identity map from $\varnothing$ to $\varnothing$. Therefore, you have $\varnothing\circ\varnothing=\varnothing=\mathrm{id}_{\varnothing}$, so indeed you have that $\varnothing$ is an invertible function $\varnothing\to\varnothing$ with $\varnothing=\varnothing^{-1}$.

You can also verify that if we view $\varnothing$ as a function from $\varnothing$ to $\varnothing$ we must conclude that it is one-to-one and onto.

I expect that the statement you were given was expected to include a non-empty clause,

If $P\neq\varnothing$ and every function $F\colon P\to P$ is a homomorphism from $(P,\leq)$ to $(P,\leq)$, with $\leq$ an arbitrary order, then $|P|=1$.

(I'm not wild about "an arbitrary order" there either... poor phrasing, IMHO...) Unless your definition of partially ordered set requires non-emptyness...

It is not uncommon to see people forget to include a nonemptiness clause when they should. For example, it is typical to see the statement:

A function $f\colon X\to Y$ is one-to-one if and only if it has a left inverse.

but the statement is false if we do not assume $X\neq\varnothing$.

$\endgroup$
1
  • $\begingroup$ Thanks for the detailed answer. $\endgroup$
    – lafinur
    Mar 5 at 19:16

You must log in to answer this question.

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