Counterintuitions and the well-ordering theorem [Logic]

Prev: Solutions manual to Entrepreneurship 1e Bygrave Zacharakis
Next: Solutions manual for Engineering Mechanics Statics (12th Edition) by Russell C. Hibbeler

From: WM on 22 Nov 2009 10:14

On 22 Nov., 15:12, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote:
> Bill Taylor says...
>
> >stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote:
> >> The claim "There is no power set of omega" is just as dubious,
> >> ontologically, as the claim "The power set of omega exists".
>
> >This SURELY can't be right! The default option is for things NOT
> >to exist, e.g. fairies etc.
>
> That default is part of the scientific method for discovering
> the truth about the *physical* world. What does it say about
> abstract objects? *WHY* should there be a default?

This is so because every "abstract object" can be traced back to the
physical world (of the brain thinking this abstract object). This may
not yet be possible in every case. But with more knowledge about the
brain functions everything can be reduced to a physical object. In
particular because of this fact the assumption of unidentifyable
numbers having an independent existence is medieval superstition.

Regards, WM

From: Daryl McCullough on 22 Nov 2009 12:51

Keith Ramsay says...

>It seems to me that the main difference is that the attempted
>justification for the use of complex number succeeded with
>relative ease. (It took a good span of time to settle the issue
>but since the power set was stated we've had a lot more
>activity on the philosophical and logical fronts than they were
>able to do when the complex numbers were a mystery.)

Well, there is one sense in which the power set of omega is
no more problematic. We just introduce the term, P(omega), together
with the rule: If X is a set, and every element of X is a natural,
then X is an element of P(omega).

This is basically just introducing "is an element of P(omega)" as
a synonym for "is a subset of omega". There is no ontological
commitment yet.

It becomes more complex when we try to make sure that the other
axioms about sets (extensionality, separation, replacement, etc.)
hold for this new set that we introduced by fiat. It's not immediately
obvious that we can apply these other axioms consistently. For
example, if we allow definitions and newly introduced terms
to count as sets, then there is the problem that two definitions
may extensionally denote the same set, but this fact is not
obvious. How can we treat sets extensionally if we allow formulas
for sets?

>I think the success of the project is due to more than just the
>consistency of some set of axioms for complex numbers,
>though. The way I like to think of it is as the development of
>an interpretation of a language. That way, not only is it
>consistent to have a square root of -1 in a field, but we can
>rest assured that a question about complex numbers, whether
>there exists a z such that e^z=z for example, really means
>the same thing as the corresponding question about real
>numbers, whether there exist numbers a,b such that
>a=e^a cos(b) and b=e^a sin(b).
>
>This is an issue for me with the axiom of choice. I've made a
>small stab at coming up with a satisfactory interpretation of
>set theory with the axiom of choice. Let's say, with a set of
>representatives for R/Q. Now I have a model that would be
>adequate, L, if all I wanted was to make the usual axioms and
>AC true in the model. But it interprets statements wrong. It
>converts the existence of a measurable cardinal into an odd
>and provably false statement about ordinals; but that's not
>what I mean by the existence of a measurable cardinal. It
>converts the existence of 0# into an odd and provably false
>statement, but one which doesn't mean what I mean if I were
>to talk about the existence of 0#.

I'm not sure I understand this "conversion" process. Could
you say a little more about it?

>It seems possible on the other hand that a suitable interpretation
>of the axiom of choice could exist. There are constructivists who've
>shown that certain results provable from AC can be interpreted
>constructively by looking at the contrapositive. AC says that under
>suitable conditions a subset of a set having some property exists.
>The contrapositive says that if every subset of a set has some
>property, then it's because certain conditions hold. This may not
>be entirely palatable constructively, but we can at least use it as
>a metamathematical tool: if you have proven that every subset of
>a set has some property, we can say something about what else
>you must've proven along the way.

The axiom of choice informally can be described as going from
"forall x:A, exists y:B, Phi(x,y)"
to
"exists f:A -> B, forall x:A, Phi(x,f(x))"

