Hubbry Logo
Projection (set theory)Projection (set theory)Main
Open search
Projection (set theory)
Community hub
Projection (set theory)
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Projection (set theory)
Projection (set theory)
Projection (set theory)
View on Wikipedia
from Wikipedia

In set theory, a projection is one of two closely related types of functions or operations, namely:

  • A set-theoretic operation typified by the th projection map, written that takes an element of the Cartesian product to the value [1]
  • A function that sends an element to its equivalence class under a specified equivalence relation [2] or, equivalently, a surjection from a set to another set.[3] The function from elements to equivalence classes is a surjection, and every surjection corresponds to an equivalence relation under which two elements are equivalent when they have the same image. The result of the mapping is written as when is understood, or written as when it is necessary to make explicit.

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Projection (set theory)

View on Grokipedia
from Grokipedia
In set theory, a projection, also known as a projection function, is a surjective function from the Cartesian product of two or more sets to one of the factor sets, defined by mapping each ordered tuple to its component in the specified coordinate. For the binary Cartesian product X×YX \times Y, the projections are the functions πX:X×Y→X\pi_X: X \times Y \to X and πY:X×Y→Y\pi_Y: X \times Y \to Y, where πX(x,y)=x\pi_X(x, y) = x and πY(x,y)=y\pi_Y(x, y) = y. These functions are fundamental in characterizing Cartesian products through their universal property: for any set ZZ and functions f:Z→Xf: Z \to X, g:Z→Yg: Z \to Y, there exists a unique function h:Z→X×Yh: Z \to X \times Y such that πX∘h=f\pi_X \circ h = f and πY∘h=g\pi_Y \circ h = g. Projections extend naturally to finite or infinite Cartesian products of indexed families of sets {Xi}i∈I\{X_i\}_{i \in I}, where the jj-th projection πj:∏i∈IXi→Xj\pi_j: \prod_{i \in I} X_i \to X_j selects the jj-th coordinate from each . In the case of infinite products, the domain consists of all functions f:I→⋃i∈IXif: I \to \bigcup_{i \in I} X_i such that f(i)∈Xif(i) \in X_i for each i∈Ii \in I, and the projections remain surjective onto each XjX_j. These maps are continuous in the , where the on the product is the coarsest making all projections continuous. Beyond direct applications in products, projections play a key role in relational structures and logic within ; for a relation R⊆A×BR \subseteq A \times B, the projection onto AA is the set {a∈A∣∃b∈B (a,b)∈R}\{a \in A \mid \exists b \in B \, (a, b) \in R\}, which captures the existential image under the projection function and is central to descriptive . In Polish spaces, such projections of Borel sets yield analytic sets, forming the basis of the projective hierarchy studied in set-theoretic contexts like forcing and .

Definitions

Binary projections

In set theory, the binary projections are functions defined on the of two sets. Given sets AA and BB, the first projection π1:A×B→A\pi_1: A \times B \to A is the function that maps each (a,b)(a, b) to its first component, so π1((a,b))=a\pi_1((a, b)) = a for all a∈Aa \in A and b∈Bb \in B. Similarly, the second projection π2:A×B→B\pi_2: A \times B \to B maps each (a,b)(a, b) to its second component, so π2((a,b))=b\pi_2((a, b)) = b for all a∈Aa \in A and b∈Bb \in B. These projection functions presuppose a construction of ordered pairs that distinguishes the first and second components in a set-theoretic manner. One such construction, due to Kuratowski, defines the ordered pair (a,b)(a, b) as the set {{a},{a,b}}\{\{a\}, \{a, b\}\}, which allows the projections to extract the components unambiguously via set membership. For example, consider the sets A={1,2}A = \{1, 2\} and B={x,y}B = \{x, y\}. The first projection π1\pi_1 maps (1,x)(1, x) to 1 and (2,y)(2, y) to 2, while the second projection π2\pi_2 maps (1,x)(1, x) to xx and (2,y)(2, y) to yy. In the binary case, the projections are conventionally denoted as π1\pi^1 and π2\pi^2, or simply π1\pi_1 and π2\pi_2, to indicate the extraction of the first or second coordinate from the .

