Sorry I totally crashed out last night, but then sadly didn't get much sleep anyway

@EliahKagan I think my maths teacher showed us a geometrical proof of that? He said the Greeks were really upset about it

Perhaps I'm thinking of something else :)

@Zanna I have heard that the Pythagoreans were very upset about that.

@Zanna No problem -- I'm sorry you didn't get much sleep, though.

The proof I know is not geometric and is commonly used as an example of proof by contradiction, which is why I brought it up.

But if you recall the geometric proof, I am interested in it.

I don't recall that alas

@EliahKagan at least it was only a greedy mosquito bothering me. I had really severe insomnia this time last year but I defeated it!

Is is seasonal?

@Zanna The proof I know is based on insight that a prime factor of a product of integers is a factor of (at least) one of the integers in the product. That is, where m, n, and p are integers and p is prime, p | mn → (p | m ∨ p | n).

That's a more general statement of the insight that is, strictly speaking, needed for the proof. What's needed for the proof is the case where p = 2. That is, where m and n are integers, mn is even only if m is even or n is even. They may both be even or just one, but the product of odd numbers is odd.

@EliahKagan I think it was caused by some struggles and anxiety. But once you start with that then you get anxious about not sleeping etc. But I read about CBT for insomnia and cured myself I guess. I have much less trouble now than I did before I had the series of severe insomnia episodes!

@EliahKagan I forgot what the pipe symbol | means here

I never defined it. It means "divides."

In the product, the factor of 2 has to come from somewhere, because 2 is prime -- there are no factors that don't themselves have 2 as a factor that multiply to 2.

But another way to see it in the case of p = 2 is that mn is the sum of an even and odd number and therefore odd. Specifically, mn = (m - 1)n + n. Since m is odd, m - 1 is even. Since m - 1 is even and n is an integer, (m - 1)n is even. Since (m - 1)n is even and n is odd, (m - 1)n + n is odd.

So, p | mn → (p | m ∨ p | n) -- for p, m, and n as integers and p prime -- is a lemma that I'll rely on to prove that no rational number squares to 2.

This proof can be, and usually is, stated in a less elaborated form than the following, but I think there is some use in making each step explicit--even though this is still an informal proof.

Suppose, with the goal of inferring a contradiction, that there is some rational number that squares to 2. To be rational, it must be expressible as a quotient of integers. And any quotient of integers can be expressed in lowest terms (by dividing both the numerator and denominator by their greatest common divisor). Call the resulting numerator and denominator a and b, respectively, and note that at most one of a and b is even.

We have (a / b)² = 2, so a² / b² = 2, so a² = 2b². Since a² is equal the product of 2 and an integer, it is even. Since a² is even and a² = aa, either a is even or a is even, so a is even. Thus there is some integer k for which a = 2k. Then a² = (2k)² = 4k². But a² = 2b², so 4k² = 2b², so 2k² = b², so b² is the product of 2 and an integer and is thus even.

Oh :) :)

The reason I've brought up proof by contradiction is, in a common way of formalizing this, you get closed sentences about a and b. But a and b aren't any particular numbers. Not only that, the point of introducing them is to show they cannot exist.

That strains the view that one cannot use standard logic to talk about nonexisting things... unless one realizes that writing those unquantified closed sentences is effectively a technique to infer quantified sentences from other quantified sentences.

