XBUP - eXtensible Binary Universal Protocol - Documentation
[Up]

# Sets

This document is part of eXtensible Binary Universal Protocol project documentation. It contains description of storage formats for sets data in XBUP protocol.

## Set

The set was taken as the basic building block of math domain. For any two objects we define if they are in a member relationship. We define the truth function which expresses the relation “being member”.

The set has defined its size, and sets with the same cardinality are isomorphic to. Still for the basic form of the set in protocol the elements are indexed by their order.

### Cardinality of the Set

Simple example is finite set, which has defined amount of its members.

XBUPProject/Math/Set/FiniteSet

UBNumber ItemsCount

Elements can be addressed using integer in the range 0 .. n-1. Individual elements can be represented by natural numbers with a defined order.

Another options are the countably and uncountably large set.

XBUPProject/Math/Set/CountableSet XBUPProject/Math/Set/UncountableSet

UBENatural UncoutabilityLevel

Previous types provides way to define the general case:

XBUPProject/Math/Set/GeneralSet

UBPointer Cardinality

### Subset

Other possible way is to define a set as a subset of another set. This can be done such as a list of elements, or using functional condition. In the case of subsets of a finite sets it is possible to use bitmap for elements belonging decision function.

XBUPProject/Math/Set/SubsetMap

UBPointer SourceSet

UBPointer Bitmap

SourceMap link refers to item of the Set type, while there should be available a predefined set, such as integers and natural numbers, etc..

Functional condition will be addressed later.

### Set Operations

There are currently following set operations under consideration: union, intersection, difference, complement

#### Set Union

Unification operation returns a new set that contains all the elements that occur in at least one of the input sets. A similar operation is connected to a given set adds all elements from the second set, which is not presented in the given set so far.

#### Intersection

The operation returns a new intersection set, which contains all the elements that appear in both input sets.

## Derived Structures

It is possible (and typical) to define other mathematical structures on top of the set theory. For example:

Algebra is a structure consisting of a set of definitions and operations on this set. This structure is particularly suitable with regard to determining equivalence.

Function could be defined as member of the Cartesian product on the source and target set with certain conditions (exactly single item or max single item for partial functions, which has the same values on source set).

Homepage: http://xbup.org
License: GNU Free Documentation License (FDL)