Why is set theory so important for computing?

For the theory of computation, formal languages among other areas as well as for programming (development) set theory is always present, I know that mathematics is strongly linked to computing, but why is there so much emphasis on sets?!

asked by anonymous 31.08.2015 / 04:21

2 answers


Some of the mathematical truths that affect sets also affect computing.

For example, you can prove that each computer program can be related to an integer. Just imagine all the bits of an application as a single, large integer. Therefore, the existing set of programs is similar to the set of integers (they have the same "cardinality").

Computational problems can be related to the set of real numbers. This set has a greater cardinality than the integers, that is, we can say that there are many more real numbers than integers, although they are two infinite sets.

From this conclusion about the sets, we conclude that there are far more computational problems than computer programs. In other words, there are numerous computational problems that have no solution, can not be solved by a computer program.

One of these problems is precisely the "stop problem", where a program must analyze another and decide whether it will execute for a finite time or not. Solving this problem would be very useful because it would make it possible for a development environment to "automatically" prove that a program is bug free, etc.

But unfortunately the problem of the stop has no solution. Of course, static parsers can catch some bugs and conclude that some programs will stop. What is impossible is to find a generic, universal algorithm capable of analyzing any other program including itself.

So here's an example of the importance of set theory. Because of it we know there are some limits to what a computer can do, which saves you the trouble of trying:)

31.08.2015 / 05:33

In addition to the context presented by colleague @epx, I believe it is important to mention that set theory is the basis for the Relational Model, widely implemented by relational database engines.

More in detail, the Relational Model is based on Relational Algebra. Serious database disciplines do not introduce any technology (Oracle, MySQL, SQL Server, SQLite) or even SQL, without first exposing the student to Relational Algebra.

Relational Algebra operations are the Projection (columns selected in the SELECT), Selection (WHERE clause), Product (a cross-join, also known as Cartesian product), Joint (an INNER JOIN), Union (UNION and UNION ALL operator), Difference (MINUS and EXCEPT operator in some databases).

More details:

Relational Model

Relational Algebra

31.08.2015 / 15:45