Mathematical Paradoxes

so PA is automatically consistent now?
Because of 100 years of a handfull people not finding a problem and a transfinite proof. I mean not that I think it's inconsostent..

I think early fourties

It may be slightly innaccurate to say "T = PA", when with respect to Gödel, the presentation of the theory matters.

It may be more accurate to say "T has the same axioms as PA".

No, it is not automatically consistent in the sense you are thinking, as the fact that T = PA depends on the consistency of PA.

>>It may be more accurate to say "T has the same axioms as PA".
so explicitly what changes between T and PA?

Here is the subtle thing that's going on.

We often implicitly identify an object with its definition; if two things define the same object, they are equal.

However, even if two things define the same object, if they do not provably define the same object (relative to whatever base axiomatic system), then this identification breaks down.

So what changes between T and PA is the associated definition. PA is given by the canonical r.e. (recursively enumerable; [math] \Sigma^0_1 [/math]) definition, while T is given by a [math] \Sigma^0_2 [/math] definition whose equivalence to the former is equiconsistent with the consistency of PA, which PA itself cannot prove. Thus PA cannot "see" that it is in fact equal to T, but it can prove that whatever T is, it is consistent, and thus, since we know that actually T = PA, T proves its own consistency.

T is equivalent to PA and can prove it's own consistency. So that means there is an axiom system T that is powerful enough to express elementary arithmetic that CAN prove it is consistent?

I'm confused, how does this not contradict the first and second incompleteness theorems?

>Specifically, what I claim is that if PA is consistent, then there is a consistent theory TT in the language of arithmetic with the following properties...

It looks like it assumes PA is consistent, which PA cannot prove, then the following things occur where T can prove the consistency of PA. Is that the gist? But how can that occur is T is the same as PA?

Ok, I read the proof. It looks like it ASSUMES PA is consistent and says IF PA is consistent (which we know by Godel's theorems PA can't prove its own consistency), THEN you can construct a T that is equilvant to PA such that PA proves T. Is that the correct understanding?

What confused me is how are T and PA different if they have the same consistent axioms? If they are the same theory then you have a contradiction of godel's second incompleteness theorem?

T is a second order theory apparently

As mentioned in , Gödel technically isn't about just the raw theory itself, but about the definition or presentation of the theory; the latter affects what it means for the theory to prove its own consistency, as expressed in (e.g.) the language of arithmetic, the assertion of the consistency of PA is actually an assertion as to the nature of whatever theory is defined by a given formula (i.e. the presentation of PA).

Sorry, can you explain what a second order theory is and how that irons out any issues? I'm not familiar with it kek

NO.

Do not lie or use terms you do not understand.

What *is*, however, true, is that T is not a recursive presentation; it is [math] \Sigma^0_2 [/math] as opposed to PA's [math] \Sigma^0_1 [/math]. Gödel applies to [math] \Sigma^0_1 [/math] [presentations of] theories.

That is too dense for me to understand. Can you unpack it in a more understandable way? I'm not an expert in logic. What I'm seeing is T is being built using the exact same axioms as PA as long as those axioms are consistent and since we are assuming PA is consistent, then PA proves T is consistent. I still can't get my head around how a consistent theory is proving itself is consistent which is in direct violation of the second incompleteness theorem. Maybe I don't understand the second incompleteness theorem well. Please unpack this for a non-logician to understand

Gödel applies to theories given by a "recursive enumeration". A recursive enumeration is an enumeration that can be done by a computer running some program: there exists some program such that the computer can recursively output all of the axioms of the theory.

Any useful mathematical theory is recursively enumerable, as only recursively enumerable theories are such that we can verify if a statement is actually in the theory.

In its usual presentation, PA is given by a recursive enumeration. What T is is a different presentation of PA that is not a recursive enumeration. The presentation of T involves a "universal unbounded quantifier"; its associated definition contains sentences like "P is in T if *for all* integers n so-and-so". This "for all" phrase cannot be checked by a computer; it is thus that this is not a recursive enumeration.

Because we, as mathematicians, are able to, in this particular case, analyze the nature of this universal quantifier and conclude that, since we know PA is consistent (which PA doesn't know), the axioms of T are precisely equal to the axioms of PA. However, the above still holds, and thus Gödel is not violated.

Thanks for this very thorough and well-written reply.

I have a dumb question... does recursively enumerably mean a finite enumeration process? Else, in my mind I am wondering how a human would check to see if a particular axiom is in a theory if there are infinite enumerations to check.

The other question I have is to see if I have the high level gist of what you said...

Godel's 2nd Incompleteness theorem is not violated because we are ASSUMING PA is consistent (which PA can't prove).

