Set Theory and Algebra in CS: Introduction to Mathematical Modeling (2013) [pdf]

https://pdfs.semanticscholar.org/d106/6b6de601c1d7d5af25af3f7091bc7ad3ad51.pdf

by lainon • 8 years ago

317 50 8 years ago

pdfs.semanticscholar.org

mlevental3• 8 years ago

call me a mathematical hipster (new frameworks etc.) but i could never get into axiomatic set theory. algebra is already boring by virtue of being abstract but then make it even more abstract by dropping all models! at least in algebra you have applications like galois groups, lie algebras, crypto, etc. yes i know that complexity theory is basically in the domain of set theory (complexity hierarchy) but even that was so abstract. so does anyone know any really cool applications of this stuff (just to be clear i don't mean technology i mean concrete theorems).

LeanderK• 8 years ago

Tbh: I didn't read the document, only the table of contents.

I think one of the problems of set-theory and applictions is that it doesn't lend itself very well to computers. An immediate thought was software verification & theorem proving, but while it's used in modelling (for example Peano Numbers), the underlying theories should (all?) be type-theories.

But that's something i am definitly not an expert in. Maybe someone with real knowledge can help answer this!

Of course everybody interested in math & it's applications should know really basics set-stuff. But I think, while foundational, set theory is just not that important to be super proficient in! You could write all the required stuff on a single sheet of paper.

auggierose4• 8 years ago

The main reason why type theory is used for mechanized theorem proving is that developments in that area are mainly driven by computer scientists, not mathematicians. And computer scientists like their formal objects to look like programs.

throwawaymath7• 8 years ago

I think one of the problems of set-theory and applications is that it doesn't lend itself very well to computers.

I might be misunderstanding what you mean here, but I'm confused by this statement. Set theory is used very often in computer science. Relational databases are essentially applied set theory.

auggierose4• 8 years ago

The stuff in that document is all very fundamental and basic, and doesn't seem that abstract at all to me. If you want to do mechanical theorem proving, you should be(come) familiar with that stuff. Personally I like set theory as a basis, because it is so simple and intuitiv.

Obviously, professional set theorists go way beyond what is described in this document, but to be honest, none of that more advanced stuff seems very useful to me in practical applications in technology.

paintstudio• 8 years ago

The stuff in that document is all very fundamental and basic, and doesn't seem that abstract at all to me.

I wondered the same thing. The first half of the linked paper is usually contained (if abridged) in the intro chapter of more or less any algebra/topology/analysis textbook. I don't remember Rudin's first book being an exception. Most of that material can be found in the first chapter of Rudin's "Principles" (3rd edition).

I'd say the basic topology in R^n is much more abstract (the 2nd chapter of Rudin "Principles" [3rd ed]) and it's not treated in the linked doc.

throwaway080383• 8 years ago

Looking at the table of contents, it looks like the first half is really foundations of abstract algebra, like you really caant rigorously talk about it or analysis or anything else without this stuff.

throwawaymath7• 8 years ago

The first half of (section one) doesn't comprise the foundations of abstract algebra in particular so much as the foundations of modern mathematics in general. The foundation of modern abstract algebra is more about axiomatic properties of structures like groups, rings, modules, fields, vector spaces, etc.

For that matter you actually don't need a lot of this machinery to derive analysis; for that all you need is a minimal subset (hah!) of set theory. Analysis focuses on the properties of continuous things, like real and complex sequences. You can derive the real and complex numbers axiomatically (like with Dedekind cuts of rationals) or synthetically (field axioms) as long as you have the definitions of sets, subsets, bounds, unions and intersections. I'm not even sure you need to care about the distinction between a subset and a proper subset.

That's not to say the material presented here isn't useful - it is. I'm just making the point that most analysis doesn't require abstract algebra aside from fields and (later on) vector spaces, and you don't need a whole lot to get there.

jacobolus3• 8 years ago

Set theory exists because something was needed to put analysis on a foundation that mathematicians were satisfied with (of course, some didn’t feel a pressing need for it, and some are still unsatisfied with the foundation), especially after Fourier threw a wrench into ideas about the possible definitions of a “function”.

So the “application” for set theory you want is point-set topology, and the “application” for point-set topology is analysis, or further down the road all sorts of modeling used in physics and engineering and so on.

Here’s a bit of a history lesson by Rudin, https://youtu.be/hBcWRZMP6xs

If you want to get a sense of the historical fights involved based on an analogy, see Lakatos’s Proofs and Refutations https://math.berkeley.edu/~kpmann/Lakatos.pdf

mlevental3• 8 years ago

i'm very familiar with all of this (i cut my teeth on baby rudin and i have dipped into papa rudin over the years). what i'm interested in is not the value (i understand the value of set theory like i understand the value of ZFC and Peano) but the "beauty". note i "know" point-set topology (at the level of munkres) and even a little cohomology so i'm looking for something a little more sophisticated than just hausdorff spaces or something like that.

edit: but that is a nice paper you linked to. thank you.

anonlastname• 8 years ago

The validity of ZFC is still an open discussion.

My favorite critic of ZFC is Norman Wildberger, who has a great YouTube channel. I found his formulations of complex multiplication, the pythagorean theorem and quadratic forms were particularly worthwhile, even though he comes off as barely computer literate in other videos.

reikonomusha• 8 years ago

The “validity” of ZFC is not in question.

antidesitter5• 8 years ago

Which criticisms of ZFC are you referring to?

gshulegaard• 8 years ago

I am not sure if this is what you are looking for, but the Relational Model is built on a mathematical foundation of Set Theory[1] and first order predicate calculus[2]. This foundation is used to define a logically closed algebra known as Relational Algebra[3]. The implications of this closed logical foundation is, in my opinion, the real power of the Relational Model and is in no small part why RDBMS's exploded in popularity.

In the context of a RDBMS, SQL is a domain language for expressing the underlying Relational Algebra:

https://cs.ulb.ac.be/public/_media/teaching/infoh417/sql2alg...

[1] https://en.wikipedia.org/wiki/Relational_model

[2] https://en.wikipedia.org/wiki/First-order_logic

[3] https://en.wikipedia.org/wiki/Relational_algebra

pron• 8 years ago

Formal systems (like formal axiomatic set theory) are more in the domain of logic than mathematics (although there are things like model theory that lie at the intersection of the two). From their very early conception, they were designed to serve two roles: 1. Serve as completely precise languages, where no ambiguity is possible, and 2. allow for mechanical reasoning. As role 1 is often in service of role 2, I think it's fair to generalize and say that the role of formal systems is mechanical reasoning.

If mechanical reasoning is not something that interests you, you have little use for these pedantic systems. Mechanical reasoning has two current uses: 1. mechanical verification of mathematical proofs and assistance in such proofs -- this application is very rarely used in practice, and is commonly the domain of a few enthusiasts who hold high hopes for improvements that would make it more mainstream. 2. Mechanical verification of software, including static analysis, model checkers, type systems and other software-relevant proof systems.

antidesitter5• 8 years ago

Axiomatic set theory isn't just for "pedantry" and mechanical reasoning, though that's an important application. It's also like a telescope array that allows us to see ever further into Cantor's paradise and the universe (multiverse?) of mathematics. The upper levels of transfinite set theory are especially breathtaking and somewhat scary [1]. Hugh Woodin spoke a little bit about this in a presentation on the Ultimate L conjecture:

"There's the other possibility: set theory is completely irrelevant to physics... That's almost more interesting because if this conjecture is true, we've argued there's truth here for set theory, and it's a truth that's not about the physical universe. To me that's almost more remarkable, that there could be some conception of truth that transcends truth that we see around us."

The presentation is called The Continuum Hypothesis and the search for Mathematical Infinity [2].

[1] http://cantorsattic.info/Cantor's_Attic

[2] https://www.youtube.com/watch?v=nVF4N1Ix5WI.

fnrslvr4• 8 years ago

Formal systems aren't just about mechanizing mathematical work to make it a subject of software engineering. (Though this is a useful and probably underdeveloped outcome.) They also turn mathematical work itself into mathematical objects which one can reason about, which opens the door to metamathematics, i.e. the ability to reason mathematically about aspects of mathematics itself.

fox404• 8 years ago

Applications of set theory: all math.

But no, seriously, it depends on what kind of set theory you're talking about. The stuff Hilbert was arguing about up to the stuff still being argued about today in the ivory tower? No, you pragmatically do not need to know that unless you're pursuing a research career in pure math. The stuff in an undergrad probability course? Yeah, sets come up basically everywhere if you're looking and are willing to think like that.

throwawaymath7• 8 years ago

Even if you're researching pure mathematics you probably don't need rigorous, axiomatic set theory. Number theorists, algebraic geometers, probability/measure/ergodic theorists, etc all can conduct their work with just naive set theory.

lapinot4• 8 years ago

Set theory basically is the same thing as type theory, these are two schools of formal languages designed to define logics (something which is even more true for this book that seems introductory). I don't really like set theory (imho it's a pain to use rigorously formally) but type theory is cool. If you've already used typed languages in the ML/haskell family you will have a lot of intuition in constructive logic (formal reasoning in type theory is literally the same thing as programming). Shallow applications of type theory are numerous in recent developments of compilers (using types, rust can manage memory correctly and statically; in general types are a good channel between humans and compilers for high level and structured information about what they are writing, leading to tons of systematical optimizations).

