Talk:Finite set/Archive 1

Archive 1

Circular definition?

Wait a minute!!

This encyclopedia defines the terms "natural number" and "finite" in terms of each other!!

-- Anon

This isn't Bourbaki; we're not trying to develop a single well-grounded development of mathematics but instead to describe all of the various interrelationships between mathematical (among other) concepts. So if X can be defined in terms of Y while Y can be defined in terms of X, then both definitions should be included.

That said, any interesting definitions of X or Y that don't mention the other property should also be included! If you have any good ones, then please add them.

-- Toby Bartels 06:46, 25 Sep 2003 (UTC)

I don't agree : even without being Bourbaki, if one definition is given in terms of the other and reciprocally, then it is mathematically completely useless !

Also, if n=0 is a natural number, then is {1,2,3,...,n} the empty set?

In fact, I wanted to know if according to wikipedia, a finite set can be empty (i.e., if the empty set is finite or not).

— MFH: Talk 23:29, 19 Apr 2005 (UTC)

Well, there exists no bijection between the empty set and one of its proper subsets, since there are no proper subsets of the empty set, so by default it is finite. bananaclaw May 5, 2005

First, natural number is not defined in terms of finite: neither Peano axioms nor the definition of von Neumann representation mention finiteness. Second, finiteness can be easily defined without using natural numbers. Dedekind's definition (having no proper equivalent subset) is mentioned in the article. There is also another definition which does not depend on the axiom of choice (I forgot who invented it, maybe Kuratowski?): a set X is finite iff every nonempty set of subsets of X contains a maximal element wrt inclusion.

As for n=0: empty set is finite, according to everybody, not just Wikipedia. Yes, {1,2,3,...,n} is a sloppy notation for the empty set in this case. -- EJ 18:28, 14 August 2005 (UTC)

Finite should be a dab page

Adjectives make bad article titles. I've moved what was at finite to finite set, but lots of the links are not in fact about finite sets, but about other notions. There should really be a disambiguation page at finite that would point also to other notions of finite quantities. --Trovatore 20:41, 25 October 2005 (UTC)

Done (but it should have lots more links) --Trovatore 22:15, 26 October 2005 (UTC)

Axiom of Choice

The reason I changed the line about AC being true to assuming it is that it strikes me as very bizarre to call an independent axiom either true or false. I suppose this is a formalist bias on my part, but suggesting that it actually has some as-yet unknown truth or falseness similarly reflects a strong realism, while simply making mention of an assumption gives a more neutral perspective, I think. --Fell Collar 18:52, 12 May 2006 (UTC)

Well, if you're going to phrase it that way you have to be consistent. If the hypothesis is to be stated formalistically (as "what we assume"), then the conclusion needs to be so stated as well, in terms of what we can prove rather than what's true. A bare mathematical statement is equivalent to the statement being true, not provable.

It could be phrased something like "the following are provably equivalent in a formal theory including the axiom of choice". But I think that's just awkward; the usual convention is to state things Platonistically, and let formalists reinterpret as they will. --Trovatore 20:36, 12 May 2006 (UTC)

minor edit: add linkage to the term 'Zermelo–Fraenkel set theory'

The first occurrence of the term 'Zermelo–Fraenkel set theory' was a cryptic unlinked acronym: ZF. I added the full term and wikilink'ed it. -- Fsmoura 22:16, 13 July 2007 (UTC)

Dedekind

"Dedekind treats infinitude as the positive notion and finiteness as its negation." What is the point of this sentence? Is it a historical remark? After all, as is later written, "Dedekind finite naturally means that every injective self-map is also surjective": the notion of Dedekind-finiteness is at least as positive as Dedekind infiniteness! OK if I change it? Sam Staton 10:52, 1 August 2007 (UTC)

Moving section "Foundational issues" elsewhere

After weeks of navigation in Wikipedia (see Talk:Cardinality), I have found the section Foundational issues, in this article. This interesting section introduces infinite set theory, but the article finite sets is not even included in the category Basic concepts in infinite set theory!

There are at least four possible places where this paragraph could be:

1. in a new separate article, such as, for instance, Introduction to infinite set theory;
2. right here, in Cardinality;
3. in Axiomatic set theory
4. in Infinite set (see suggestion by JRSpriggs below)
5. just where it is now.

Please do not answer here. You are invited to give your opinion about this in this page. Regards,Paolo.dL 10:07, 31 August 2007 (UTC)

Redundancy

There is redundancy between the Basic Properties and Closure Properties sections. Perhaps they should be merged? WardenWalk (talk) 04:26, 27 April 2009 (UTC)

Done. — Emil J. 10:34, 27 April 2009 (UTC)

Countable choice is enough

Arthur Rubin (talk · contribs) questioned whether ZF plus the axiom of countable choice is sufficient to establish the equivalence of:

1. S is a finite set.
2. (Dedekind-finite) Every function from S one-to-one into itself is onto.
3. Every function from S onto itself is one-to-one.
4. S is empty or every partial ordering of S contains a maximal element.

Do you agree that it is obvious that the finiteness of S implies the other three conditions?

