Sets

AUTHORS:

  • William Stein (2005) - first version
  • William Stein (2006-02-16) - large number of documentation and examples; improved code
  • Mike Hansen (2007-3-25) - added differences and symmetric differences; fixed operators
sage.sets.set.EnumeratedSet(X)

Return the enumerated set associated to $X$.

The input object $X$ must be finite.

EXAMPLES:

sage: EnumeratedSet([1,1,2,3])
{1, 2, 3}
sage: EnumeratedSet(ZZ)
...
ValueError: X (=Integer Ring) must be finite
sage.sets.set.Set(X)

Create the underlying set of $X$.

If $X$ is a list, tuple, Python set, or X.is_finite() is true, this returns a wrapper around Python’s enumerated immutable frozenset type with extra functionality. Otherwise it returns a more formal wrapper.

If you need the functionality of mutable sets, use Python’s builtin set type.

EXAMPLES:

sage: X = Set(GF(9,'a'))
sage: X
{0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2}
sage: type(X)
<class 'sage.sets.set.Set_object_enumerated'>
sage: Y = X.union(Set(QQ))
sage: Y
Set-theoretic union of {0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2} and Set of elements of Rational Field
sage: type(Y)
<class 'sage.sets.set.Set_object_union'>

Usually sets can be used as dictionary keys.

sage: d={Set([2*I,1+I]):10}
sage: d                  # key is randomly ordered
{{I + 1, 2*I}: 10}          
sage: d[Set([1+I,2*I])]
10
sage: d[Set((1+I,2*I))]
10

The original object is often forgotten.

sage: v = [1,2,3]
sage: X = Set(v)
sage: X
{1, 2, 3}
sage: v.append(5)
sage: X
{1, 2, 3}
sage: 5 in X
False

Set also accepts iterators, but be careful to only give finite sets.

sage: list(Set(iter([1, 2, 3, 4, 5])))
[1, 2, 3, 4, 5]
class sage.sets.set.Set_object(X)

A set attached to an almost arbitrary object.

EXAMPLES:

sage: K = GF(19)
sage: Set(K)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}
sage: S = Set(K)

sage: latex(S)
\left\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18\right\}
sage: loads(S.dumps()) == S
True

sage: latex(Set(ZZ))
\Bold{Z}
__add__(X)

Return the union of self and X.

EXAMPLES:

sage: Set(RealField()) + Set(QQ^5)
 Set-theoretic union of Set of elements of Real Field with 53 bits of precision and Set of elements of Vector space of dimension 5 over Rational Field
sage: Set(GF(3)) + Set(GF(2))
{0, 1, 2, 0, 1}
sage: Set(GF(2)) + Set(GF(4,'a'))
{0, 1, a, a + 1}
sage: Set(GF(8,'b')) + Set(GF(4,'a'))
{0, 1, b, b + 1, b^2, b^2 + 1, b^2 + b, b^2 + b + 1, a, a + 1, 1, 0}
__and__(X)

Returns the intersection of self and X.

EXAMPLES:

sage: Set([2,3]) & Set([3,4])
{3}
sage: Set(ZZ) & Set(QQ)
Set-theoretic intersection of Set of elements of Integer Ring and Set of elements of Rational Field
__cmp__(right)

Compare self and right.

If right is not a Set compare types. If right is also a Set, returns comparison on the underlying objects.

Note

If X < Y is true this does not necessarily mean that X is a subset of Y. Also, any two sets can be compared, which is a general Python philosophy.

EXAMPLES:

sage: Set(ZZ) == Set(QQ) False sage: Set(ZZ) < Set(QQ) True sage: Primes() == Set(QQ) False sage: Primes() < Set(QQ) True

sage: Set(QQ) == Primes() False

__contains__(x)

Return True if $x$ is in self.

EXAMPLES:

sage: X = Set(ZZ)
sage: 5 in X
True
sage: GF(7)(3) in X
True
sage: 2/1 in X
True
sage: 2/1 in ZZ
True
sage: 2/3 in X
False