Under that assumption we construct the axioms in PA using a recursively enumerable process and construct a logically equivalent axiom system T that defines the same axioms in PA (which are consistent) in T using universal unbounded quantifiers-- dumb question here what do you mean by unbounded? A sentence containing x in a 'For all x' would be bounded by x and thus bounded yeah?--Since we are only adding consistent axioms from PA in T and since we can analyze the nature of these universal quantifiers we can deduce that T is also consistent. This doesn't violate GIT because we ASSUMED from the beginning PA is consistent and if we know PA is consistent and construct a logically eq. theory T then we know that it is also consistent.

Is that the logic? Correct me where I am wrong

>does recursively enumerable mean a finite enumeration process?
If I interpret you correctly, this is an excellent question. Indeed, given an infinite r.e. set, for any element in the set we can algorithmically tell if it's in the set, but given an element not in the set, we cannot algorithmically know if it's in the set!

However, for "recursive" theories, we can. Every recursive theory is also r.e., so Gödel applies to this special case as well. And every useful mathematical theory is recursive: we can algorithmically tell if something is in it or not.

>what do you mean by unbounded?
That the universal quantifier "for all" has unbounded domain: it is asking about "for all" of infinitely many integers (rather than being bounded, asking about "for all integers less than n" for some n).

In "For all x", x is the argument of the quantifier. Boundedness means as described above. "For all x P(x)" is asking about infinitely many things.

>Is that the logic?
Yes, sounds like it.

Great, thank you so much for taking the time to answer my questions with such detailed and insightful explanations. I really enjoyed this exercise. Logic is fascinating!

Does the set of every set that do not contain themselves contain itself?
This is one of my favourites and it's very weird isn't it?
[math]\displaystyle Let\ S=\{x|x\in x\}\implies (S\in S) \land (S\notin S)[/math]

Isn't that faulty?

If you assume that it is consistent then you can show that it is consistent by constructing T, and if you assume that it is inconsistent???

that's not a set, this was a paradox when people didn't know what sets were

nowadays it's an example used in the first class of set theory so people realize they don't know what sets are

Yes, that is a set. S is defined as the set with every element being an element if they don't contain themselves. It's very evident. Don't think you're so smart at maths, junior. I'm at uni.

But we still don't know what sets are.

>Yes, that is a set.
Get new axioms, yours are shit.

This prick misunderstood everything.

IF PA IS CONCISTENT THEN THERE IS A THEORY T WITH SO OR SO PROPERTY

Read carefully

I do not misunderstand anything, and all of my explanations are accurate. It is simply a mathematical theorem (a consequence of ZF) that PA is consistent. So everything is as stated.

He didn't. Look at the construction in the link he posted above.

>a consequence of ZF
I know what you did there

>There are infinitely as many IRRATIONAL numbers are there are RATIONAL numbers.
>Between any two IRRATIONAL numbers there are infinitely many RATIONAL numbers.

math, not even once

I really don't know why you're so sure that PA is consistent...

Just because there are some proves about it - in theories that involve mathematical notions that some people may be skeptic about?
I mean as long as there are intelligent people having a doubt, I'd not speak of it as if it was fact.

and voila the circle is complete

Well, the same holds of any two rational numbers.

Also, if we take equinumerosity as a measure of "as many as", there are more irrational numbers insofar as the cardinality of the set of irrational numbers is [math]2^{\aleph_0}[/math] while the cardinality of the set of rational numbers is [math]\aleph_0[/math].

No mathematician doubts the consistency of PA, and as stated the consistency of PA is a mathematical theorem insofar as it is a consequence of ZF. The consistency of PA really is "obvious": take the least infinite ordinal and endow it with addition and multiplication as recursively defined from incrementation.

So, I presented two somewhat advanced mathematical paradoxes in and .

Here is one that is simpler.

[math]\text{Problem}[/math]: A train initially has one person on it.

It stops successively at villages [math]v_0, v_1, v_2, \ldots [/math], and at each village two people get on and one person gets off.

