Timeline for Is non-connectedness of graphs first order axiomatizable?
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2010 at 13:07 | comment | added | Stefan Geschke | Andras, I am not sure I understand your question. You mean, can one axiomatize by infinitely many first order statements every property of $\omega$-categorical graphs or more general structures (where a structure is $\omega$-categorical if its theory is)? I don't think so. This is because an $\omega$-categorical theory might not be finitely axiomatizable. However, the answer is yes for all properties of countably infinite structures over a given (finite) vocabulary that have a finitely axiomatizable theory that is $\omega$-categorical. Is this understandable? | |
| Aug 30, 2010 at 20:53 | comment | added | András Salamon | Stefan, you are right: my comment above is tangential. Thanks for suggesting a canonical construction of a countable axiomatization for any property of finite structures. Could this be made to work for $\omega$-categorical structures also? Poizat, Marker and (shorter) Hodges don't obviously cover this. | |
| Aug 30, 2010 at 17:03 | comment | added | Stefan Geschke | @AS: I believe that you are talking about properties that can be described by a single first order axiom. My question was about an infinite set of axioms. Every property of finite graphs can be axiomatized by infinitely many axioms. Why? Every property is described by countably many forbidden finite graphs. For each forbidden finite graph, there is a sentence that says that the graph under consideration is not isomorphic to that forbidden graph. The collection of all these sentences axiomatizes the property over finite graphs. | |
| Aug 30, 2010 at 10:06 | comment | added | András Salamon | This is a nice argument! It is also true, by reduction from the property over linear orders "the cardinality of the universe is even", that neither connectedness nor disconnectedness is FO-definable over finite graphs. See Section 3.6 of Libkin's Elements of Finite Model Theory. | |
| Aug 29, 2010 at 17:23 | vote | accept | Stefan Geschke | ||
| Aug 29, 2010 at 17:18 | vote | accept | Stefan Geschke | ||
| Aug 29, 2010 at 17:18 | |||||
| Aug 29, 2010 at 17:17 | comment | added | Stefan Geschke | Thanks Joel. I have no idea why I didn't think of categoricity in the uncountable. | |
| Aug 29, 2010 at 16:41 | comment | added | Pete L. Clark | +1: if you had given this argument in July, I probably would have mentioned it in my (half)-course on introductory model theory and its applications. | |
| Aug 29, 2010 at 13:21 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
order -- degree
|
| Aug 29, 2010 at 13:11 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 11 characters in body
|
| Aug 29, 2010 at 13:04 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |