0

Let $R$ be a binary relation. $R$ is said to be cycle-free iff there are no cycles in the relation, meaning, there are no $x_1, ... ,x_n$ such that $x_1 R x_2, ..., x_n R x_1$. Certainly, the class of cycle-free binary relations is axiomatizable by an infinite set of sentences. Is it also finitely axiomatizable?

user107952
  • 20,508
  • The answer is "no", because of a compactness argument. What have you tried? I can leave a slightly more detailed hint as an answer if you like, but I think this has been asked before. I'll try to find this as a duplicate. – HallaSurvivor Jul 17 '21 at 03:12
  • Of course not. If it had a finite axiomatization, then (by compactness) some finite subset of the infinite axiomatization you alluded to would be such an axiomatization. You see why that can't be? – bof Jul 17 '21 at 03:13
  • 1
    Also, note that for a given number $n$, a sufficiently long cygle graph is indistinguishable from the endless path graph by a Fraisse–Ehrenfeucht game of length $n$. – bof Jul 17 '21 at 03:18

0 Answers0