General finite projections

In , the concept of projection functions extends naturally from the binary case to finite s of multiple sets. For n≥2n \geq 2 sets X1,X2,…,XnX_1, X_2, \dots, X_n, the X1×⋯×XnX_1 \times \cdots \times X_n consists of all ordered nn-tuples (x1,…,xn)(x_1, \dots, x_n) where xi∈Xix_i \in X_i for each i=1,…,ni = 1, \dots, n. These ordered tuples provide a structured way to combine elements from each factor set, preserving the order and distinguishing components based on their positions. The jj-th projection map, denoted πj:X1×⋯×Xn→Xj\pi_j: X_1 \times \cdots \times X_n \to X_j for 1≤j≤n1 \leq j \leq n, is defined by πj(x1,…,xn)=xj\pi_j(x_1, \dots, x_n) = x_j, extracting the jj-th component of any in the product. This notation, sometimes written as projj\mathrm{proj}_j, emphasizes the indexed selection and is standard for finite products to avoid confusion with infinite cases. These projections are surjections onto each factor set, meaning they are surjective provided the sets are non-empty: for any xj∈Xjx_j \in X_j, there exists a (x1,…,xn)(x_1, \dots, x_n) mapping to it by choosing arbitrary elements from the other XiX_i. For illustration, consider X1={a}X_1 = \{a\}, X2={b,c}X_2 = \{b, c\}, X3={1}X_3 = \{1\}. The product X1×X2×X3X_1 \times X_2 \times X_3 includes tuples like (a,b,1)(a, b, 1) and (a,c,1)(a, c, 1). Here, π2((a,b,1))=b\pi_2((a, b, 1)) = b and π3((a,c,1))=1\pi_3((a, c, 1)) = 1, demonstrating how projections isolate specific coordinates while the full encodes the combined information.

Properties

Surjectivity and range

In , the projection function πj:X1×⋯×Xn→Xj\pi_j: X_1 \times \cdots \times X_n \to X_j, defined by πj(x1,…,xn)=xj\pi_j(x_1, \dots, x_n) = x_j for each j=1,…,nj = 1, \dots, n, is surjective whenever the product X1×⋯×XnX_1 \times \cdots \times X_n is nonempty, which holds if each XiX_i is nonempty. To see this, consider any xj∈Xjx_j \in X_j. Since the other sets XiX_i for i≠ji \neq j are nonempty, there exist elements xi∈Xix_i \in X_i for all i≠ji \neq j. The (x1,…,xn)(x_1, \dots, x_n) then lies in the product, and πj(x1,…,xn)=xj\pi_j(x_1, \dots, x_n) = x_j, so every element of XjX_j is attained. The image of πj\pi_j, denoted Im⁡(πj)\operatorname{Im}(\pi_j), is precisely XjX_j, as the surjectivity implies that the range equals the codomain. This follows directly from the definition of the image as {πj(x)∣x∈X1×⋯×Xn}\{ \pi_j(x) \mid x \in X_1 \times \cdots \times X_n \} and the onto property established above. Projections are generally not injective. For example, consider the first projection π1:X×Y→X\pi_1: X \times Y \to X. If YY has at least two distinct elements b≠cb \neq c, then π1((a,b))=a=π1((a,c))\pi_1((a, b)) = a = \pi_1((a, c)) for any a∈Xa \in X, so distinct elements map to the same output. More generally, the fiber (preimage) πj−1(xj)\pi_j^{-1}(x_j) over any xj∈Xjx_j \in X_j is homeomorphic to the product ∏i≠jXi\prod_{i \neq j} X_i, consisting of all tuples that agree with xjx_j in the jj-th coordinate. In the context of finite cardinals, assuming each XiX_i is finite and nonempty, the of each satisfies ∣πj−1(xj)∣=∏i≠j∣Xi∣|\pi_j^{-1}(x_j)| = \prod_{i \neq j} |X_i| for every xj∈Xjx_j \in X_j, reflecting the size of the product excluding XjX_j. This aligns with the overall of the domain being ∣X1×⋯×Xn∣=∏i=1n∣Xi∣|X_1 \times \cdots \times X_n| = \prod_{i=1}^n |X_i|, consistent with surjectivity where each covers the preimages evenly across the . While projections exhibit additional topological properties—such as being open maps in the when the sets are equipped with topologies—the focus here remains on their set-theoretic surjectivity and characteristics./03%3A_Topological_Spaces/3.08%3A_Product_Topology)

