Practice Question 1 (will be discussed next class)

Let be an asymmetric binary relation on a finite set X that does not have a

cycle, that is there is no finite sequence of elements x₁, x₂, ... , x_K, where K > 2,

such that x₁ x₂ ... x_K x₁.

Show (by induction on the size of X) that can be extended to a complete ordering (i.e., a complete, asymmetric, and transitive binary relation).