0
$\begingroup$

Imagine I have 10 students in an elementary school. I believe it is proper to say the following: The students' age induces a total order on the students (assuming no 2 students have the exact same age). However, suppose I consider a discrete category like the grade of the student, and further suppose that at least 2 of the students are in the same grade. I would like to say something like the following: the students' grades induce a total order on the students. However, students who are in the same grade map to the same value. Thus, if I consider the set into which the students are mapped, it is smaller than the set of students. Can I still say that the students' grade induces a total order on the students? I believe that a more precise statement would be, there are multiple total orders on the students consistent with their assignment to grades. For example if Alice, Bob, and Charlie are in 2nd, 3rd, and 3rd grades respectively, then their ordering is consistent with the total orders a<=b<=c and also a<=c<=b. However, this is cumbersome, and I'm looking for a more compact way to say it.

To summarize, I would like to say that a non-injective mapping induces a total order on a set, but I'm not sure that is valid terminology. Thanks for any help.

$\endgroup$
1
  • 1
    $\begingroup$ I think you might be interested in the concept of Preorder $\endgroup$
    – amrsa
    Commented Jun 24 at 13:32

1 Answer 1

Reset to default
2
$\begingroup$

A function $f : A \to B$, when $B$ is equipped with the structure of a total preorder $- \leq -$, induces a "pulled back" total preorder on $A$ given by $f(-) \leq f(-)$. If in addition $f$ is injective and $\leq$ is antisymmetric (hence $B$ is a total order), then the induced total preorder on $A$ is also antisymmetric (hence a total order).

$\endgroup$
12
  • $\begingroup$ Why would $f$ need to be injective to induce a total order? $\endgroup$
    – user3716267
    Commented Jun 24 at 13:51
  • 1
    $\begingroup$ @user3716267 I've rephrased. The point is that injectivity guarantees that the order is antisymmetric. $\endgroup$
    – Naïm Favier
    Commented Jun 24 at 13:53
  • $\begingroup$ Oh god; i've found myself in a rabbithole re: terminology and realize there are unfortunately many meanings of the word "total" in this case; I learned in a context where we strictly called those "linear orders" and reserved total for another meaning. I hate nomenclature. Thanks for the edit. $\endgroup$
    – user3716267
    Commented Jun 24 at 14:03
  • $\begingroup$ @user3716267 Now I'm curious: what is the other meaning of "total" you know of? $\endgroup$
    – Naïm Favier
    Commented Jun 24 at 14:11
  • $\begingroup$ The other meaning is simply "not partial." $\endgroup$
    – user3716267
    Commented Jun 24 at 14:15

You must log in to answer this question.

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