2

Let the function $f(x)=x^2$ be defined on the set of positive integers $\{1,2,\ldots\}$. Let the set $S$ be defined as follows:

$$S:=\bigl\{x: f(x)\geqslant |S|\bigr\}.$$

Is the set $S$ well defined? Why not?

NB. I have a more complicated function than $f(x)=x^2$.

Thanks a lot.

Asaf Karagila
  • 393,674
Jarbou
  • 181

4 Answers4

14

The statement $$S=\{x: f(x)\ge\vert S\vert\}$$ is a meaningful statement about a set $S$. However, it doesn't constitute a definition: you can't use the thing you're trying to define, to define itself.

Now, that said, there are contexts in which self-referential "definitions" work! (A keyword here is "impredicative.") For example, defining a function by recursion can be viewed as such a definition: if we want to build a function $f$ satisfying "$f(n)$ is the number of $k<n$ such that $f(k)$ is even," we can define $f$ as $$f(n)=I(f\upharpoonright n)$$ (where $f\upharpoonright n$ is the function $f$ restricted to numbers $<n$, and $I$ applied to a function with finite domain outputs the number of times that function spits out an even number). This may seem bonkers at first, but it turns out to make perfect sense:

  • There are no $k<0$, so $f(0)=0$.

  • There is one $k<1$ - namely $0$ - and $f$ spits out an even number on that input (since $f(0)=0$, as we concluded above) - so $f(1)=1$.

  • There's still only one $k<2$ with $f(k)$ even - so $f(2)=1$.

  • And it's not hard to see that indeed $f(n)=1$ for all $n>0$.

See e.g. this paper for a serious treatment of definition by recursion as self reference.

But we have to be careful. Even if we allow $S$ to appear in its own definition, we still don't let anything go: in order to not be nonsense, a self-referential definition has to have two properties:

  • It's true of at most one set.

  • It's true of at least one set.

That is, something satisfying the definition has to exist, and has to be unique. Neither of these is obviously true of the statement you've written down.

Indeed, the second one is false in the case you outline: in the case $f(x)=x^2$, there is no $S$ with this property! Such an $S$ would have to be finite (since we never have $f(x)$ infinite), but then taking $n>\vert S\vert$ we'd have $n\in S$ (since $n^2>n>\vert S\vert$). But there are infinitely many $n>\vert S\vert$ if $S$ is finite, so then $S$ would be infinite; contradiction.

(Note that all we used was that $x^2$ is not bounded. However, boundedness isn't enough to guarantee the existence of such an $S$: consider the function $f(0)=2$, $f(n)=1$ for $n>0$. Can there be any set $S$ such that $S=\{x: f(x)\ge\vert S\vert\}$?

It's actually a good exercise to show that there is any function $f$ for which some $S$ exists! HINT: see what happens if you make $f$ take on its maximum value infinitely many times . . .)

Noah Schweber
  • 245,398
  • Thank you. If for example $f(x)=\frac{1}{x}$, $S$ would be equal to the set of positive integers, would it? – Jarbou Dec 22 '16 at 23:03
  • @Jarbou No: the size of that $S$ is infinite; so e.g. ${1\over 8}=f(8)$ is not bigger than the size of $S$, even though $8\in S$. And, you shouldn't speak of $S$ as if it's determined by $f$: the whole point of my answer is that such an $S$ may not exist, and if it exists it may not be unique. – Noah Schweber Dec 22 '16 at 23:05
  • Ah, ok thanks again. – Jarbou Dec 22 '16 at 23:06
  • Is it then possible that your first point "It's true of at most one set." fails? Can such self-referencing definitions hold true for more than one set? I can't think of any such example right now. – H. Kissos Dec 23 '16 at 09:59
  • @H.Kissos How about "$S=S$?" Every set satisfies that. – Noah Schweber Dec 24 '16 at 02:13
  • Oh I see now. The context was more in general there. I was still thinking at the case $S={x\colon\text{ statement about }S}$ which doesn't really seem to allow such problem at a first glance, right? Or not? You did wrote the poster's condition was not obvious about unicity of definition. – H. Kissos Dec 24 '16 at 08:49
3

You can't have a circular definition. The condition defining $S$ should not depend on $S$.

Well, I should modify that. You can, of course, have a recursive definition. But in that case there is a procedure for determining membership in the set that will always terminate. That is not so here.

Robert Israel
  • 448,999
  • 1
    This is not true. $S = {x : x = |S| \wedge x^2-x = |S|}$ is a set that has a unique solution: $S = {2, 2}$. At no point did I specify some 'terminating' condition. This is a fairly basic example, but this can be as self-referential and complex as I wish to make it. The definition just needs to be somehow proven unique and existing. – orlp Dec 23 '16 at 06:28
  • @orlp: Your point may be valid but your example doesn't work, because ${2,2}={2}$ so $|S|=1$. –  Dec 23 '16 at 08:10
  • 2
    @Rahul Right, as a programmer I'm used to ordered sets, rather than sets. As a valid example: $S = {x : x \in \mathbb{Z} \wedge |S| = 2x^2}$ with solution ${1, -1}$. – orlp Dec 23 '16 at 09:25
1

There is a self-reference problem in here. So $S$ is not well-defined.

user64066
  • 2,480
1

The statement $$S:=\bigl\{x: f(x)\geqslant |S|\bigr\}.$$ may be one of the property of your set $S$ (if such $S$ exists) rather than the definition of $S$. Moreover, in this circular sense, $S$ doesn't seem to be well defined.

It is something like searching the solution to the problem: "Construct a building in such a way that the height of each storey is greater than or equal to the number of storeys of the building." Clearly, the construction is possible iff the number of storeys are finite but with an extravagant idea of an unbounded number of storeys, such a construction would be fancy!!

Nitin Uniyal
  • 7,946