1
$\begingroup$

$\exists \mathbb{1}.\forall \left(A,\left(R^{\mathcal A}\right)_{R\in \sigma}\right). \exists f:\mathcal A \rightarrow_{hom} \mathbb{1}.$

Or in Words: Let $\sigma$ be a signature.

Show that a $\sigma$-structure $\mathbb{1}$ exists so that for any $\sigma$-structure $\mathcal A$ exists a (unique) homomorphism from $\mathcal A$ to $\mathbb 1$. This 1-structure is supposed to be unique upto isomorphism.

The tutorial in class concluded with $\mathbb 1 = (\{1\},(\{1\}^k)_{R\in\sigma.k=\operatorname{arity}(R)})$ (edit: not exactly like that, but all symbols of $\sigma$ interpreted in $\mathcal 1$ would have to be there ...). However, I had thought that would be too simple, if an order relation, eg. $>$ was concerned, $1>1$ shouldn't be in $\sigma$, although that's my own notion as the script is quite sparse. There, a signature just contains ''symbols'', which is my problem, I guess, as all given definitions seem to be met.

I imagine instead a homomorphism to map substructures to a universal structure, that contains all admissible objects and relations (or functions etc.): $\exists U_1. \forall x. x \in U_1$ together with all possible relations over that set.

Now, there doesn't seem to exist a bijection between the two solutions, so only one can be correct. I assume that I am wrong. But how?

We didn't chose any fundamental set theory, so I suppose the setup wasn't rigid enough and I ran into some kind of Russel's paradox. Books on abstract algebra are somewhat intimidating so I'd appreciate a quick heads up.

Now the actual question, if you will, is this homomorphism called a universal property? Or perhaps an initial object?

