Limitation xample The property of being strongly-connected is not a first-order property of directed graphs Assume that sentence psc represents the property of being strongly-connected. Define sentences psL, IN and out as follows LetΦs=(x)(-E(x,x) eLetΦour=(x)(y)(z)(E(x,y)∧E(x,2)→y=2) eLetΦN=(x)(vy)(z)(E(y,x)AE(z,x)→y=2)Limitation . Example . . The property of being strongly-connected is not a first-order property of directed graphs. . Proof. . . Assume that sentence ΦSC represents the property of being strongly-connected. Define sentences ΦSL, ΦIN and Φout as follows. Let ΦSL = (∀x)(¬E(x, x)). Let ΦOUT = (∀x)(∀y)(∀z)(E(x, y) ∧ E(x, z) → y = z). Let ΦIN = (∀x)(∀y)(∀z)(E(y, x) ∧ E(z, x) → y = z). Yi Li (Fudan University) Discrete Mathematics June 9, 2013 12 / 15