5
$\begingroup$

I am going to teach a course in set theory for software engineering students. I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some cardinal invariants (such as $\mathfrak b$, $\mathfrak d$). I might also give a gentel introduction to forcing theory.

I was asked by the head of the department, to add to this course some application of this theory to software engineering.

Since my main area is math and not computer science, I don't have an idea for such an application.

Any ideas for such an application? If there is I would be greatfull if you could give me a detailed source.

Thank you!

$\endgroup$
  • $\begingroup$ The title of the question seems to suggest that you are asking for a "software application" rather than "an application to software", which is somewhat misleading. $\endgroup$ – Dave Clarke Mar 31 '15 at 11:38
  • $\begingroup$ Maybe I'm being naive, but I think "that does not make any sense" is a reasonable response from one professor to another. (The query sounds like "we want to be more applied so I have to ask" to me.) $\endgroup$ – Raphael Mar 31 '15 at 12:54
  • 1
    $\begingroup$ Certainly there are plenty of applications of partial orders in computer science (the whole field of domain theory), though that's hardly software. Domain theory is the foundation of denotational semantics of programming languages, and software is written using programming languages. Voila! $\endgroup$ – Dave Clarke Mar 31 '15 at 13:07
  • 1
    $\begingroup$ Domain theory can be rather advanced. Chapters 5-9 from Nielson and Nielson's Semantics with Applications covers programming language semantics and program analysis. Probably this would be suitable for a 3rd year student. What is the level of the students? Another good place to start is with a book on Discrete Mathematics. This would cover relations (application: databases), graphs (application: networks), trees (application: networks, data structures), etc. $\endgroup$ – Dave Clarke Mar 31 '15 at 14:41
  • 1
    $\begingroup$ My immediate reaction (admittedly based on knowing little about set theory or software engineering) is that filters, cardinal invariants and forcing have nothing whatsoever to do with software engineering. Are you sure that's the kind of set theory you're expected to be teaching? $\endgroup$ – David Richerby Mar 31 '15 at 18:21
4
$\begingroup$

The areas of set theory you refer to are generally rather abstract and don't seem to have a lot of applications. Also, the concept of "application" is different in math than in CS. Anyway, though applied CS is so vast now that even very abstract concepts can find applications somewhere. Here is one possible link.

This paper Tree Automata Make Ordinal Theory Easy (Cachat) shows that tree automata can be used as representing ordinal sets with infinite trees. Then, once connected to automata, there are many practical applications of automata. (There are possibly other connections with Buchi automata.)

We give a new simple proof of the decidability of the First Order Theory of ($\omega^{\omega^i}, +)$ and the Monadic Second Order Theory of $(\omega^i, <),$ improving the complexity in both cases. Our algorithm is based on tree automata and a new representation of (sets of) ordinals by (infinite) trees.

Another idea, this blog quotes a reference that ordinal theory is used in High Frequency Trading (HFT) algorithms but there seem to be few other independent references to this on the internet. This could be explained in that HFT field is very secretive with its technology, or possibly that it's erroneous, but the claim has been repeated widely.

$\endgroup$
  • 1
    $\begingroup$ another idea/ angle: "forcing-like methods" are apparently used in CS theory complexity class separation and relativization proofs although few have sketched out the connection. Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence )(cstheory.se) $\endgroup$ – vzn Apr 1 '15 at 22:21
  • $\begingroup$ I agree that these are examples of the various aspects of set theory in computer science but is it software engineering? The question definitely needs to be clarified on that point. $\endgroup$ – David Richerby Apr 1 '15 at 22:39
  • 1
    $\begingroup$ with this answer am aiming at flexible interpretation & taking the question to basically ask for applications in software engr or CS & not require/ demand further clarification/ narrowing $\endgroup$ – vzn Apr 1 '15 at 22:51
  • 1
    $\begingroup$ Yes, This seems very suitable. I will liik into all these ideas. Thank you!!! $\endgroup$ – user135172 Apr 2 '15 at 9:49
4
$\begingroup$

Generally speaking, if you want to present some applications of the theory, it's more effective to start with applications first and teach the theory that's needed for that application, rather than select a collection of theory and then search around for some application of it.

So, one way to approach your question is to ask why the department wants software engineers to know set theory. How will set theory help software engineers? Then once you know the answer to that question, you could devise a curriculum based upon the elements of set theory that will be relevant to software engineers. Most likely the set of topics that should be taught to software engineers is quite different from the set of topics that we would teach to mathematicians.

If you've followed this approach to course design, you should able to answer very clearly what the applications are and why you are teaching them this material. This approach can also potentially lead to better student engagement, depending on student's motivations. However, this approach likely requires re-thinking the entire course and starting over from scratch on the syllabus and topics you plan to teach, which might or might not be attractive in this case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.