Timeline for first-order definability transitive closure operator
Current License: CC BY-SA 2.5
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 21, 2010 at 11:42 | comment | added | Carl Mummert | @Adam: just a note, MathWorld makes a bad reference for non-experts; you have to read it very skeptically in general. They have idiosyncratic definitions that don't match the general literature, and other strange things. Two examples from the article you linked. (1) Their definitions don't include (∀ x)(y=y) as a well formed formula. (2) Their use of the word "closest" is confusing at best, and I would say wrong. Consider (∀ x)( (∀ x)(x=x) → x=x) . | |
| Jun 21, 2010 at 11:18 | comment | added | Carl Mummert | Adam: it's fine to use TC(x) on a blackboard. It simply "hides" a quantifier that would otherwise appear. So Φ(z, TC(z)) is an abbreviation for (∀ x)(ISTC(x,z) → Φ(z, x)). This is sound as long as you have previously proved that every set has a transitive closure. There are many other examples of this kind of shorthand; all that it does is unwind the definitional extension that JDH mentions below. | |
| Jun 21, 2010 at 9:03 | answer | added | Philip Welch | timeline score: 6 | |
| Jan 21, 2010 at 18:47 | vote | accept | Adam | ||
| Jan 21, 2010 at 18:46 | vote | accept | Adam | ||
| Jan 21, 2010 at 18:46 | |||||
| Jan 20, 2010 at 11:45 | answer | added | Joel David Hamkins | timeline score: 15 | |
| Jan 20, 2010 at 5:37 | answer | added | Mike Shulman | timeline score: 5 | |
| Jan 20, 2010 at 5:24 | comment | added | François G. Dorais | There are no terms in set theory, it's a purely relational language. However, it is a well-known fact that if $\phi(x,y)$ defines the graph of a total function, then expanding the language with a function symbol $f$ defined by $\phi(x,f(x))$ is conservative. (That works for any theory, not just set theory.) | |
| Jan 20, 2010 at 5:17 | comment | added | Adam | Er, I meant $(\exists z)ISTC(z,y)\wedge x\in z$, but I think you know what I mean. | |
| Jan 20, 2010 at 5:16 | comment | added | Adam | I guess I'm just starting to wonder if it's illegitimate to write $x\in TC(y)$ on a blackboard, and that only $ISTC(x,y)$ (where "ISTC(x,y)" means "x is the unique transitive closure of y") is formally correct. I guess if that's really the case, and set theoreticians generally agree to hand-wave around it, that would answer my question. But I'd kinda like to hear somebody confirm that this is actually the convention among practicing set theorists. | |
| Jan 20, 2010 at 5:13 | comment | added | Adam | Dorais, yes, you can show that sequence exists, but can you write a "term" for it (a good formal definition of "term" can be found here: mathworld.wolfram.com/First-OrderLogic.html) | |
| Jan 20, 2010 at 5:11 | comment | added | Adam | Dorais, if you want to prove that the transitive closure exists, then yes, what you write is absolutely correct. But I seek to show that "TC(x)" is a legitimate syntactic abbreviation by expanding "TC(x)" into some (probably vastly longer) expression. Simply knowing that $\alpha$ exists does not help expand this abbreviation. | |
| Jan 20, 2010 at 5:11 | comment | added | François G. Dorais | There is an alternative route where you show using replacement that the sequence $\langle x,\bigcup x,\bigcup \bigcup x,\dots\rangle$ exists. The union of that sequence is the transitive closure of $x$. This avoids the powerset axiom, which is useful from time to time. | |
| Jan 20, 2010 at 5:10 | comment | added | Adam | I think the homework exercise is actually "prove that for any set x, TC(x) exists"; start from the textbook proof (from regularity) that $(\forall x\exists\alpha)x\in V\alpha$, show by transfinite induction that for every ordinal $\alpha$, the transitive closure of every member of $V_\alpha$ exists, exploiting the fact that each element of $V_{\alpha+1}$ is a subset $V_\alpha$; at limit stages the TC of the union is the union of the transitive closure. So, I can see how to define the "ISTC(x,y)" predicate meaning "x is the transitive closure of y"; that's not what has me confused. | |
| Jan 20, 2010 at 5:08 | comment | added | François G. Dorais | You don't have to say which $\alpha$. Any one will do, so you can put an existential quantifier in front of it (so long as you know there is one). | |
| Jan 20, 2010 at 5:01 | comment | added | Adam | "If you can prove that x is contained in a transitive set" -- yes, exactly! But the problem is that now you have to say which $\alpha$, so now you need a "function symbol" for rank. I feel like I'm banging my head up against some missing assumption that is built in to everyday set-theoretical discourse... | |
| Jan 20, 2010 at 4:34 | comment | added | François G. Dorais | If the class is definable, then the intersection with a set is a set by comprehension. If you can prove that $x$ is contained in a transitive set, then you don't need to talk about classes at all. You might do this by proving that $x \subseteq V_\alpha$ for some ordinal $\alpha$, for example. (By the way, this is a pretty standard homework exercise. You might want to reassure us that this is not the case.) | |
| Jan 20, 2010 at 3:11 | answer | added | Gerhard Paseman | timeline score: 0 | |
| Jan 20, 2010 at 2:49 | history | asked | Adam | CC BY-SA 2.5 |