Eventually, it gets to village [math] v_\omega [/math], where [math] \omega [/math] is the first infinite ordinal (if you don't know ordinals, it gets to village [math] v_\omega [/math] after stopping at all the villages [math] v_n [/math] for finite [math] n [/math]).

How many people are on the train at village [math]v_\omega[/math]?

[math]\textbf{Solution/Paradox} [/math]: As the number of people on the train is unbounded (increases on net by 1 at each village), we expect there to be infinitely many people on the train at village [math]v_\omega[/math]. But even though the number of people on the train is unbounded for finite [math]n[/math], it is possible that at village [math]v_\omega[/math], the train is [math]empty[/math]. The solution to the problem is that the number of people on the train at village [math]v_\omega[/math] can be any natural number or infinity.

Proof: Exercise.

I still feel that not doubting it doesn't grant using language that implies we know it for sure, let alone use it in an argument, dropping the condition.

Also, in the sentence above, did you assume the continuum hypothesis there?

I think we do know for sure, insofar as it is a mathematical theorem that PA is consistent. However, some may still appreciate the relativized statement.

>did you assume the continuum hypothesis there?
No. It would have been assuming the continuum hypothesis if I had written [math] \aleph_1 [/math] instead of [math] 2^{\aleph_0} [/math].

Wait, I see how you might have thought that. Well, the set of irrationals is equinumerous with [math]\mathbb{R}[/math], so also has cardinality [math] 2^{\aleph_0} [/math].

>insofar as it is a mathematical theorem that PA is consistent.
But a) that means you must trust the proof system (it involves at east Gentzens large number and that's dubious from a constructive perspective) and an inconsistent system easily prove stuff like it being consistent - an inconsistent system gives you lots of theorems, i.e. being a theorem isn't extremely assuring in of itself.

So you doubt the consistency of ZF? Silly user.

This is Russell's paradox, and it literally threw upside-down what was being considered the foundations of mathematics back then.

erm what?

PA is a super small aspect of ZF and we're discussing the consistency of PA. The doubt about ZF is severely larger.

How about you gentlemen help unravel the mysteries of this thread ?

No one knows, most of the mathematicians think PA is consistent. As inconsistent theories prove whatever you want (at least under classical logic), giving a proof of the consistency of a theory is meaningless in the sense that you will never be completely sure that the theory is objectively consistent.

So you doubt the consistency of PA? Even a sillier user!

The consistency of PA is absolutely utterly obvious. Literally the only way to doubt it is to doubt the existence of an infinite set. Have an infinite set, and you have [math]\omega[/math], the least infinite ordinal, which can be canonically endowed with an arithmetic structure (by recursively defining addition and then multiplication from incrementation) such that the resulting structure models PA.

The consistency of PA is literally, absolutely beyond any reasonable doubt.

I too think it's consistent, but the way you talk is just dogmatic.
If it were UTTERLY obvious, then it wouldn't have been a research goal in Hilberts time to show it by conservatice means.

>The "set of reals" is so much not really defined by ZFC

I'm pretty sure you can define a model of the reals in ZFC.

>It is simply a mathematical theorem (a consequence of ZF)
yeah but ZF is a dubious set theory and we do not know whether ZF is consistent

>Literally the only way to doubt it is to doubt the existence of an infinite set.
I have no problem rejecting this faith

You're right that I was being a bit dogmatic, but I'm sure that even at the time its consistency was obvious. The challenge was to prove it from finitary principles, which is not possible. But anyone who can visualize an infinite set can visualize a model of PA.

Of course ZF is consistent.

t. set theorist

With emphasis on the plural.
The axioms of the theory leave so much open that addingcthis and that other axiom makes a huge differece with regard what actually has to be in the sets or how they relate to each other. This freedom makes forcing even possible.

So now you're down to "visualize". Sure the guys who got rekt by Russels and Girads paradox could visualized their system just fine. Of course, if you're looking at a feaspable subsystem, the inconsistency isn't there.
Adding the negation of the continuum hypothesis to a theory including axioms that fater decades of work have been show to prove the contonuum hypothwsis - this gives you systems unknowing individuals will take decades to find out are inconsistens.

Fater isn't a word, and I have no idea what you're trying to say about CH.

after. friendo.

bump

Paradoxes so far. Anyone have others?

Ostensible math paradoxes only (there are no true paradoxes in mathematics).

I am reading on this

Is this just a Hamkins thread? Sounds like everything here is related to him in some manner.

Only one of the paradoxes is due to Hamkins — the definable reals paradox — but he happened to also provide a nice recapitulation on mathoverflow of Feffer's proof of an axiomatic system whose axioms are precisely those of PA but which proves its own consistency.

Well thanks for answering and I've enjoyed reading the thread.

Grelling–Nelson_paradox

uppose one interprets the adjectives "autological" and "heterological" as follows:

An adjective is autological (sometimes homological) if and only if it describes itself. For example, the English word "English" is autological, as are "unhyphenated" and "pentasyllabic".
An adjective is heterological if it does not describe itself. Hence "long" is a heterological word (because it is not a long word), as are "hyphenated" and "monosyllabic".
All adjectives, it would seem, must be either autological or heterological, for each adjective either describes itself, or it doesn't. Problems arise in a number of instances, however:

The Grelling–Nelson paradox arises when we consider the adjective "heterological". One can ask: Is "heterological" a heterological word? If the answer is 'no', "heterological" is autological. This leads to a contradiction, for in this case "heterological" does not describe itself: it must be a heterological word. But if the answer is 'yes', "heterological" is heterological. This again leads to a contradiction, because if the word "heterological" describes itself, it is autological.

Is "heterological" a heterological word?
no → "heterological" is autological → "heterological" describes itself → "heterological" is heterological, contradiction
yes → "heterological" does not describe itself → "heterological" is not heterological, contradiction

en.wikipedia.org/wiki/Grelling–Nelson_paradox

That's a fine one, and it is an analogue to the barber who shaves those who don't shave themselves, both of which are analogues to Russel's paradox.

While a paradox of self-referential language, it is not a mathematical paradox because the concepts are not expressible even in an arithmetized syntax of, say, first-order logic. The aspect that prevents the construction of a word like heterological is Tarski's undefinability a truth -- defining "heterological" requires quantifying over the interpreted truth values of other sentences.

Thus, while a paradox of language (though really, it seems more to illuminate a restriction on what we can do with defining new words, just as Russel's paradox restricts the former axiom of universal comprehension), it has no analogue to any ostensible mathematical paradox.

>it has no analogue to any ostensible mathematical paradox.
what do you mean by math here ?

Math, a mathematical theorem. For example, Skolem's paradox is an ostensibly paradoxical *mathematical theorem*: that there exist countable models of set theory.

The other four results presented here are mathematical theorems that appear to be paradoxical.

Russel's paradox is neither a paradox nor an ostensible paradox in mathematics, but a proof of the inconsistency of a certain axiom system.

That's pretty neat.

bump

Not really in the same spirit as the other facts on this thread, but something I found interesting:

There's an uncountable collection of sets [math]A \subseteq P(\mathbb{N})[/math], such that for every [math]a,b \in A[/math], either [math]a \subseteq b[/math] or [math]b \subseteq a[/math].

Try to construct one!

Put [math] \mathbb{N} [/math] in bijection with the rationals and take the dedekind cuts?

>Try to construct one!
I have two answers for you:

1. I'm a constructivist, I can't construct and uncountable set.

2. I'm a classical logician, here's your set
[math] A = P( {\mathbb N} ) \setminus \{ B \in P( {\mathbb N} ) | \forall a. \, \forall b. \neg ( (a \subseteq a) \lor (b \subseteq a) ) \} [/math]

>Try to construct one!
I have two answers for you:

1. I'm a constructivist, I can't construct and uncountable set.

2. I'm a classical logician, here's your set

[math] A := P( {\mathbb N} ) \setminus \{ X \in P( {\mathbb N} ) | \exists (a,b\in X). \ \neg (a \subseteq b) \land \neg (b \subseteq a) ) \} [/math]

What does it mean for one integer to be a subset of another? I must assume you are identifying integers with finite ordinals. Given that, because for any two ordinals one is a subset of the other, your set [math]A[/math] is all of [math] \mathcal{P}(\mathbb{N}) [/math] which clearly does not work.

Not but this is a valid answer, well done. So could have in fact said a continuum-sized collection [math]A \subseteq \mathcal{P}(\mathbb{N}) [/math] such that etc.

> I'm a classical logician

how's unemployment treatin ya?

I remember another one.

[math]\textbf{Paradox} [/math]: In the absence of the axiom of choice, it is possible to partition [math]\mathbb{R}[/math] into more than continuum disjoint subsets (!). You don't even need a strange partition to do this — [math] \mathbb{R} / \mathbb{Q} [/math] can have strictly greater cardinality than [math] \mathbb{R} [/math] !

Proof: The reason our intuition breaks down is that, in the absence of choice, this partition does not actually beget a surjection of [math]\mathbb{R}[/math] onto a set of strictly greater cardinality. Regardless, a quotient structure having strictly greater cardinality seems blatantly false. The proof of the consistency of the assertion is quite nontrivial; it follows from the construction of a model of set theory in which every set of reals has the baire property, together with a modified version of a 1947 theorem of Sierpiński.

These things really bed the question hoe mathaticans working in the field overcome their cognetive dissonace when they realize their formal machinery and the sfuff they discover in it, is a failure when judged by how good it captured, as a mathematical theory, any prior notion of "sets".
It's just some nice expressible theory of a binary predicate - not a theory of collections any any good sense.

>it has no analogue to any ostensible mathematical paradox.
What about tarski's undefinability of truth? It's more or less the same.

Imo the undefinability of truth doesn't even look like a paradox. It's just an amazing result, albeit surprisingly simple to prove.

Well, I guess that to those who have no idea what the theorem actually says, it could seem vaguely paradoxical.

so we have been infiltrated by the ultrafinitists

how long will it be until the freemasons and scientologists come

>freemasons and scientologists
I managed to imprison them on where they belong. I hear they've escaped to Veeky Forums recently but I can't investigate it personally unless I'm invited to join their thread.

Unfortunately ultrafinitists are trapped completely inside the physical conception of a universe so I've no authority over them whatsoever. Luckily a fairy can never lose an argument against an ultrafinitist.

Seems you cursed us.

I wonder if there are paradoxes once you stop fantasizing about classical reasoning and stick to predicative constructive maths.

>I wonder if there are paradoxes if you don't look at them

The existence of space-filling curves — that is, of a continuous surjection of [math]\mathbb{R} \rightarrow \mathbb{R}^2 [/math] — is fairly counterintuitive.

Here's another counterintuitive fact:

The multiplicative group of the complex unit circle is isomorphic to that of [math]\mathbb{C}^*[/math].

In this direction there this nice one:
For any compact metric space there is a continous surjection from the cantor set to it.

You must need additional conditions, as a set with [math]2^{2^{\omega}}[/math] elements endowed with the trivial topology (the only set in the topology is the entire set) is a counter example.

I think that what you're trying to say is that, if [math]X[/math] is any Polish space, and [math]\mathcal{N}[/math] is the Baire space, there is a continuous surjection [math]\mathcal{N} \rightarrow X [/math].

it's clearly not

That space is not hausdorff so is not metric
It's similar to that result, and proved with a similar technique. But I think this one is more immediately striking, the cantor set seems pretty "sparse" that it can cover, say, any n-dimensional ball is pretty cool.

you can have a continuous suryection from Cantor in a line to an n dimensional compact ball? source?

I'm glad you think so; that means it was appropriate for this thread.

But what I said is a fact.

sciencedirect.com/science/article/pii/0022314X69900110

jesus

I dont have a source, this theorem is usually given as an exercise on a lot of analysis books. What you can do is look up a proof for this and adapt it for this exercise.
A proof of that result is given for example in theorem 2.2.8 of the book "geometric measure theory" by Federer, though there must be a more reader friendly treatment somewhere...

>>But what I said is a fact.
>
>sciencedirect.com/science/article/pii/0022314X69900110
>proof by contradiction

people are paid for this.

mathboi

Moron.

Here's an extremely counterintuitive puzzle.

You and Bob are going to play a game which has the following steps.

1. Bob thinks of some function [math]f: \mathbb{R} \rightarrow \mathbb{R} [/math] (arbitrary; doesn't have to be continuous or anything)

2. You pick an [math]x \in \mathbb{R} [/math]

3. Bob tells you the value of [math] f(x_0) [/math] at every [math]x_0 \neq x [/math].

4. You guess the value of [math]f(x)[/math]

You win if you guess correctly.

What is an optimal strategy?

[math]\textbf{Bizarre} \ \textbf{Resolution}[/math]: You would think that it's hopeless, that the value of [math]f(x)[/math] is totally random relative to the values of [math]f[/math] at all other points. However, [math]you \ have \ a \ strategy \ that \ wins \ with \ probability \ 1 [/math].