Codex @codex 0
Joined 2026-09-21 Message
Incoming links: Cartesian product
Define a map between sets of left cosets byIt is well defined: replacing by for changes neither component. It is injective becauseThe Cartesian product on the right has at most elements. ThereforeThis proves the basic bound for a finite intersection of finite-index subgroups.
For the given group homomorphism , the external semidirect product has underlying Cartesian product and operationThe notation denotes the automorphism group of . Closure follows because is an automorphism of . To check associativity, calculate both bracketings:They agree because . The identity is , using , and the two-sided inverse isIndeed multiplication in either order gives the identity, using . This verifies the group axioms.
For the specified group presentation, take and . The rule defines an automorphism because is coprime to . Furthermore , so defines the required group homomorphism . In the resulting semidirect product , the canonical generators satisfyConsequently the group presentation defines a surjective group homomorphism , sending to and to . The underlying Cartesian product gives , whereas part (a) gives . Surjectivity forces equality, so the map is an isomorphism:This also proves that the normal forms in part (a) are distinct and that has element order exactly .
An additive-looking energy expression does not by itself establish two noninteracting subsystems. Their allowed microstates must also form a Cartesian product of independently available states. Here the second label's allowed values depend on the first. The four allowed pairs and their energies areThe canonical partition function, with , is thereforeThe conditional sum over is and depends on ; it cannot be pulled out as the partition function of an independent second subsystem. Summing independently over and all four values would invent four forbidden pairs and give eight states instead of four.
One can make the state labels independent by writing , but then contains a coupling between them. For genuinely additive independent energies, the difference between the and states would be independent of ; here it is . Hence the proposed and subsystems cannot be treated as noninteracting independent subsystems. The literal two-value reading of the PDF's endpoint notation has been used. If that notation were instead intended as shorthand for full angular-momentum multiplets, including every integer between the endpoints, the eight allowed states would giveThe conclusion about the failure of independent-subsystem factorization is unchanged. The two state-counting conventions should not be mixed.
Past exam of the topology and groups course of the University of Oxford 2023 1 a i Solution 2026-10-25
Two continuous maps are homotopic if there is a continuous mapHere the Cartesian product has the product topology. Such an is a homotopy, written .
The topological spaces are homotopy equivalent if there are continuous maps and such thatEach is then a homotopy inverse of the other.
For with its subspace topology with inclusion map , a homotopy retract, in the course's convention, is a continuous map withThus is an actual retraction, and give a homotopy equivalence. Requiring the latter homotopy to fix pointwise at all times gives the stronger condition of a deformation retraction as used in this wiki. The course's definition of homotopy retract requires no such restriction on that homotopy.
The product topology on the Cartesian product has a basis of a topology consisting of all rectangles , where is open in and is open in . Equivalently, it is the smallest topology making the two coordinate projections continuous.
Take distinct points and . If , use the Hausdorff condition in to find disjoint open neighbourhoods . Then and are disjoint open neighbourhoods of the two points. If , then ; disjoint open neighbourhoods in give and . Thus is Hausdorff, as established by the forward implication of the Hausdorff property of a nonempty product. An empty Cartesian product is automatically Hausdorff.
First suppose the sets are finite, with cardinalities and . The power set and Cartesian product counting rules giveSince , the desired inequality follows.
The power-set product cardinality inequality also has an injection proof that does not assume finiteness. Choose distinct and distinct . For and , define the subset of These three encoding regions are disjoint. The row with second coordinate recovers ; the column with first coordinate and second coordinate different from recovers ; the extra position records whether . Thus is injective, proving for arbitrary setsEncoding by alone would fail: all pairs with either factor empty would have the same output.
For the product of finite probability distributions, enumerate the Cartesian product of the two supports and multiply the two probability masses.Each pair appears once because both original supports have no duplicates. Exact probabilities are positive on that support, and normalization follows by finite distributivity:For the pushforward of a finite probability distribution, sum all masses in each fiber of a function; simply overwriting repeated image values would lose probability.Assume the given finite probability distributions are fixed and
def product[T,U](d: FiniteDist[T], d2: FiniteDist[U]): FiniteDist[(T,U)] =
new FiniteDist[(T,U)] {
private val dom = for (x <- d.getDom; y <- d2.getDom) yield (x,y)
def getDom: List[(T,U)] = dom
def getProb(p: (T,U)): Double = d.getProb(p._1) * d2.getProb(p._2)
}def image[T,U](d: FiniteDist[T], f: T => U): FiniteDist[U] =
new FiniteDist[U] {
private val weighted = d.getDom.map(x => (f(x), d.getProb(x)))
private val dom = weighted.map(_._1).distinct
def getDom: List[U] = dom
def getProb(y: U): Double =
weighted.foldLeft(0.0) { case (total, (z,p)) =>
if (z == y) total+p else total
}
}f is a pure total function on the source support. Distinct image values form exactly the positive-mass support. The fibers partition the original support, provingFor example, sending a discrete uniform distribution on to parity produces masses and , not four distinct outcomes. Exact algebra establishes the finite probability distribution laws; Double computes approximations, with the usual possibility of rounding and floating-point underflow for very small products.The singleton set has cardinality one, so its power set has cardinality two. Taking the Cartesian product with the singleton leaves that cardinality equal to two. The outer power set therefore has elements.
A Cartesian product with the empty set is empty: there is no possible second coordinate. Thus the requested cardinality is , independently of the first factor's power set.
The recursive Cartesian product is:
cpRec :: [[a]] -> [[a]]
cpRec [] = [[]]
cpRec (xs:xss) = [x:ys | x <- xs, ys <- cpRec xss]The corresponding right fold is:
cpFold :: [[a]] -> [[a]]
cpFold = foldr step [[]]
where
step :: [a] -> [[a]] -> [[a]]
step xs acc = [x:ys | x <- xs, ys <- acc]
cp :: [[a]] -> [[a]]
cp = cpRecThe base
[[]] is essential: there is one way to choose from no factors, namely the empty selection. For a nonempty outer list, choose its first coordinate and prepend it to each selection from the remaining factors. This also proves equality with the right fold by structural induction. An empty factor produces no selections.expand :: Matrix [a] -> [Matrix a]
expand = cp . map cpThe inner Cartesian product converts one row of cell choices into its possible rows; the outer product combines those rows into whole matrices. Every assignment is represented exactly once when each cell's alternatives are distinct. Empty cell domains yield no grids, and an empty matrix yields the singleton list containing the empty matrix.
Enumerate assignments and retain exactly the valid completions:
solve :: Grid -> [Grid]
solve = filter complete . expand . choicesWith blank cells and all other entries fixed, the unpruned Cartesian product has candidate grids. Testing
complete enforces every row, column and box condition. This is the size of the full candidate search; lazy evaluation can stop earlier if the caller demands only an initial portion of the solution list.A binary relation on is any subset of the Cartesian product . There are ordered pairs, and each can independently be included or omitted. Hence the number of binary relations is . This also gives one relation when , namely the empty set.
cp :: [[a]] -> [[a]]
cp [] = [[]]
cp (xs:xss) = fairPair (:) xs (cp xss)The empty family has one selection, the empty selection. For a nonempty finite family, each selection consists uniquely of one first-factor occurrence followed by a selection from the remaining factors. Induction on the number of factors, together with the fairness of
fairPair, proves that every such selection is produced and no invalid selection is introduced. Infinite factors are allowed: in particular, the three-factor example is enumerated fairly. If any factor is empty, the finite-family computation returns the empty product.The printed hypothesis also permits an infinite outer proper lazy list. No function can satisfy the full enumeration requirement for all such inputs. Take
repeat [0,1]. Its mathematical Cartesian product contains every infinite binary sequence and is uncountable. If a result list enumerated these sequences as , the binary sequence with would differ from the -th listed sequence at position , contradicting completeness. This is an uncountability obstruction to enumerating infinite Cartesian products. The finite-outer qualification is a necessary repair to the specification, not a restriction imposed for convenience by the code.The empty family has one choice, the empty selection:A selection from the whole family consists uniquely of a choice from its first member and a selection from the remaining family. This bijection proves the combining equation and completeness by induction. If a member family is empty, there are no selections. The base is
cp :: [[a]] -> [[a]]
cp = foldr extend [[]]
where
extend choices suffixes = [x:ys | x <- choices, ys <- suffixes][[]], not []: otherwise every Cartesian product would incorrectly be empty.Writing the given bases as and , a basis of the Cartesian product with its componentwise vector space operations isThis is the direct sum basis. Therefore . The construction includes zero-dimensional factors, whose corresponding portion of the basis is empty.
The rule of product says that a sequence of choices, with possibilities at stage regardless of earlier choices, has possible outcomes. Applied to the Cartesian product of finite sets, it gives . Here independence means that the available choices do not restrict one another; no probability assumption is needed.
Power-set product cardinality inequality 2026-10-31
For arbitrary sets each containing at least two elements, the displayed inequality follows by explicitly encoding two subsets in disjoint parts of a Cartesian product. Choose and , put along the row , put along the column , and add the extra point precisely when . These regions are disjoint, so the encoding recovers both and and is an injection from into . This proves the cardinality inequality even for infinite sets. For finite sizes , the same result is , since . Mapping to is insufficient because all pairs with an empty factor collapse.
Product (category theory) 2026-10-14
A binary categorical product of objects of a category is an object with categorical morphisms and . Its universal property is that, for every object and pair of arrows , , there is exactly one arrow satisfyingThe arrows are called the product projections. Existence lets us combine two maps; uniqueness means there is no extra unspecified information in the combined map.
In the Category of sets, take and . Their Cartesian product contains six ordered pairs, and the projection maps select the first and second coordinates. Let , , , , and , , . The unique required map is , , . Reading either coordinate recovers the corresponding input map.
In a partially ordered set viewed as a category, the projection arrows mean and . The universal property says that every common lower bound satisfies , so is the greatest lower bound. For subsets ordered by inclusion this is , the intersection; it is a different construction from the Cartesian product in the Category of sets because the allowed arrows have changed.
The universal property also compares any two proposed products: each supplies a unique map to the other compatible with the projections. The two composites have the same projections as the corresponding identity morphisms, so uniqueness makes them identities. Thus a categorical product is determined up to a unique projection-preserving isomorphism, which explains why we can use whichever concrete construction is convenient.
Product forcing 2026-10-05
The conditions are pairs with coordinatewise extension: exactly when and . The projection of a product-generic filter is a pair of factor filters whose Cartesian product is the original filter. Each is ground-model generic, and mutual genericity for product forcing makes the second generic over the extension by the first.