$\sigma$-structure $\mathbb{1}$

161 Views Asked by At

$\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?

1

There are 1 best solutions below

6
On BEST ANSWER

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}$.