Composition and identification

In the context of s, projection functions exhibit specific composition properties that facilitate the definition of projections on multi-factor products using binary projections. For a ternary A×B×CA \times B \times C, the projection πA:(A×B)×C→A\pi_A: (A \times B) \times C \to A is given by the composition πA∘(πA×B×idC)\pi_A \circ (\pi_{A \times B} \times \mathrm{id}_C), where πA×B:(A×B)×C→A×B\pi_{A \times B}: (A \times B) \times C \to A \times B is the projection onto the first factor and πA:A×B→A\pi_A: A \times B \to A is the first binary projection. This composition preserves the surjective nature of the resulting map, as projections are surjective onto their respective coordinate sets. More generally, compositions of projections yield either another projection or the on a coordinate set. For projections πi\pi_i and πj\pi_j on the same nn-fold ∏k=1nXk\prod_{k=1}^n X_k, the composition πi∘πj\pi_i \circ \pi_j is defined only when the of πj\pi_j matches the domain required for πi\pi_i, which occurs precisely when i=ji = j; in this case, it reduces to the identity idXi\mathrm{id}_{X_i} on the ii-th coordinate. Otherwise, direct composition is not applicable, as πj\pi_j maps to a single coordinate set rather than the full product. For instance, composing the first projection on A×B×CA \times B \times C with the identity on B×CB \times C recovers the first projection unchanged. Projections also enable the identification of tuple components through a . In the binary X×YX \times Y, two elements a,b∈X×Ya, b \in X \times Y satisfy a=ba = b πX(a)=πX(b)\pi_X(a) = \pi_X(b) and πY(a)=πY(b)\pi_Y(a) = \pi_Y(b). This extends to finite nn-s in ∏k=1nXk\prod_{k=1}^n X_k, where (x1,…,xn)=(y1,…,yn)(x_1, \dots, x_n) = (y_1, \dots, y_n) πj(x1,…,xn)=πj(y1,…,yn)\pi_j(x_1, \dots, x_n) = \pi_j(y_1, \dots, y_n) for all j=1,…,nj = 1, \dots, n. For the standard Kuratowski (x,y)={{x},{x,y}}(x, y) = \{\{x\}, \{x, y\}\}, the projections recover xx as the unique element of the unique singleton subset and yy as the element in the doubleton not in the singleton, ensuring this equality holds uniquely. In set theory, projections underpin component-wise constructions by allowing definitions that operate independently on each coordinate without invoking recursive procedures. This property supports the axiomatic development of products and functions, as the universal mapping property of Cartesian products—where a pair of functions into the factors uniquely determines a function into the product via projections—relies on such compositions and identifications.

Applications in set theory

Ordered pairs and tuples

