How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The power set
Definition
Let be a set. By For every set there is exactly one set whose elements are precisely the subsets of there is exactly one set whose elements are precisely the subsets of (Subset , proper subset , and the separation notation ); it is the power set of , written . Thus holds if and only if , and in the class notation of the page,
Remarks
-
Two axioms, not one. The elements of are pinned down by The Axiom of Power Set: together with The Axiom Schema of Separation: for each formula , , because the axiom is assumed here only in its implication form. The axiom ledger for this page: which of the ZFC axioms each construction and each result actually consumes keeps that cost visible.
-
The power set is never empty. always holds, so for every ; in particular rather than . That and the other basic identities are ; and ; if and only if ; ; ; and while only holds.
Depends on
Used by
- For a nonempty index set I: B ∩ ⋃_i ∈ I Aᵢ = ⋃_i ∈ I (B ∩ Aᵢ), B ∪ ⋂_i ∈ I Aᵢ = ⋂_i ∈ I (B ∪ Aᵢ), X ∖ ⋃_i ∈ I Aᵢ = ⋂_i ∈ I (X ∖ Aᵢ), and X ∖ ⋂_i ∈ I Aᵢ = ⋃_i ∈ I (X ∖ Aᵢ) Corollary
- Sets a and b with P(a) ∪ P(b) ⊊ P(a ∪ b) Counterexample
- Choice function Definition
- Equivalence relation, equivalence class, and the quotient set A/∼ Definition
- Filter on a set Definition
- The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) } Definition
- {∅} × {∅,{∅}} listed in full, together with the inclusion in P(P(A ∪ B)) that makes it a set Example
- For any indexed family the product ∏_i ∈ I P(Xᵢ) contains the constant function with value ∅, and ∏_i ∈ I {i} has exactly one element Example
- P(∅) = {∅}, P({∅}) = {∅,{∅}}, and P({∅,{∅}}) listed in full Example
- Singletons define a natural transformation from the identity functor on sets to the covariant power-set functor Example
- For sets A and B the collection of all functions A → B is a set, being a subset of P(A × B) Lemma
- If a ∈ A and b ∈ B then (a,b) ∈ P(P(A ∪ B)) Lemma
- The equivalence classes of an equivalence relation are nonempty, cover A, and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation Lemma
- P(∅) = {∅}; ∅ ∈ P(a) and a ∈ P(a); a ⊆ b if and only if P(a) ⊆ P(b); ⋃ P(a) = a; ⋂ P(a) = ∅; and P(a ∩ b) = P(a) ∩ P(b) while only P(a) ∪ P(b) ⊆ P(a ∪ b) holds Proposition
- The axiom ledger for this page: which of the ZFC axioms each construction and each result actually consumes Remark
- a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c) and a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c); and for a nonempty set F, a ∩ ⋃ F = ⋃ { a ∩ b : b ∈ F } and a ∪ ⋂ F = ⋂ { a ∪ b : b ∈ F } Theorem
- Let ∼ be an equivalence relation on A with quotient map π : A → A/∼, and let f : A → B. There is a function g : A/∼ → B with g ∘ π = f if and only if a ∼ a' implies f(a) = f(a'); and such a g is then unique Theorem
- On a set A, R ↦ R ∖ Δ_A and S ↦ S ∪ Δ_A are mutually inverse bijections between the partial orders on A and the irreflexive, transitive relations on A; R ∖ Δ_A is the strict order of R, and every irreflexive transitive relation is asymmetric Theorem
- X ∖ (a ∪ b) = (X ∖ a) ∩ (X ∖ b) and X ∖ (a ∩ b) = (X ∖ a) ∪ (X ∖ b); and for a nonempty set F, X ∖ ⋃ F = ⋂ { X ∖ a : a ∈ F } and X ∖ ⋂ F = ⋃ { X ∖ a : a ∈ F } Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 6 results over 4 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Power set (Wikipedia) (standard reference, not scraped)
- B. Kaya, MATH 320 Set Theory (METU), Axiom 6 (standard reference, not scraped)
- C. Wilson, A Brief Introduction to ZFC (Chicago REU 2016), §2.3 (standard reference, not scraped)