0

I've been experimenting with the following idea, and I wondered if there's a name for it:

Suppose $S_0, S_1, ... S_{n-1}$ is an array of $n$ sets of elements in $U$. Now for any element $e \in U$ we can test whether or not $(e \in S_0), (e \in S_1), ... (e \in S_{n-1})$ etc, producing an array of $n$ boolean values.

Since we can treat these results as the digits of an $n$-digit binary number, it's clear that we've partitioned $U$ into $2^n$ distinct sets.

This seems like a promising way to model variables in a little automated theorem prover I'm building, and I'm hoping someone out there could point me to something similar in the literature.

Peter Taylor
  • 13,425
tangentstorm
  • 423
  • 2
    The sequence $S_0,S_1,\ldots,S_n$ has $n+1$ elements. And the term you're probably looking for is the boolean algebra generated by $S_0,\ldots,S_n$ – tomasz Apr 04 '14 at 23:59
  • Corrected. Thanks. http://en.wikipedia.org/wiki/Boolean_algebra_(structure) looks promising. – tangentstorm Apr 05 '14 at 00:08
  • Is it clear that you've "partitioned $U$ into $2^n$ distinct sets"? What if your sets are such that there exist two elements $e_1$ and $e_2$ such that $e_1 \in S_i \iff e_2 \in S_i$ for all $i$? – mhum Apr 05 '14 at 00:17
  • Your “$2^n$ sets” are not necessarily distinct. For example, suppose the $S_i$ are disjoint. Then an element $e\in U$ can be in at most one $S_i$, and the only binary numbers that arise are those with a single 1-bit. For every binary number with more than one 1-bit, the corresponding set is empty. This is probably what @mhum was getting at. (In mathematics, even one empty set isn’t usually allowed to be one of the sets in a partition. It would be unusual to call $\mathbb{Z}=\mathbb{Z}\cup\emptyset$ a partition of $\mathbb{Z}$ into two sets.) – Steve Kass Apr 05 '14 at 01:23
  • I see. These are the semantics I want, I'm just lacking the mathematical vocabulary. (I come from a programming background and am writing a little logic system to help me learn.) I simply mean that none of the resulting $2^n$ sets overlap. Being able to show that some of them are empty is kind of the goal. – tangentstorm Apr 05 '14 at 02:36

0 Answers0