(Also, some formal proof systems don't require that one actually do the instantiation to produce unquantified sentences about a and b.)

Considering that we regard sentences generated according to permitted technique of proof by contradiction, in the subproof in which the consequences of a sentence we believe to be false are explored, to be sentences that have a truth value -- that is, we regard them, for purpose of considering their implications, to be true or false -- it might seem that what sentence are taken to have a truth value is extremely expansive.

Given this, it might seem that any grammatically declarative sentence that has nothing that corresponds to a free variable and in which no part is ambiguous can be considered to have a truth value.

But that is probably not the case. Specifically, there are examples of sentences that strongly appear to meet those qualifications, and that most people (including most logicians) who encounter believe meet those qualifications, but that cannot be said to be true or false. For example:

> This sentence is false.

If it's false then it's true. If it's true then it's false.

You may be familiar with that sentence. It's the liar paradox. There are a number of sentences that aren't all effectively the same and many of which are far less compelling as paradoxes, that are called the liar paradox. The etymology is that many versions involve a speak who claims to be a liar.

There is not widespread agreement about precisely what generalizable properties of "This sentence is false." cause the problem, but it is very widely agreed that it cannot be rightly said to have a truth value (at least in a two-valued logic, which is the kind of logic I'm talking about)

Some people think all or part of the problem in the liar paradox is self-reference: that the sentence refers to itself. Some self-referential sentences don't seem to be a problem. There are also sentences that seem to be a problem in the same way as the liar paradox but that either are not self-referential or are self-referential in a weaker way. Quine' paradox is:

> "yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

Sentences that have truth values are called statements. I've held off for so long in using that term, because I feel it carries considerable philosophical weight. In a first-order system with a unary predicate F and a constant a, with no real-world interpretation given to either of them, this is a sentence and it is regarded to have a truth value -- proof rules based on the idea that it is true or false are permitted:

Fa

But is that really true or false? What does that mean?

One approach, that was once thought to be adequate, is to say that it's true if you can prove it in that system and false if you can prove its negation in that system. This is not quite as silly as it sounds because, for any formal system that is consistent (by this I mean, no contradiction can be proved in it, i.e., you cannot use it to prove a sentence of the form p ∧ ¬p), one might regard it as describing all the various worlds or structures that work in keeping with its rules.

The problem comes when you consider that some sentences that you can express in a system may be independent of that system, i.e., the system can neither prove nor disprove them. For example, if we don't have any axioms, but just a predicate F and a constant a, then

Fa

is independent of our system.

Many years ago, it was assumed that, in this sort of situation, one should just get oneself a better system.

A system that can decide every sentence expressible in its language--that is, given any sentence it can express, either that sentence or its negation is a theorem of the system--is said to be complete. It was once hoped that a complete system could be found that could be used to perfectly formalize mathematics. It was a big deal when Gödel proved this cannot be done.

(It is not that there are no complete consistent systems, but that the complete consistent systems are either not effectively generated--there's no practical way to know what their theorems actually are, even in principle--or they are not expressive enough even for basic arithmetic.)

@EliahKagan *** involve a speaker

It occurred to me that you probably meant was the prevalence of mosquitoes seasonal, not my insomnia!

the answer to that question is a resounding yes! Mosquitoes are, I am informed by everyone, prevalent in winter. But I don't think the mosquitoes themselves are aware of it

or at least it hasn't deterred them from doing their work all year round

@Zanna I did mean your insomnia.

oh :)

@EliahKagan yes I am familiar with this; I have encountered it many times in fiction, probably in Jorge Luis Borges among others

Cool. :)

@EliahKagan this also I have heard about

Some other paradoxes are due to the appearance of something being well-defined that is not. Of particular interest because of its connection to set theory is the Grelling-Nelson paradox. Some adjectives accurately describe themselves while others do not. Call an adjective that accurately describes itself autological. Call an adjective that is not autological heterological. Is "heterological" autological or heterological?

On the one hand, this is really uncompelling. "Heterological" and "autological" don't really seem well-defined, since what it means for an adjective to accurately describe itself is so nebulous. And yet it seems like the problem cannot be fully explained by that intuitive way in which they are not well defined.

Another more fundamental way autological and heterological may be regarded as not well defined is that whether or not an adjective accurately describes a word (whether that word being described is an adjective or not, and whether that word being described is the adjective describing it or not) is not a feature of the individual words but depends on the language as a whole.

hmm yes

We might consider some dialect of English and formalize it, somehow, or at least imagine doing so, to eliminate the ambiguity of what describes what. Call this language E. Then we might introduce the words "autological" and "heterological" that applies to adjectives in language E with the meanings "accurately describes itself in language E" and "not heterological", respectively. But these words are not themselves in language E.

We can call E with "heterological" and "autological" added E'. But "heterological" and "autological", which are words in E', are still about language E. Then the problem with asking if "heterological" is autological or heterological becomes immediately apparent, because they don't apply to all adjectives in E', just to those in E, and they are about the semantics of adjectives in E, which might not have the same semantics in E' anyway.

Relatedly, consider the Berry paradox (which I looked up to get an actual formulation of, since that is easier than doing the computation). It consists of a phrase like:

> The smallest positive integer not definable in under sixty letters

There are other variants--here's one of the top of my head, in the phrasing I would usually use (but there is not intended to be any difference in meaning between "definable" and "specifiable"):

> The smallest nonnegative integer not specifiable in fewer than a billion words (short scale).

Unlike the Grelling-Nelson paradox, the Berry paradox immediately feels compelling. It feels like there is a problem here.

To figure out the partial mapping between English expressions (of whatever kind; perhaps we're not limiting ourselves to noun phrases) and natural numbers, one must choose a particular formalization of at least the parts of English one wishes to recognize as specifying numbers.

Suppose we develop such a formal fragment of English. Call that fragment F. In defining F, we will not have managed to define "definable" or "specifiable", because (I'll just use "specifiable" from here on out) specifiable in what? We will also not have managed to correctly define "specifiable in F". Whatever machinery F provides to specify numbers, it will not be sufficient.

This no longer really seems like so much of a problem; the Berry paradox is intuitively compelling because our informal language is very powerful and it seems, at first glance, like it might be powerful enough for this, though it is not. It is not surprising that a formal language we don't actually use and in which any nebulous specification is ill-formed is now powerful enough to specify numbers relative to its own specifying power as observable from outside it.

Of course, we can still say things like:

> The smallest nonnegative integer not specifiable in fewer than a billion words (short scale) in F.

But we cannot formalize it in F. We can make F' for this, though, consisting of the expressive power of F plus some more expressive power that lets us specify things in terms of the abilities of F. But then there is no paradox; it is in the more powerful F' that we are managing to specify, in 16 words (or however many it is in the formal language F') a number that requires at least 10⁹ words to specify in F.

A caveat: The Berry paradox is, I believe, actually somewhat messier than I am letting on, because you might be able to specify a particular number but not be able ever to know what number you specified. It's really something like decidable specification that I'm talking about here, and arguably that does not do justice to the full generality of the Berry paradox.

@EliahKagan * is not powerful enough

That one I meant XD

I think I found a very small "life hack" to waste less time in the evenings

@Zanna :)

@Zanna What's that?

@EliahKagan I should watch that movie. I haven't.

It also works to ask either guard, "Would you tell me that this door leads to the castle?" (Then one need not negate the answer, and it works even if there is only one guard.)

one feels this may be why the guards are a bit fazed by her question

it wasn't quite what they were expecting

@EliahKagan Every evening I first sweep the floor and then mop it. I keep a small table in my hall / lounge and I usually put it upside down on my desk while cleaning the floor. This means I can't sit at my desk or use my laptop, which is almost inevitably on my desk, until I have finished cleaning the floor. I realised that I would take a break after sweeping the floor to check messages and stuff, on my phone, and waste a lot of time that way.

Now I decided to place the table upside down on the bed (there is very little furniture in my apartment) instead (I did this accidentally first, because there was too much stuff on my desk). I can access my desk, so I can do my work, so I don't waste so much time. In fact I clean the floor faster because I don't feel a vague sense of frustration that I can't access my desk!

Cool!

:)

It's interesting, and in line with my own experience, that eliminating or reducing some distractions causes other greater distractions. In this case, it seems that a useful distraction was inadvertently eliminated, causing the problem. If I understand correctly.

yes indeed

Although the Grelling-Nelson paradox is due to the false appearance that "heterological" has been given a clear meaning, there are paradoxes of that form that don't result from any lack of clarity and that do not involve any invalid deductions, but that result from inconsistent premises (that might seem at first to be consistent).

One such paradox is the barber paradox, which like the Grelling-Nelson paradox is very closely related to Russell's paradox. I had, until very recently, though Russell actually devised the Barber paradox as well, but it looks like that's not the case. Russell used the barber paradox as a way of explaining Russell's paradox.

(Specifically, I have been told, as a way of showing that Russell's paradox arrives at a contradiction from a valid deduction and that the problem is inconsistent premises.) Since we're already talking about paradoxes that are often informally stated, and since I have not stated the axioms of Frege's set theory to which Russell's paradox applies, I'll present the barber paradox first. Though I imagine you may already be familiar with it.

> There is a town whose barber shaves all and only those who do not shave themselves. Does the barber shave himself?

(That statement of it is intuitive but it can be made more specific. The barber is taken to be a townsperson, and it is specifically townspeople who do not shave themselves that the barber shaves. This makes it easier to recognize that the problem does not arise from questions like "Does the barber shave the town?" and also shows how the paradox can be formulated symbolically in a first-order system whose universe of discourse consists of the people of the town.)

I guess the barber will have to make some exception for himself

That's one way of putting it, yes. As you've noticed, the barber shaves himself if and only if he doesn't. So the premise that leads to this contradiction--the claim that there is such a barber (or, as some people say, the claim that there is such a town with such a barber) is inconsistent, and therefore false.

At one time during his work on mathematical logic, Gottlob Frege developed and used a set theory in which, for anything that can be said about x, there exists a set of all and only those objects x that satisfy it. Some people describe this by saying that, in Frege's set theory, every property has an associated set, or that every unary predicate has an associated set.

These characterizations are fairly good and they illustrate that Frege was trying to do: use sets with the same power as predicates (more precisely: as predicates, but where equality of sets is extensional, rather than not being defined or being defined in some intensional way).

You might wonder how this can be done in first-order logic, since one cannot quantify over predicates, i.e., with F as a unary predicate, this is not a well-formed sentence in a language of first-order logic:

∀F ∃s ∀x (x ∈ s ↔ Fx)

But that's not the problem with Frege's set theory.

You can have a first-order system with the same first-order theorems as that second-order sentence would give you. I'll say how below; it is analogous to how, if you wished to state the axioms of identity that permit substitution, you would be able to do so. That is, this second-order sentence with F as a unary predicate is not well-formed in a language of first-order logic either, but the effect of it can be achieved nonetheless:

∀F ∀x ∀y ((Fx ∧ x = y) → Fy)

Also, I don't think Frege was actually working or developing a first-order system, at least not strictly speaking... though conceptually, if his set theory were consistent, it would eliminate most of the benefit of higher order logics. However, we can formulate Frege's set theory as a first-order system. Whatever kind of system it is formulated as, it is inconsistent, due to Russell's paradox.

x ∉ x (you might prefer ¬ x ∈ x) is a formula about x. That is, it is possible to ask of a set whether or not it is not a member of itself. So there is a set of all and only those sets that are not members of themselves. Call that set r. That is, in set-builder notation:

r := {x | x ∉ x}

Or with a definite description:

r := ɿs ∀x (x ∈ s ↔ x ∉ x)

The important thing is that it is true of r that:

∀x (x ∈ r ↔ x ∉ x)

(r is today conventionally called the Russell set.)

Do you see the inconsistency that can be inferred from this, analogously to the barber paradox?

r is the set of all sets that are not members of themselves.

@EliahKagan To clarify, I mean only that set defined as r is today called the Russell set, not that the symbol r was historically used for this when it wasn't called that.