Here's how choice can fail, constructively. One constructive notion of a
set is that we start with some underlying type (maybe naturals), and
we apply a partial equivalence relation to the elements. For example,
the rationals are pairs <x,y> of integers such that <x,y> == <x',y'>
if and only if y ~=0 and y' ~= 0 and x*y' = x'*y.

A constructive proof of a statement of the form
"forall x: rational, exists y:natural, Phi(x,y)
might involve an operation f which given a *representation*
of a rational x, will return a natural y such that
Phi(x,y) holds. This by itself doesn't imply that
there is a *function* from rationals to naturals
such that Phi(x,f(x)) holds. The reason why not is
because the operation on representations can fail
to be a function if it is not extensional. That is,
f is an extensional function of (representations
of) rationals if <x,y> == <x',y'> implies
f(<x,y>) = f(<x',y'>). An operation doesn't need
to be extensional.

>Suppose you've proven that no ideal of a ring R containing {x,y,z}
>is maximal. Then it surely follows that you've actually proven that
>1 is contained in the ideal generated by {x,y,z}, and hence that
>1=ax+by+cz for some a,b,c in R, even if you don't realize that.
>
>I think there might be a general way to translate statements about
>these purported choice sets like a set of representatives of R/Q
>that would seem faithful to me, but I don't know how to do it yet.
>
>With the powerset axiom, I have the feeling that it's not so much
>the axiom on its own as its combination with certain others that
>is at issue. Or to put it another way, it seems like we can cook
>up interpretations that fit with it, but maybe not the ones that
>fit with everything else. One philosopher, and I wish I could
>remember for sure which one, suggested that the cumulative
>hierarchy motivating ZFC was a kind of chimera, a mix of two
>motivations that worked better separately than together: on the
>one hand, we have the idea that the problem with the Russell
>set and so on has to do with its being "too big" in some sense.
>This idea is good for motivating the replacement axiom, since
>the replacement axiom creates something that at least is not
>bigger than the set it's being applied to. On the other hand,
>we have the idea that the problem had to do with circularity of
>membership, which more directly motivates the cumulative
>hierarchy. I think in fact the combination is O.K., but it's a
>potential concern.

Okay. I think we're saying the same thing.

>I think impredicativity is more of a meaningful concern here.
>If you have a set of natural numbers, in the usual context,
>then you also have all the subsets definable by formulas
>quantifying over sets, which include all such possible subsets
>of the natural numbers. Hence you have that kind of
>impredicativity. If you have a set of all subsets of natural
>numbers (or equivalent if you have a real line), then you have
>also all of the subsets produced by selection, where the
>formula can now quantify over all of those subsets. That's a
>further kind of impredicativity. (But seriously, it hardly seems
>likely that the one kind would be O.K. while the other is not.)
>
>I think it's a valid concern that impredicative definitions might
>be consistent without being entirely meaningful.

I just wanted to point out that impredicativity is only relevant
if you think that the objects are being "brought into existence"
by the definition. If I say "Tom is the tallest person in the
room", I've identified Tom by a quantification over a set that
includes Tom as a member, so it's impredicative. However, that
use of impredicativity is harmless because Tom existed prior
to the definition. The definition is just selecting Tom, not
creating him. Mathematical impredicative definitions are similarly
harmless if you believe that the objects exist independently of
their definitions.

>You could have a model containing a phony real line that merely had
>enough of an appearance of completeness to make all of your
>impredicative definitions be satisfied. One wants to make sure
>that we're not just lucking out in this way. It should be, as
>most of us expect, that for each such definition, there is a
>bona fide set of natural numbers, the one that the definition
>gives you if you apply it to the model with *all* the sets of
>sets of natural numbers included. I just find it very difficult
>to imagine what sort of argument could be used to further
>justify the sort of vague intuition most of us seem to have
>that this is okay.

