2

Suppose $A$ and $B$ are non-empty sets and $f:A\rightarrow B$ is an onto function

What is the standard way to express this as a first order structure?

For example, one may consider a language $L$ containing a $2$-ary predicate symbol $F$ (intuitively Fxy means $(x,y)\in f$, i.e. $f(x)=y$), two $1$-ary predicate symbols $P_{A}$ and $P_{B}$ ($P_{A}x$ intuitively means $x\in A$, and similarly for $P_{B}x$), then constant symbols $c_{a}$ and $c_{b}$ for each $a\in A$ and $b\in B$ and an equality symbol $=$.

Then and onto function $f$ between the sets $A$ and $B$ is an $L$-structure $\mathcal{M}$ satisfying the obvious $L$-sentences: (onto axiom) $\forall x\;P_{B}x\Rightarrow \exists y\;P_{A}y\wedge Fyx$, the axioms $Fc_{a}c_{b}$ for all $(a,b)\in f$, and the well-defined axiom.

The domain of $\mathcal{M}$ is $A\cup B$, then $F^{\mathcal{M}}:= f$, $P_{A}^{\mathcal{M}}:=A$, $P_{B}^{\mathcal{M}}:=B$, the constant symbols are interpreted as $c_{a}^{\mathcal{M}}:=a$ and $c_{b}^{\mathcal{M}}:=b$ ($=$ is interpreted in the obvious manner).

Is my approach correct? $\mathcal{M}$ should "be" the function $f$, no? I feel I am missing something.

John
  • 4,305

2 Answers2

5

What you write is correct, there are only a couple redundancies.

You only need the predicate $F$ in the language, then domain and range are definable by $\exists y Fxy$ and $∃ x Fxy$.

There is no need to introduce parameters (for your purpose these are irrelevant).

Primo Petri
  • 5,174
  • I see, thank you. How do we express the onto condition? The sentence $\forall x\exists y,Fyx$ is not true when, say $y$ is an element $a\in A$. – John Jun 19 '22 at 19:38
  • The best I can do to express the onto property is this: Let $\phi$ be the $L$-formula of a single free-variable $y$ defned by $\phi:=\exists x,Fxy$. Then saying $f$ is onto is the same as saying $\mathcal{M}\vDash \phi[y/b]$ for all $b\in B$. Is there a better way? Because this is not really expressing the onto property in the language $L$. It seems to do this $L$ needs more symbols. – John Jun 19 '22 at 20:00
  • Which brings me to this: the structure $\mathcal{M}$ is not an onto function per se. It contains an isomorphic copy of one, so to speak. But it has other elements in its domain. Am I correct? – John Jun 19 '22 at 20:08
  • The onto condition is built-in the definition of range that I give above. – Primo Petri Jun 20 '22 at 16:08
1

Somewhat contra Primo Petri's answer, in my opinion there isn't a single way to construe a function as a structure - it all depends on what you want that structural construction to do.

For example, here's one case where having constant symbols is absolutely crucial: if we want a construction $$f\leadsto\mathcal{M}_f$$ such that whenever $g$ is a function with domain and codomain containing those of $f$ and $\mathcal{M}_f$ is elementarily equivalent to (the appropriate reduct of) $\mathcal{M}_g$ we get that $f$ is a "subfunction" of $g$. This is often desired when applying compactness (similarly to here) but crucially relies on the presence of constant symbols.

I would say that your approach is the optimal one for as-yet-undetermined applications - if all I know is that I'm about to use model theory to think about a function in some way but I don't know the details, I'd probably adopt the construction you describe - but I'd rather emphasize flexibility and pragmatism than pick a specific construction without further details.

Noah Schweber
  • 245,398
  • 1
    @John Hm, I think for onto-ness specifically you don't need constants but rather just predicate symbols for domain and codomain: $$\forall x[C(x)\rightarrow \exists y(D(y)\wedge F(y,x))].$$ – Noah Schweber Jun 19 '22 at 20:20
  • @John In fact, if your domain and codomain are disjoint, you don't even need predicates: $$\forall x\exists y(F(x,y)\vee F(y,x))$$ does the job. (Separately, I don't see how constant symbols help in any case.) – Noah Schweber Jun 19 '22 at 20:23
  • @indeed, thank you. I asked this question because I was learning many-sorted logics, and I was practicing the concepts by defining a 2-sorted language and model for an onto function $f$. When I reduced this to single-sorted, the 1-ary predicates appeared and I began noticing this single-sorted language reduction allowed me to express things (like onto-ness) that the language in my original question could not express. – John Jun 19 '22 at 20:29