Power Set Ontology

FLOW ALGEBRA
POWER SET ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Set Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/set-theory/power-set-ontology-2.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)

1. DOMAIN
ontology PowerSetOntology extends SetTheoryOntology
purpose: formalise the collection of all subsets of a set, its structure, laws and computational interpretation.

2. TYPED ENTITIES
entity Set<T> : collection of distinct elements of type T
entity Subset<T> : Set<T> with membership constrained by a parent set
entity PowerSet<T> : Set<Set<T>>
entity EmptySet<T> : Set<T> with cardinality 0
entity UniversalSet<T> : Set<T> specifying the ambient universe when required
entity Cardinality : nonnegative integer for finite sets; cardinal number generally
entity Membership : predicate (element, set) -> Boolean
entity Inclusion : predicate (set, set) -> Boolean
entity Partition : family of nonempty pairwise-disjoint subsets whose union is the base set

3. DEFINITIONS AND OPERATIONS
P(A) := { S | S ⊆ A }
S ⊆ A iff ∀x (x ∈ S -> x ∈ A)
S ∈ P(A) iff S ⊆ A
∅ ∈ P(A)
A ∈ P(A)
P(∅) = {∅}
P({a}) = {∅, {a}}
P({a,b}) = {∅, {a}, {b}, {a,b}} when a ≠ b
P(A) ∩ P(B) = P(A ∩ B)
P(A) ∪ P(B) ⊆ P(A ∪ B) ; equality is not guaranteed
A ⊆ B iff P(A) ⊆ P(B)
P(A) = P(B) iff A = B
P(A) × P(B) is a set of ordered pairs of subsets, not generally P(A × B)

4. CARDINALITY
For finite A, |P(A)| = 2^|A|.
For any set A, |P(A)| = 2^|A| in cardinal arithmetic, and |P(A)| > |A| (Cantor's theorem).
For finite A with n elements, number of k-element subsets = binomial(n,k).
Σ(k=0..n) binomial(n,k) = 2^n.

5. BOOLEAN ALGEBRA
Relative to universe A, (P(A), ∪, ∩, complement_A, ∅, A) is a Boolean algebra.
For S,T ∈ P(A):
S ∪ T ∈ P(A); S ∩ T ∈ P(A); A\S ∈ P(A).
S ∪ ∅ = S; S ∩ A = S.
S ∪ (A\S) = A; S ∩ (A\S) = ∅.
A\(S ∪ T) = (A\S) ∩ (A\T).
A\(S ∩ T) = (A\S) ∪ (A\T).

6. SEMANTIC RELATIONSHIPS
PowerSet --contains_as_element--> Subset
Subset --is_subset_of--> BaseSet
EmptySet --is_element_of--> PowerSet
BaseSet --is_element_of--> ItsPowerSet
PowerSet --has_cardinality--> Cardinality
PowerSet --supports--> BinaryRelationRepresentation
PowerSet --forms--> BooleanAlgebra

7. INFERENCE RULES
R1: IF S ⊆ A THEN infer S ∈ P(A).
R2: IF S ∈ P(A) THEN infer S ⊆ A.
R3: IF A ⊆ B THEN infer P(A) ⊆ P(B).
R4: IF |A| = n AND A finite THEN infer |P(A)| = 2^n.
R5: IF S,T ∈ P(A) THEN infer S ∪ T ∈ P(A) AND S ∩ T ∈ P(A).
R6: IF S ∈ P(A) THEN infer A\S ∈ P(A).

8. VALIDATION
V1: Every member of P(A) must itself be a set.
V2: Every S ∈ P(A) must satisfy ∀x∈S, x∈A.
V3: For finite A, enumerate unique subsets and verify count 2^|A|.
V4: Distinguish ∅ (empty set) from {∅} (singleton containing the empty set).
V5: Distinguish x ∈ A from {x} ⊆ A and from {x} ∈ P(A).
V6: Do not assume P(A ∪ B) = P(A) ∪ P(B).
V7: Do not assume a finite enumeration algorithm can exhaust an infinite power set.

9. COMPUTATIONAL MODEL
input: finite Set<T> A
output: PowerSet<T> P(A)
algorithm: start result={∅}; for each element a∈A, add S∪{a} for each existing S in a snapshot of result.
time_complexity: Θ(n·2^n) for explicit subset materialisation of n-element input.
space_complexity: Θ(n·2^n) for explicit materialisation of all subset elements; Θ(2^n) subset references excluding element storage.
warning: exponential growth limits practical enumeration.

10. SEMANTIC_EQUIVALENCE
power set ≡ set of all subsets
powerset ≡ power set
P(A) ≡ 2^A when 2^A denotes {0,1}-valued functions on A via characteristic-function correspondence (canonical bijection, not literal identity in every formalisation)

11. CONFIDENCE
mathematical_definitions: 1.00 (standard set theory)
source_page_alignment: unverified (live page not inspected)
confidence_scope: formal mathematical claims only; not a claim of page-specific transcription.

12. FLOW_HASH
hash_algorithm: SHA-256
hash_scope: UTF-8 bytes of this document excluding any externally appended digest field
hash_value: calculate on publication or ingestion

13. UPDATE_MODEL
versioning: semantic
update_triggers: definition correction; notation clarification; added proof; computational refinement
validation_policy: preserve mathematical consistency and regenerate hash on changes

14. AI_CONSUMPTION
representation: typed ontology and deterministic mathematical rules
retrieval_keys: power set, powerset, subsets, cardinality, Cantor theorem, Boolean algebra
reasoning_tasks: subset-membership checks; finite subset enumeration; combinatorial counting; logical equivalence
safety_constraint: verify finite-set assumptions before enumeration and cardinality computations
provenance: Kireth Semantic Library source URL above; formalisation prepared independently pending page verification