Finite fields better illustrate the difference between __contains__ for objects and their underlying sets.

sage: X = Set(GF(7)) sage: X {0, 1, 2, 3, 4, 5, 6} sage: 5/3 in X False sage: 5/3 in GF(7) False sage: Set(GF(7)).union(Set(GF(5))) {0, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 0} sage: Set(GF(7)).intersection(Set(GF(5))) {}
__hash__()
__init__(X)

Create a Set_object

This function is called by the Set function; users shouldn’t call this directly.

EXAMPLES:

sage: type(Set(QQ))
<class 'sage.sets.set.Set_object'>
__iter__()

Iterate over the elements of this set.

EXAMPLES:

sage: X = Set(ZZ)
sage: I = X.__iter__()
sage: I.next()
0
sage: I.next()
1
sage: I.next()
-1
sage: I.next()
2
__or__(X)

Return the union of self and X.

EXAMPLES:

sage: Set([2,3]) | Set([3,4])
{2, 3, 4}
sage: Set(ZZ) | Set(QQ)
Set-theoretic union of Set of elements of Integer Ring and Set of elements of Rational Field
__sub__(X)

Return the difference of self and X.

EXAMPLES:

sage: X = Set(ZZ).difference(Primes())
sage: Y = Set(ZZ) - Primes()
sage: X == Y
True
__xor__(X)

Returns the symmetric difference of self and X.

EXAMPLES:

sage: X = Set([1,2,3,4])
sage: Y = Set([1,2])
sage: X.symmetric_difference(Y)
{3, 4}
sage: X.__xor__(Y)
{3, 4}
_latex_()

Return latex representation of this set.

This is often the same as the latex representation of this object when the object is infinite.

EXAMPLES:

sage: latex(Set(QQ))
\Bold{Q}

When the object is finite or a special set then the latex representation can be more interesting.

sage: print latex(Primes())
\text{Set of all prime numbers: 2, 3, 5, 7, ...}
sage: print latex(Set([1,1,1,5,6]))
\left\{1, 5, 6\right\}
_repr_()

Print representation of this set.

EXAMPLES:

sage: X = Set(ZZ)
sage: X
Set of elements of Integer Ring
sage: X.rename('{ integers }')
sage: X
{ integers }
cardinality()

Return the cardinality of this set, which is either an integer or Infinity.

EXAMPLES:

sage: Set(ZZ).cardinality()
+Infinity
sage: Primes().cardinality()
+Infinity
sage: Set(GF(5)).cardinality()
5
sage: Set(GF(5^2,'a')).cardinality()
25
difference(X)

Return the intersection of self and X.

EXAMPLES:

sage: X = Set(ZZ).difference(Primes())
sage: 4 in X
True
sage: 3 in X
False

sage: 4/1 in X
True

sage: X = Set(GF(9,'b')).difference(Set(GF(27,'c')))
sage: X
{0, 1, 2, b, b + 1, b + 2, 2*b, 2*b + 1, 2*b + 2}

sage: X = Set(GF(9,'b')).difference(Set(GF(27,'b')))
sage: X
{0, 1, 2, b, b + 1, b + 2, 2*b, 2*b + 1, 2*b + 2}
intersection(X)

Return the intersection of self and X.

EXAMPLES:

sage: X = Set(ZZ).intersection(Primes())
sage: 4 in X
False
sage: 3 in X
True

sage: 2/1 in X
True

sage: X = Set(GF(9,'b')).intersection(Set(GF(27,'c')))
sage: X
{}

sage: X = Set(GF(9,'b')).intersection(Set(GF(27,'b')))
sage: X
{}
is_finite()

EXAMPLES:

sage: Set(QQ).is_finite()
False
sage: Set(GF(250037)).is_finite()
True
sage: Set(Integers(2^1000000)).is_finite()
True
sage: Set([1,'a',ZZ]).is_finite()
True
object()

Return underlying object.

EXAMPLES:

