Expressing Barber Paradox in functional notation?

[xouper]

Regarding the Barber of Seville paradox, I am looking for something equivalent that is expressed in functional notation.

For example, this is my attempt at a piecewise definition of such a function:

For a function $f : \mathbb{N} \mapsto \{0,1\}$

$$f(n)=\left\{\begin{array}{cc}0,&\mbox{ if }f(n)=1\\1,&\mbox{ if } f(n)=0\end{array}\right.$$

Does this function definition express the essence of the Barber paradox?

 

[Hurkyl]

I don't think so -- I can't figure out a way of interpreting the pieces to make it look like the Barber's Paradox.

 

[matt grime]

Obivously, that isn't even a function. (and obviously you aren't going to get a function because the definition of a function precludes such things.)

 

[xouper]

matt grime: Obivously, that isn't even a function. (and obviously you aren't going to get a function because the definition of a function precludes such things.)

Agreed. I suspected as much but it is nice to see someone else say it explicitly.

Using the definition of a function at mathworld, I infer that my "function" is not a function because it does not seem to uniquely assign a value to f(n).

But that's exactly what I want, something that looks like a definition of a function, but is for a "function" that cannot exist, just like the Barber of Seville cannot exist, just as the set of all sets that are not members of themselves cannot exist.

My objective is to show that just because a function can be described does not mean it exists. Using functional notation, I am trying to capture the essence of one of Russell's points that just because a set can be described does not mean it exists, which motivated the axiomatic constraints on how sets can be defined.

Here is perhaps a less abstract version of the problem: If I write a book that has a bibiliography of all the books that do not mention themselves in their own bibliography, do I mention my own book in its bibliography? I conclude that such a book cannot be written. I want to be able to make that same argument using standard notations for defining functions.

Given all that, does my definition above of a "function" do what I want?

I could, of course, obscure the recursion (just barely) by splitting it into two functions:

