# Application of set theory subjects as ordinals, forcing, generic filters in software engineering

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!

• 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. Mar 31, 2015 at 11:38
• 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.)
– Raphael
Mar 31, 2015 at 12:54
• 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! Mar 31, 2015 at 13:07
• 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. Mar 31, 2015 at 14:41
• 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? Mar 31, 2015 at 18:21

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.

• 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)
– vzn
Apr 1, 2015 at 22:21
• 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. Apr 1, 2015 at 22:39
• 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
– vzn
Apr 1, 2015 at 22:51
• Yes, This seems very suitable. I will liik into all these ideas. Thank you!!! Apr 2, 2015 at 9:49
• In the aforementioned blog I wrote: "But it sounds a bit like a joke, and I haven’t been able to track down any references to trans-quantitative analysts, except people talking about Christian Marks’ blog article." I'm pretty sure it was a joke! May 14, 2020 at 20:30

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.