Let $ A $ and $ B $ be arbitrary sets. Is there a function $ f:A \times A\to B $ such that all functions from $A$ to $B$ are representable by $f$?

Question

$\mathbf{def}:$ let $A, B$ be sets, and $ f : A \times A \rightarrow B$ be any function. A function$ g : A \rightarrow B $ is representable by $f$ iff there is $ a \in A$ such that for all $ x \in A, g(x) = f(x, a)$.

$\mathbf{Theorem}:$ [Cantor’s Little Theorem] Let $ A, B $ be sets and $f : A × A → B$ be any function such that all functions $g : A → B$ are representable by $f$. Then every function $φ : B → B$ has a fixed point.

$\mathbf{proof}:$ Suppose that $f : A × A → B$ is such a function that all functions $g : A → B$ are representable by $f$. Let $φ : B → B$ be any function. Define a function $ψ : A → A × A$ , called Cantor’s diagonalization, by $ψ(x) = (x, x)$. Let $h = φ ◦ f ◦ ψ$;Since the function $h : A → B$ is representable by $f$ , we have an $a ∈ A$ such that for all $x ∈ A, h(x) = f(x, a)$. In particular, $h(a) = f(a, a)$. But $h(a) = φ(f(ψ(a))) = φ(f(a, a))$. Writing $f(a, a) = b$, we have $φ(b) = b$. Thus $φ$ has a fixed point, namely,$b$.

$\mathbf{Question}:$ It says Let $ A, B $ be sets and $f : A × A → B$ be any function such that $\mathbf{all}$ functions $g : A → B$ are representable by $f$.This assumption seems logically wrong to me because the cardinality of the set of all functions from $A$ to $B$ is bigger than the cardinality of $A$,so how can there exists a function $f : A × A → B$ such that $\mathbf{all}$ functions $g : A → B$ are representable by it?In the proof the assumption is applied to the function "h" (defined in the proof ).

link of the paper containing the theorem:https://mat.iitm.ac.in/home/asingh/public_html/papers/cantor.pdf

Answer 1

Your mistake is thinking that the cardinality of the set $B^A$ of all functions from $A$ to $B$ must be bigger than the cardinality of $A$.

For example, if $A$ is non empty and $B$ is empty, then there is no function from $A$ to $B$, so the cardinality of $B^A$ is $0$, which is less than the cardinality of $A$.

Also, if $A$ has at least two elements and $B$ has a single element $b$, then there is a unique function $f \colon A \to B$ (mapping all elements of $A$ to $b$), and so the cardinality of $B^A$ is $1$, which is less than the cardinality of $A$.

Answer 2

Have you seen the classic proof that $\sqrt 2$ is irrational? In modern terms, it's really more a proof of a statement like this:

If $a, b$ are integers such that $a^2 = 2b^2$, then for any natural number $n$ we have $2^n\mid a, b$.

This is an if-then-formulated theorem. If we stop worrying about circularity here for a moment, note that it is well-known that the assumption, i.e. the existence of such integers $a, b$, is (nearly) impossible. Yet the theorem is true. How could this be?

This is exactly because the conclusion, that $a, b$ are both divisible by any power of $2$, is impossible (unless $a = b = 0$, which is an uninteresting triviality).

In your case, you have the statement (slightly paraphrased to make the if-then structure a bit clearer)

If $ A, B $ be sets and $f : A × A → B$ is a function such that all functions $g : A → B$ are representable by $f$, then every function $φ : B → B$ has a fixed point.

You seem hung up on the fact that the assumption, i.e. the existence of such a function $f$, seems impossible when the fact is that this is (almost) a proof by contradiction, just like the classical proof of the irrationality of $\sqrt 2$. That's because the conclusion, that any function $B\to B$ has a fixed point, is impossible (unless $|B|<2$, which is an uninteresting triviality). Your theorem is still true.

Answer 3

Here is another theorem:

Theorem: If $A$ is a nonempty finite set such that there is an injective map $A\times A\to A$, then every map $A\to A$ has a fixed point.

You would say, but this assumption doesn't make sense, there are no injective maps $A\times A\to A$ since $A\times A$ is bigger than $A$. And you would be almost right: $A\times A$ is bigger than $A$ except in very exceptional cases, and this theorem is precisely telling you which are these exceptional cases.

Answer 4

If $B$ is empty, then there is a unique function $\phi : B \to B$ and it has no fixed point. If $B$ has $1$ element, then there is a unique function $\phi: B \to B$ and it has a fixed point. If $B$ has $2$ elements (or more), then Cantor's theorem as it is usually stated tells us that for any set $A$, there is no surjective function from $A$ to the set of functions $A \to B$ and hence no function $A \times A \to B$ that represents every function from $A$ to $B$ in the sense of your question. Hence the hypothesis of your "Theorem" is false if $B$ has more than $1$ element.

So your statement is correct for non-empty sets $A$ and $B$ and is very closely related to Cantor's theorem as normally stated but it is extremely misleading: the existence of a fixed point for every function $\phi : B \to B$ just means that $B$ has exactly one $1$ element.

Answer 5

First of all it is my personal opinion that a false hypothesis does not have to be a "wrong hypothesis", for me a wrong hypothesis is one that does not allow you to conclude your thesis.

With that said, as others have already noted the hypothesis

all functions $g \colon A \to B$ are represented by $f$

is not at all logically false, indeed it is verified whenever $B$ has only one element, and that is also the only case of course, since for every $B$ with al least two elements you can find a function with no fixed point (hence violating the thesis of Cantor's Little theorem).

So this theorem may seem pretty useless since it applies to so few families of sets, nevertheless if you replace sets and functions with objects and morphisms of a cartesian closed category the same proof provides you with a criterion for fixed points.

This can applied to the category of dcpos and continuous functions between them, in this way you get Kleene fixed point theorem.

There are other applications of this theorem in [this paper] from Lawvere who I believe was the first person to notice the importance of this theorem for cartesian closed categories.

I hope this helps.