$$f(n)=\left\{\begin{array}{cc}0,&\mbox{ if }g(n)=1\\1,&\mbox{ if } g(n)=0\end{array}\right.$$

$$g(n)=f(n)$$

Neither of these functions are problematic by themselves, but when taken together, has the same effect as the original. This would seem to overcome the objection that the individual definitions do not conform to proper functions.

However, my gut feeling tells me that a single "function" is a more elegant way to express the notion.

Any other thoughts or suggestions?

 

[xouper]

Hurkyl: I don't think so -- I can't figure out a way of interpreting the pieces to make it look like the Barber's Paradox.

Good point.

In hindsight I see that I was sloppy in my opening sentence. I am not looking to capture the entire Barber Paradox in a function, but rather only the essence of the question, "Does the barber shave himself?". Also, I used $\mathbb{N}$ as the domain for reasons not related to the Barber Paradox.

Sorry for the confusion.

 

[Hurkyl]

At that point, it sounds like it would just reduce to the liar's paradox "P := ~P".

I'm not entirely sure what you mean by "expressed in functional notation". If my best guess as to what that means is true, though, all you'd have to do is to write relations as functions whose image is {true, false}. (I.E. a truth mapping)

 

[xouper]

Hurkyl: ... I'm not entirely sure what you mean by "expressed in functional notation".

Sorry. Perhaps I explained my requirements backwards. And perhaps I should have used the Liar's paradox as you noted.

My primary requirement is to describe a function that has a domain of N and a range of {0,1}, and to do it with the notation I used in my opening post. This is more important than which paradox I use as an analogy for how the "function" behaves.

I appreciate your patience with me as we work through what I am trying to ask here. Suppose I ask my question differently. Given the function definition in my first post, is it a valid function? Matt Grime says no, and I concur.

Secondly, aside from its validity as a function, is the definition itself well formed according to the notation I used?

Thirdly, does it behave similarly to any of the paradoxes that have been mentioned?

Or perhaps I could have defined the function to have a behavior based on Russell's Paradox:

$$f(n)=\left\{\begin{array}{cc}0,&\mbox{ if }S \notin S\\1,&\mbox{ if } S \in S\end{array}\right.$$

And then defined the set S:

$$S = \{ A | A \notin A \}$$

But that doesn't define the function in terms of n. Also, I was hoping to distill that whole notion into something simpler and came up with the function in my opening post. Do you see any other problems with that "function"?

 

[Hurkyl]

It might help greatly if we knew what you're trying to accomplish!

 

[xouper]

My objective is to show, with a very specific example, that just because a function can be described does not mean it is valid. When Russell described the set of all sets that are not members of themselves, he showed that just because you can describe a set does not mean it is a valid set or that the set exists. I want to do something similar with a function from N to {0,1}.

 

[matt grime]

I think it is better to remember that he showed that just because you *call* it a set, describe it in terms of being a subset doesn't mean that it makes sense. So, in one sense, you're notional function is OK: you call it a function, and show that it doesn't make sense, but then anything will do that, the difference is that in the Barber Paradox, we thought we had a good idea of what a set is, but Russel showed that we didn't. We do know what a function is so it isn't a valid comparison.

 

[VazScep]

My objective is to show that just because a function can be described does not mean it exists. Using functional notation, I am trying to capture the essence of one of Russell's points that just because a set can be described does not mean it exists, which motivated the axiomatic constraints on how sets can be defined.

Don't forget that Russell was working specifically with Frege's theory developed in Begriffsschrift. His argument wouldn't have gone through in the set theory being developed by Cantor (which had its own paradoxes). Russell's Paradox relies on the specific rules which allow you to state whether a set or class or extension or whatever exists.

I don't know of any formally agreed upon rules for describing a function based on the notation you use in the OP. I always regarded it as an informal notation, like the informal set notations we usually use for doing maths outside of formal set theory, and as informal notations they are easily open to abuse.

In the formal context of ZF set theory, there are two ways to introduce a function f:A->B. One is by showing the unique existence of a set S which is a subset of the Cartesian Product AxB such that if (a,b) and (a,c) are in S, then b=c. And the other is to define a two-place predicate p(x,y) such that if p(x,a) and p(x,b) then a=b.

 

[Hurkyl]

When Russell described the set of all sets that are not members of themselves, he showed that just because you can describe a set does not mean it is a valid set or that the set exists.

Allow me to go into more detail about this example:

Once upon a time, Cantor introduced what we now usually call naive set theory. One of the main features of this theory was unrestricted comprehension: that, for any unary proposition P, we have the set $\{ x \, | \, P(x)\}$.

The famous paradoxes, like Russell's paradox, were death blows to Cantor's formulation of set theory. Because of the axiom of unrestricted comprehension, naive set theory admits the existence of sets such as $\{x \, | \, x \notin x \}$. These were valid sets that really did exist in naive set theory!

Nowadays, we usually use Zermelo-Fraenkel (ZF) set theory, or something related. It includes an axiom of "restricted" comprehension, a.k.a. the axiom of subsets: for any proposition P and set S, there exists a set $\{ x \in S \, | \, P(x) \}$. We also have the axiom of replacement: for any logical function f and set S, there exists a set $\{ f(x) \, | \, x \in S \}$.

In ZF, $\{x \, | \, x \notin x \}$ is not a valid "description" of a set.

 

[VazScep]

Allow me to go into more detail about this example:
Once upon a time, Cantor introduced what we now usually call naive set theory. One of the main features of this theory was unrestricted comprehension: that, for any unary proposition P, we have the set $\{ x \, | \, P(x)\}$.

According to PlanetMath,

Frege is the only logician who has assumed the unrestricted comprehension principle. Cantor and others had no such principle, and therefore it is not correct to say that Russell's paradox demonstrated their views inconsistent.

http://planetmath.org/encyclopedia/Class.html"

I cannot verify this, and I'm actually reading contradictory claims on the internet about Cantor's own comprehension principle (if he bothered to state one at all). What I do know is that Russell originally identified his paradox in a letter to Frege. Not having read Cantor, I'm not actually sure whether the paradox goes through in his set theory or not.

 

[Hurkyl]

Interesting -- I knew that Russel's paradox was not the first problem for naive set theory, just the simplest. I had read that it applied to Cantor's set theory, but I've never actually seen an axiomization that he actually used. (If he used one at all!)

I don't know all of the other paradoxes discovered, but here's one: the Burali-Forti paradox: the set of all ordinal numbers would be an ordinal number larger than every ordinal number it contains. (Again, I don't know if this applied to Cantor's theory)

 

[xouper]

Thanks for all the feedback. You have essentially confirmed what I wanted to know.

And thanks also for the set theory review, which I didn't need, but at least confirms we are on the same page, so to speak. :tongue2:

Hurkyl: ... In ZF, $\{x \, | \, x \notin x \}$ is not a valid "description" of a set.

Agreed. Not valid in NBG either. Seems to me, however, that is not a valid set in any set theory. Isn't that Russell's point? Or to ask it another way, what axiom(s) would allow such a set to be valid? (It occurs to me that my question might be taken as contentious, but that is not my intention. I am just curious, is all.)

In any case, seeing how the conversation has drifted (as threads are won't to do now and then), do any of you have an opinion about this book:

Bertrand Russell and the Origins of the Set-Theoretic 'Paradoxes'
by Alejandro R. Garciadiego, 1992

I just started reading it (the English translation) a handful of days ago, so I don't yet have an opinion. Section 2.2 (p. 21-32) addresses Burali-Forti's 'paradox', for example. Not being an expert on these things, I don't yet know what to make of Garciadiego's opinions.

 

[VazScep]

Agreed. Not valid in NBG either. Seems to me, however, that is not a valid set in any set theory. Isn't that Russell's point?

Russell had been working through Frege's texts on logic, the Begriffsschrift and Grundgesetze der Arithmetik. Russell pointed out that Frege's rules allowed for the predicate "to be a predicate that cannot be predicated of itself" to be considered, which leads to a contradiction. In modern day terms, Frege's logic considered the set $\{x\,: x\notin x\}$ to be valid, and so Frege's theory was contradictory.

Or to ask it another way, what axiom(s) would allow such a set to be valid? (It occurs to me that my question might be taken as contentious, but that is not my intention. I am just curious, is all.)

Hurkly already answered this. An unrestricted comprehension allows the set to be valid. In formal logic, that would be the axiom scheme

$\exists x \, \forall y \, (y \in x \iff \phi(y))$

where $\phi(y)$ is a wff with free-variable $y$.
At the level of the axioms, we don't talk about valid descriptions of sets. Allowing sets to be described with notation of the form $\{x\in y: p(x)\}$ requires that set-builder notation be introduced which is formally justifed by the axioms. Similarly, if you wanted to use the notation you use in the OP in the context of a formal system for set theory, you would need to introduce function-builder notation, also justifed by the axioms. It will be the particular rules of the function-builder notation which will tell you why what you have written in the OP is not allowed.

 

[xouper]

VazScep: ... An unrestricted comprehension allows the set to be valid. In formal logic, that would be the axiom scheme

$\exists x \, \forall y \, (y \in x \iff \phi(y))$

Perhaps we need to make explicit the distinction between sets and descriptions of sets? A description of a set might be valid under a given set of axioms, but does that necessarily make the set itself valid?

In other words, while $\{x\,: x\notin x\}$ might be a valid description in Frege's universe, the set being described is nonetheless invalid, no?

I am just looking for clarity here, is all, in case I am missing your point.

 

[Hurkyl]

I guess it all hinges upon what you mean by a description.

For example, one might consider this as a description of a set:

$$\forall y: y \in S \Leftrightarrow y \notin y$$

and then one would prove that no set fits this description. Just as easily, one could describe a (real) function via $x f(x) = 1$ and prove no such function exists.

On the other hand, there are senses in which you might mean "description" for which these are not descriptions of sets. E.G. you might only consider expressions built up by pairs, set-builder notation, and function application (including power set and union) to be descriptions of sets. In such a case, anything that could be described would exist.

 

[VazScep]

Perhaps we need to make explicit the distinction between sets and descriptions of sets? A description of a set might be valid under a given set of axioms, but does that necessarily make the set itself valid?
In other words, while $\{x\,: x\notin x\}$ might be a valid description in Frege's universe, the set being described is nonetheless invalid, no?

When studying formal set theory as a formal theory, set descriptions are not usually part of the basic language. Not even the most basic notation such as the symbol $\emptyset$, nor the notation $\{x,y\}$ are included. Such notation can be introduced, but it must be justified by proving certain theorems in the basic language. For instance, the notation for pairs can be introduced by proving the unique existence theorems

$\exists A \, \forall z \, (z \in A \iff (z=x \vee z=y))$

and
$(\forall A \, \forall B \, (\forall z \, (z \in A \iff (z=x \vee z=y)) \wedge (\forall z \, (z \in B \iff (z=x \vee z=y)))) \Longrightarrow A=B)$
(Informally, for any x and y, there is a set consisting of those elements alone and it is unique.)

We cannot introduce the notation $\{x : x \notin x\}$ into the language because the associated unique existence statements cannot be proven. The description is invalid because the sets themselves don't exist.

I'm not sure how this applies to Frege's theory. I have never read his work but I suspect things were looked at very differently back then.

I am just looking for clarity here, is all, in case I am missing your point.

I'm not sure you'll get any clarity from me, as I suspect I have gone overboard on this one. But I felt that your original question was best answered by considering formal logic, given that this was the original context of Russell's paradox, and it is where paradoxes are usually resolved.

 

[Martin Rattigan]

Does it have to be a function rather than a relation?

If you define an element x as stationary in a relation R if xRx then the relation S defined by xSR if x is stationary in R would itself be a binary relation (so long as you adopt a naive enough viewpoint). Here x can also be a binary relation, e.g. if C is the relation between a binary relation and its converse then you could say CSC.

If you define a non-stationary relation N by xNy iff not xSy, then the relation N can't exist because if NNN then not NSN i.e. not NNN, whereas if not NNN then NSN i.e NNN.

 

[Martin Rattigan]

Or for a function as follows:

Some functions such as the identity function and the converse function (for binary relations) map themselves to themselves.

Let $$f:g \mapsto g-\{(g,g)\}$$ if $$g:g \mapsto g$$ and otherwise $$f:g \mapsto g$$.

Then f can't exist, because if $$f:f \mapsto f$$ then $$f:f \mapsto f-\{(f,f)\}$$, but $$f-\{(f,f)\} \neq f$$, so $$not(f:f \mapsto f)$$. However if $$not(f:f \mapsto f)$$ then $$f:f \mapsto f$$ from the definition.