TRWBW | ihope: the only non-math thing about computer science is that it's mostly elementary math instead of deep math, but hell, it's 40 years old. how deep was geometry 40 years after the first guy drew a triangle? |

klafka | isn't computer science just a part of discrete math really? |

ihope | That's what I'd say, yes. |

Dacicus | What's discrete math cover? |

LoganCapaldo | I'd say it depends how you squint at it |

ihope | Also, I might have discovered a big mathy paradox. But I probably didn't. |

Dacicus | yay, paradox |

ihope | Big mathy question #1: is there a sequence of ordinal numbers that exceeds all of them? |

TRWBW | ihope: maybe you mean http://en.wikipedia.org/wiki/Burali-Forti_paradox |

ihope | ...Indeed there isn't. |

TRWBW | Dacicus: traditionally discrete math was a grab bag course of a bit of combinatorics, number theory, lattice theory, graph theory, and set theory. i don't think it was ever considered a "field" |

klafka | things dealing in discrete numbers? |

TRWBW | it was a halfway course between the calculus non-math people took and the things like number theory and abstract algebra that math majors took |

klafka | yeah |

ihope | Well, anyway, the paradox goes as follows: let's define A_n = the smallest ordinal number that is not a recursive ordinal, except using a class-n machine instead of a Turing machine, where a class-n machine is a Turing-machine plus the ability to solve the halting problem for all class-m machines where m < n. Then the iffy and probably incorrect part: A_n is always countable, but A_n > A_m if n > m. Therefore, the ordinal numbers can be mapped one-to-one with the countable ordinal numbers. |

TRWBW | ihope: i got no idea what you are saying, but i got a neat proof of the incomputability of the halting problem |

ihope | "A_n is always countable, but A_n > A_m if n > m" would be the part that's probably wrong. TRWBW: diagonalization is fun, aye? |

TRWBW | ihope: it's a different proof than that or the standard one ihope: and as far as i know, it's my own |

ihope | Sounds interesting. |

TRWBW | ihope: the inspiration is to connect proofs of the halting problem to classical paradoxes ihope: diagonalization proof goes to russels paradox ihope: the standard proof goes to the paradox of "this statement is false" ihope: my proof is based on the paradox "x is the smallest number that requires more than 100 characters to describe" |

Dacicus | TRWBW: You said, "traditionally." What does discrete math cover now? |

TRWBW | so basically, you ask for the smallest number that requires a turing machine of length greater than n to generate it. but if you have a turing machine that solves the halting problem, you can construct a machine of size m+log(n) (or smaller) that computes the number that needs a turing machine of size n to compute it. Dacicus: no idea. maybe the same thing, maybe something else, i haven't actually looked at the syllabus of a discrete math course in more than 20 years |

ihope | TRWBW: ah. Sounds fun :-) |

TRWBW | i told it to Gregory Chaitan in the mid 80's and he thought he hadn't heard it before, so i felt clever. |

LoganCapaldo | as o 2 or so years ago it covered the same stuff (Discrete math) at least where I go oh and logic was in the grab bag too |

ihope | So is the order type of a non-degenerate real interval [a,b] the same no matter what a and b are? |

TRWBW | ihope: um, what's an order type? and what's a degenerate interval? ihope: i'm pretty fuzzy on the abstract stuff |

ihope | An order type is essentially the order they're in, rather than them themselves. |

TRWBW | ihope: so an equivalence class under order isomorphism? |