In his book "Analysis 1", Terry Tao writes (check out page 39):

To summarize so far, among all the objects studied in mathematics, some of the objects happen to be sets; and if $x$ is an object and $A$ is a set, then either $x\in A$ is true or $x\in A$ is false. (If $A$ is not a set, we leave the statement $x\in A$ undefined; for instance, we consider the statement $3\in 4$ to neither be true or false, but simply meaningless, since $4$ is not a set.)

But when discussing Russell's Paradox, he defines on page 53 a set

$\Omega := \{x : x \text{ is a set and }x\notin x\}$.

So he defines that an arbitrary object $x$ is an element of $\Omega$ if and only if $x$ is a set and $x\not\in x$. But this definition does not make any sense, since, according to his definition, we would have $4\in\Omega$ if and only if $4$ is a set and $4\not\in 4$. But $4\not\in 4$ is meaningless, as he says, and therefore "$4$ is a set and $4\not\in 4$" is meaningless as well.


How to fix this fault?

Note: I understand Russell's Paradox. But the definition

$\Omega := \{x : x \text{ is a set and }x\not\in x\}$

does not satisfy me formally.
My question is exactly how to make it formally work.

  • 16
    $\begingroup$ I encourage you to continue to read Terry's discussion of Russell's Paradox, because you are currently missing the point. $\endgroup$ – davidlowryduda Mar 16 '16 at 17:32
  • 5
    $\begingroup$ Fix: $x\notin x$ under the condition that $x$ is a set. $\endgroup$ – Friedrich Philipp Mar 16 '16 at 17:34
  • 5
    $\begingroup$ Your question really has nothing to do with Russell's paradox. You could state it equally well in terms of the set $\Omega:=\{x: x\text{ is a set and } 3\in x\}$, simply noting that the statement "$4$ is a set and $3\in4$" is meaningless (because "$3\in4$" is meaningless). $\endgroup$ – Barry Cipra Mar 16 '16 at 18:30
  • 3
    $\begingroup$ 3 ∈ 4 seems not to be the best example for a meaningless statement since 3 ∈ 4 is actually true in the von Neumann construction of natural numbers. $\endgroup$ – aventurin Mar 17 '16 at 22:25
  • 4
    $\begingroup$ @aventurin - Terry Tao consider set theory with urelements; see page 38: "not all objects are sets; for instance, we typically do not consider a natural number such as $3$ to be a set." For info, this was the original Zermelo's axiomatization of 1908. $\endgroup$ – Mauro ALLEGRANZA Mar 18 '16 at 9:46

Decades ago, in the 1970s, there arose in computer programming the issue of conditions "A and B" where B only makes sense if A is true. B might not have made sense, for example, because if A was false, computing B involved division by zero. Compilers were free to compute B first or to compute B always and computer programs would then crash. The creators of the C programming language invented the symbol && so that A && B meant "A and B where B is only evaluated if A is first found to be true."

Mathematicians are not as dumb and unthinking as computer programs, so they let you write "A and B" even if B only makes sense when A is true. That is what Tao appears to have done.

| cite | improve this answer | |
  • 27
    $\begingroup$ Credit where credit is due. Short-circuit evaluation was invented by John McCarthy in the early 1960s, and was present for example in Algol-68. Nothing to do with the inventors of C. $\endgroup$ – Marquis of Lorne Mar 16 '16 at 22:47
  • $\begingroup$ Do you mean "A first or to compute B always.."? $\endgroup$ – mowwwalker Mar 16 '16 at 22:58
  • $\begingroup$ @EJP Apologies. I am not familiar with Algol 68, not for lack of trying to read their revised report way back when. I have checked online what the situation was in Maclisp, the language I've used which is closest to the kind of stuff McCarthy did, and indeed Maclisp's AND was short-circuit only. $\endgroup$ – ForgotALot Mar 16 '16 at 23:06
  • $\begingroup$ @mowwwalker I meant "compute B first or to compute B always." Compilers (or rather the code they produced) were also free, of course, to compute A first, but if they did that, they would have had the info needed to avoid having to compute B. $\endgroup$ – ForgotALot Mar 16 '16 at 23:10
  • $\begingroup$ I built a language once with those I it. I called them MCAND and MCOR in his honour. $\endgroup$ – Marquis of Lorne Mar 17 '16 at 3:39

