Science and Technology news... :: View topic

Peter Webb · Guest

It seems to me that I can create within FOL a predicate that determines
whether a finite set has a particular finite cardinality.

Lets define C_0 being a wff that states a set A is of cardinality zero as:

C_0(A) = (def) a={}

C_1 states A is of cardinality 1 as follows:

C_1(A) = E (x e A) & (C_0(A-x))

or in English, there is an element that you can remove that produces the
empty set

Recursively, for all finite n,

C_n(A) = E(x e A) & C_(n-1)(A-x)

This all looks fine for finite sets. I can count the elements in a set.

Now, I think I can also produce a wff that states a set is infinite:

~En & C_n(A)

As a (possible) aside, I am reading Peter Smith>s book on Goedel>s
Incompleteness theorems, and he discusses w-consistency on p142. This seems
a related concept. The wff may not be effectively decidable.

Returning to the main theme, I cannot see how the concept of cardinality can
be extended to include different sorts of infinite sets within FOL itself.
The definitions that are commonly used relate to the existence of
bijections, which are sets, and hence require quantification over sets. FOL
only allows quantification over numbers.

This seems to me that you can create a wff that captures the concept of
cardinality n for any finite n, but not for infinite sets. Is this the deal?

Peter Webb · Guest

"Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message
news:48e71e32$0$4449$afc38c87@news.optusnet.com.au...
[quote]It seems to me that I can create within FOL a predicate that determines
whether a finite set has a particular finite cardinality.

Lets define C_0 being a wff that states a set A is of cardinality zero as:

C_0(A) = (def) a={}

[/quote]
Oops, sorry, should be A={}

[quote]C_1 states A is of cardinality 1 as follows:

C_1(A) = E (x e A) & (C_0(A-x))

or in English, there is an element that you can remove that produces the
empty set

Recursively, for all finite n,

C_n(A) = E(x e A) & C_(n-1)(A-x)

This all looks fine for finite sets. I can count the elements in a set.

Now, I think I can also produce a wff that states a set is infinite:

~En & C_n(A)

[/quote]
No I can>t. Thats the union of an infinite set of smaller wffs. So FOL can>t
capture the property of being an infinite set at all?

[quote]As a (possible) aside, I am reading Peter Smith>s book on Goedel>s
Incompleteness theorems, and he discusses w-consistency on p142. This
seems a related concept. The wff may not be effectively decidable.

Returning to the main theme, I cannot see how the concept of cardinality
can be extended to include different sorts of infinite sets within FOL
itself. The definitions that are commonly used relate to the existence of
bijections, which are sets, and hence require quantification over sets.
FOL only allows quantification over numbers.

This seems to me that you can create a wff that captures the concept of
cardinality n for any finite n, but not for infinite sets. Is this the
deal?

[/quote]

William Elliot · Guest

On Sat, 4 Oct 2008, Peter Webb wrote:

[quote]It seems to me that I can create within FOL a predicate that determines
whether a finite set has a particular finite cardinality.

You are not using FOL. You>re using set theory.[/quote]
With FOL you can express
none not some P(x)
at least one some P(x)

With FOL_= you can express more. For example, exactly one,
two or more, exactly two, no more than one, no more than two.

[quote]Lets define C_0 being a wff that states a set A is of cardinality zero as:

C_0(A) = (def) a={}

C_1 states A is of cardinality 1 as follows:

C_1(A) = E (x e A) & (C_0(A-x))

or in English, there is an element that you can remove that produces the
empty set

----[/quote]

translogi · Guest

On Oct 5, 7:13 am, William Elliot <ma...@hevanet.remove.com> wrote:
[quote]On Sat, 4 Oct 2008, Peter Webb wrote:
It seems to me that I can create within FOL a predicate that determines
whether a finite set has a particular finite cardinality.

You are not using FOL. You>re using set theory.
With FOL you can express
none not some P(x)
at least one some P(x)

With FOL_= you can express more. For example, exactly one,
two or more, exactly two, no more than one, no more than two.

Lets define C_0 being a wff that states a set A is of cardinality zero as:

C_0(A) = (def) a={}

C_1 states A is of cardinality 1 as follows:

C_1(A) = E (x e A) & (C_0(A-x))

or in English, there is an element that you can remove that produces the
empty set

----
[/quote]
just clarification

FOL_= is first order logic with identity

FOL is more about predicates than about sets so it is more

Nothing is P

Ax ~Px

Only one thing is P

Ex (Px & Ay (Py ->(x=y)))

there are two P>s

