I'm studying algebraic specification for formal software development. In the book I'm reading (Foundations of Algebraic Specification and Formal Software Development) the following definitions are given:
A Σ -algebra A consists of:
- an S-sorted set |A| of carrier sets (or carriers); and
- for each $f : s_1 × · · · × s_n → s$ in Σ , a function (or operation) $(f : s_1 × · · · × s_n →s)_A : |A|_{s1} × · · · × |A|_{s n} → |A|_s$
And
Let A and B be Σ -algebras. B is a subalgebra of A if:
- |B| ⊆ |A|; and
- for $f : s_1 × · · · × s_n → s$ in Σ and $b_1 ∈ |B|_{s1} , . . . , b_n ∈ |B|_{sn} , f_B (b_1 , . . . , b_n ) = f_A (b_1 , . . . , b_n )$.
Where $Σ = (S,Ω)$, with $S$ a set of sort names, and $Ω$ an indexed family of operation names, indexed by $(s^*,s) \in (S^*,S)$
And from another book I found:
Given a family G of sets $G_s \subseteq A_s$ for $s \in S$. Then a subalgebra $B$ of $A$ is called generated by $G$ if $G_s \subseteq B_s$ for $s \in S$ and there is no proper subalgebra $B'$ of $B$ which contains $G$, i.e. $G_s \subseteq B'_s$ for $s \in S$.
In the book there are two exercises:
1)If $Ω_{ε,s} \neq ∅$ for some s ∈ S, then there are no (S, Ω)-algebras having an empty carrier of sort $s$. Characterise signatures for which all algebras have non- empty carriers of all sorts.
2)Let A be a Σ -algebra. Show that the intersection of any family of (carriers of) subalgebras of A is a (carrier of a) subalgebra of A
My first question is: what happens if I have an operation defined in the signature (Σ),for example $f: a × b → c $, and define an algebra with non-empty carrier sets for $a$ and $b$? Would that imply that the carrier set of $c$ must be non-empty? What happens to the "totality" of $f$? Or is that only for constant functions as the exercise 1) states? And in case all the carrier sets are empty, would that be valid algebra (the function $f$ would be defined as just empty)? Or that breaks the "totality" of the function in the algebra?
My second question is: In the last definition it's not stated, but does $B'$ need to be different from $G$? What will cause the inexistence of $B'$ as a proper subalgebra? Will it be due to incoherences in the algebra caused by removing an element from any carrier set? For example having just one element in the carrier set and a constant function that has as a result a element of that sort, so removing that element from the carrier sort would result in that constant function to be incoherent. Are there other scenarios?
Finally, I'd appreciate any hints for proving the second exercise.
For (1), if $a, b$ are interpreted as non-empty sets but $c$ is empty, then there is no total function to interpret $f$. ( If you consider semantics using partial functions instead of total functions, then this is OK. Likewise if you consider semantics in a category. )
An algebra with nullary symbols, i.e., constants, for every sort cannot have any empty carries. Indeed, if $a$ is interpreted as the empty set ∅ and we have a constant $e : a$, then we must interpret $e$ as a value of ∅, which is impossible since ∅ has no values.
Hence, we can interpret all carriers as empty only if there are no constant symbols.
For (2), note that $G$ is a family of sets whereas $B'$ is an algebra. Perhaps you meant to ask “Does $B′$ need to be different from $B$”? ---Since $B$ is the algebra ‘containing the family $G$’. In that case, then “yes” since we are speaking of “proper subalgebras” which refers to an irreflexive relation, like “<” for arithmetic.
One says “ℬ is the subalgebra of generated by $G$” to mean that ℬ is the smallest subalgebra of that contains $G$, and so removing anything from it will disqualify it as a subalgebra or it may no longer contain $G$.
For example, consider Σ with one sort τ and one symbol $\_{}′ : τ → τ$, “tick”.
Then, ⟦τ⟧ = ℕ and $⟦\_{}′⟧ = (x ↦ x)$ is a Σ-algebra. Call this algebra .
We have many other Σ-algebras, for each $n$, call it , and it has $⟦τ⟧ = \{0, 1, 2, ..., n-1\}$ and $⟦\_{′}⟧ = (x ↦ x)$. That is, for each $n$, the algebra has as carrier an $n$ element set and the tick operation is interpreted as the identity function. Each is clearly a subalgebra of .
Exercise: What $G$ generates , as a subalgebra of ?
Explicitly, the subalgebra of is given by ⟦τ⟧ = ∅ and $⟦\_{}′⟧$ being the empty function ---i.e., the identity function on the empty set.
Exercise: Why is not generated by $G$, from the previous exercise?
Finally, let ℳ be the algebra with ⟦τ⟧ = ℕ and $⟦\_{}′⟧ = (x ↦ 1 + x)$. What happens if we use ℳ instead of everywhere above? ;-)