# Lab ideas for set theory

The title of the question actually says almost everything there is to say. I cannot think of any programming labs whatsoever that would naturally flow from set theory.

My students will be coding in Scheme (Racket), and will be pretty new at it when we approach this topic. Are there any ways to translate the concepts of set theory into a reasonable lab?

We are covering:

• Basic definitions
• Venn Diagrams
• Union
• Cardinality
• Cartesian Products
• Power Sets
• Bijection (as proof of cardinality)
• Infinite sets $$\aleph_0$$ and $$\aleph_1$$
• Drawing a diagonal line to prove $$|\mathbb{R}| \neq |\mathbb{N}|$$
• Are you more interested in set theory per se, or in the programming? – Buffy Sep 25 '18 at 20:11
• A problem you will have, if they know neither set theory, nor Racket, is that you are trying to advance them simultaneously on two independent axes. That is difficult in principle, as well as in practice. – Buffy Sep 25 '18 at 20:29
• @Buffy I'm more interested in set theory. – Ben I. Sep 25 '18 at 20:38
• I would be looking at using/creating a library that operates on sets/lists. With operations such as is_all_in my_collection (lambda x: x>7) : Boolean. Some basic operations are is_all collection lambda: Boolean, contains collection lambda: Boolean (at least one), is_subset collection collection:Boolean, union collection collection: set, intersection collection collection: set. I have used these libraries in many languages, can't remember which. – ctrl-alt-delor Sep 29 '18 at 17:43

This answer will be general, rather than specific to your proposed curriculum. Since you note in a comment that it is set theory that you want to stress over Racket programming, I'll suggest the following.

First, it is difficult to advance students on two orthogonal axes simultaneously without confusing at least some of them. Therefore you want to put the stress on set theory and its beauty and limitations over the programming aspect. If you were using a language that they already knew well, I'd make a slightly different suggestion.

But first, give them a good, traditional, view of set theory and how it relates in general to modes of thought. Any good book, even if it doesn't mention programming at all, could be used, even Naive Set Theory by Halmos. Use programming primarily to illustrate things in a simple way so that the functional programming doesn't take up too much of their thought space - just enough to get the flavor of, for example deep recursive programming.

The programming exercises can be quite simple, but I would choose them in such a way that they also serve as an introduction to complexity theory and the problem of growth. Something simple with Cartesian product and many dimensions can illustrate the growth. It is also possible to write functional programs for things that seem simple but have terrible run-time. For example, a naive version of reversing a list can easily be quadratic if care isn't taken.

I don't know what libraries Racket offers for support of sets, but it might be useful to talk about the development of such a library - building a tool box of simple set operations.

But, in the main, use the programming as a way to reinforce the theory, not so much as an end in itself. Set theory is rich enough and with enough applications to math and CS that you don't really need to do much more.

If you really want to teach FP in Racket, then a different set of exercises that help the functional thought process develop would probably be better than trying to force it into one realm.

• Perfect, thank you. This is exactly the sort of thing that I had in mind. You have helped to clarify my thinking on this matter! – Ben I. Sep 26 '18 at 18:04

I propose for instance for

1. basic definitions
2. venn diagrams
3. Union
4. Cardinality
5. Cartesian products

Using SQL language, why?

When you create a schema database you need to think in entities, relations, boolean algebra.

I mean you can study this concepts oriented to programming field, making schemas and identifying relationships between tables.

For example when you use JOINS operators and UNION and UNION ALL concepts you need to abstract the concepts about diagram venn(when you use left join, right join, etc)

So if your students and you need make a knowledge route about these concepts; SQL is a good option for it

I hope to be useful.....

• But my course isn't about SQL. One of the course goals is to teach a functional programming language, and we are using Racket. – Ben I. Sep 26 '18 at 2:40
• @beni apparently Racket is a pedagogic language, often used for constructing other languages. So have the students create parts of SQL using Racket, then teach the set theory using the SQL. I don't know of any other language more related to sets and relational concepts than SQL. Do you? – Scott Rowe Sep 26 '18 at 20:49
• @ScottRowe It's true that Racket allows you to reconstruct Racket until it mimics another language,a but you're deep into Scheme if you're doing that. That activity wouldn't be at an introductory level for that language. – Ben I. Sep 27 '18 at 2:36
• @beni I know that SICP has some data structure definitional stuff, like defining pairs, then creating other things from those, but it seems pretty advanced to me. I think that Lisp, like parts of the Torah, should be off-limits until someone has turned 35. – Scott Rowe Sep 27 '18 at 23:22