OpenMath Content Dictionary: set1

Canonical URL:
http://www.openmath.org/cd/set1.ocd
CD File:
set1.ocd
CD as XML Encoded OpenMath:
set1.omcd
Defines:
cartesian_product, emptyset, in, intersect, map, notin, notprsubset, notsubset, prsubset, set, setdiff, size, subset, suchthat, union
Date:
2001-03-12
Version:
2
Review Date:
2003-04-01
Status:
official
Uses CD:
arith1, fns1, quant1, logic1, alg1, interval1, nums1, setname1, relation1

This CD defines the set functions and constructors for basic set theory. It is intended to be `compatible' with the corresponding elements in MathML.


cartesian_product

This symbol represents an n-ary construction function for constructing the Cartesian product of sets. It takes n set arguments in order to construct their Cartesian product.

Example:
An example to show the representation of the Cartesian product of sets: AxBxC.
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="cartesian_product"/>
    <OMV name="A"/>
    <OMV name="B"/>
    <OMV name="C"/>
  </OMA>
</OMOBJ>

cartesian_product ( A, B, C)

Signatures:
sts


[Next: emptyset] [Last: notprsubset] [Top]

emptyset

This symbol is used to represent the empty set, that is the set which contains no members. It takes no parameters.

Commented Mathematical property (CMP):
The intersection of A with the emptyset is the emptyset
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="relation1" name="eq"/>
    <OMA>
      <OMS cd="set1" name="intersect"/>
      <OMV name="A"/>
      <OMS cd="set1" name="emptyset"/>
    </OMA>
    <OMS cd="set1" name="emptyset"/>
  </OMA>
</OMOBJ>

eq (intersect ( A, emptyset) , emptyset)

Commented Mathematical property (CMP):
The union of A with the emptyset is A
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="relation1" name="eq"/>
    <OMA>
      <OMS cd="set1" name="union"/>
      <OMV name="A"/>
      <OMS cd="set1" name="emptyset"/>
    </OMA>
    <OMV name="A"/>
  </OMA>
</OMOBJ>

eq (union ( A, emptyset) , A)

Commented Mathematical property (CMP):
the size of the empty set is zero
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="relation1" name="eq"/>
    <OMA>
      <OMS cd="set1" name="size"/>
      <OMS cd="set1" name="emptyset"/>
    </OMA>
    <OMS cd="alg1" name="zero"/>
  </OMA>
</OMOBJ>

eq (size (emptyset) , zero)

Signatures:
sts


[Next: map] [Previous: cartesian_product] [Top]

map

This symbol represents a mapping function which may be used to construct sets, it takes as arguments a function from X to Y and a set over X in that order. The value that is returned is a set of values in Y. The argument list may be a set or an integer_interval.

Example:
The set of even values between 0 and 20, that is the values 2x, where x ranges over the integral interval [0,10].
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="map"/>
    <OMBIND>
      <OMS cd="fns1" name="lambda"/>
      <OMBVAR>
        <OMV name="x"/>
      </OMBVAR>
      <OMA>
        <OMS cd="arith1" name="times"/>
        <OMI> 2 </OMI>
	<OMV name="x"/>
      </OMA>
    </OMBIND>
    <OMA>
      <OMS cd="interval1" name="integer_interval"/>
      <OMI> 0 </OMI>
      <OMI> 10 </OMI>
    </OMA>
  </OMA>
</OMOBJ>

map (lambda [ x ] . (times ( 2 , x) ) , integer_interval ( 0 , 10 ) )

Signatures:
sts


[Next: size] [Previous: emptyset] [Top]

size

This symbol is used to denote the number of elements in a set. It is either a non-negative integer, or an infinite cardinal number. The symbol infinity may be used for an unspecified infinite cardinal.

Example:
The size of the set{3,6,9} = 3
<OMOBJ>
  <OMA>
    <OMS cd="relation1" name="eq"/>
    <OMA>
      <OMS cd="set1" name="size"/>
      <OMA>
        <OMS cd="set1" name="set"/>
        <OMI> 3 </OMI>
        <OMI> 6 </OMI>
        <OMI> 9 </OMI>
      </OMA>
    </OMA>
    <OMI> 3 </OMI>
  </OMA>
</OMOBJ>

eq (size (set ( 3 , 6 , 9 ) ) , 3 )

Example:
The size of the set of integers is infinite
<OMOBJ>
  <OMA>
    <OMS cd="relation1" name="eq"/>
    <OMA>
      <OMS cd="set1" name="size"/>
      <OMS cd="setname1" name="Z"/>
    </OMA>
    <OMS cd="nums1" name="infinity"/>
  </OMA>
</OMOBJ>

eq (size (Z) , infinity)

Signatures:
sts


[Next: suchthat] [Previous: map] [Top]

suchthat

This symbol represents the suchthat function which may be used to construct sets, it takes two arguments. The first argument should be the set which contains the elements of the set we wish to represent, the second argument should be a predicate, that is a function from the set to the booleans which describes if an element is to be in the set returned.

Example:
This example shows how to construct the set of even integers, using the suchthat constructor.
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="suchthat"/>
    <OMS cd="setname1" name="Z"/>
    <OMBIND>
      <OMS cd="fns1" name="lambda"/>
      <OMBVAR>
        <OMV name="x"/>
      </OMBVAR>
      <OMA>
        <OMS cd="set1" name="in"/>
	<OMA>
	  <OMS cd="arith1" name="divide"/>
	  <OMV name="x"/>
	  <OMI> 2 </OMI>
	</OMA>
	<OMS cd="setname1" name="Z"/>
      </OMA>
    </OMBIND>
  </OMA>
</OMOBJ>

suchthat (Z, lambda [ x ] . (in (divide ( x, 2 ) , Z) ) )

Signatures:
sts


[Next: set] [Previous: size] [Top]

set

This symbol represents the set construct. It is an n-ary function. The set entries are given explicitly. There is no implied ordering to the elements of a set.

Example:
The set {3, 6, 9}
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="set"/>
    <OMI> 3 </OMI>
    <OMI> 6 </OMI>
    <OMI> 9 </OMI>
  </OMA>
</OMOBJ>

set ( 3 , 6 , 9 )

Signatures:
sts


[Next: intersect] [Previous: suchthat] [Top]

intersect

This symbol is used to denote the n-ary intersection of sets. It takes sets as arguments, and denotes the set that contains all the elements that occur in all of them.

Commented Mathematical property (CMP):
(A intersect B) is a subset of A and (A intersect B) is a subset of B
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="logic1" name="and"/>
    <OMA>
      <OMS cd="set1" name="subset"/>
      <OMA>
        <OMS cd="set1" name="intersect"/>
	<OMV name="A"/>
	<OMV name="B"/>
      </OMA>
      <OMV name="A"/>
    </OMA>
    <OMA>
      <OMS cd="set1" name="subset"/>
      <OMA>
        <OMS cd="set1" name="intersect"/>
	<OMV name="A"/>
	<OMV name="B"/>
      </OMA>
      <OMV name="B"/>
    </OMA>
  </OMA>
</OMOBJ>

and (subset (intersect ( A, B) , A) , subset (intersect ( A, B) , B) )

Signatures:
sts


[Next: union] [Previous: set] [Top]

union

This symbol is used to denote the n-ary union of sets. It takes sets as arguments, and denotes the set that contains all the elements that occur in any of them.

Commented Mathematical property (CMP):
A is a subset of (A union B) and B is a subset of (A union B)
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="logic1" name="and"/>
    <OMA>
      <OMS cd="set1" name="subset"/>
      <OMV name="A"/>
      <OMA>
        <OMS cd="set1" name="union"/>
	<OMV name="A"/>
	<OMV name="B"/>
      </OMA>
    </OMA>
    <OMA>
      <OMS cd="set1" name="subset"/>
      <OMV name="B"/>
      <OMA>
        <OMS cd="set1" name="union"/>
	<OMV name="A"/>
	<OMV name="B"/>
      </OMA>
    </OMA>
  </OMA>
</OMOBJ>

and (subset ( A, union ( A, B) ) , subset ( B, union ( A, B) ) )

Commented Mathematical property (CMP):
for all sets A,B and C union(A,intersect(B,C)) = intersect(union(A,B),union(A,C))
Formal Mathematical property (FMP):
<OMOBJ>
  <OMBIND>
    <OMS cd="quant1" name="forall"/>
    <OMBVAR>
      <OMV name="A"/>
      <OMV name="B"/>
      <OMV name="C"/>
    </OMBVAR>
    <OMA>
      <OMS cd="relation1" name="eq"/>
      <OMA>
        <OMS cd="set1" name="union"/>
        <OMV name="A"/>
        <OMA>
          <OMS cd="set1" name="intersect"/>
          <OMV name="B"/>
          <OMV name="C"/>
        </OMA>
      </OMA>
      <OMA>
        <OMS cd="set1" name="intersect"/>
        <OMA>
          <OMS cd="set1" name="union"/>
          <OMV name="A"/>
          <OMV name="B"/>
        </OMA>
        <OMA>
          <OMS cd="set1" name="union"/>
          <OMV name="A"/>
          <OMV name="C"/>
        </OMA>
      </OMA>
    </OMA>    
  </OMBIND>
</OMOBJ>

forall [ A B C ] . (eq (union ( A, intersect ( B, C) ) , intersect (union ( A, B) , union ( A, C) ) ) )

Signatures:
sts


[Next: setdiff] [Previous: intersect] [Top]

setdiff

This symbol is used to denote the set difference of two sets. It takes two sets as arguments, and denotes the set that contains all the elements that occur in the first set, but not in the second.

Commented Mathematical property (CMP):
the difference of A and B is a subset of A
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="subset"/>
    <OMA>
      <OMS cd="set1" name="setdiff"/>
      <OMV name="A"/>
      <OMV name="B"/>
    </OMA>
    <OMV name="A"/>
  </OMA>
</OMOBJ>

subset (setdiff ( A, B) , A)

Signatures:
sts


[Next: subset] [Previous: union] [Top]

subset

This symbol has two (set) arguments. It is used to denote that the first set is a subset of the second.

Commented Mathematical property (CMP):
if B is a subset of A and C is a subset of B then C is a subset of A
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="logic1" name="implies"/>
    <OMA>
      <OMS cd="logic1" name="and"/>
      <OMA>
        <OMS cd="set1" name="subset"/>
        <OMV name="B"/>
        <OMV name="A"/>
      </OMA>
      <OMA>
        <OMS cd="set1" name="subset"/>
        <OMV name="C"/>
        <OMV name="B"/>
      </OMA>
    </OMA>
    <OMA>
      <OMS cd="set1" name="subset"/>
      <OMV name="C"/>
      <OMV name="A"/>
    </OMA>
  </OMA>
</OMOBJ>

implies (and (subset ( B, A) , subset ( C, B) ) , subset ( C, A) )

Signatures:
sts


[Next: in] [Previous: setdiff] [Top]

in

This symbol has two arguments, an element and a set. It is used to denote that the element is in the given set.

Commented Mathematical property (CMP):
if a is in A and a is in B then a is in A intersect B
Formal Mathematical property (FMP):
<OMOBJ>
  <OMA>
    <OMS cd="logic1" name="implies"/>
    <OMA>
      <OMS cd="logic1" name="and"/>
      <OMA>
        <OMS cd="set1" name="in"/>
        <OMV name="a"/>
        <OMV name="A"/>
      </OMA>
      <OMA>
        <OMS cd="set1" name="in"/>
        <OMV name="a"/>
        <OMV name="B"/>
      </OMA>
    </OMA>
    <OMA>
      <OMS cd="set1" name="in"/>
      <OMV name="a"/>
      <OMA>
        <OMS cd="set1" name="intersect"/>
        <OMV name="A"/>
        <OMV name="B"/>
      </OMA>
    </OMA>
  </OMA>
</OMOBJ>

implies (and (in ( a, A) , in ( a, B) ) , in ( a, intersect ( A, B) ) )

Signatures:
sts


[Next: notin] [Previous: subset] [Top]

notin

This symbol has two arguments, an element and a set. It is used to denote that the element is not in the given set.

Commented Mathematical property (CMP):
if a is a member of a then it is not true that a is not a member of A
Formal Mathematical property (FMP):
<OMOBJ>
<OMA>
  <OMS cd="logic1" name="implies"/>
  <OMA>
    <OMS cd="set1" name="in"/>
    <OMV name="a"/>
    <OMV name="A"/>
  </OMA>
  <OMA>
    <OMS cd="logic1" name="not"/>
    <OMA>
      <OMS cd="set1" name="notin"/>
      <OMV name="a"/>
      <OMV name="A"/>
    </OMA>
  </OMA>
</OMA>
</OMOBJ>

implies (in ( a, A) , not (notin ( a, A) ) )

Example:
4 is not in {1,2,3}
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="notin"/>
    <OMI> 4 </OMI>
    <OMA>
      <OMS cd="set1" name="set"/>
      <OMI> 1 </OMI>
      <OMI> 2 </OMI>
      <OMI> 3 </OMI>
    </OMA>
  </OMA>
</OMOBJ>

notin ( 4 , set ( 1 , 2 , 3 ) )

Signatures:
sts


[Next: prsubset] [Previous: in] [Top]

prsubset

This symbol has two (set) arguments. It is used to denote that the first set is a proper subset of the second, that is a subset of the second set but not actually equal to it.

Commented Mathematical property (CMP):
A is a proper subset of B implies that A is a subset of B and A not= B
Formal Mathematical property (FMP):
<OMOBJ>
<OMA>
  <OMS cd="logic1" name="implies"/>
  <OMA>
    <OMS cd="set1" name="prsubset"/>
    <OMV name="A"/>
    <OMV name="B"/>
  </OMA>
  <OMA>
    <OMS cd="logic1" name="and"/>
    <OMA>
      <OMS cd="set1" name="subset"/>
      <OMV name="A"/>
      <OMV name="B"/>
    </OMA>
    <OMA>
      <OMS cd="relation1" name="neq"/>
      <OMV name="A"/>
      <OMV name="B"/>
    </OMA>
  </OMA>
</OMA>
</OMOBJ>

implies (prsubset ( A, B) , and (subset ( A, B) , neq ( A, B) ) )

Example:
{2,3} is a proper subset of {1,2,3}
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="prsubset"/>
    <OMA>
      <OMS cd="set1" name="set"/>
      <OMI> 2 </OMI>
      <OMI> 3 </OMI>
    </OMA>
    <OMA>
      <OMS cd="set1" name="set"/>
      <OMI> 1 </OMI>
      <OMI> 2 </OMI>
      <OMI> 3 </OMI>
    </OMA>
  </OMA>
</OMOBJ>

prsubset (set ( 2 , 3 ) , set ( 1 , 2 , 3 ) )

Signatures:
sts


[Next: notsubset] [Previous: notin] [Top]

notsubset

This symbol has two (set) arguments. It is used to denote that the first set is not a subset of the second.

Commented Mathematical property (CMP):
if A is not a subset of B then there exists an x in B s.t. x is not a member of B
Formal Mathematical property (FMP):
<OMOBJ>
<OMA>
  <OMS cd="logic1" name="implies"/>
  <OMA>
    <OMS cd="set1" name="notsubset"/>
    <OMV name="A"/>
    <OMV name="B"/>
  </OMA>
  <OMBIND>
    <OMS cd="quant1" name="exists"/>
    <OMBVAR>
      <OMV name="x"/>
    </OMBVAR>
    <OMA>
      <OMS cd="logic1" name="and"/>
      <OMA>
        <OMS cd="set1" name="in"/>
	<OMV name="x"/>
	<OMV name="B"/>
      </OMA>
      <OMA>
        <OMS cd="set1" name="notin"/>
	<OMV name="x"/>
	<OMV name="A"/>
      </OMA>
    </OMA>
  </OMBIND>
</OMA>
</OMOBJ>

implies (notsubset ( A, B) , exists [ x ] . (and (in ( x, B) , notin ( x, A) ) ) )

Example:
{2,3,4} is not a subset of {1,2,3}
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="notsubset"/>
    <OMA>
      <OMS cd="set1" name="set"/>
      <OMI> 2 </OMI>
      <OMI> 3 </OMI>
      <OMI> 4 </OMI>
    </OMA>
    <OMA>
      <OMS cd="set1" name="set"/>
      <OMI> 1 </OMI>
      <OMI> 2 </OMI>
      <OMI> 3 </OMI>
    </OMA>
  </OMA>
</OMOBJ>

notsubset (set ( 2 , 3 , 4 ) , set ( 1 , 2 , 3 ) )

Signatures:
sts


[Next: notprsubset] [Previous: prsubset] [Top]

notprsubset

This symbol has two (set) arguments. It is used to denote that the first set is not a proper subset of the second. A proper subset of a set is a subset of the set but not actually equal to it.

Commented Mathematical property (CMP):
A is not a proper subset of B implies that it is not true that A is a proper subset of B
Formal Mathematical property (FMP):
<OMOBJ>
<OMA>
  <OMS cd="logic1" name="implies"/>
  <OMA>
    <OMS cd="set1" name="notprsubset"/>
    <OMV name="A"/>
    <OMV name="B"/>
  </OMA>
  <OMA>
    <OMS cd="logic1" name="not"/>
    <OMA>
      <OMS cd="set1" name="prsubset"/>
      <OMV name="A"/>
      <OMV name="B"/>
    </OMA>
  </OMA>
</OMA>
</OMOBJ>

implies (notprsubset ( A, B) , not (prsubset ( A, B) ) )

Example:
{1,2,3} is not a proper subset of {1,2,3}
<OMOBJ>
  <OMA>
    <OMS cd="set1" name="notprsubset"/>
    <OMA>
      <OMS cd="set1" name="set"/>
      <OMI> 1 </OMI>
      <OMI> 2 </OMI>
      <OMI> 3 </OMI>
    </OMA>
    <OMA>
      <OMS cd="set1" name="set"/>
      <OMI> 1 </OMI>
      <OMI> 2 </OMI>
      <OMI> 3 </OMI>
    </OMA>
  </OMA>
</OMOBJ>

notprsubset (set ( 1 , 2 , 3 ) , set ( 1 , 2 , 3 ) )

Signatures:
sts


[First: cartesian_product] [Previous: notsubset] [Top]