|
|
On 28 Aug 2006 09:40:50 -0700, "MoeBlee" <jazzmobe@xxxxxxxxxxx> wrote:
>David C. Ullrich wrote:
>> >So how did you get card(T) < card(P(S)) without the axiom of choice?
>>
>> Come now.
>>
>> Without AC I'm not sure what card even means. So forget that.
>
>Without AC, I take card comparisons to be quick jotted notation for the
>existence and non-existence of injections. In my original problem I
>didn't mention card:
>
>Show (in Z set theory, without choice):
>
>AxEy(x equinumerous with y & x disjoint from y).
>
>Then, in my response to Rupert, I did use card, but I could have
>written it out without card by asserting the existence or non-existence
>of injections instead (that proof used the axiom of choice anyway, but,
>if I'm not mistaken, it did not use the axiom schema of replacement so
>I was still in Z not ZF). What I'm interested in is whether this is a
>theorem of just Z - without choice, regularity, or replacement.
>
>I'm not trying to give you a hard time. I just wanted to understand
>whether you meant for your prove to rely upon choice.
>
>> But come on now - all we need here is that there exists y such
>> that y is not in T; the fact that card(T) < card(P(S)) was just
>> supposed to be a convenient way to see there is such a thing,
>> but in fact P(S) is irrelevant.
>
>Then I don't understand the proof. I understand this:
>
>> Theorem: For every T there exists y such that y is not an element of
>> T.
>>
>> Proof: Surely you've seen the proof of this? QED.
>
>Of course, and I used it, though unstated, in my proof of the finite
>case. And I understand your y not in T. And, by filling in the step I
>mentioned, I understand your original proof, but using the axiom of
>choice. I just wanted to know if we can get the theorem without choice.
I really don't see what the problem is. Where does the following
argument use AC?
Thm. If S is a set then there exists a set S' disjoint from S
which is equinumerous with S.
Proof: Let T be the set of all y such that there exists x with
(x,y) in S. Choose y such that y is not an element of T. Let
S' = S x {y} = {(x,y) : x in S}. Then x <-> (x,y) is a bijection
of S and S', and S' is disjoint from S, since y is not in T. QED.
Silly details, written out explicitly lest AC be lurking in
the bits left to the reader:
SD1: Define f : S -> S' by f(x) = (x,y). The definition of
S' shows that f is surjective. And (x,y) = (x',y) implies that
x = x', hence f is injective.
SD2: Suppose that z in in S intersect S'. Then the definition
of S' shows that there exists x in S with z = (x,y). So
(x,y) is in S, hence the definition of T shows that t is in
T, contradicting the choice of y.
SD3: If T is any set then there exists y such that y is not in T.
Proof: Suppose to the contrary that every y is an element of T.
Let A = {y in T: not y in y}. Since A is an element of T we
have A in A if and only if not A in A, contradiction.
>Thanks,
>
>MoeBlee
************************
David C. Ullrich
|
|