To me, ZFC set theory is best thought *not* in terms of formulas,
but in terms of some transfinite processes of constructing sets.
You start with a nonempty set S_0. Then you "reach inside" S and
pick out an element at random to get s_0 and a new set S_1 =
S_0 - {s_0}. You keep going, transfinitely many steps, until you
have removed every element of S. Any set S_alpha you could produce
at any stage is a subset of S_0. In this view, there is no reason
to believe that sets are uniquely associated with formulas. Many
sets that you might produce have no finite description whatsoever.

Of course, it's all a fiction, because there are no transfinite
processes able to pick an element at random from an uncountable
set, but it seems to me that ZFC is the theory of this imaginary
situation.

--
Daryl McCullough
Ithaca, NY

From: Daryl McCullough on 22 Nov 2009 13:01

Frederick Williams says...

>Bill Taylor wrote:
>
>> This SURELY can't be right! The default option is for things NOT
>> to exist, e.g. fairies etc.
>
>Why?

Right. There is no *logical* reason for ontological parsimony. It's
really a *strategy* for coping with the world. In science, we are trying
to come up with a theory for how the universe works
that allow us to make successful predictions (and the reason we want
predictions is to be able to make plans to accomplish desirable things
and to avoid undesirable things). A priori, there are
infinitely many possible theories that could be considered. How can
we hope to find the correct one?

Well, the strategy is that we start with as simple a description of the
world as possible, and only add complexity when evidence calls for (that
is, when simpler theories fail to account for something we observe).
This approach is *not* guaranteed to settle on the *true* laws of
the universe, but, assuming that the universe is not too chaotic,
this approach should eventually settle down into a useful approximation
to the laws of the universe. And an approximation is good enough
for most purposes.

When we are talking about abstract entities (sets, reals, measurable
cardinals, whatever), I don't think the same considerations apply.
Unless we are doing engineering, getting the theory correct doesn't
have survival advantages. It's just a matter of intellectual curiosity.
I don't see necessarily why parsimony should be our standard.

--
Daryl McCullough
Ithaca, NY

From: George Greene on 22 Nov 2009 15:36

On Nov 22, 1:01 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough)
wrote:
> When we are talking about abstract entities (sets, reals, measurable
> cardinals, whatever), I don't think the same considerations apply.
> Unless we are doing engineering, getting the theory correct doesn't
> have survival advantages. It's just a matter of intellectual curiosity.
> I don't see necessarily why parsimony should be our standard.

In the case of set (or subset) theory in particular, it is ABUNDANTLY
clear that ANTI-parsimony is the standard: YOU OBVIOUSLY want "subset"
to mean ALL the subsets,NOT JUST the ones you can consistently include
in
a countable model!!

From: Rupert on 22 Nov 2009 18:21

On Nov 22, 8:26 pm, Keith Ramsay <kram...(a)aol.com> wrote:
> On Nov 20, 5:12 am, stevendaryl3...(a)yahoo.com (Daryl McCullough)
> wrote:
> |Bill Taylor says...|>stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote:
>
> |>> Does it really make sense to doubt the truth of the
> |>> claim that there is a number i such that i*i = -1?
> |
> |>That's totally different and completely unobjectionable.
> |>Complex numbers can be defined trivially as ordered pairs with
> |>the appropriate operations, and all the usual results obtained.
> |>It has no logical or philosophical problematicity at all -
> |>i.e none beyond whatever the reals that make them up, already have.
> |
> |I don't think it is different at all.

There is one sense in which the difference is clear. Let RA be a
theory in a two-sorted language, one sort of variables for real
numbers and one sort of variables for sets of real numbers, and take
the axioms for a complete ordered field and unrestricted comprehension
and take the deductive closure in second-order logic. Con(RA) is
strictly stronger than Con(PA) in PA, assuming that PA+Con(PA) is
consistent. But you can easily formulate a second-order theory of
complex numbers and show that it is equiconsistent and indeed bi-
interpretable with RA. So in one sense the difference is clear; namely
that we have an increase in consistency strength.