incidence geometry

Incidence geometry is essentially geometry based on the first postulate in Euclid’s The Elements. Basically, the first postulate states that we can draw a straight line from one point to another point. At the end of the 19th century, David Hilbert extended and axiomatized this postulate by adding several companion “incidence axioms” in his famous “Grundlagen der Geometrie” (). Since Hilbert’s publication, his axioms of incidence have been characterized by alternative but equivalent (http://planetmath.org/Equivalent3) versions, as well as generalized as to include areas of interests from other branches of mathematics, especially, in combinatorics. In this entry, we will define incidence geometry using abstract notions of sets, functions, and relations (specifically, an incidence relation) and then briefly discuss how this definition is related to the axioms of incidence that we know from high school and college.

Definition. Let $P$ be a set and $n$ a positive integer. An incidence geometry on $P$ consists of

• an onto function $t:P\to \{0,1,\mathrm{\dots },n\}$ called a type function. If we define $P_i:=t^{-1}(i)$, then $P$ can be partitioned into a finite number of subsets:

  $$P=P_0\cup \mathrm{\cdots }\cup P_n,\text{ with }{P}_i\cap P_j=\mathrm{\varnothing }\text{ for }i\ne j.$$

  Elements of $P_i$ are variously known as blocks or varieties of type $i$. Sometimes, they are also called flats of dimension $i$. For this discussion, we will use the latter terminology. Flats of specific dimensions have further conditions:

  1. $P_0\ne \mathrm{\varnothing }$. Flats of dimension 0 are called points.

  2. $P_n\ne \mathrm{\varnothing }$ and consists of one element $S$, called the space.

• a reflexive (http://planetmath.org/Reflexive) and symmetric relation $I\subseteq P\times P$ on $P$, called an incidence relation, with the following conditions (or axioms):

  1. for any $a,b$ such that $(a,b)\in I$ and $t(a)=t(b)$, then $a=b$;

  2. suppose $t(a)\le t(b)\le t(c)$ with $(a,b)\in I$ and $(b,c)\in I$, then $(a,c)\in I$;

  3. given that , there is a point $p$ such that $(p,a)\notin I$;

  4. given and a point $p$ with $(p,a)\notin I$, there is a unique $b$ with $t(b)=t(a)+1$, such that $(a,b)\in I$ and $(p,b)\in I$; furthermore, if, in addition, there is a $c$ such that $(p,c)\in I$ and $(a,c)\in I$, then $(b,c)\in I$ as well;

  5. given that $t(a)>0$, there is a pair of a point $p$ and a flat $b$, with $t(b)=t(a)-1$ and $(p,b)\notin I$, such that $(b,a)\in I$ and $(p,a)\in I$;

  6. given that , a point $p$ with $(p,a),(p,b)\in I$, and a flat $d$ with $t(d)=i+1$, $(a,d),(b,d)\in I$, then there is a $c$ with $t(c)=i-1$ such that $(a,c),(b,c)\in I$.

An incidence geometry is often written as a triple $(P,n,I)$.

Remarks.

• Flats of dimensions 1 and 2 are commonly called lines and planes, respectively. Flats of dimension $n-1$ are called hyperplanes.

• When $(a,b)\in I$, we say that $a$ is incident with $b$. Since $I$ is symmetric, we also say that $a$ and $b$ are incident without any ambiguity. Furthermore, if $a$ and $b$ are incident with $t(a)\le t(b)$, then we say that $a$ lies on $b$, or $b$ passes through $a$.

• Condition 2 is known as the “weak” , or the “transversality” of $I$. Basically, $(a,b)\in I$ and $(b,c)\in I$ imply $(a,c)\in I$ whenever the dimensions of $a,b$ and $c$ are in a non-decreasing order.

• From Conditions 4 and 5 above, given any flat $a$ of dimension $i>0$, there exist a point $p$ and a flat $b$ of dimension $i-1$ with the properties that

  1. $p$ is not incident with $b$,

  2. $a$ is incident with $p$, and

  3. $a$ is incident with $b$,

  then the unique flat of dimension $i$ mentioned in Condition 4 is $a$. We say that $a$ is generated by $p$ and $b$, or that $p$ and $b$ generate $a$, and we write $a=⟨p,b⟩$. When $b$ is a point, $a$ is often written as $\overleftrightarrow{pb}$. In addition, if we were to pick a different pair of a point $p^{\prime }$ and a flat $b^{\prime }$ of dimension $i-1$ satisfying the above three properties, then $a=⟨p^{\prime },b^{\prime }⟩$ as well.

• From the second part of Condition 4, $⟨p,b⟩$ is, in a sense, the smallest block (in terms of its type number), such that the above three properties hold. In other words, for any block $a$ with $(p,a)\in I$ and $(b,a)\in I$, then $(⟨p,b⟩,a)\in I$. It is easy to see that $t(a)\ge t(⟨p,b⟩)$. For otherwise, , which means $t(a)\le t(b)$. This inequality together with $(p,a)\in I$ and $(a,b)$ imply that $(p,b)\in I$, a contradiction.

• In Condition 6, if $a\ne b$, then $c$ is necessarily incident with $p$. Otherwise, $a=⟨p,c⟩=b$. Also, without much trouble, one can show that $d$ in the condition must be unique.

• $P_i\ne \mathrm{\varnothing }$ for all $0\le i\le n$. In other words, there exists at least one flat of every dimension. To see this, we first observe that $P_0\ne \mathrm{\varnothing }$, there is at least one point $p$. With $p$, there is a point $q$ such that $(p,q)\notin I$. Therefore, there is a (unique) line $\mathrm{\ell }$ that is incident with both $p$ and $q$. Continue this way until we reach $i=n$.

• Any flat of dimension $i$ is incident with at least $i+1$ points.

• Every flat is incident with at least one flat of every dimension. As a result, the space $S$ is incident with every flat of every dimension.

Shadow. For any $a\in P$, define $I(a)=\{b\in P\mid (a,b)\in I\}$, $I^{-}(a)=\{b\in I(a)\mid t(b)\le t(a)\}$, and $I^{+}(a)=\{b\in I(a)\mid t(b)\ge t(a)\}$. For specific type $k$, we also define $I_k(a)=\{b\mid t(b)=k\text{ and }(b,a)\in I\}$. When $k=0$, $I_0(a)$, the set of all points incident with $a$, is referred to as the shadow of $a$. We have that $I_0(a)\subseteq I^{-}(a)\subseteq I(a)$. We also have $I^{-}(a)\cap I^{+}(a)=I_{t(a)}(a)=\{a\}$.

Remark. It is possible to show that $(a,b)\in I$ if and only if $I_0(a)\subseteq I_0(b)$ or $I_0(b)\subseteq I_0(a)$. Furthermore, if $I_0(a)\subseteq I_0(b)$, then $t(a)\le t(b)$. In particular, $a=b$ if and only if $I_0(a)=I_0(b)$. From the last remark above, $I(S)=P$, and in particular $P_k=I_k(S)\subset I(S)$. We also have for any flat $a$, $I_0(a)\subseteq I_0(S)$. This says that every singleton subset of $I_0(S)$ is of the form $I_0(p)$ for some $p$. The discussion so far suggests the following simpler, more intuitive, formulation of incidence geometry:

Let $A$ be a set. An incidence geometry on $A$ is a subset $P$ of the power set of $A$ such that $P$ can be partitioned into $n+1$ finite subsets $P_0,\mathrm{\dots },P_n$ with the following axioms:

1. $P_0$ consists of all singleton subsets of $A$ and $P_0$ is non-empty; elements of $P_0$ are called points of $A$. Since there is an obvious one-to-one correspondence between $A$ and $P_0$, we shall follow by convention and call elements of $A$ points of $A$ instead;

2. $P_n=\{A\}$; $A$ is called the space;

3. for every element $a$ of $P_i$, where , there is a point $p$ such that $p\notin a$;

4. for every $a\in P_i$, where , and point $p$ such that $p\notin A$, there is a unique $b\in P_{i+1}$ such that $a\subset b$ and $p\in b$; furthermore, if there is a $c$ with $a\subset c$ and $p\in c$, then $b\subseteq c$;

5. for every $a\in P_i$, where $i>0$, then there is a point $p$ and a $b\in P_{i-1}$ with $p\notin b$, such that $p\in a$ and $b\subset a$;

6. if $a,b\in P_i$ and $d\in P_{i+1}$, where , with a point $p$ such that $p\in a\subset d$ and $p\in b\subset d$, then there is a $c\in P_{i-1}$ such that $c\subset a$ and $c\subset b$.

If we define $I$ on $P$ to be $(a,b)\in I$ if and only if there is a symmetrized inclusion relation between $a$ and $b$ ($a\subseteq b$ or $b\subseteq a$), it is not hard to verify that $I$ is an incidence relation on $P$.

Remarks. Elements of $P_1$ are called lines of $A$ and elements of $P_2$ are called planes of $A$. Whenever $a,b\in P$ such that $a\subset b$, then we say that $a$ lies on $b$ or $b$ passes through $a$. Two special types of incidence geometries are worth mentioning:

• If $n=2$, an incidence geometry on $A$ is called a plane incidence geometry. In a plane incidence geometry, Axioms 1 through 3, 5 and first part of 4 are necessary. Axiom 2 says that the space is the unique plane of $A$. Axiom 3 enumerates elements of $P$. Axiom 4 is the heart of the incidence geometry; it says that two distinct points lie on a unique line. Furthermore, Axiom 4, together with Axiom 3, say that any line is a subset of the plane. Second part of Axiom 4 is redundant in a plane incidence geometry. If any element of $P$ that passes through two distinct points must be either a line or the plane. If it is a line, it must be the unique line determined by the two points, or the plane, which, clearly includes the unique line. Axiom 5 says that there is only to create lines (and the plane), namely, via Axiom 4. Axiom 6 is trivial too (let $c=p$).

• If $n=3$, an incidence geometry on $A$ is called a solid incidence geometry. Axioms 1 through 3, 5, and the first part of Axiom 4 here play the same role as they do in a plane incidence geometry. First part of Axiom 4 also says that a line and a point not lying on it determine a unique plane. The second part of Axiom 4 and Axiom 6 play an equally important role as the other Axioms. Without the second part of Axiom 4, we would not be able to show, for example, that given a plane $\pi$ and a point $p$ lying on $\pi$, there is a line $\mathrm{\ell }$ lying on $\pi$ but not passing through $p$. Axiom 6 is decidedly non-trivial in solid incidence geometry. It basically says that two planes passing through a common point must pass through a line. Without it, it is possible to find an example such that two planes “intersect” at exactly one point.

• Several familiar concepts concerning particular incidence properties of flat can be defined: points are collinear if they lie on the same line; points and lines are coplanar if they lie on the same plane; a pencil is a collection of flats of the same dimension sharing a common incidence property which, in most cases, states they have the same “intersection”.

Speaking of intersections, it would be proper to formally define what it means for two hyperplanes to “intersect”.

Intersection. Let $a,b\in P$. An intersection of $a$ and $b$ is a flat $c$, if it exists, such that $I_0(c)=I_0(a)\cap I_0(b)$.

Immediately, we see that, if an intersection of $a$ and $b$ exists, it must be unique. For if $I_0(c)=I_0(a)\cap I_0(b)=I_0(d)$, then $c=d$. We shall abuse the use of set-theoretic intersection to mean incidental intersection: if $a$ and $b$ are two flats, then $a\cap b$ denotes their intersection. Furthermore, if no intersection exists, we write $a\cap b=\mathrm{\varnothing }$.

Remarks.

• It is easy to show that if $a$ and $b$ be flats with $i=t(a)\le t(b)$ and $a\cap b=d\ne \mathrm{\varnothing }$, then $(d,a)\in I$ and $(d,b)\in I$. In addition, if $(a,b)\in I$, then $a=d$. Also, the unique $c$ in Condition 6 above is the intersection or $a$ and $b$.

• In light of the introduction of the concept of the intersection (of two flats), it seems feasible to toss in an additional element, called the empty block or empty flat, $\mathrm{\varnothing }$, into the underlying set $P$ of the incidence geometry: $P_{-1}:=\{\mathrm{\varnothing }\}$ and $P^{\prime }=P_{-1}\cup P$. If we next define a binary relation $I^{\prime }$ on $P^{\prime }$ to be:

  $$(a,b)\in I^{\prime }\text{ if }\{\begin{array}{cc}(a,b)\in I,\hfill & \\ a=\mathrm{\varnothing }\text{, or}\hfill & \\ b=\mathrm{\varnothing }.\hfill & \end{array}$$

  then $I^{\prime }$ becomes an incidence relation on $P^{\prime }$ if we restrict flat $a$ in Condition 3 to be non-empty only. Furthermore, $P^{\prime }$, together with $I^{\prime }$ have almost all the ingredients of being an incidence geometry, except that the range of the type function has now been extended to include $-1$.

• For every pair of non-empty $a,b\in P^{\prime }$, $U=I^{+}(a)\cap I^{+}(b)$ is a non-empty set since the space $S$ is in it. In addition, since $n$ is finite, $U$ has a minimal element $c$ if we order its elements by their corresponding type numbers. Moreover, $c$ is unique. We denote this $c$ by $⟨a,b⟩$. This definition is consistent with our earlier definition of $⟨\cdot ,\cdot ⟩$ when the first coordinate is a point and the second coordinate is a flat not passing through the point.

• Collecting all the data above, it is now easy to see that $P^{\prime }$, together with the intersection operator $\cap$, and the angle bracket operator $⟨\cdot ,\cdot ⟩$ form a semimodular lattice, if we set $a\wedge b:=a\cap b$ and $a\vee b:=⟨a,b⟩$.

• parallelism. Let $a$ be a flat. A flat $b$ is said be parallel to $a$ if

  1. $t(b)=t(a)$,

  2. $a\cap b$ is either $a$ or $\mathrm{\varnothing }$.

  We write $a\parallel b$. Note that if $a\cap b=a$, then $a=b$, since $t(b)=t(a)$. So if $a$ is parallel to $b$, $b$ is parallel to $a$, and we may say that $a$ and $b$ are parallel. Parallelism is a reflexive and symmetric relation. However, it is not transitive (http://planetmath.org/Transitive3) (as in the case of a hyperbolic geometry). Condition 6 above can now be restated as: if two flats of dimensions $i$, both lying in a flat of dimension $i+1$, are not parallel, then their intersection is a flat of dimension $i-1$.

• An incidence geometry with the condition (or axiom) that every pair of (non-empty) flats of dimensions $>0$ have non-empty intersection is called a projective incidence geometry.

• An incidence geometry with the condition (or axiom) that for every (non-empty) flat $a$ of dimension $i$ with , and any point $p$ not lying on $a$, there is a flat $b$ passing through $p$, such that $a\parallel b$, is called an affine incidence geometry. The condition just stated is known as the Playfair’s Axiom.

Note to reader: the historical background of this entry is weak. Any additional historical information on this is welcome!

Title	incidence geometry
Canonical name	IncidenceGeometry
Date of creation	2013-03-22 15:26:13
Last modified on	2013-03-22 15:26:13
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	26
Author	CWoo (3771)
Entry type	Definition
Classification	msc 05B35
Classification	msc 06C10
Classification	msc 51A05
Synonym	lies on
Synonym	lying on
Synonym	passes through
Synonym	passing through
Related topic	SemimodularLattice
Defines	incident
Defines	incidence relation
Defines	type function
Defines	plane incidence geometry
Defines	solid incidence geometry
Defines	incidence axiom
Defines	shadow
Defines	pass through
Defines	lie on
Defines	line
Defines	plane
Defines	projective incidence geometry
Defines	affine incidence geometry
Defines	Playfair’s axiom
Defines	coplanar