I actually asked this question Terry Tao himself. Half an hour ago, I got the following response per email:

A conjunction such as "A and B" is false when A is false, even if B is undefined. For instance, the assertion "x is non-zero and y = 1/x" is false when x=0, even though 1/0 is undefined. (Similar to the concept of lazy evaluation https://en.wikipedia.org/wiki/Lazy_evaluation in programming, one does not need to evaluate all inputs to a statement if one can already determine the truth of that statement from the portion that one is able to evaluate.)



| cite | improve this answer | |
  • 6
    $\begingroup$ Although it is related to lazy evaluation, I believe (although I could be wrong), as EJP has mentioned, short circuiting is a better term to describe this. The main reason being that lazy evaluation is much larger in scope and has further applications beyond this example. It refers to not computing values until they are needed, whereas short circuiting specifically refers to not computing values because they are unneeded. $\endgroup$ – Dair Mar 17 '16 at 0:15
  • 3
    $\begingroup$ +1. Incidentally, I think that "A and B" is also false when B is false, even if A is undefined. (This differs from the short-circuiting behavior seen in programming languages, where an exception in calling A() means that A() && B() will raise an exception without ever calling B().) That comes up less often, though, since it's more intuitive (and therefore clearer) to put the always-well-defined conjunct first. $\endgroup$ – ruakh Mar 17 '16 at 1:25
  • 11
    $\begingroup$ Did you obtain Terry Tao's permission to repost his email here? $\endgroup$ – David Richerby Mar 17 '16 at 4:18
  • 1
    $\begingroup$ I think it is questionable whether this would be considered correct in the kind of formal logical language that is usually used for set theory. Undoubtedly, though, it does reflect the way "and" is used in everyday mathematical discourse. If you write "$P(x)$ and $Q(x)$" and $Q(x)$ is meaningful only when $P(x)$ is true, then the way around this, as Mark Fischler explains in his answer, is usually to define $Q(x)$ in an arbitrary way when $P(x)$ is false. $\endgroup$ – David Mar 17 '16 at 5:01
  • 2
    $\begingroup$ @chi Well of some denotational models. Hyland and Ong achieved full abstraction of PCF in their article and they also provided a categorical model that makes use of the distributive law of a comonad over a monad, again using game semantics. $\endgroup$ – Bakuriu Mar 17 '16 at 19:36

This is a matter of semantics of the logical connective "and". IN computer languages, for example, $P \mbox{ and } Q$ is evaluated and defined such that evaluating $P$ has to be meaningful, but if $P$ evaluates to "false" then that is the end of the matter and $Q$ is never evaluated.

In that sense the phrase "x is a set and $x \not\in x$" is fine if x is not a set, because the second clause is never considered.

That is a bit unsatisfying (since one would like "and" to be commutative, so one is tempted to modify one's definitions. For example, one can say that $x \in x$ is meaningful for all objects, but can only be true if $x$ happens to be a set. But if you insist that a set can be defined as a collection of all objects having some logical property, then you get in trouble (the paradox).

That is why logic demands a somewhat less flexible panel of axioms as to how one can form a set. There are many choices for the axiom replacing the troublesome one.

As to considering this as a "mistake" by Tao, that is a bit harsh -- the reasoning inevitably leads to a contradiction, so the fact that one step is presented a bit less than fromally seems to be moot.

| cite | improve this answer | |

$\Omega$ should consist of all objects for which its defining property "$x$ is a set and $x\notin x$" is true. In fact this property is well defined for all objects. If $x$ is not a set, then it's false, even though we can't determine whether $x$ contains itself, because the defining property is a conjunction: it becomes false as soon as either half of it is false. If $x$ is a set, then there is no problem.

With different conjunctions of statements that don't always have truth values, you could run into trouble. Already we can't determine the members of $\Omega'=\{x:x\text{ is not a set and }x\notin x\}$. But we can still tell, for instance, that no sets are elements of $\Omega'$!

In practice, it's very rare that we have to worry about undefined properties like these: in part to avoid such paradoxes, we tend to only ask for a property of an object once we've assumed the object is of a type for which that property is defined.

| cite | improve this answer | |

This entirely depends on how you interpret logical symbols with respect to undefined values. If you interpret $\mathrm{FALSE}\land\mathrm{UNDEFINED}$ as false (which is reasonable), then there is no problem at all. If you instead interpret $\mathrm{FALSE}\land\mathrm{UNDEFINED}$ as undefined, you can resolve the problem by using somewhat restricted comprehension, like so: $$ \{x\in \mathbf{Sets}:x\notin x\}. $$

Side rant: Note that most of the time, when doing actual mathematics, we do leave a lot of things ambiguous. It is likely clear from the context that in the text you are reading, the conjunction $\mathrm{FALSE}\land\mathrm{UNDEFINED}$ is simply false (because, as you have noticed, the other possible reading does not make sense).

Mathematical writing is not read by mindless computer programs (except when it is, but that is distinct from mainstream mathematics), it is read by people who can and do infer from the context what is meant, so we can and do deviate from formality. We could hardly get anything done (and even less verified by people, and not computer programs!).

I urge you to take a look at Principia Mathematica. I think that should be enough to convince you that strict formalism is not the right way to do (or think about?) mathematics. It is important to have some formal definitions to use (though it is certainly important to have some informal ideas lying around as well), but there is no reason to spell everything out all the time.

| cite | improve this answer | |
  • $\begingroup$ Principia is an outdated comparison: it’s the fully formalised mathematics of 100 years ago. Modern formal systems are much much much better! Of course, ordinary written mathematics still isn’t strictly formal, and probably never will or should be. But it is very feasible now to formalise serious large-scale mathematics on computers, and have the fully formalised terms reasonably human-readable — no further from mathematical prose than a well-written program is from the prose description of an algorithm, say. $\endgroup$ – Peter LeFanu Lumsdaine Mar 18 '16 at 10:19
  • $\begingroup$ @PeterLeFanuLumsdaine: Sure, but even if the fully formalised terms are fully human-readable in principle, I very much doubt a human (well, an ordinary mathematician, anyhow) could understand a nontrivial reasoning (completely, not locally) without first translating it back into the not-strictly-formal language. Principia was just an example. Modern systems seem to have very much the same faults: proofs of simple facts (like famous $1+1=2$ in Principia) take inordinate amount of space, while proofs of really complicated facts seem to be infeasible. I'd like to be contradicted, though. $\endgroup$ – tomasz Mar 18 '16 at 21:42
  • $\begingroup$ Just for illustration, here is a proof of “1 + 1 = 2” in Coq (an implementation of dependent type theory), starting completely from scratch, i.e. including the definitions of the natural numbers, equality, and addition: Inductive N := Z | S (n:N). Fixpoint plus (m n : N) := match m with Z => n | S m' => S (plus m' n) end. Inductive Eq {A} : A -> A -> Prop := refl a : Eq a a. Lemma short : Eq (plus (S Z) (S Z)) (S (S Z)). apply refl. Qed. So it takes less than half of a single stackexchange comment :-) It’s not prose — but it’s much closer to prose than it is to Principia. [cont’d] $\endgroup$ – Peter LeFanu Lumsdaine Mar 18 '16 at 21:57
  • $\begingroup$ Recent major milestones in formalisation include the Feit-Thompson theorem and the Kepler conjecture. Formalisation is still more work than non-formalised mathematics; I don’t want to overstate the progress of the field. But comparisons with Principia grossly understate it, I think; we’re as far from that as computers in the 1960’s were from Babbage’s Difference Engine. $\endgroup$ – Peter LeFanu Lumsdaine Mar 18 '16 at 22:04

It is formally correct when x is a set (a set of sets). It does not make sense if x is not a set (a number, for instance). But Russell's paradox is referred to the first case.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.