sage: X = Set(QQ)
sage: X.object()
Rational Field
sage: X = Primes()
sage: X.object()
Set of all prime numbers: 2, 3, 5, 7, ...
subsets(size=None)

Return the Subset object representing the subsets of a set. If size is specified, return the subsets of that size.

EXAMPLES:

sage: X = Set([1,2,3])
sage: list(X.subsets())
[{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
sage: list(X.subsets(2))
[{1, 2}, {1, 3}, {2, 3}]
symmetric_difference(X)

Returns the symmetric difference of self and X.

EXAMPLES:

sage: X = Set([1,2,3]).symmetric_difference(Set([3,4]))
sage: X
{1, 2, 4}
union(X)

Return the union of self and X.

EXAMPLES:

sage: Set(QQ).union(Set(ZZ))
Set-theoretic union of Set of elements of Rational Field and Set of elements of Integer Ring
sage: Set(QQ) + Set(ZZ)
Set-theoretic union of Set of elements of Rational Field and Set of elements of Integer Ring
sage: X = Set(QQ).union(Set(GF(3))); X
Set-theoretic union of Set of elements of Rational Field and {0, 1, 2}
sage: 2/3 in X
True
sage: GF(3)(2) in X
True
sage: GF(5)(2) in X
False
sage: Set(GF(7)) + Set(GF(3))
{0, 1, 2, 3, 4, 5, 6, 1, 2, 0}
class sage.sets.set.Set_object_difference(X, Y)

Formal difference of two sets.

__cmp__(right)

Try to compare self and right.

Note

Comparison is basically not implemented, or rather it could say sets are not equal even though they are. I don’t know how one could implement this for a generic intersection of sets in a meaningful manner. So be careful when using this.

EXAMPLES:

sage: Y = Set(ZZ).difference(Set(QQ))
sage: Y == Set([])
False
sage: X = Set(QQ).difference(Set(ZZ))
sage: Y == X
False
sage: Z = X.difference(Set(ZZ))
sage: Z == X
False

This illustrates that equality testing for formal unions can be misleading in general.

sage: X == Set(QQ).difference(Set(ZZ))
True            
__contains__(x)

Return true if self contains x.

Since self is a formal intersection of X and Y this function returns true if both X and Y contains x.

EXAMPLES:

sage: X = Set(QQ).difference(Set(ZZ))
sage: 5 in X
False
sage: ComplexField().0 in X
False
sage: sqrt(2) in X     # since sqrt(2) is not a numerical approx
False
sage: sqrt(RR(2)) in X # since sqrt(RR(2)) is a numerical approx
True
sage: 5/2 in X
True
__init__(X, Y)

EXAMPLES:

sage: S = Set(QQ)
sage: T = Set(ZZ)
sage: X = S.difference(T); X
Set-theoretic difference between Set of elements of Rational Field and Set of elements of Integer Ring
sage: latex(X)
\Bold{Q} - \Bold{Z}

sage: loads(X.dumps()) == X
True
__iter__()

Return iterator through elements of self.

Self is a formal difference of X and Y and this function is implemented by iterating through the elements of X and for each checking if it is not in Y, and if yielding it.

EXAMPLES:

sage: X = Set(ZZ).difference(Primes())
sage: I = X.__iter__()
sage: I.next()
0
sage: I.next()
1
sage: I.next()
-1
sage: I.next()
-2
sage: I.next()
-3
_latex_()

Return latex representation of self.

EXAMPLES:

sage: X = Set(QQ).difference(Set(ZZ))
sage: latex(X)
\Bold{Q} - \Bold{Z}
_repr_()

Return string representation of self.

EXAMPLES:

sage: X = Set(QQ).difference(Set(ZZ)); X
Set-theoretic difference between Set of elements of Rational Field and Set of elements of Integer Ring
sage: X.rename('Q - Z')
sage: X
Q - Z
cardinality()

This tries to return the cardinality of this formal intersection.

Note that this is not likely to work in very much generality, and may just hang if either set involved is infinite.

EXAMPLES:

sage: X = Set(GF(13)).difference(Set(Primes()))
sage: X.cardinality()
8
class sage.sets.set.Set_object_enumerated(X)

A finite enumerated set.

__cmp__(other)

Compare the sets self and other.

EXAMPLES:
sage: X = Set(GF(8,’c’)) sage: X == Set(GF(8,’c’)) True sage: X == Set(GF(4,’a’)) False sage: Set(QQ) == Set(ZZ) False
__hash__()
__init__(X)

EXAMPLES:

sage: S = EnumeratedSet(GF(19)); S
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}
sage: print latex(S)
\left\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
ight}
sage: loads(S.dumps()) == S True
__iter__()