To show that they are all equivalent, it is sufficient to show that if S is infinite, then the other three conditions fail. Let B_n be the set of injective functions from n+1 to S. Using mathematical induction one can show that all the B_n are non-empty. So {B_n|n∈ω} is a countable set of non-empty sets. Let f be its choice function. Let g(n) be the first element in the image of f(B_n) which is not equal to any g(k) for k<n. Then g is an injection from ω to S which implies the Dedekind-infiniteness of S, since h which maps each element of S to itself unless it is in the range of g in which case h(g(n))=g(n+1) is injective but not surjective. Let l(g(n+1))=g(n) and let l be the identity on S otherwise, then l is surjective but not injective. Let the partial ordering put x<g(0)<g(1)<g(2)<... for every x not in the range of g, then this ordering has no maximal element. JRSpriggs (talk) 11:35, 25 September 2009 (UTC)

OK, I should have thought of that. It's not (almost) immediately obvious, like the other equivalences, though. I can't find my copy of Rubin and Howard, Consequences of the Axiom of Choice; if the axiom of countable choice is listed as implying every Dedekind finite set is finite (which should both be there), I'd consider it proved, although I shouldn't add it as a reference, myself. — Arthur Rubin (talk) 15:27, 25 September 2009 (UTC)

The article on Dedekind-infinite says "... that a set is infinite if and only if it is Dedekind-infinite. ... The full strength of AC is not needed to prove the equivalence; in fact, the equivalence of the two definitions is strictly weaker than the axiom of countable choice (CC).". JRSpriggs (talk) 00:43, 26 September 2009 (UTC)

The condition about partial orderings is equivalent to saying the (seemingly stronger) statement that for every partial ordering of S, for every element x of S, there is a maximal element m which is greater or equal to x. For (Kuratowski) finite S, this is easily proved by induction. For the empty set, it is vacuously true because there is no x in S. Let us make the inductive assumption that it is true for S, and consider T=S∪{b}. If x≠b, let m be the element which is maximal over x in S, then either m is still maximal in T or m≤b in which case b must be maximal in T. Otherwise, m≤b≤y∈S which contradicts the maximality of m in S. On the other hand, if x=b, then either b is maximal over itself in T or b≤y∈S in which case there is a m which is maximal over y in S and thus m is maximal over b in T. So by induction, this stronger property of partial orderings holds for all finite sets. So the last condition in the equivalence also holds. QED.

Arthur, if you (or anyone) has doubts about any part of these proofs, I will be happy to provide more details to convince you. Just indicate which part you want explained in more detail. JRSpriggs (talk) 23:53, 29 September 2009 (UTC)

Do you intend to add source material? Cliff (talk) 18:05, 6 May 2011 (UTC)

Error in Dedekind-finite example?

With regard to:

"In ZF, Kuratowski finite implies Dedekind finite, but not vice-versa. In the parlance of a popular pedagogical formulation, when the axiom of choice fails badly, one may have an infinite family of socks with no way to choose one sock from more than finitely many of the pairs. That would make the set of such socks Dedekind finite: there can be no infinite sequence of socks, because such a sequence would allow a choice of one sock for infinitely many pairs by choosing the first sock in the sequence. However, Kuratowski finiteness would fail for the same set of socks."

Isn't this technically incorrect? AC is not decidable in ZF, so there are models in which such a sequence exists, and others in which it does not. So it is expressly not the case that "there can be no infinite sequence of socks" must be true when AC is not assumed. This should imply that such a set can not be determined in ZF to be either Dedekind-infinite or Dedekind-finite! This is very different from asserting it is Dedekind-finite. TricksterWolf (talk) 23:39, 21 August 2011 (UTC)

A "set" lies in a particular model of ZF; some sets are Dedekind-finite in the model, and some are "Kuratowski-finite". In a sense, a set being "Kuratowski-finite" may be absolute between models of set theory, while a set being "Dedekind-finite" is not. However, that's not relevant to the arguments here. — Arthur Rubin (talk) 00:06, 22 August 2011 (UTC)

Suppose we are given a model of ZF containing a Dedekind-finite (Kuratowski-)infinite set, call it D. As Kurt Gödel showed, this can be cut-down to a model of ZFC (in which there are no such sets). It is not the case that D changes its character in this submodel. Rather D simply is not in this submodel. JRSpriggs (talk) 02:31, 22 August 2011 (UTC)

That's true. However, the model might be contained (indeed, because AC is Platonistically true, is contained, assuming the model is wellfounded) in a larger model in which D is present, but is no longer Dedekind-finite. In the larger model, there is a map from D to a proper subset of D. The original model can delude itself that D is Dedekind-finite, because the original model does not contain this map. --Trovatore (talk) 09:14, 22 August 2011 (UTC)

Hopefully you all can parse what I'm saying--I'm very, very rusty on model theory and tend to use all the wrong words. I just wanted to double-check that my intuition was not the case here. TricksterWolf (talk) 03:47, 31 August 2011 (UTC)

