'normal' set paradox


by radou
Tags: normal, paradox
radou
radou is offline
#1
Jun30-05, 06:53 PM
HW Helper
radou's Avatar
P: 3,225
Let's define S as a 'normal' set if [tex]\neg(S \in S)[/tex]. Now let's look at the set of all normal sets N. If N is normal, then is belongs to the set of all normal sets N, and therefore it is not normal. On the other hand, if N is not normal, then it doesn't belong to the set of all normal sets N, and therefore it's normal. I'm very confused (or very dumb) :)
Phys.Org News Partner Science news on Phys.org
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
Hurkyl
Hurkyl is offline
#2
Jun30-05, 06:58 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
What confuses you?
radou
radou is offline
#3
Jun30-05, 08:09 PM
HW Helper
radou's Avatar
P: 3,225
Well, we started with the assumption that the set of all normal sets N was normal and came across a contradiction - it is not normal. Then again, if we assume that N is not normal, we reach the fact that it is normal. Both ways, we get a contradiction.

honestrosewater
honestrosewater is offline
#4
Jul1-05, 03:29 AM
PF Gold
honestrosewater's Avatar
P: 2,330

'normal' set paradox


Maybe you should change the axioms(s) that allowed you to conclude that N was a set. Which axiom(s) allowed N to be a set?
Hurkyl
Hurkyl is offline
#5
Jul1-05, 05:29 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
Oh good, that's where I was hoping the confusion lied.

Notice that there's a hidden assumption -- there exists a set of all normal sets. So what you have here is a proof by contradiction that this assumption is false!
radou
radou is offline
#6
Jul1-05, 01:11 PM
HW Helper
radou's Avatar
P: 3,225
Yup, right. There's something more. A set can only be an element of another set if this other set is a family of sets, rather than just an ordinary set. So, if N is a family of sets, in the more consistent notation of P(N), then a set is defined as 'normal' if P(N) is not an alement of itself. But, can P(N) actually be an element of itself? It's elements are all subsets of N. I think P(N) can only, by definition, be it's own subset... So, if this is true, then the paradox actually doesn't make sense from the beginning.
matt grime
matt grime is offline
#7
Jul1-05, 02:35 PM
Sci Advisor
HW Helper
P: 9,398
Quote Quote by radou
Yup, right. There's something more. A set can only be an element of another set if this other set is a family of sets
not necessarily

So, if N is a family of sets, in the more consistent notation of P(N)
P(N) usually means the power set of N. what mlore consistent notation are you atalking about?
radou
radou is offline
#8
Jul1-05, 02:40 PM
HW Helper
radou's Avatar
P: 3,225
oops, i messed a few facts up...nevermind, i was talking about the power set P(N).
hicksrules
hicksrules is offline
#9
Apr11-11, 09:09 AM
P: 1
There is nothing fishy about your argument. Though it might be ill posed. The paradox you are conveying is a famous one. It is called a "Godelian riddle" and it highlights the incompleteness theorem formalised and roved by Godel. In a nutshell the incompleteness theorem says that no formal set of axioms for mathematics is complete, meaning that there exist propositions that can neither be proved nor disproved using the axioms.

Here is a better version of your paradox. Denote the set of all two player games that end as S. Define game X with the following rules

1) First player picks a game from set S
2) Second player makes the first move

(as an example of a run of game X, i pick chess and you play the first move.). The question now is. Does X belong in set S?

If it does belong in the set, then consider the following sequence of events. Playing game X the first player chooses a game from S. Let him chose X, since by assumption X is in S. The second player now executes the first move of game X which is to choose a game from S. He too picks X. The players continue in this fashion at infinitum. Clearly then game X does not end and therefore it does not belong in S.

Now for the converse. Assume that X is not in S. Then in playing game X, the argument above no longer holds, since X is not in S. Hence game X will now end, and therefore belongs in S.
pwsnafu
pwsnafu is offline
#10
Apr11-11, 11:20 PM
Sci Advisor
P: 773
Quote Quote by hicksrules View Post
The paradox you are conveying is a famous one. It is called a "Godelian riddle" and it highlights the incompleteness theorem formalised and roved by Godel.
No. It's Russel's paradox on Cantor's Naive set theory. This is a problem in whether something can be defined, not proved. "Q is the Gödel number of a false formula" simply doesn't exist.
Personally I think the Berry Paradox is more interesting.

In a nutshell the incompleteness theorem says that no formal set of axioms for mathematics is complete
Not true. You can have completeness or consistency, you just can't have both.
eczeno
eczeno is offline
#11
May5-11, 08:31 PM
P: 242
maybe xzibit can help.



Register to reply

Related Discussions
Resolving the Barber Paradox and the Russell's Paradox General Discussion 18
What is the resolution of the The Bug-Rivet Paradox paradox in special relativity? Special & General Relativity 4
Phi- normal distribution (how to look normal tables!!!) Set Theory, Logic, Probability, Statistics 3