GLOBAL KNOWLEDGE ARK

Reference library

Foundations

Explore concepts, laws, equations and methods, with clear explanations of their use and sources. Choose an area of study or find a specific entry.

Connections

Reference entries can connect several areas of study. The same entry may appear in more than one area.

Explore relationships within this area of study and its connections to other areas.

Showing 1–50 of 464 relationships

Scientific relationships · 50 / 460

The relationship type describes the connection. Its linked statements, sources and conditions define the scope.

  1. Uses definition
    Relationship sources · 1

    Linked statements

    • The cardinality of a finite set is its number of distinct elements. The empty set has cardinality zero.
  2. Uses definition
    Relationship sources · 1

    Linked statements

    • A claim that P(x) holds for every x in a specified domain is false if an element of that domain makes P(x) false. Testing some successful examples does not establish the claim for an infinite domain.
  3. Uses definition
    Relationship sources · 1

    Linked statements

    • Axioms are assumptions accepted within a mathematical system. A proof derives a proposition from those assumptions and previously established results through permitted logical deductions.
  4. Uses definition
    Relationship sources · 1

    Linked statements

    • If P(0) holds and P(n) implies P(n+1) for every nonnegative integer n, mathematical induction establishes P(n) for every nonnegative integer n.
  5. Uses definition
    Relationship sources · 1

    Linked statements

    • A function f:A→B assigns exactly one element of B to each element of A. A is the domain, B the codomain, and the range consists of outputs actually attained.
  6. Uses definition
    Relationship sources · 1

    Linked statements

    • A complex number is written z=a+bi with real a and b and i²=−1. Its real part is a and its imaginary part is b. It is represented by (a,b) in the complex plane; addition combines the two components and multiplication uses i²=−1.
  7. Uses definition
    Relationship sources · 1

    Linked statements

    • A real linear map T:ℝⁿ→ℝᵐ satisfies T(αu+βv)=αT(u)+βT(v). After choosing input and output bases, it is represented by an m×n matrix A: the output coordinates are y=Ax, with yᵢ=Σⱼ₌₁ⁿaᵢⱼxⱼ.
  8. Uses definition
    Relationship sources · 1

    Linked statements

    • A real linear map T:ℝⁿ→ℝᵐ satisfies T(αu+βv)=αT(u)+βT(v). After choosing input and output bases, it is represented by an m×n matrix A: the output coordinates are y=Ax, with yᵢ=Σⱼ₌₁ⁿaᵢⱼxⱼ.
  9. Uses definition
    Relationship sources · 1

    Linked statements

    • The limit of f(x) as x approaches a is L if every positive output tolerance ε admits a positive input tolerance δ such that 0 < |x−a| < δ implies |f(x)−L| < ε.
  10. Uses definition
    Relationship sources · 1

    Linked statements

    • A probability space consists of an outcome set Ω, a sigma-algebra of events and a probability P. Probabilities are nonnegative, P(Ω)=1, and the probability of a countable union of pairwise disjoint events equals the sum of their probabilities.
  11. Uses definition
    Relationship sources · 1

    Linked statements

    • For P(B)>0, the conditional probability of A given B is P(A∩B)/P(B). Events A and B are independent when P(A∩B)=P(A)P(B).
  12. Uses definition
    Relationship sources · 1

    Linked statements

    • For a discrete real-valued random variable X with probabilities p(x), its finite expected value is Σx xp(x) when Σx |x|p(x) is finite. The expected value need not itself be a possible observed value.
  13. Uses definition
    Relationship sources · 1

    Linked statements

    • For a finite discrete distribution with probabilities pᵢ, Shannon entropy is −Σᵢ pᵢ log₂ pᵢ, measured in bits. A zero-probability term contributes zero by its limiting value.
  14. Uses definition
    Relationship sources · 1

    Linked statements

    • There is no algorithm that always terminates and correctly decides, for every program-input pair in a Turing-complete computation model, whether that program eventually halts on that input.
  15. Uses definition
    Relationship sources · 1

    Linked statements

    • For nonnegative cost functions, T(n)=O(g(n)) means there are constants c>0 and n₀ such that T(n)≤cg(n) for every n≥n₀. A time or space complexity bound must specify the computation model, input-size measure and case being analysed.
  16. Uses definition
    Relationship sources · 1

    Linked statements

    • In classical first-order logic, ∀x φ holds when φ holds for every domain element; ∃x φ holds when it holds for at least one. Free variables require an assignment.
  17. Uses definition
    Relationship sources · 1

    Linked statements

    • ZFC combines extensionality, empty-set, pairing, union, power-set, infinity, foundation and choice axioms with separation and replacement schemas. Separation selects elements from an already given set.
  18. Uses definition
    Relationship sources · 1

    Linked statements

    • A set is countably infinite if it has a bijection with the natural numbers. Here, countable means finite or countably infinite, equivalently admitting an injection into N.
  19. Uses definition
    Relationship sources · 1

    Linked statements

    • A relation on X is an equivalence relation when it is reflexive, symmetric and transitive. Its classes [x] = {y ∈ X: y ∼ x} partition X.
  20. Uses definition
    Relationship sources · 1

    Linked statements

    • Every nonconstant polynomial with complex coefficients has a complex root. Repeated factorization expresses a degree-n polynomial as a product of n linear factors times its leading coefficient, counting multiplicity.
  21. Uses definition
    Relationship sources · 1

    Linked statements

    • A metric d on X is nonnegative, vanishes exactly when its arguments coincide, is symmetric and satisfies the triangle inequality. Open balls contain points at distance less than a positive radius.
  22. Uses definition
    Relationship sources · 1

    Linked statements

    • A topology on X contains ∅ and X and is closed under arbitrary unions and finite intersections. A subset is closed when its complement in X is open.
  23. Uses definition
    Relationship sources · 1

    Linked statements

    • For a linear map T:V→W with finite-dimensional V, dim V = dim ker T + dim im T. Rank is the image dimension and nullity is the kernel dimension.
  24. Uses definition
    Relationship sources · 1

    Linked statements

    • Every real m×n matrix A admits A=UΣVᵀ with orthogonal U,V and rectangular diagonal Σ having nonnegative entries. These singular values are square roots of eigenvalues of AᵀA, with zero padding as needed.
  25. Uses definition
    Relationship sources · 1

    Linked statements

    • On a measure space, the integral of a nonnegative measurable f is the supremum of integrals of nonnegative simple functions below f. A real measurable f is integrable when ∫|f|dμ<∞; then ∫f=∫f⁺−∫f⁻.
  26. Uses definition
    Relationship sources · 1

    Linked statements

    • For f:U⊂Rⁿ→Rᵐ with U open, f is differentiable at a if a linear map B satisfies ‖f(a+h)−f(a)−Bh‖/‖h‖→0 as h→0. This B is the total derivative Df(a).
  27. Uses definition
    Relationship sources · 1

    Linked statements

    • For a constant real n×n matrix A, x′=Ax with x(0)=x₀ has the unique global solution x(t)=eᵗᴬx₀, where eᵗᴬ=Σₖ₌₀∞ tᵏAᵏ/k! converges for every real t.
  28. Uses definition
    Relationship sources · 1

    Linked statements

    • For a real random variable X, F_X(x)=P(X≤x) is its cumulative distribution function. Discrete laws use probability masses; absolutely continuous laws use a nonnegative density integrated over events.
  29. Uses definition
    Relationship sources · 1

    Linked statements

    • For iid real variables with mean μ and finite variance, the sample mean X̄ₙ converges in probability to μ: for every ε>0, P(|X̄ₙ−μ|>ε)→0.
  30. Uses definition
    Relationship sources · 1

    Linked statements

    • For finite random variables X,Y, I(X;Y)=Σₓ,ᵧ p(x,y)log₂[p(x,y)/(p_X(x)p_Y(y))]=H(X)−H(X|Y). It is nonnegative and zero exactly when X and Y are independent.
  31. Uses definition
    Relationship sources · 1

    Linked statements

    • For an iid finite-alphabet source, fixed-length block schemes at rates above H(X) bits per symbol can have block error tending to zero. At a fixed rate below H(X), block error tends to one.
  32. Uses definition
    Relationship sources · 1

    Linked statements

    • For a finite discrete memoryless channel p(y|x), C=max_pₓ I(X;Y) bits per channel use. Rates below C allow vanishing average block error; rates above C do not.
  33. Uses definition
    Relationship sources · 1

    Linked statements

    • Hamming distance counts differing coordinates of equal-length words. A binary block code with minimum distance 2t+1 can correct up to t bit substitutions by nearest-codeword decoding and detect up to 2t substitutions by codeword membership.
  34. Uses definition
    Relationship sources · 1

    Linked statements

    • TCP provides a connection-oriented, in-order byte stream using sequence numbers, per-segment checksums and retransmission. Application write boundaries need not correspond to received segment or read boundaries.
  35. Uses definition
    Relationship sources · 1

    Linked statements

    • A≤ₘB means a total computable f maps every input w so that w∈A iff f(w)∈B. If B is decidable, so is A; hence undecidable A with A≤ₘB implies undecidable B.
  36. Uses definition
    Relationship sources · 1

    Linked statements

    • P contains decision problems solved by a deterministic algorithm in time polynomial in input length. NP contains problems whose yes instances admit polynomial-size certificates verified in polynomial time, with no accepted certificate for no instances. P⊆NP.
  37. Uses definition
    Relationship sources · 1

    Linked statements

    • A decision problem B is NP-hard when every problem in NP has a polynomial-time reduction to B. B is NP-complete when it is also in NP. A polynomial algorithm for any NP-complete problem would give polynomial algorithms for all NP problems.
  38. Uses definition
    Relationship sources · 1

    Linked statements

    • BPP consists of decision languages with a probabilistic polynomial-time algorithm whose error is at most 1/3 on every input. Independent repetition and majority voting reduce a fixed error below 1/2 to any chosen positive constant.
  39. Uses definition
    Relationship sources · 1

    Linked statements

    • A stack removes the most recently added item; a queue removes the earliest. A dictionary supports key lookup, insertion and deletion. Arrays offer constant-time indexed access in a word-RAM model, while linked-list traversal to an arbitrary index takes linear time.
  40. Uses definition
    Relationship sources · 1

    Linked statements

    • A loop proof establishes an invariant initially, preserves it through each guarded iteration, and uses it with the false guard to derive the postcondition. Total correctness also requires termination, for example a nonnegative integer variant that strictly decreases.
  41. Uses definition
    Relationship sources · 1

    Linked statements

    • Sorting n distinct keys by binary comparisons has n! possible orders. Its decision tree therefore needs worst-case depth at least ⌈log₂(n!)⌉, which is Ω(n log n).
  42. Uses definition
    Relationship sources · 1

    Linked statements

    • BFS explores successive edge-distance layers; DFS follows unvisited neighbors and backtracks. With adjacency lists and constant-cost visited checks, full traversal runs in O(|V|+|E|). BFS yields unweighted shortest distances; DFS need not.
  43. Uses definition
    Relationship sources · 1

    Linked statements

    • BFS finds shortest paths measured by number of edges in an unweighted graph. Dijkstra's algorithm computes single-source minimum-weight distances when every edge weight is nonnegative, repeatedly settling the smallest tentative distance.
  44. Uses definition
    Relationship sources · 1

    Linked statements

    • An n-ary relation R⊆D₁×⋯×Dₙ is a set of tuples. A table can represent this model: rows are tuples and columns draw values from their declared domains.
  45. Related to
    Relationship sources · 1

    Linked statements

    • For normalized discrete microstate probabilities, Gibbs entropy is S = −k_BΣ_i p_i ln p_i, using natural logarithms and the convention 0 ln 0 = 0.

    Statistical entropy is connected to thermodynamic entropy under an appropriate macroscopic statistical model, not for every arbitrary probability list.

  46. Related to
    Relationship sources · 1

    Linked statements

    • In finite dimensions, a density operator is Hermitian, positive semidefinite and has trace one. A pure state has ρ = |ψ⟩⟨ψ|; mixtures have ρ = Σ_j p_j|ψ_j⟩⟨ψ_j|.

    Pure and statistical quantum states determine observable outcome statistics.

  47. Uses definition
    Relationship sources · 1

    Linked statements

    • For specified finite-dimensional subsystems, the joint space is H_A⊗H_B. A pure state is entangled when it cannot be written as ψ_A⊗ψ_B; its subsystem state is obtained by partial trace.

    A specified pure bipartite state yields a reduced density operator by partial trace.

  48. Related to
    Relationship sources · 1

    Linked statements

    • Ordinary bosonic wave functions are symmetric and fermionic wave functions antisymmetric under simultaneous exchange of the complete coordinates and spin labels of two identical particles.

    Multiparticle states must respect exchange of complete identical-particle labels; an arbitrary distinguishable-factor model alone does not impose this.

  49. Uses definition
    Relationship sources · 2

    Linked statements

    • Monte Carlo propagation draws input vectors from their assigned joint distribution and evaluates the measurement model. The resulting output sample estimates its distribution, central value, uncertainty and coverage interval.

    Joint input samples are passed through a valid measurement model, retaining dependencies and numerical tolerance.

  50. Uses definition
    Relationship sources · 1

    Linked statements

    • Differentiable real functions satisfy (fg)′=f′g+fg′ and (g∘f)′=(g′∘f)f′. Where g≠0, (f/g)′=(f′g−fg′)/g².