Ex Ey (((Px & Py) & ~(x=y)) & Az(Pz -> ((z=x) v (z=y)))

and for three Ps it becomes a very long sentence
(that is just me being lazy)

but it is more or less in words

There is an v, w, x and
Pv Pw Px and v isn>t w isn>t x in all combinations
and for every z if Pz then z is v w or x.

(sometimes logic is shoretr in english)

Chris Menzel · Guest

On Sat, 4 Oct 2008 17:41:50 +1000, Peter Webb
<webbfamily@DIESPAMDIEoptusnet.com.au> said:
[quote]It seems to me that I can create within FOL a predicate that
determines whether a finite set has a particular finite cardinality.
[/quote]
Well, yes, in first-order ZF set theory, it is possible to define
"finite" in the sense that there is a formula that picks out exactly the
finite sets *in a standard model* of ZF. There will, however, always be
nonstandard models of ZF in which your formula will be true of sets that
are not, in fact, finite.

William Elliot · Guest

On Mon, 6 Oct 2008, Chris Menzel wrote:
[quote]webbfamily@DIESPAMDIEoptusnet.com.au> said:

It seems to me that I can create within FOL a predicate that
determines whether a finite set has a particular finite cardinality.

Well, yes, in first-order ZF set theory, it is possible to define
"finite" in the sense that there is a formula that picks out exactly the
finite sets *in a standard model* of ZF. There will, however, always be
nonstandard models of ZF in which your formula will be true of sets that
are not, in fact, finite.

ZF needs the axiom[/quote]
substandard models not accepted.

herbzet · Guest

William Elliot wrote:
[quote]
On Mon, 6 Oct 2008, Chris Menzel wrote:
webbfamily@DIESPAMDIEoptusnet.com.au> said:

It seems to me that I can create within FOL a predicate that
determines whether a finite set has a particular finite cardinality.

Well, yes, in first-order ZF set theory, it is possible to define
"finite" in the sense that there is a formula that picks out exactly the
finite sets *in a standard model* of ZF. There will, however, always be
nonstandard models of ZF in which your formula will be true of sets that
are not, in fact, finite.

ZF needs the axiom
substandard models not accepted.
[/quote]
There would be non-standard models of ZF + no non-standard models.

See http://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem .

(Let me know if this ascii-gibberish doesn>t work.)

--
hz

Aatu Koskensilta · Guest

Chris Menzel <cmenzel@remove-this.tamu.edu> writes:

[quote]Well, yes, in first-order ZF set theory, it is possible to define
"finite" in the sense that there is a formula that picks out exactly the
finite sets *in a standard model* of ZF. There will, however, always be
nonstandard models of ZF in which your formula will be true of sets that
are not, in fact, finite.
[/quote]
Which reminds me, a relative consistency proof by means of forcing
yields not only relative consistency but also relative arithmetical
soundness. I thought to mention this in connection with the result
that it>s consistent with ZF that there is an infinite set with no
denumerable subset, but for some reason did not.

--
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, darÃ¼ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

William Elliot · Guest

On Tue, 7 Oct 2008, herbzet wrote:
[quote]William Elliot wrote:
On Mon, 6 Oct 2008, Chris Menzel wrote:

It seems to me that I can create within FOL a predicate that
determines whether a finite set has a particular finite
cardinality.

Well, yes, in first-order ZF set theory, it is possible to define
"finite" in the sense that there is a formula that picks out exactly
the finite sets *in a standard model* of ZF. There will, however,
always be nonstandard models of ZF in which your formula will be
true of sets that are not, in fact, finite.

ZF needs the axiom
substandard models not accepted.

There would be non-standard models of ZF + no non-standard models.

See http://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem .

(Let me know if this ascii-gibberish doesn>t work.)

What gibberish? The Lowenhwein Skolem paradox? It>s wonderful theorem[/quote]
proving infinite is infinite is infinite and neither bigger nor
smaller than infinite and to think otherwise is illusion.

To cut through the illusions, use GCH as recommended by Occam
and nothing is inaccessible, also approved by Occam.

--
Prochoice mathematician and proud of it.

----

herbzet · Guest

William Elliot wrote:
[quote]On Tue, 7 Oct 2008, herbzet wrote:
William Elliot wrote:
On Mon, 6 Oct 2008, Chris Menzel wrote:

It seems to me that I can create within FOL a predicate that
determines whether a finite set has a particular finite
cardinality.

Well, yes, in first-order ZF set theory, it is possible to define
"finite" in the sense that there is a formula that picks out exactly
the finite sets *in a standard model* of ZF. There will, however,
always be nonstandard models of ZF in which your formula will be
true of sets that are not, in fact, finite.

ZF needs the axiom
substandard models not accepted.

There would be non-standard models of ZF + no non-standard models.

See http://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem .

(Let me know if this ascii-gibberish doesn>t work.)

What gibberish?
[/quote]

I was referring to "L%C3%B6wenheim%E2%80%93Skolem_theorem" which looks
like gibberish in my newsreader.

[quote]The Lowenhwein Skolem paradox? It>s wonderful theorem
proving infinite is infinite is infinite and neither bigger nor
smaller than infinite and to think otherwise is illusion.
[/quote]
But more fun!

[quote]To cut through the illusions, use GCH as recommended by Occam
and nothing is inaccessible, also approved by Occam.

--
Prochoice mathematician and proud of it.
[/quote]
--
hz

William Elliot · Guest

On Wed, 8 Oct 2008, herbzet wrote:
[quote]
I was referring to "L%C3%B6wenheim%E2%80%93Skolem_theorem" which looks
like gibberish in my newsreader.

It is gibberish for omlot o which appears on the web as grade[/quote]
school division sign. The other surge of gibberish is a short
dash. That>s your punishment for not using proprietary software,
to eat gibberish. You see, it>s value added to have a fancy dash
instead of a plane -. Most wonderful the modern inconveniences of
automation who can take a simple 1 k plane text and turn it into
an a connectivity clogging 50 k.

Mommy? Is a person an alien if he>s intelligent?

Peter Webb · Guest

"Aatu Koskensilta" <aatu.koskensilta@uta.fi> wrote in message
news:87abdfv7ss.fsf@alatheia.dsl.inet.fi...
[quote]Chris Menzel <cmenzel@remove-this.tamu.edu> writes:

Well, yes, in first-order ZF set theory, it is possible to define
"finite" in the sense that there is a formula that picks out exactly the
finite sets *in a standard model* of ZF. There will, however, always be
nonstandard models of ZF in which your formula will be true of sets that
are not, in fact, finite.

Which reminds me, a relative consistency proof by means of forcing
yields not only relative consistency but also relative arithmetical
soundness. I thought to mention this in connection with the result
that it>s consistent with ZF that there is an infinite set with no
denumerable subset, but for some reason did not.

--
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, darÃ¼ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
[/quote]
Forcing is way over my head, and indeed *I* am in over my head, but I have
somewhat corrected my terminology and though of a new wrinkle.

Consider the subsets of N, ie the power set.

I can create an equivalence function of all the subsets with exactly n
elements (where n is finite) - ie specify all sets with any finite
cardinality.

I can do this because I can pick out the empty set as one subset, and define
this as having Cardinality 0.
Then

Card (A) = n <=> Ex Card(A-x) = n-1

And define finite Cardinality inductively.

So for example I have {} as the only set with cardinality 0,
{1}, {2}, {3} ... with cardinality 1, etc

Easy for P(N), but the same principle applies to all sets.

So I can pick out all the sets with any finite cardinality.

It seems that I can almost (but not quite) define an "infinite" cardinality
by using the property that I can remove any one item from an infinite set
and it will still be infinite, something like:

Card (A) is infinite <=> Ex Card(A-x) is infinite

But unfortunately that doesn>t seem guaranteed to work. There may be other
interpretations of the Card function and what "infinite" means that it may
also pick finite sets. It hasn>t properly captured the concept that it is
not finite, ie that

~(Card(A) =0) & ~(Card(A) =1) & ...

which having "..." at the end cannot be directly expressed in ZFC.

herbzet · Guest

William Elliot wrote:
[quote]herbzet wrote:

I was referring to "L%C3%B6wenheim%E2%80%93Skolem_theorem" which looks
like gibberish in my newsreader.

It is gibberish for omlot o which appears on the web as grade
school division sign. The other surge of gibberish is a short
dash. That>s your punishment for not using proprietary software,
to eat gibberish. You see, it>s value added to have a fancy dash
instead of a plane -. Most wonderful the modern inconveniences of
automation who can take a simple 1 k plane text and turn it into
an a connectivity clogging 50 k.
[/quote]
I suppose software engineers must live, too.

--
hz

William Elliot · Guest

On Thu, 9 Oct 2008, herbzet wrote:
[quote]William Elliot wrote:
herbzet wrote:

I was referring to "L%C3%B6wenheim%E2%80%93Skolem_theorem" which looks
like gibberish in my newsreader.

It is gibberish for omlot o which appears on the web as grade
school division sign. The other surge of gibberish is a short
dash. That>s your punishment for not using proprietary software,
to eat gibberish. You see, it>s value added to have a fancy dash
instead of a plane -. Most wonderful the modern inconveniences of
automation who can take a simple 1 k plane text and turn it into
an a connectivity clogging 50 k.

I suppose software engineers must live, too.

In China of course, or India where wages[/quote]
are what US companies are willing to pay.

-- As the recession progresses into a regression ...


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Logic Forum
Page 1 of 1