Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: When can a comprehension be expressed as a function?

Julius Hamilton (Oct 14 2024 at 17:50):

I have been learning some new topics lately, and a question came up from multiple angles, that I am starting to think is quite deep.

Set comprehension is the ability to define a set with regards to a formula, $\phi$.

The axiom schema of restricted comprehension says that for all formulas $\phi$ in a language $L$, for all $x$, there exists a $y$ such that for all $z$, $z \in x \wedge \phi(z) \leftrightarrow z \in y$.

I often think of “generating new sets from old” as an inherently functional process, but this is not the case. There is some difference I can’t see clearly, between assigning elements of a set $S_1$ to a set $S_2$ according to a rule; versus choosing elements of a set $S_1$ according to a rule.

Let $\phi(X)$ denote $\{x \in X \; | \; \phi(x)\}$. There always exists at least one function $i : \phi(X) \to X$: the one such that $i(x) = x$.

But what more can be said?

What about functions $X \to \phi(X)$?

There exist $|\phi(X)|^{|X|}$ unique functions from $X$ to $\phi(X)$.

But many of these functions are “arbitrary”, in the sense that they can only be defined by stating their values. For example, let $f : \{0,1,2\} \to \{1,2\}$, such that $f(0) = 2, f(1) = 2, f(2) = 1$.

Defining a function point-wise is not the same as “defining a function by a rule”, which makes me wonder what the true definition of “a function defined by a rule” is.

I would ordinarily give examples of “a function defined by a rule” as common operations like addition, $f(x) = x + 3$; or exponentiation, $f(x) = x^2$.

When one defines a function “point-wise”, one writes out a number of equations, like so:

Let $a, b$ be fixed sets.
Let $f$ be a function $\{a, b\} \to \{a,b\}$.
Let $f(a) = b$.
Let $f(b) = b$.

When one defines addition inductively, one also writes out a number of equations:

Let $N$ be a fixed set.
Let $0 \in N$.
Let $S$ be a function $N \to N$.
Let $+$ be a function $N \times N \to N$.
For all $n \in N$, $+(0, n) = n$.
For all $n, m \in N, +(S(n), m) = S(+(n, m))$.

Is there no inherent difference in the methods of definition of the above?

The first can be rewritten in terms of a rule:

For all $x \in \{a, b\}, f(x) = b$.

The second may be able to be rewritten in terms of values:

Let $1 = S(0)$.

Let $2 = S(1)$.

$\ldots$

$+(0, 0) = 0$.

$+(0, 1) = 1$.

$\ldots$

Is there a well-defined difference between “arbitrary” and “rule-based” functions?

We would need a distinction of those concepts to even ask the question, “When does there always exist a rule-based function $X \to \phi(X)$?”

Let $f : \mathbb{R} \to \mathbb{R}$.

For all $x \in \mathbb{R}$, let $f(x) = |x|$.

If a function $f$ is an operation $S \to S$, then its image $Im(f) \subseteq S$.

This guarantees that there will be an inclusion map $i : Im(f) \to S$.

$Im(f)$ can also be expressed via a set-comprehension.

For example, for all $y \in \mathbb{R}$, let $\phi(y)$ say “there exists an $x \in \mathbb{R}$ such that $f(x) = y$”.

Then every function determines a set comprehension: its image.

The converse does not seem to be true.

We can associate $\phi(X)$ with a characteristic function $f : X \to \{0,1\}$ such that for all $x \in X$, if $\phi(x)$, then $f(x) = 1$, and if $\neg \phi(x)$, then $f(x) = 0$.

Julius Hamilton (Oct 14 2024 at 18:52):

But this is a function $X \to \{0,1\}$, and does not help us find a function $X \to \phi(X)$.

A related scenario is taking a quotient of a set over an equivalence relation.

Let $S$ be a set.

Let $\sim$ be a reflexive, transitive, symmetric relation on $S \times S$.

Let $f$ be a function $S \to \mathcal{P}(S)$ such that $f(s) = \{x \in S | x \sim s \}$.

This is a map from elements $s$ of $S$ onto its subsets $S_i \subseteq S$.

There’s more to be said, but I’m considering if the paradigm to make these types of relationships clearer is to study the extensions of all formulas, and see if correspondences can be found between formulas (used in set comprehensions) and their extensions (the set of elements they determine).

Morgan Rogers (he/him) (Oct 14 2024 at 19:15):

One thing to notice is that when you are able to define a function by a rule, there are other special, pre-existing functions or structure that enable you to do so. You can only define a function inductively on the natural numbers because you have the inductive definition/axiomatization of the natural numbers to hand. So perhaps what you're noticing is that many sets which one encounters in maths are inherently (by the way they are presented) equipped with structure that facilitates construction of certain classes of function.

Julius Hamilton (Oct 16 2024 at 16:02):

I see.

Are you saying, “You need functions from the beginning, to define more functions?”

Because, here is something related.

Let $S$ be a “sets of elements”. For example, $S = \{a, b, d, h\}$.

The most fundamental next thing we can do is define operations on this set.

For example, let $* : S \to S$.

In this scenario, assume we do not have logical concepts like quantifiers, equality, and connectives. We cannot define axioms such as, “For all $x \in S\ldots$”. We cannot state “$*(a) = d$”.

These structures are known as term-algebras.

However, a function $A \to B$ is a left-total, right-unique relation $R$. A relation is a subset of a product $A \times B$. A product is the set of all ordered pairs $\{(a, b) | a \in A, b \in B\}$. An ordered pair of two sets $a, b$ is the set $\{a, \{a, b\}\}$.

How are we going to formally define “the ordered pair of $a, b$ is $\{a, \{a, b\}\}$?”

It’s clearly a function on the class of sets: $\text{OrderedPair} : \text{Set} \to \text{Set}$, such that $\forall x, y \in \text{Set}, \text{OrderedPair}(x, y) = \{x, \{x,y\}\}$?

Are functions inescapable as a primitive notion?

John Baez (Oct 16 2024 at 16:48):

Functions aren't a primitive notion in ZF set theory; the concept of function is a defined notion.