Generating general term of union of two countably infinite sets

Question

I have two sets whose general terms are given as: $$ \begin{align*} A &= \{2⋅n \mid n ∊ ℤ\} \\ B &= \{2⋅n + 1 \mid n ∊ ℤ\} \end{align*} $$ I want to find the union of these two sets and return the common term of the set, something like $\{n \mid n ∊ ℤ\}$.

I have the following questions:

• Given that I can't store the entire sets, what are some efficient ways of merging these two sets?
• How can I find the common term of any given sequence?
• What would be some other approaches to solve this problem?

I would really appreciate if someone can share some relevant literature or an algorithm for this question.

Note that the members of the sets need not be integers – they can be rationals too.

Answer 1

In functional programming languages, there is a technique called lazy evaluation, to deal with infinite sets. In lazy evaluation, the sets are used as generators, and the elements of the set are only generated when they are needed.

We can even have lazy operations on lazy data: like lazy union, lazy intersection, and the like, particularly if the lazy generation spits out elements in some order. Particularly, lazy union is very efficient. Lazy intersection and lazy minus are problematic in cases such as yours.

Answer 2

You need to take a step back or two, because there is a huge gap between the example you posted and the extremely broad problem you describe.

The number of sets of integers is uncountable. So it's impossible to represent them all. The number of representable sets is finite. That's a gap already.

If you stick to the sets that are the image of a computable function, i.e. the sets of the form $\{f(n) \mid n \in \mathbb{N}\}$ where $f : \mathbb{N} \to \mathbb{N}$ is computable, then you have exactly the recursively enumerable sets. That's still too large to do anything, because any nontrivial property of these sets is undecidable: if a property $P$ is such that $P(A_1) \iff P(A_2)$ when $A_1$ and $A_2$ are representations of the same set, then $P$ is undecidable unless it's one of the two properties “always true” or “always false”. This is a variation on Rice's theorem.

(Note: it's customary to work on the natural integers, so I'm using $\mathbb{N}$. But going to $\mathbb{Z}$ or $\mathbb{Q}$ is just a matter of a simple reencoding.)

In particular, a key property to do useful things with just about anything is to test whether the result of two computations represent the same mathematical object. That is, equality of representations: if you have two representations, do they represent the same set? For functions, this is decidable only for some very “small” classes (and there is no maximal class). The situation is similar for their images.

There are three basic approaches you can take:

• Decide that sometimes your system will not spot that two objects represent the same set, and you can live with that. Then you can be very liberal in what inputs you accept, but there will be many inputs for which your system will not produce any useful results. You need to be careful about your simplification procedures, as it may be difficult to ensure that they terminate, let alone terminate in a reasonable time.
• Restrict your inputs to a “small” class of set representations for which equality is decidable. For example, if your sets are all images of linear functions with integer coefficients, then their equality is fairly easy to decide, and it is fairly easy to obtain canonical representations. But if you allow multiplication, you've lost the game.
• An intermediate stance: get human assistance. When your system needs to prove something and the built-in rules aren't enough, ask a human to decide one way or the other. If you want to ensure that the results are correct (as opposed to trusting the human), you enter the realm of proof assistants.

Which approach to take, as well as which class of sets to target, depends very heavily on the problem you want to solve. Once you've decided that, you can start thinking about problems such as simplifying representations and making calculations such as unions and intersections.