Iterating through the elements of self.

EXAMPLES:

sage: S = EnumeratedSet(GF(19))
sage: I = iter(S)
sage: I.next()
0
sage: I.next()
1
sage: I.next()
2
sage: I.next()
3
__len__()

EXAMPLES:

sage: len(Set([1,1]))
1
_latex_()

Return the LaTeX representation of self.

EXAMPLES:

sage: S = EnumeratedSet(GF(2))
sage: latex(S)
\left\{0, 1\right\}
_repr_()

Return the string representation of self.

EXAMPLES:

sage: S = EnumeratedSet(GF(2))
sage: S
{0, 1}
cardinality()

EXAMPLES:

sage: Set([1,1]).cardinality()
1
difference(other)

Returns the set difference self-other.

EXAMPLES:

sage: X = Set([1,2,3,4])
sage: Y = Set([1,2])
sage: X.difference(Y)
{3, 4}
sage: Z = Set(ZZ)
sage: W = Set([2.5, 4, 5, 6])
sage: W.difference(Z)
{2.50000000000000}
frozenset()

Return the Python frozenset object associated to this set, which is an immutable set (hence hashable).

EXAMPLES:

sage: X = Set(GF(8,'c'))
sage: X
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}
sage: s = X.set(); s
set([0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1])
sage: hash(s)
...
TypeError: unhashable type: 'set'
sage: s = X.frozenset(); s
frozenset([0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1])
sage: hash(s)
-1390224788            # 32-bit
 561411537695332972    # 64-bit
sage: type(s)
<type 'frozenset'>
intersection(other)

Return the intersection of self and other.

EXAMPLES:

sage: X = Set(GF(8,'c'))
sage: Y = Set([GF(8,'c').0, 1, 2, 3])
sage: X.intersection(Y)
{1, c}
set()

Return the Python set object associated to this set.

Python has a notion of finite set, and often Sage sets have an associated Python set. This function returns that set.

EXAMPLES:

sage: X = Set(GF(8,'c'))
sage: X
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}
sage: X.set()
set([0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1])
sage: type(X.set())
<type 'set'>
sage: type(X)
<class 'sage.sets.set.Set_object_enumerated'>
symmetric_difference(other)

Returns the set difference self-other.

EXAMPLES:

sage: X = Set([1,2,3,4])
sage: Y = Set([1,2])
sage: X.symmetric_difference(Y)
{3, 4}
sage: Z = Set(ZZ)
sage: W = Set([2.5, 4, 5, 6])
sage: U = W.symmetric_difference(Z)
sage: 2.5 in U
True
sage: 4 in U
False
sage: V = Z.symmetric_difference(W)
sage: V == U
True
sage: 2.5 in V
True
sage: 6 in V
False
union(other)

Return the union of self and other.

EXAMPLES:

sage: X = Set(GF(8,'c'))
sage: Y = Set([GF(8,'c').0, 1, 2, 3])
sage: X
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}
sage: Y
{1, c, 3, 2}
sage: X.union(Y)
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1, 2, 3}
class sage.sets.set.Set_object_intersection(X, Y)

Formal intersection of two sets.

__cmp__(right)

Try to compare self and right.

Note

Comparison is basically not implemented, or rather it could say sets are not equal even though they are. I don’t know how one could implement this for a generic intersection of sets in a meaningful manner. So be careful when using this.

