4

This is a followup to this question. I am trying to formalize an intuitive notion/question: Is it always possible to write down necessary and sufficient conditions (i.e. formulas) for a property $P$?

Let $\mathcal {Y,X}$ be two arbitrary sets, and $f:\mathcal X\to\mathcal Y$ some function.

Let $\mathcal L_{\mathcal X}$ be a language in first order logic over some set $\mathcal X$, i.e. containing propositional formulae and quantifiers only over $\mathcal X$. A set $X\subseteq\mathcal {X}$ is called "characterizable in $\mathcal L_{\mathcal X}$" if we can write down an $\mathcal L_{\mathcal X}$-formula $\phi_X(x)$ such that $\phi_X(x)$ is true iff $x\in X$. Similarly for $Y\subseteq \mathcal{Y}$ if there is such a formula $\phi_Y(y)$ in a language $\mathcal L_{\mathcal Y}$.

A function $f$ is called "characterizable" if we can write down an $\mathcal L_{\mathcal X, \mathcal Y}$-formula $\phi_f(x,y)$ such that $\phi_f(x,y)$ is true iff $f(x)=y$.

Conjecture. If a set $Y\subseteq \mathcal Y$ is characterizable in some $\mathcal L_{\mathcal Y}$, and $f:\mathcal X\to\mathcal Y$ is characterizable in some $\mathcal L_{\mathcal X, \mathcal Y}$, then $X=f^{-1}(Y)$ is characterizable in some language $\mathcal L_{\mathcal X}$.

  • Does this formalism capture the desired intuition well? (that we can always write down "necessary and sufficient conditions").

  • Does this definition of "characterizable" already exist?

  • Is this conjecture correct?

user56834
  • 12,925
  • Comment in response to the edit: Can you clarify what you mean by $\mathcal{L}_{\mathcal{X},\mathcal{Y}}$? Can you give an example of an interesting characterizable function between two explicit structures $\mathcal{X}$ and $\mathcal{Y}$? – Alex Kruckman Sep 30 '18 at 14:35
  • I ask because the usual setting for the notion of definable function is that $\mathcal{X}$ and $\mathcal{Y}$ are sorts or definable subsets within a single $\mathcal{L}$-structure. If instead they are separate structures with no primitive relations between them, there will be very few definable functions between them (essentially just piecewise constant functions with finitely many pieces). – Alex Kruckman Sep 30 '18 at 14:40
  • Also: in the edited version of the conjecture, I don't think you mean the conclusion to be that $X$ is characterizable in some language $\mathcal{L}_{\mathcal{X}}$. Indeed, every set is characterizable in some language, namely the language that includes a relation symbol picking out that set. Instead, you have some fixed language for $\mathcal{X}$ in mind from the beginning. – Alex Kruckman Sep 30 '18 at 14:46

2 Answers2

4

Yes, the definition already exists. In logic, we use the word definable (e.g. definable set, definable function) to mean exactly this.

The answer to your conjecture depends on what logical framework you're working in (what counts as a formula?). But in first-order logic, for example, the answer is yes. If $Y\subseteq \mathcal{Y}$ is defined by $\varphi_Y(y)$ and $f\colon \mathcal{X}\to \mathcal{Y}$ is defined by $\varphi_f(x,y)$, then $X = f^{-1}(Y)$ is defined by $\exists y\, (\varphi_f(x,y)\land \varphi_Y(y))$.

Alex Kruckman
  • 76,357
  • Thank you Alex, this clarifies. Now that you gave the definition of $X$, I noticed that I really wanted to put a stronger requirement on what it means for $X$ to be “characterizable”. What I really mean is, that it is definable using formula’s in a language that is only allows to refer to elements in $\mathcal X$. Let me edit the question. – user56834 Sep 30 '18 at 07:24
0

For characterizable $X\subseteq{\cal X}$ think about the characteristic function of $X$ in the universe $\cal X$, i.e., $$\chi_X = \left\{\begin{array}{ll} 1 & \mbox{if } x\in X\\0 & \mbox{otherwise.} \end{array}\right.$$ For characterizable $f:{\cal X}\rightarrow{\cal Y}$ just consider the graph of the function, i.e., $$R_f = \{(x,f(x))\mid x\in{\cal X}\}.$$

Wuestenfux
  • 20,964
  • I would say that these don't count because e.g. $\chi_X$ is using the symbol for $X$ even though $X$ is not defined (it is supposed to be the job of $\chi_X$ to do that). In other words, this formula $\chi$ doesn't pin down a particular such set $X$. – user56834 Sep 29 '18 at 13:35
  • This answer seems to be describing a way of assigning a definable function to each definable set and vice-versa. This is sometimes a useful thing to do, but I don't see any connection to the actual question. – Alex Kruckman Sep 29 '18 at 16:29