I do not think that model theory is necessary or helpful to interpret the paragraph which you quoted. Suppose S is an infinite set of pairs of socks and for every B⊆S which has a choice function, B is finite. Obviously this contradicts the axiom of choice. It also implies that ∪S is Dedekind-finite because any injection f from ω into ∪S would allow one to define a choice function on the infinite subset of S consisting of pairs of socks which have a nonempty intersection with the image of f. That is what it is saying. JRSpriggs (talk) 06:27, 31 August 2011 (UTC)

I believe I understand this now; thanks much. (Although model theory isn't needed, my lack of foundation with it is one of the reasons I originally misinterpreted this section. This is why I'm currently reviewing Enderton's Mathematical Intro. to Logic.) TricksterWolf (talk) 19:43, 1 September 2011 (UTC)

Is it really true that I-finite does not imply T-finite in ZF?

Alan U. Kennington (talk · contribs) just added the interesting subsection Finite set#Other definitions of finiteness to the article. Among other things, it says that I-finite (i.e. finite in the normal sense) does not imply T-finite in ZF without AxCh. I find this difficult to believe. If a set S is finite, then a simple application of mathematical induction shows that its powerset is also finite since the powerset of S∪{x} (for x not in S) is equivalent to the disjoint union of two copies of the powerset of S. Thus I-finiteness of S would imply I-finiteness of P(S) which would imply II-finiteness of P(S) which is the same as the definition of T-finiteness of S. What am I missing here? JRSpriggs (talk) 07:54, 8 August 2014 (UTC)

OK. Now I see that the axiom of choice may be needed to select the order in which the elements of S are added to the empty set and thus to determine the bijection between the powerset of S and its finite cardinality. JRSpriggs (talk) 08:01, 8 August 2014 (UTC)

Actually, I don't know how to do most of the proofs. I just trust what Howard and Rubin wrote in their really excellent "Consequences of the axiom of choice" book. It has such good binding, I figure it must be true! But perhaps I could just comment that I find it fascinating to find proofs in ZF without AC of the various finiteness equivalences and non-equivalences. I'm working on some of those right now, like showing equivalence of the Kuratowski finiteness, the I-finiteness (Tarski) and the enumerative definition. It's so very difficult to see where AC comes in, and so very easy to accidentally use AC unwittingly. The Kuratowski 1920 paper has a very nice short proof of equivalence of his definition and the enumerative definition. It's too bad we can't fill this "finite sets" page with proofs, because I think some of them are very interesting in themselves. I used to think that finite sets were trivial. Not any more! --Alan U. Kennington (talk) 08:24, 8 August 2014 (UTC)

You were right. The T-finiteness does not belong on that list. It is ambiguously presented in Howard/Rubin. The same definition is given in Jech "Set theory" apparently. (I don't have that book, but the T-finite definition is quoted from Jech on web sites.) It is crystal clear that I-finite implies T-finite when the definition is written correctly. But I don't know how it fits into the rest of the scale. I think the remaining 8 definitions are solid though. By the way, if you google "T-finite" right now, it points to the finite set wikipedia page!
--Alan U. Kennington (talk) 03:26, 9 August 2014 (UTC)

And just another little note about this. The Howard/Rubin and Jech definitions of T-finite sets look to me to be absolutely identical to the II-finite definition. Jech gives the T-finite definition on page 52 of his "The axiom of choice" book, which I do possess. And now I have just discovered also that Howard Rubin on page 184 say explicitly that T-finite and II-finite are the same. That confirms it. So I don't know why they didn't say so on pages 278–280. Now I'm beginning to think you can't judge a mathematics book by its binding!
--Alan U. Kennington (talk) 03:41, 9 August 2014 (UTC)

To Alan: Thanks for fixing the subsection and providing references. In particular, thanks for removing T-finite as a kind of super-finiteness.

However, the subsection still seems unclear on whether some of the reverse implications work — saying no in one place and yes in another.

I notice that Dedekind finite is equivalent to 1+|S|>S, making that similar to the next two definitions in the subsection.

I wonder whether some of the definitions might be equivalent to the following:

• S⊆P(D) where D is Dedekind finite.
• S⊆P(P(D)) where D is Dedekind finite.

Any thoughts? JRSpriggs (talk) 07:43, 9 August 2014 (UTC)

The Howard/Rubin book is fairly unambiguous about this.

"In Tarski (1954) and Levy (1958) it is shown that if a set is finite according to any definition in the above list then it is finite according to any following definition and none of the reverse implications hold."

Now that is fairly bold for 1958 because Paul Cohen's model theory triumphs date from 1963. So they were using a restricted range of models before that time. However. Tarski was an important pioneer in model theory. So I am not surprised that he got some of these reverse non-implications proved in 1954. This article has some info on Levy's contributions to this problem: Levy and set theory.
--Alan U. Kennington (talk) 09:01, 9 August 2014 (UTC)

The Levy (1958) paper is available online here: The independence of various definitions of finiteness. This is the right paper to look at! It's got all of the 8 definitions that I put in the finite set wiki page. The reverse implications are all disproved using Mostowski models.
--Alan U. Kennington (talk) 09:24, 9 August 2014 (UTC)