EXAMPLES:
sage: Y = Set(ZZ).intersection(Set(QQ)) sage: X = Set(QQ).intersection(Set(ZZ)) sage: X == Y True sage: Y == X True

This illustrates that equality testing for formal unions can be misleading in general.

sage: Set(ZZ).intersection(Set(QQ)) == Set(QQ)
False            
__contains__(x)

Return true if self contains x.

Since self is a formal intersection of X and Y this function returns true if both X and Y contains x.

EXAMPLES:

sage: X = Set(QQ).intersection(Set(RR))
sage: 5 in X
True
sage: ComplexField().0 in X
False

Any specific floating-point number in Sage is to finite precision, hence it is rational:

sage: RR(sqrt(2)) in X
True

Real constants are not rational:

sage: pi in X
False
__init__(X, Y)

EXAMPLES:

sage: S = Set(QQ^2)
sage: T = Set(ZZ)
sage: X = S.intersection(T); X
Set-theoretic intersection of Set of elements of Vector space of dimension 2 over Rational Field and Set of elements of Integer Ring
sage: latex(X)
\Bold{Q}^{2} \cap \Bold{Z}

sage: loads(X.dumps()) == X
True
__iter__()

Return iterator through elements of self.

Self is a formal intersection of X and Y and this function is implemented by iterating through the elements of X and for each checking if it is in Y, and if yielding it.

EXAMPLES:

sage: X = Set(ZZ).intersection(Primes())
sage: I = X.__iter__()
sage: I.next()
2
_latex_()

Return latex representation of self.

EXAMPLES:

sage: X = Set(ZZ).intersection(Set(QQ))
sage: latex(X)
\Bold{Z} \cap \Bold{Q}
_repr_()

Return string representation of self.

EXAMPLES:

sage: X = Set(ZZ).intersection(Set(QQ)); X
Set-theoretic intersection of Set of elements of Integer Ring and Set of elements of Rational Field
sage: X.rename('Z /\ Q')
sage: X
Z /\ Q
cardinality()

This tries to return the cardinality of this formal intersection.

Note that this is not likely to work in very much generality, and may just hang if either set involved is infinite.

EXAMPLES:

sage: X = Set(GF(13)).intersection(Set(ZZ))
sage: X.cardinality()
13
class sage.sets.set.Set_object_symmetric_difference(X, Y)

Formal symmetric difference of two sets.

__cmp__(right)

Try to compare self and right.

Note

Comparison is basically not implemented, or rather it could say sets are not equal even though they are. I don’t know how one could implement this for a generic symmetric difference of sets in a meaningful manner. So be careful when using this.

EXAMPLES:

sage: Y = Set(ZZ).symmetric_difference(Set(QQ))
sage: X = Set(QQ).symmetric_difference(Set(ZZ))
sage: X == Y
True
sage: Y == X
True
__contains__(x)

Return true if self contains x.

Since self is the formal symmetric difference of X and Y this function returns true if either X or Y (but now both) contains x.

EXAMPLES:

sage: X = Set(QQ).symmetric_difference(Primes())
sage: 4 in X
True
sage: ComplexField().0 in X
False
sage: sqrt(2) in X      # since sqrt(2) is currently symbolic
False
sage: sqrt(RR(2)) in X # since sqrt(RR(2)) is currently approximated
True
sage: pi in X
False
sage: 5/2 in X
True
sage: 3 in X
False
__init__(X, Y)

EXAMPLES:

sage: S = Set(QQ)
sage: T = Set(ZZ)
sage: X = S.symmetric_difference(T); X
Set-theoretic symmetric difference of Set of elements of Rational Field and Set of elements of Integer Ring
sage: latex(X)
\Bold{Q} \bigtriangleup \Bold{Z}

sage: loads(X.dumps()) == X
True
__iter__()

Return iterator through elements of self.

Self is the formal symmetric difference of X and Y. This function is implemented by first iterating through the elements of X and yielding it if it is not in Y. Then it will iterate throw all the elements of Y and yielding it if it is not in X.

