Infinity Question
Elmer Fudd
equivalent to a subset of itself."
The set of all natural numbers N is an infinity, and {2,3} is
a subset of N, but {2,3} is surely not equal to the infinity N. So how
does N fit the defintion of infinity? How does anything fit that
definition? What am I missing here, apart, perhaps, from a brain? :-)
aske...@my-dejanews.com
Sorry, but you are missing a correct statement of that
way of defining infinity; more corect would be:
"A set that contains itself as a PROPER subset"
set {1,2,3,4} contains itself {1,2,3,4} as a subset, but a"proper"
subset is a set which fails to contain SOME of the elements of
the set of which it is a subset
so, consdier the integers {1,2,3,4,5,6.....}
and the even integers {2,4,6,8,10,...}
there are "as many" elements in the set of even integers as
in the set of all integetsr, namely an "infinite" nubmer of
them.... the word "cardinality" comes to mind....
but i am not a total expert here.... maybe sometonw will take
pity on us and explain it exactly
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Dr. Michael Albert
> equivalent to a subset of itself."
> The set of all natural numbers N is an infinity, and {2,3} is
> a subset of N, but {2,3} is surely not equal to the infinity N. So how
One way to characterize an infinite set is to say that a set is
infinite if and only if it is equivalent (in the sense of Cantor) to
a proper subset of itself. Thus the set of natural number is
infinite as it is equivalent to the set obtained by removing the
first natural number.
This is *not* to say that an infinite set is equivalent to
*any* subjet, just that *there exists* a proper subset to which
it is equivalent. Note that there are actually many such subsets,
but as your point out not *all* subsets are equivalent to the
set.
Jeremy Boden
<el...@fudd.com> writes
> It is said that a defintion of infinity is, "A set that is
>equivalent to a subset of itself."
>
> The set of all natural numbers N is an infinity, and {2,3} is
>a subset of N, but {2,3} is surely not equal to the infinity N. So how
>definition? What am I missing here, apart, perhaps, from a brain? :-)
>
It says that if a set is equivalent to some *proper* subset of itself
then it is infinite.
--
Jeremy Boden mailto:jer...@jboden.demon.co.uk
Virgil Hancher
> It is said that a defintion of infinity is, "A set that is
>equivalent to a subset of itself."
>
> The set of all natural numbers N is an infinity, and {2,3} is
>a subset of N, but {2,3} is surely not equal to the infinity N. So how
>does N fit the defintion of infinity? How does anything fit that
>definition? What am I missing here, apart, perhaps, from a brain? :-)
A set is infinite if it can be put into 1 to 1 correspondence with SOME
proper subset of itself. The subset you chose must itself be infinite,
since it is to be equivalent to the infinite set.
You just picked the wrong subset.
There is no set that can can be put into 1 to 1 correspondence with EVERY
proper subset of itself.
The set {1, 2, 3, ...} can be put into 1 to 1 correspondence with
the set {2, 4, 6, ...} by the rule x -> 2x.
The second set is clearly a proper subset of the first.
Thus the first, namely {1, 2, 3, ...}, is infinite. QED
--
vmh...@friix.comx | Un-x to reply
Ronald Bruck
Elmer Fudd <el...@fudd.com> wrote:
> It is said that a defintion of infinity is, "A set that is
>equivalent to a subset of itself."
>
> The set of all natural numbers N is an infinity, and {2,3} is
>a subset of N, but {2,3} is surely not equal to the infinity N. So how
It's not just ANY subset of itself; one definition of being infinite is,
"S is infinite if it can be put in a one-one correspondence with SOME
proper subset of itself." For example, {1,2,3,...} is in a 1-1 cor-
resondence with {2,3,4,...} via n -> n+1, so it's infinite.
Another definition is, "A set is FINITE if it is in a one-one cor-
respondence with an initial segment of the natural numbers, i.e. a
set of the form {p \in N : p <= n} for some n (including n = -1, so we
get the empty set). It is INFINITE if it is NOT finite."
Now I have a request for the logicians in the group. What ARE the
relationships between various definitions of a set being infinite?
Under exactly which axiom systems? What are the sticking points?
Someone (Rubin?) referred to this in a post sometime within the last
month, and I'd like to hear more.
--Ron Bruck
Arthur L. Rubin
>
> It's not just ANY subset of itself; one definition of being infinite is,
> "S is infinite if it can be put in a one-one correspondence with SOME
> proper subset of itself." For example, {1,2,3,...} is in a 1-1 cor-
> resondence with {2,3,4,...} via n -> n+1, so it's infinite.
This is called Dedekind finite, in the field.
> Another definition is, "A set is FINITE if it is in a one-one cor-
> respondence with an initial segment of the natural numbers, i.e. a
> set of the form {p \in N : p <= n} for some n (including n = -1, so we
> get the empty set). It is INFINITE if it is NOT finite."
>
> Now I have a request for the logicians in the group. What ARE the
> relationships between various definitions of a set being infinite?
> Under exactly which axiom systems? What are the sticking points?
> Someone (Rubin?) referred to this in a post sometime within the last
> month, and I'd like to hear more.
It was probably me. If you assume the axiom of choice, all of the
definitions of finite and/or infinite are equivalent. I'll forward this
to my mother for more references, as I can see you really want to learn.
(My mother is a professor of mathematics at Purdue, specializing in
mathematical logic and set theory. I've written some of the papers with
her, but I am working in industry and can't claim to keep up with all
the details.)
--
Arthur L. Rubin 216-...@mcimail.com
Brian M. Scott
wrote:
[snip]
>It's not just ANY subset of itself; one definition of being infinite is,
>"S is infinite if it can be put in a one-one correspondence with SOME
>proper subset of itself." For example, {1,2,3,...} is in a 1-1 cor-
>resondence with {2,3,4,...} via n -> n+1, so it's infinite.
Such sets are called 'Dedekind infinite'.
>Another definition is, "A set is FINITE if it is in a one-one cor-
>respondence with an initial segment of the natural numbers, i.e. a
>set of the form {p \in N : p <= n} for some n (including n = -1, so we
>get the empty set). It is INFINITE if it is NOT finite."
>Now I have a request for the logicians in the group. What ARE the
>relationships between various definitions of a set being infinite?
>Under exactly which axiom systems? What are the sticking points?
>Someone (Rubin?) referred to this in a post sometime within the last
>month, and I'd like to hear more.
I don't think that I've seen any definitions essentially different
from these. In ZF every Dedekind infinite set is necessarily infinite
(since a finite set obviously can't be injected properly into itself),
but you can say more: a set S is D-infinite iff there's an injection
of w into S. [Pf. sketch: If S is D-infinite, let f : S --> S be an
injection to a proper subset of S, and fix x(0) in S\f[S]. For n in w
let x(n+1) = f(x(n)); then x is the desired injection from w. The
converse is trivial.] This characterization makes it obvious that in
ZFC a set is D-infinite iff it's infinite, but in fact one needs
considerably less than full AC: DC (dependent choice) suffices. (DC
says that if R is a binary relation on S such that dom(R) = S, then
there's a function f : w --> S such that (An in w)[f(n) R f(n+1).)
This isn't perhaps quite obvious. Let F be the set of finite subsets
of the infinite set S, and for u and v in F put u R v iff u is a
subset of v and |v| = |u| + 1. Let f : w --> F be the choice function
promised by DC, and for n in w let x(n) be the unique element of
f(n+1)\f(n); clearly x : w --> S is an injection.
Some part of AC is definitely necessary: In Cohen's original model of
ZF + ~AC there's an infinite, D-finite subset of P(w). Thus, that
model doesn't even satisfy DC. (It actually doesn't even satisfy ACw
(countable choice), which says that if {A(n) : n in w} is a countable
family of non-empty sets, it has a choice function. It's easy to see
that DC implies ACw, and I believe that ACw is known to be strictly
weaker than DC.)
In ZF alone, however, it's true that if S is infinite, P(P(S)) is
D-infinite: for x in w let x(n) = {A in P(S) : |A| = n} in P(P(S)).
(This was discussed here recently and is perhaps what you were
thinking of.) I believe that it's possible to have an infinite S for
which P(S) is D-finite, but I don't know the details.
By the way, an infinite, D-finite subset of P(w) distinguishes another
familiar pair of notions. Say that a set S in a topological space is
sequentially closed iff S contains the limits of all convergent
sequences of points of S. ACw implies that in a metric space each
limit point p of a set S is the limit of a sequence in S\{p} and hence
that S is closed iff S is sequentially closed. Without ACw, however,
the two closures may be distinct. To see this, suppose that S is an
infinite, D-finite subset of P(w).
P(w) can be thought of as 2^w, in which form it can easily be
identified with the middle-thirds Cantor set and so can be thought of
as a subspace of R. It's not hard to show that S has a limit point,
p, and we may assume that p is not in S and hence that S is not closed
in R. (If p is in S, replace S by S\{p}, which is obviously still
infinite and D-finite.) But each sequence x : w --> S has finite
range, so S is sequentially closed. [If a sequence in S had infinite
range, we could construct from it a 1-1 sequence, contradicting the
D-finiteness of S.]
Brian M. Scott
Arthur L. Rubin
>
> In article <361fba3a....@news.erols.com>,
> Elmer Fudd <el...@fudd.com> wrote:
> > It is said that a defintion of infinity is, "A set that is
> >equivalent to a subset of itself."
> >
> > The set of all natural numbers N is an infinity, and {2,3} is
> >a subset of N, but {2,3} is surely not equal to the infinity N. So how
> >does N fit the defintion of infinity? ...
>
> "S is infinite if it can be put in a one-one correspondence with SOME
> proper subset of itself." For example, {1,2,3,...} is in a 1-1 cor-
> resondence with {2,3,4,...} via n -> n+1, so it's infinite.
>
> respondence with an initial segment of the natural numbers, i.e. a
> set of the form {p \in N : p <= n} for some n (including n = -1, so we
> get the empty set). It is INFINITE if it is NOT finite."
>
> Now I have a request for the logicians in the group. What ARE the
> relationships between various definitions of a set being infinite?
> Under exactly which axiom systems? What are the sticking points?
> Someone (Rubin?) referred to this in a post sometime within the last
> month, and I'd like to hear more.
OK, first some preliminary definitions. (I will frequently confuse
sets with their cardinality, even though cardinality, itself, is
problematical without the axiom of choice or a weak form of the
axiom of regularity.)
If X and Y are sets, then we define X <= Y (writen with wiggly lines)
if either of the equivalent definitions hold:
(1) There is a one-to-one function from X into Y.
(2) There is a one-to-one function from a subset of X onto Y.
If X and Y are sets, write X == Y (actually written with a single pair
of wavy lines, and read X is equipollent to Y) if either of the two
equivalent conditions below hold:
(1) X <= Y and Y <= X
(2) There is a 1-1 function from X onto Y.
If X and Y are sets, then write X < Y if X <= Y and not X == Y.
If X is a set, define "X+1" to be any set Y containing X such that
Y\X is a singleton. (As used, it won't matter which set is used, and
the axiom of choice will not be required in any of the proofs, but
this is NOT obvious. There is, however, a formal definition that
will work, but I don't need to go into that much detail at this time.)
If X is a non-empty set, define "X-1" to be any subset of X with only
element removed. (Again, the axiom of choice will not be required
in any of the proofs, but, this time, there is no suitable formal
definition.)
Define X <=_* Y if any of the equivalent definitions below hold:
(1) X is empty, or there is a function from Y onto X.
(2) There is a function from a subset of Y onto X.
(3) There is a function from Y+1 onto X+1.
If X is a set, define P(X) (usually written with a script P) to be the
power set of X, the collection of all subsets of X.
"omega" will be the first infinite ordinal. (Ordinal numbers are
defined in such a way that "n" = {0, 1, 2, ..., n-1}. I don't think
I need to go into the details of the defintion.)
X is n-finite (n for normal) if any of the following equivalent
definitions hold:
(1) X is equipollent to a finite ordinal.
(2) X < omega
(3) P(X) is PD-finite
(4) P(X) is D*-finite
(5) P(P(X)) is D-finite
X is A-finite if for any subset Y of X, Y is n-finite or X\Y is
n-finite. (A stands for amorphous.)
X is PD-infinite if P(X) is D-infinite (defined below).
X is D*-infinite if any of the following equivalent conditions hold:
(1) There is a proper subset Y of X such that X <=* Y
(2) X <=* X-1
(3) X+1 <=* X
(4) omega <=* X (oops, that's not quite the same but 1-3 imply 4)
X is D-infinte (Dedekind-infinite) if any of the following equivalent
conditions hold:
(1) There is a proper subset Y of X such that X <= Y
(2) There is a proper subset Y of X such that X == Y
(3) X+1 <= X
(4) X+1 == X
(5) X <= X-1
(6) X == X-1
(7) omega <= X
It can be seen that, for any set X, with the following definitions,
(1) -> (2) -> (3) -> (4) -> (5) -> (6)
(1) X is D-infinite
(2) X is D*-infinite
(3) X is D*-infinite (definition 4, but I don't have a separate
name)
(4) X is PD-infinite
(5) X is A-infinite
(6) X is n-infinite
(BTW, some of the lemmas used are:
(A) If X <=_* Y, then P(X) <= P(Y).
(B) If X is n-infinite, then P(X) is D*-infinite
(C) If X is D*-infinite, then P(X) is D-infinite.)
With more effort and a lot of knowledge of set theory, one can show that
none of these implications is reversable.
For some background, including the definitions of <=, and <=_*, I
recommend _Set Theory for the Mathematician_, by Jean E. Rubin. I have
a vague memory of a paper by one or more Rubin's about relationships
between definitions of finiteness, but I can't find a reference at the
moment.
Jon Haugsand
| (1) There is a one-to-one function from X into Y.
| (2) There is a one-to-one function from a subset of X onto Y.
Eh? You mean
(2) There is a one-to-one function from X onto a subset of Y?
--
Jon Haugsand
Norwegian Computing Center, <http://www.nr.no/engelsk/>
<mailto:haug...@nr.no> Pho: +47 22852608 / +47 22852500,
Fax: +47 22697660, Pb 114 Blindern, N-0314 OSLO, Norway
Arthur L. Rubin
> (2) There is a one-to-one function from a subset of X onto Y.
As Jon Haugsand <haug...@procyon.nr.no> pointed out, this should be:
(2) There is a one-to-one function from a subset of Y onto X.
...
> X is D*-infinite if any of the following equivalent conditions hold:
>
> (1) There is a proper subset Y of X such that X <=* Y
> (2) X <=* X-1
> (3) X+1 <=* X
> (4) omega <=* X (oops, that's not quite the same but 1-3 imply 4)
Please replace this by:
X is D'-infinite iff any of the following equivalent conditions hold:
(1) There is a proper subset Y of X such that X <=* Y
(2) X <=* X-1
(3) X+1 <=* X
X is D*-infinite (read "Dedekind star infinite") if omega <=* X.
...
> It can be seen that, for any set X, with the following definitions,
> (1) -> (2) -> (3) -> (4) -> (5) -> (6)
> (1) X is D-infinite
> (2) X is D*-infinite
Now that's D'-infinite.
> (3) X is D*-infinite (definition 4, but I don't have a separate
> name)
Now that's D*-infinite.
> (4) X is PD-infinite
> (5) X is A-infinite
> (6) X is n-infinite
I don't see the proof of (2) implies (3) any more. In fact, I'm pretty
sure it fails in some model of ZF or NBG set theory. The correct
statement is that (1) implies (3) implies (4) implies (5) implies (6),
and none of these are reversable. Also, (1) implies (2) implies (4),
and I think thatno implication that does not follow from these holds in
all models.
I'll keep updating this, and put it on my home page when I get access
to it again.
Arthur L. Rubin
>
> * Arthur L. Rubin
> | (1) There is a one-to-one function from X into Y.
> | (2) There is a one-to-one function from a subset of X onto Y.
>
> (2) There is a one-to-one function from X onto a subset of Y?
Thanks. I needed that. Suppose I say:
(2) There is a one-to-one function from a subset of Y onto X.
in future versions. There is another, more subtle error, which
occured to me last night.
--
Arthur L. Rubin
Brian M. Scott
>Arthur L. Rubin wrote:
>> Ronald Bruck wrote:
>> (1) There is a one-to-one function from X into Y.
>> (2) There is a one-to-one function from a subset of X onto Y.
>As Jon Haugsand <haug...@procyon.nr.no> pointed out, this should be:
>(2) There is a one-to-one function from a subset of Y onto X.
>...
>Please replace this by:
>...
Unless I'm missing something that's right under my nose, you can prove
it as follows. Suppose that X is D'-infinite, and let f : Y --> X
be a map from a proper subset, Y, of X onto X. Let
A(0) = X\Y,
A(n+1) = {y in Y : f(y) in A(n)} for n in w, and
A(w) = X\U{A(n) : n in w}.
The A(k) for k <= w partition X, and all except possibly A(w)
are non-empty. Define g : X --> w by
g(x) = n if x in A(n) for some n in w,
g(x) = 0 if x in A(w).
Then g witnesses w <=* X, and X is D*-infinite.
Brian M. Scott
Arthur L. Rubin
>
> Unless I'm missing something that's right under my nose, you can prove
> it as follows. Suppose that X is D'-infinite, and let f : Y --> X
> be a map from a proper subset, Y, of X onto X. Let
>
> A(0) = X\Y,
> A(n+1) = {y in Y : f(y) in A(n)} for n in w, and
> A(w) = X\U{A(n) : n in w}.
>
> The A(k) for k <= w partition X, and all except possibly A(w)
> are non-empty. Define g : X --> w by
>
> g(x) = n if x in A(n) for some n in w,
> g(x) = 0 if x in A(w).
>
> Then g witnesses w <=* X, and X is D*-infinite.
I thought it was something like that, but I looked at it again, and
couldn't see it. That is correct.