In set theory, the ordered pair (a,b)(a, b) is constructed using the Kuratowski definition, which encodes it as the set {{a},{a,b}}\{\{a\}, \{a, b\}\}. This representation ensures that the order is preserved, as (a,b)=(c,d)(a, b) = (c, d) if and only if a=ca = c and b=db = d. The components of the ordered pair are recovered using projection functions defined via set operations. The first projection π1((a,b))\pi_1((a, b)) identifies the singleton set in {{a},{a,b}}\{\{a\}, \{a, b\}\} that is not equal to {a,b}\{a, b\}, and then takes its unique element; formally, π1((a,b))=⋃({{a},{a,b}}∖{{a,b}})\pi_1((a, b)) = \bigcup \big( \{\{a\}, \{a, b\}\} \setminus \big\{ \{a, b\} \big\} \big). The second projection π2((a,b))\pi_2((a, b)) is then π2((a,b))={a,b}∖{a}\pi_2((a, b)) = \{a, b\} \setminus \{a\}, where {a}\{a\} is recovered from the first projection. These binary projections, as defined earlier, allow the unique extraction of aa and bb from the set-theoretic encoding. This construction extends recursively to finite nn-tuples, where an nn-tuple (a1,a2,…,an)(a_1, a_2, \dots, a_n) is defined as a nested sequence of ordered pairs: for n=3n=3, (a,b,c)=((a,b),c)(a, b, c) = ((a, b), c), and in general, (a1,…,an)=((a1,…,an−1),an)(a_1, \dots, a_n) = ((a_1, \dots, a_{n-1}), a_n). The projections for nn-tuples are defined recursively using the binary case: πk((a1,…,an))\pi_k((a_1, \dots, a_n)) applies the appropriate binary projection to the nested structure to extract aka_k. For example, π1((a,b,c))=π1((a,b))\pi_1((a, b, c)) = \pi_1((a, b)) and π3((a,b,c))=π2((a,b,c))\pi_3((a, b, c)) = \pi_2((a, b, c)), with intermediate steps unfolding the nesting. Given the values of all projections π1(t),π2(t),…,πn(t)\pi_1(t), \pi_2(t), \dots, \pi_n(t) for an nn- tt, the original tuple is uniquely determined, as the encoding via nested pairs provides a between the tuple and the of its components. This supports the set-theoretic encoding of finite sequences without assuming primitive ordered structures beyond sets. For instance, in the Kuratowski pair, π1((a,b))=a\pi_1((a, b)) = a and π2((a,b))=b\pi_2((a, b)) = b, achieved through the set operations described above.

Relations and functions

In set theory, a binary relation RR from a set AA to a set BB is defined as a subset of the A×BA \times B. The domain of RR, denoted \dom(R)\dom(R), is the projection of RR onto the first coordinate, given by π1(R)={a∈A∣∃b∈B ((a,b)∈R)}\pi_1(R) = \{a \in A \mid \exists b \in B \ ((a, b) \in R)\}. Similarly, the range of RR, denoted \ran(R)\ran(R), is the projection onto the second coordinate, π2(R)={b∈B∣∃a∈A ((a,b)∈R)}\pi_2(R) = \{b \in B \mid \exists a \in A \ ((a, b) \in R)\}. These projections extract the relevant subsets by applying the projection functions π1:A×B→A\pi_1: A \times B \to A and π2:A×B→B\pi_2: A \times B \to B to the elements of RR, yielding π1(R)={π1(r)∣r∈R}\pi_1(R) = \{\pi_1(r) \mid r \in R\} and π2(R)={π2(r)∣r∈R}\pi_2(R) = \{\pi_2(r) \mid r \in R\}. Functions arise as special cases of binary relations. A function f:A→Bf: A \to B corresponds to a relation Rf⊆A×BR_f \subseteq A \times B such that π1(Rf)=A\pi_1(R_f) = A (ensuring every element of the domain is related to something) and, for each a∈Aa \in A, the set π2(Rf∩({a}×B))\pi_2(R_f \cap (\{a\} \times B)) contains exactly one element (ensuring ). This characterization views functions purely as sets of ordered pairs with the specified projection properties, without invoking additional structure beyond the relation itself. For example, consider the relation R={(1,x),(2,x),(2,y)}R = \{(1, x), (2, x), (2, y)\} where A={1,2}A = \{1, 2\} and B={x,y}B = \{x, y\}. The domain is \dom(R)=π1(R)={1,2}\dom(R) = \pi_1(R) = \{1, 2\}, as both elements of AA appear in the first positions of pairs in RR. The range is \ran(R)=π2(R)={x,y}\ran(R) = \pi_2(R) = \{x, y\}, capturing the distinct second components. Note that RR is not a function, since 2 relates to two distinct elements in BB. The set-theoretic projections on relations provide a basis for similar operations in other fields, such as the projection operator in , which eliminates attributes from relations in ; however, the discussion here remains confined to pure . These operations extend naturally to multi-ary relations using general finite projections, though the binary case suffices for defining domains and ranges of relations and functions.
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.