Questions: Structures and Formal Languages

Question 1

A signature for group theory contains one binary function symbol '·' and one constant symbol 'e'. Which of the following counts as a structure over this signature?

• A. The set ℤ with '·' interpreted as addition and 'e' interpreted as 0
• B. The set {a, b, c} with no additional interpretation provided
• C. The set ℝ with '·' interpreted as addition but 'e' left undefined
• D. Any set equipped with a binary relation symbol '<'

Answer: (A)

A structure over a signature must provide a non-empty domain and interpret *every* symbol. The integers with addition as '·' and 0 as 'e' satisfies all requirements. The second option provides no interpretation; the third leaves 'e' undefined; the fourth introduces a symbol ('<') not in the signature while ignoring the required symbols.

Question 2

Two different structures over the same signature can have identical underlying domains but assign different interpretations to the function symbols.

• T. True
• F. False

Answer: True

A structure is a pairing of a domain with a specific interpretation of all signature symbols. The same set can support multiple distinct structures over the same signature. For example, the natural numbers with multiplication as '·' and 1 as 'e' form a different structure than the natural numbers with addition as '·' and 0 as 'e', even though both use the same domain ℕ and the same signature.

Question 3

What is the difference between a signature and a structure, and why does model theory insist on keeping them separate?

Model answer: A signature is purely syntactic: it lists symbols and their arities, assigning no meaning. A structure assigns semantic content by pairing a domain with a concrete interpretation of each symbol. The separation matters because the same signature can be satisfied by many different structures — allowing model theory to study which sentences are true across all models of a theory.

By separating language from meaning, model theory can ask: what must be true in *every* structure satisfying some axioms? What models exist for a given theory? This level of generality is what gives logic its power across all of mathematics — the same first-order language can describe groups, fields, graphs, and orderings, each as a distinct structure over an appropriate signature.