So: all kinds of typed programming languages with non trivial features being effects (monads&modalities, linear logic), structuring/interfaces (parametrized modules, type classes, translucent types, ..) or interactive theorem proving.

nikofeyn2• 8 years ago

call me a mathematical hipster (new frameworks etc.) but i could never get into axiomatic set theory. algebra is already boring by virtue of being abstract but then make it even more abstract by dropping all models!

can you elaborate here? what is a mathematical hipster, and what are “new frameworks”? and what do you mean by algebra “dropping all models”? i am confused by what these mean.

algebras are about studying various means of combination. given some set, how can we combine two things from that set to get another thing in the set? what are the structures that arise as we explore that question? i highly recommend reading the expository chapter one of pinter’s abstract algebra book.

user68858788• 8 years ago

I learned this years ago and forgot everything. I'm curious - does anyone actually use linear algebra in their day to day, and if so, what's your job title?

theoh• 8 years ago

Isn't it very important for machine learning?

Zezima• 8 years ago

The entire field of computer graphics

mitch3x3• 8 years ago

Aerial Imaging. We use it for both photogrammetry and some aspects of image color correction based on its histogram. I imagine its used extremely often in robotics as well.

nikofeyn2• 8 years ago

when you say “this” do you mean the content in the linked book or linear algebra? because the linked pdf doesn’t have much to do with linear algebra.

leke• 8 years ago

I think set theory, at least, has something to do with database querying.

ganzuul• 8 years ago

It is a source of endless wonder and bemusement to me that we did not choose geometry as our basis for logic and proof over the equality symbol. Many brilliant minds are barred from entry into the field of mathematics because of this error.

Set Theory and Algebra in CS: Introduction to Mathematical Modeling (2013) [pdf]

Related Stories