EXAMPLES:

sage: X = Set(ZZ).symmetric_difference(Primes())
sage: I = X.__iter__()
sage: I.next()
0
sage: I.next()
1
sage: I.next()
-1
sage: I.next()
-2
sage: I.next()
-3
_latex_()

Return latex representation of self.

EXAMPLES:

sage: X = Set(ZZ).symmetric_difference(Set(QQ))
sage: latex(X)
\Bold{Z} \bigtriangleup \Bold{Q}
_repr_()

Return string representation of self.

EXAMPLES:

sage: X = Set(ZZ).symmetric_difference(Set(QQ)); X
Set-theoretic symmetric difference of Set of elements of Integer Ring and Set of elements of Rational Field
sage: X.rename('Z symdif Q')
sage: X
Z symdif Q
cardinality()

This tries to return the cardinality of this formal symmetric difference.

Note that this is not likely to work in very much generality, and may just hang if either set involved is infinite.

EXAMPLES:

sage: X = Set(GF(13)).symmetric_difference(Set(range(5)))
sage: X.cardinality()
8
class sage.sets.set.Set_object_union(X, Y)

A formal union of two sets.

__cmp__(right)

Try to compare self and right.

Note

Comparison is basically not implemented, or rather it could say sets are not equal even though they are. I don’t know how one could implement this for a generic union of sets in a meaningful manner. So be careful when using this.

EXAMPLES:

sage: Y = Set(ZZ^2).union(Set(ZZ^3))
sage: X = Set(ZZ^3).union(Set(ZZ^2))
sage: X == Y
True
sage: Y == X
True

This illustrates that equality testing for formal unions can be misleading in general.

sage: Set(ZZ).union(Set(QQ)) == Set(QQ)
False            
__contains__(x)

Returns True if x is an element of self.

EXAMPLES:

sage: X = Set(GF(3)).union(Set(GF(2)))
sage: GF(5)(1) in X
False
sage: GF(3)(2) in X
True
sage: GF(2)(0) in X
True
sage: GF(5)(0) in X
False
__init__(X, Y)

EXAMPLES:

sage: S = Set(QQ^2)
sage: T = Set(ZZ)
sage: X = S.union(T); X
Set-theoretic union of Set of elements of Vector space of dimension 2 over Rational Field and Set of elements of Integer Ring

sage: latex(X)
\Bold{Q}^{2} \cup \Bold{Z}

sage: loads(X.dumps()) == X
True
__iter__()

Return iterator over the elements of self.

EXAMPLES:

sage: [x for x in Set(GF(3)).union(Set(GF(2)))]
[0, 1, 2, 0, 1]
_latex_()

Return latex representation of self.

EXAMPLES:

sage: latex(Set(ZZ).union(Set(GF(5))))
\Bold{Z} \cup \left\{0, 1, 2, 3, 4\right\}
_repr_()

Return string representation of self.

EXAMPLES:

sage: Set(ZZ).union(Set(GF(5)))
Set-theoretic union of Set of elements of Integer Ring and {0, 1, 2, 3, 4}
cardinality()

Return the cardinality of this set.

EXAMPLES:

sage: X = Set(GF(3)).union(Set(GF(2)))
sage: X
{0, 1, 2, 0, 1}
sage: X.cardinality()
5

sage: X = Set(GF(3)).union(Set(ZZ))
sage: X.cardinality()
+Infinity
sage.sets.set.is_Set(x)

Returns true if $x$ is a Sage Set (not to be confused with a Python 2.4 set).

EXAMPLES:

sage: from sage.sets.set import is_Set
sage: is_Set([1,2,3])
False
sage: is_Set(set([1,2,3]))
False
sage: is_Set(Set([1,2,3]))
True
sage: is_Set(Set(QQ))
True
sage: is_Set(Primes())
True

Previous topic

A class for wrapping Sage or Python objects as Sage elements

Next topic

The set of prime numbers

This Page