# Partitioning of geometric net into equivalence classes

Fellow Puny Humans,

A geometric net is a system of points and lines that obeys three axioms:

1. Each line is a set of points.
2. Distinct line has at most one point in common.
3. If $p$ is a point and $L$ is a line with $p \notin L$, then there is exactly one line $M$ such that $p \in M$ and $L \cap M = \phi$.

And whenever $L \cap M = \phi$ we say that $L$ is parallel to $M$ i.e $L || M$.

So far so good.

I want to partition these lines of geometric net into equivalence classes with two lines in same class if they are equal or parallel. One can easily show that binary operation equal or parallel is an equivalence relation.

Let's say there are $m$ such classes, then how many points does a line have in each class? For a given line $l$ in any class, if a point $p \in l$ then how many lines passes through $p$.

For example, if I partition them into two classes $CL_1$ and $CL_2$ of parallel or equal lines, then number of points on any line in $CL_1$ is equal to number of lines in $CL_2$. This implies that each point belongs to two line. Can this be extended to a case when number of classes are $m$ i.e. each point belong to $m$ lines? I am confused because I can not show it for the case when more than two lines passes through the same point.

This problem is from TAOCP 4(a) : combinatorial searching Problem 21. (Edision Wesly).

-

Let $C_1,\dots,C_m$ be your equivalence classes. Suppose first that there is a point $p$ that is in more than $m$ lines; then there is some class $C_i$ such that $p$ is in two distinct lines in $C_i$. But that’s impossible, since the lines in $C_i$ are mutually parallel, so every point is in at most $m$ lines.

Now suppose that some point $p$ is in fewer than $m$ lines; then there is some class $C_i$ such that no line in $C_i$ contains $p$. Let $L\in C_i$; $p\notin L$, so by axiom (3) there is a line $M$ such that $p\in M$ and $M\,||\,C_i$. But then $p\in M\in C_i$, contradicting the assumption that no line in $C_i$ contains $p$. Thus, each point is in at least $m$ lines.

Putting the two pieces together, we see that every point of the net belongs to exactly $m$ lines.

-

It is exactly the number of lines you have in a class, simply because equal or parallel is an equivalence relation. Let me clarify:

Say $C_1, C_2,\dots, C_m$ are your equivalence classes. Say $L\in C_i$ is a line in $C_i$, for some $i\in\{1,\dots,m\}$. Say $1\leq j \leq m$, $j\neq i$, and $M\in C_j$. If $L\cap M = \emptyset$, then $L$ is parallel to $M$, and so $L$ and $M$ must belong to the same class. In other words, $C_i\cap C_j\neq \emptyset$, or $C_i = C_j$ by equivalence. But by assumption, $i\neq j$, so $C_i\neq C_j$, and so $L$ must intersect $M$. By one of your axioms, it must intersect $M$ in only one point. By arbitrariness of $M$, $L$ must intersect every line in $C_j$ in only one point.

-