In mathematics, a signed set is a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

of elements together with an assignment of a

sign A sign is an object, quality, event, or entity whose presence or occurrence indicates the probable presence or occurrence of something else. A natural sign bears a causal relation to its object—for instance, thunder is a sign of storm, or me ...

(positive or negative) to each element of the set.

Representation

Signed sets may be represented mathematically as an

ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...

disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...

, one set for their positive elements and another for their negative elements. Alternatively, they may be represented as a

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...

, a function whose domain is the underlying unsigned set (possibly specified explicitly as a separate part of the representation) and whose range is a two-element set representing the signs. Signed sets may also be called

\Z_2

- graded sets.

Application

Signed sets are fundamental to the definition of

oriented matroid An oriented matroid is a mathematics, mathematical mathematical structure, structure that abstracts the properties of directed graphs, Vector space, vector arrangements over ordered fields, and Arrangement of hyperplanes, hyperplane arrangements o ...

s. They may also be used to define the

faces The face is the front of an animal's head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may affe ...

of a

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...

. If the hypercube consists of all points in

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...

of a given dimension whose

Cartesian coordinates A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in t ...

are in the interval

1,+1 Onekama ( ) is a village in Manistee County in the U.S. state of Michigan. The population was 411 at the 2010 census. The village is located on the shores of Portage Lake and is surrounded by Onekama Township. The town's name is derived from "On ...

/math>, then a signed subset of the coordinate axes can be used to specify the points whose coordinates within the subset are

-1

+1

(according to the sign in the signed subset) and whose other coordinates may be anywhere in the interval

/math>. This subset of points forms a face, whose

codimension In mathematics, codimension is a basic geometric idea that applies to subspaces in vector spaces, to submanifolds in manifolds, and suitable subsets of algebraic varieties. For affine and projective algebraic varieties, the codimension equals the ...

is the

cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

of the signed subset.

Combinatorics

Enumeration

The number of signed subsets of a given

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...

n

elements is

3^n

, a

power of three In mathematics, a power of three is a number of the form where is an integer – that is, the result of exponentiation with number three as the base and integer as the exponent. Applications The powers of three give the place values in ...

, because there are three choices for each element: it may be absent from the subset, present with positive sign, or present with negative sign. For the same reason, the number of signed subsets of cardinality

r

is :

2^r\binom,

and summing these gives an instance of the

binomial theorem In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial into a sum involving terms of the form , where the ...

, :

\sum_r 2^r\binom=3^n.

Intersecting families

An analogue of the

Erdős–Ko–Rado theorem In mathematics, the Erdős–Ko–Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common. Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it ...

on intersecting families of sets holds also for signed sets. The intersection of two signed sets is defined to be the signed set of elements that belong to both and have the same sign in both. According to this theorem, for any a collection of signed subsets of an

n

-element set, all having cardinality

r

and all pairs having a non-empty intersection, the number of signed subsets in the collection is at most :

2^\binom.

For instance, an intersecting family of this size can be obtained by choosing the sign of a single fixed element, and taking the family to be all signed subsets of cardinality

r

that contain this element with this sign. For

r\le n/2

this theorem follows immediately from the unsigned Erdős–Ko–Rado theorem, as the unsigned versions of the subsets form an intersecting family and each unsigned set can correspond to at most

2^

signed sets. However, for larger values of

r

a different proof is needed.

References

{{reflist, refs= {{citation , last = Brini , first = A. , at = Art. B55g , date = July 2005 , journal =

Séminaire Lotharingien de Combinatoire The ''Séminaire Lotharingien de Combinatoire'' (English: ''Lotharingian Seminar of Combinatorics'') is a peer-reviewed academic journal specialising in combinatorial mathematics, named after Lotharingia. It has existed since 1980 as a regular jo ...

, mr = 2373407 , title = Combinatorics, superalgebras, invariant theory and representation theory , url = https://eudml.org/doc/227556 , volume = 55; see in particular Section 3.4, p. 15 {{citation , last1 = Bollobás , first1 = B. , author1-link = Béla Bollobás , last2 = Leader , first2 = I. , author2-link = Imre Leader , doi = 10.1016/S0898-1221(97)00215-0 , issue = 11 , journal = Computers and Mathematics with Applications , mr = 1486880 , pages = 9–13 , title = An Erdős–Ko–Rado theorem for signed sets , volume = 34 , year = 1997, doi-access = free This formula for the number of signed subsets and the number of faces of a hypercube generalizes to the number of faces of a

Hanner polytope In geometry, a Hanner polytope is a convex polytope constructed recursively by Cartesian product and polar dual operations. Hanner polytopes are named after Olof Hanner, who introduced them in 1956.. Construction The Hanner polytopes are construct ...

; see {{citation , last = Kalai , first = Gil , authorlink = Gil Kalai , doi = 10.1007/BF01788696 , issue = 1 , journal =

Graphs and Combinatorics ''Graphs and Combinatorics'' (ISSN 0911-0119, abbreviated ''Graphs Combin.'') is a peer-reviewed academic journal in graph theory, combinatorics, and discrete geometry published by Springer Japan. Its editor-in-chief is Katsuhiro Ota of Keio U ...

, mr = 1554357 , pages = 389–391 , title = The number of faces of centrally-symmetric polytopes , volume = 5 , year = 1989 {{citation , last = Las Vergnas , first = Michel , authorlink = Michel Las Vergnas , doi = 10.1016/0095-8956(80)90082-9 , issue = 2 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 586435 , pages = 231–243 , series = Series B , title = Convexity in oriented matroids , volume = 29 , year = 1980, doi-access = free {{citation , last1 = Metropolis , first1 = N. , author1-link = Nicholas Metropolis , last2 = Rota , first2 = Gian-Carlo , author2-link = Gian-Carlo Rota , doi = 10.1090/S0002-9904-1978-14477-2 , issue = 2 , journal =

Bulletin of the American Mathematical Society The ''Bulletin of the American Mathematical Society'' is a quarterly mathematical journal published by the American Mathematical Society. Scope It publishes surveys on contemporary research topics, written at a level accessible to non-experts. I ...

, mr = 462997 , pages = 284–286 , title = On the lattice of faces of the

n

-cube , volume = 84 , year = 1978, doi-access = free Set theory