0

Consider a statement like: the graph G has an infinite path. I'm trying to translate that into predicate logic. I keep finding myself relying on the crutch of the ellipsis, e.g. expressing a path as $a_1, a_2 ... a_k$, but the ellipsis is not allowed in predicate logic. So how can the statement be expressed? More generally, the ellipsis is used a lot in informal mathematical writing, so what is the standard strategy for eliminating it in predicate logic?

  • 2
    I'm not sure you can. Such infinite properties lie on the border between first-order and second-order logic, on the second-order side. – Angina Seng Jul 08 '18 at 07:52
  • 1
    The existence of an infinite path in a graph is not expressible in first-order logic. Any first-order statement purporting to express it would be a consequence of the infinite set ${c_nEc_{n+1}:n\in\mathbb N}$ (where the $c_n$'s are new constant symbols and $E$ denotes the adjacency relation) but not a consequence of any finite subset. That would contradict the compactness theorem. – Andreas Blass Jul 08 '18 at 15:48
  • @AndreasBlass So it is impossible to prove a theorem like König's lemma from the ZF axioms using first-order logic? –  Jul 08 '18 at 22:39
  • 1
    Depending on the particular formulation of König's Lemma, it is provable in first order logic from ZF or from ZF+"countable choice". (There's a big difference between first-order expressibility in the universe of sets and first-order expressibility in some graph.) – Andreas Blass Jul 08 '18 at 23:53

0 Answers0