Math 101

[President]

Theorem: |S|<|P(S)| for all S.

Proof:

Suppose that f is a function that maps S into P(S).

Let x be an element in S.

Since f maps into P(S), f(x) ∈ P(S).

Thus, f(x) is a subset of S.

So, x ∈ f(x) or x ∉ f(x).

Let C = {x in S |x ∉ f(x)}

Since C is a subset of S, C ∈ P(S).

Assume that f maps S onto P(S).

Then there exists an x in S such that f(x) = C.

Either x ∈ C or x ∉ C.

Case 1. Suppose that x ∈ C.

By the definition of C, x ∉ f(x).

So x ∉ C. Contradiction!

Case 2. Suppose that x ∉ C.

By the definition of C, x ∈ f(x).

S x ∈ C. Contradiction!

Either way, we get a contradiction.

Therefore, f does not map S onto P(S).

Hence, there does not exist a function that maps S onto P(S).

So, P(S) does not have the same size as S: |S| ≠ |P(S)|.

Since |S| ≤ |P(S)| and |S|≠ |P(S)|, it follows that |S|<|P(S)|.

---------------------------------------------------------------------------
How are the parts in bold relevant to the sentences that come right before them? They totally appear out left field and bear no relation to anything that precedes them. This proof is driving me up the wall. Please, help.

Thanks.

[President]

Помню в мой последний визит на етот сайт, тут была пара математиков вроде. Мож они знают. До сих пор никто мне не может внятно обьяснить или просто у меня мозгов не хватает.

[Барон_Мюнхау]

Theorem: |S|<|P(S)| for all S.

Пусть -∞ ≤ S ≤ ∞.
Допустим, P(S)= sin/cos/tan/etc.
T.e. абсолютное значение P(S) всегда > самой S ?!?!?!?

[Quanty]

Что такое P(S) и что такое S?

[President]

S is a set. P(S) is its power set.

[President]

Here's like the 10000000000....th try:
__________________________________________________ _________________________________--

Suppose |N| = |P(N)|.

To that end, we will try and establish bijection between N and its power set P(N) like this below:

x f f(x)

N P(N)

1 ↔ {2, 3, 8}

2 ↔ {3, 4, 9}

3 ↔ {3, 6, 9}

4 ↔ {1, 9, 4}

. . .

. . .

Some natural numbers (x's) dont appear in f(x). Let's call the set of all such natural numbers (x's) C. Since the power set contains all sets of natural numbers, it contains C. So there has to be a bijection between a natural number(x), say c, and C as per the assumption that |N| = |P(N)|, like so:

x f f(x)

N P(N)

c ↔ C

In bijective pairs(I am sure there are more proper and technical ways to say this) such as 1 ↔ {2, 3, 8}, 2 ↔ {3, 4, 9}, 3 ↔ {3, 6, 9}, 4 ↔ {1, 9, 4}, x is either in f(x) or not. This property is preserved in all bijective pairs(Why? Not sure.). But the would-be bijection c ↔ C doesnt seem to abide by this property:

If c is in C, x is in f(x). But C is defined as a set that contains only the natural numbers(x's) that are not in f(x). So c is not in C. If c is not in C, x is not in f(x). All the natural numbers(x's) that are not in f(x) are contained in the set C. So c is in C. Contradiction.

Again, by the property above, in all the bijective pairs, x is either in f(x) or not, but in the pair c ↔ C, c is neither in C, nor outside it, so it fails as a bijection.

A single non-bijective relation like c ↔ C is enough to invalidate our assumption that there's one-to-one correspondence between N and P(N).

Therefore, |N| =/= |P(N)|.

-----------------------------------------------------------------

I was told "It might help to see this actually proves surjection is impossible, not just bijection.".

[President]

Пусть -∞ ≤ S ≤ ∞.
Допустим, P(S)= sin/cos/tan/etc.
T.e. абсолютное значение P(S) всегда > самой S ?!?!?!?

S is a set, P(S) is its power set, not a trig function. No absolute values here. )

[Quanty]

понятно. это классический результат (теорема Кантора).

что непонятно, например, в этом доказательстве? http://www.math.ucla.edu/~hbe/resour...06w/cantor.pdf

могу попытаться объяснить

[President]

понятно. это классический результат (теорема Кантора).

что непонятно, например, в этом доказательстве? http://хттп://щщщ.матх.уцла.еду/ъхбе...06щ/цантор.пдф

могу попытаться объяснить

Спасибо за линк. Достаточно толковое обьяснение. Пока вопросов не имею, но они обьязательно будут. Как будут, зайду.

[реднек]

Теорема неверна.
Рассмотрим пустое множество. Оно не имеет подмножеств. Его паурмножество есть следовательно само пустое множество. Отчего следует что их размерность одинакова.