$\endgroup$
  • 3
    $\begingroup$ There is no problem with $1<1$: as you note, these are only relation symbols in this context, i.e. no further axioms are posed on them. $\endgroup$ – Berci Jun 5 '17 at 20:21
  • 1
    $\begingroup$ @vectorious There's two questions there: why would one use the specific symbol "$<$" to refer to something that's not even a preorder, and why would mathematicians care about arbitrary structures in general? For the first one, the point is that it's often useful to consider a specific class of structures in a broader context. E.g. every linear order can be thought of as a directed graph, where there's an arrow from $a$ to $b$ if $a<b$. In this context, for simplicity we keep using the same symbol, to avoid the tedium of frequently introducing new symbols which behave just as old ones. (cont'd) $\endgroup$ – Noah Schweber Jun 8 '17 at 15:44
  • 1
    $\begingroup$ For the second question, well, very strange-looking structures can turn out to be surprisingly interesting! For instance, consider the language consisting of three binary function symbols $+, -, f$ and a constant symbol $0$. The class of structures satisfying the law $$f(a_2, a_3)-f(a_1+a_2, a_3)+f(a_1, a_2+a_3)-f(a_1, a_2)=0$$ may seem really artificial; however, this law turns out to be very important - it's the 1-cocycle condition in group cohomology! Of course working in maximum generality isn't always interesting, but at the same time it's often something we want to do. $\endgroup$ – Noah Schweber Jun 8 '17 at 15:48
  • 1
    $\begingroup$ - but what guarantees this, given that all the $\Sigma$-structure is forgotten at $\mathcal{C}$? If we avoid this by not allowing any morphisms between structures in different signatures, then we don't have a terminal object. If you really want something broader than the category of $\Sigma$-structures for a given $\Sigma$, the right thing to do in my opinion is look at the category of pairs $(\mathcal{A},\Sigma)$ where $\mathcal{A}$ is a $\Sigma$-structure; there's a natural notion of morphism here (hint: send symbols to symbols of the same type), (cont'd) $\endgroup$ – Noah Schweber Jun 9 '17 at 20:25
  • 1
    $\begingroup$ and the terminal object in this category is the one-element structure in the language consisting of exactly one symbol of each type. $\endgroup$ – Noah Schweber Jun 9 '17 at 20:26
3
$\begingroup$

It's clear that $\mathbb{1}$ has the desired properties - as you note, although there are relation symbols that we're used to having negative properties (like $<$, which "should" be irreflexive), in this context symbols are "contextless" - all a binary relation symbol like "$<$" denotes is, well, a binary relation, and could indeed be reflexive.

So the real question is, why is $\mathbb{1}$ the unique (up to isomorphism) solution?

The first problem is that the structure you've outlined isn't technically a structure - it has a proper class of elements. More importantly for your intuition, though, it's too universal! Remember the goal is

for any $\sigma$-structure $\mathcal{A}$ there exists a unique homomorphism from $\mathcal{A}$ to $\mathbb{1}$.

The key word there is "unique." If your structure is "too big," then there will be "too many" homomorphisms into it! For instance, take $\sigma$ to be the language of graphs (a single binary relation symbol) and consider as your universal structure the countable random graph. This structure is "universal" in many senses - in particular, any countable graph admits a homomorphism into it. However, any countable graph admits lots of homomorphisms into it, so it has the wrong property! In category-theoretic language, we're looking for a terminal object in the category of $\sigma$-structures, and this terminal object can't be too "large" for the same reason that the terminal object in Set can't have more than one element.


If we drop the uniqueness requirement, then there are indeed lots of solutions - indeed, if $\mathcal{U}$ is any structure such that there is a homomorphism $h: \mathbb{1}\rightarrow\mathcal{U}$, then for any other structure $\mathcal{A}$ there is a homomorphism $f: \mathcal{A}\rightarrow\mathcal{U}$, given by $f=h\circ !$, where $!$ is the unique homomorphism from $\mathcal{A}$ to $\mathbb{1}$.

On the other hand, the requirement "there is a homomorphism $h: \mathbb{1}\rightarrow\mathcal{U}$" is not trivial: for example, if $\sigma$ consists of a single function symbol $f$, $\mathbb{1}$ is the one-element $\sigma$-structure, and $\mathcal{U}$ is the two-element $\sigma$-structure with elements $a, b$ and $f^\mathcal{U}(a)=b$ and $f^\mathcal{U}(b)=a$, then there is no homomorphism from $\mathbb{1}$ to $\mathcal{U}$.

$\endgroup$
  • $\begingroup$ The end confused me. I read that as $\not \exists \mathcal 1 \rightarrow A \Rightarrow \not \exists h$, but It doesn't seem implied. Is id not a homomorphism mapping 1 to U? $\endgroup$ – vectorious Jun 11 '17 at 8:29
  • $\begingroup$ @vectorious "Is id not a homomorphism mapping 1 to U?" What? I don't understand what you're asking - id only potentially makes sense as a homomorphism from one structure to another if the former's domain is a subset of the latter, and I haven't specified what the domain of $\mathbb{1}$ is, so the identity map doesn't even need to be a function from $\mathbb{1}$ to $\mathcal{A}$! But suppose $\mathbb{1}$ has domain $\{a\}$, so id is in fact a function. Then in $\mathbb{1}$ we have $f(a)=a$, but in $\mathcal{A}$ we don't have $f(id(a))=id(a)$, so id isn't a homomorphism. $\endgroup$ – Noah Schweber Jun 11 '17 at 14:13
  • $\begingroup$ There are three points to this answer. (1) Whenever $\mathcal{A}$ is a $\sigma$-structure, there is a unique homomorphism from $\mathcal{A}$ to $\mathbb{1}_\sigma$; and $\mathbb{1}_\sigma$ is the unique $\sigma$-structure with this property. (2) If we drop the uniqueness requirement, then there are lots of other examples - whenever $\mathcal{U}$ is a $\sigma$-structure such that there is a homomorphism $h:\mathbb{1}_\sigma\rightarrow\mathcal{U}$, then we have: "For every $\sigma$-structure $\mathcal{A}$, there is at least one homomorphism $\mathcal{A}\rightarrow\mathcal{U}$. (cont'd) $\endgroup$ – Noah Schweber Jun 11 '17 at 14:18
  • $\begingroup$ (3) The condition in (2) isn't trivial - we can find an example of a structure $\mathcal{V}$ such that there is no homomorphism from $\mathbb{1}_\sigma$ to $\mathcal{V}$. Does that make sense? $\endgroup$ – Noah Schweber Jun 11 '17 at 14:20
  • $\begingroup$ @vectorious I've changed the variable name in the last paragraph - does this make things clearer? $\endgroup$ – Noah Schweber Jun 11 '17 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.