Talk:Finite set

Cofinite

So now we have:

"Ia-finite. Each subset of S is either finite or cofinite or both.",

whereas before there was:

"Ia-finite. S is not equal to the union of two disjoint sets neither of which is I-finite."

There are some problems with this. The whole idea is to define finiteness in 8 ways which do not use the traditional definition of ω as a yardstick to measure sets using equipollences or bijections. Now a simple low-level set-theoretic definition has been replaced with the concept "finite" which invokes existence of bijections to and from ω, and cofinite, which most readers know even less well than "finite", and presumably they came to the finite set page to discover what finite means, and now Ia-finite is being defined in terms of finite and cofinite. That really does defeat the core purpose of the 8 definitions, which is to provide simple self-contained logical predicates using the equality and element-of relations to define finite set concepts of various kinds.

Of course, the definition of Ia-finite in terms of finite and cofinite is simpler when you know and understand ω, the axiom of infinity, recursion, and so forth. But that is defining low-level concepts in terms of high-level concepts. I think that Ia-finite should be defined in terms of I-finite.
--Alan U. Kennington (talk) 07:40, 11 August 2014 (UTC)

I thought about saying "Each subset of S is either I-finite or co-I-finite or both.". But I thought that would sacrifice some of the benefit of a simpler statement. And the line just above says that I-finite "is also equivalent to the normal definition of finiteness". That is, finite = I-finite. This is also stated in the section on Necessary and sufficient conditions for finiteness. JRSpriggs (talk) 09:42, 11 August 2014 (UTC)

Yes, however, Zorn's lemma is equivalent to the axiom of choice, but we don't say that they are the same thing. In fact, I-finite and finite are only equivalent in full ZF. I think they are probably not so equivalent without the axiom of infinity. How do you measure sets against finite ordinal numbers if the set of finite ordinal numbers does not exist.

But the real issue is not what is equivalent to what. The real issue is what is the definition. A definition is a particular logical expression, which may or may not be equivalent to other definitions under particular ranges of circumstances. The whole point of having Kuratowski's definition, Tarski's definition and the old-style numerical definition of finiteness is that the methods of proving equivalence are themselves interesting methods. I don't know how to express it any better than this. There was a move at a point in history to find definitions for finiteness that did not involve bijections to/from the finite ordinals. Dedekind's and Tarski's and Kuratowski's definitions arose from that effort. Substituting the old numerical definition for the pure set-theoretic definitions would defeat the whole spirit of the endeavour.

What I have done several minutes ago is to simply remove the double-negatives so that it read better. Otherwise it is the same as the original, since the equivalence of not-not-P to P is a purely logical matter.
--Alan U. Kennington (talk) 09:52, 11 August 2014 (UTC)

Yes, I think that the double negative was a big problem. I am glad you fixed it.

I appreciate your desire to avoid referring (indirectly) to natural numbers. However, I have shown elsewhere that the natural numbers can be defined as a proper class, if necessary.

Some people are familiar with the filter of cofinite subsets or the ideal of finite subsets. I wanted to suggest that the powerset of S is merely the union of that filter and that ideal in this case. JRSpriggs (talk) 10:46, 11 August 2014 (UTC)

Even if the natural numbers do not form a set (i.e. ω does not exist), one can still talk about the natural numbers because there is a predicate which separates them from other sets (see Axiom of infinity#Extracting the natural numbers from the infinite set). If NatNum is that predicate, then

$\forall M(\forall r\in M\forall s\in r(s\in M)\Rightarrow \forall n\in M(n\in \omega \Leftrightarrow M\models \operatorname {NatNum} (n)))$

can be proven in V using ZF, even though the transitive model M may only obey the axiom of extensionality and the axiom of induction (which includes the axiom of regularity). JRSpriggs (talk) 07:03, 15 August 2014 (UTC)

Ignoring any models, it is well known, and stated and proved in numerous mathematical logic textbooks (and in my own book too), that there is a relatively simple closed formula for the finite ordinals, and that this does not require the axiom of infinity. However, that's missing the point. The point is that many authors over many decades sought definitions of finite sets which did not require comparison via bijections to the set ω, whether that class is specified by a set-theoretic predicate or via an axiom of infinity. The purpose of this was to get a "non-comparative" definition of finiteness, not a definition which defines it in terms of equal cardinality to a finite ordinal number.

In other words, the issue is not the length of the logical predicate which defines finite sets, nor whether an axiom of infinity is required a-priori. The issue is whether one can plug any set into a simple set-theoretic predicate which does not make comparisons to the set ω. Examples of such non-comparative definitions were given by Sierpinski, Dedekind, Kuratowski, Tarski and numerous others. They certainly knew how to define the class of finite ordinals using a set-theoretic predicate, but they were looking something which did not involve von-Neumann-style ordinals at all. (Nor any other kind of ordinal number representation.) — Preceding unsigned comment added by Alan U. Kennington (talk • contribs) 07:21, 15 August 2014 (UTC)

Subsets of finite sets

The concepts of finiteness should be compatible with the notion of cardinality in two ways: (1) any set which can be mapped bijectively onto a ?-finite should also be ?-finite; and (2) any subset of a ?-finite set should also be ?-finite. There does not seem to be any problem with the first condition. But it is not clear to me that the second condition is met by: V-finite, VI-finite, or VII-finite. Can you show that it is?

There is a generalization of Ia-finite which might be of interest. Imagine forming the disjoint union of three Ia-finite sets. Then one can show that any partition of that union into four parts would result in at least one of the parts being I-finite. This could be generalized as follows

• S is Ib-finite iff there exists a I-finite set A such that for any function f from S to A there would be an element a∈A such that { x∈S | f (x) = a } is I-finite.

This should lie between Ia-finite and II-finite. JRSpriggs (talk) 10:19, 17 August 2014 (UTC)

It sounds like you've been doing some original research on this. I think that original research is a good idea, but I understand that in wikipedia, we are supposed to fairly represent the consensus of the literature. As I said above, what I added comes from "the standard literature in peer-reviewed books and journals, like by Tarski, Mostowski, Lindenbaum, Howard, Rubin, Jech, Moore and many others." If you have some improvements on their publications, you probably should get them peer-reviewed in a journal first before adding them to wikipedia. The 8 different finiteness concept definitions are as I have seen them in all of those esteemed, peer-reviewed authors. I should mention also that I do much original research of my own, and I have many ideas that are opposite to what appears in wikipedia, and which I am certain are opposite to your own beliefs. However, I do not add them to wikipedia because of the original research policy. (My ideas will appear in my own book, where they belong.) If you disagree with some of the finiteness definitions, I think you need to provide peer-reviewed references, which I have done with the 8 finiteness concepts.
--Alan U. Kennington (talk) 10:29, 17 August 2014 (UTC)

So you are writing a book. Will it be your first book? Who will be the publisher? What topics will you cover? Is it related to getting a degree? JRSpriggs (talk) 04:00, 18 August 2014 (UTC)

I shouldn't exploit wikipedia talk-pages to advertise my own book, although it's free at the moment in draft form (currently 1322 pages), and probably always will be free in electronic form. I'll just say something which could possibly be of some interest to readers of this talk-page though. My first book has four parts: I. Foundations. II. Algebra. III. Analysis/topology. IV. Differentiable manifolds (i.e. geometry). The biggest part is on foundations (logic, set theory, numbers). (I'm thinking of self-publishing this part as a separate book.) My motivation for this part arose from the discovery that very large numbers of core concepts in differential geometry rest very heavily on controversial foundational issues, like the axiom of choice. (At least I claim that there are still controversial issues in the foundations after 130 years of research by some of the best minds in mathematics.) Therefore I have read and written a lot about these issues in a book that is supposedly primarily focused on the definitions of differential geometry. (It's strongly focused on definitions as opposed to theorems.)

The reason why this potentially could have some relevance in this forum is that the foundational issues are not purely academic. Virtually all of mathematical analysis rests very heavily upon foundational assumptions, like the assumption that Dedekind-finite sets are finite, or rather that infinite sets always contain an infinite sequence of distinct elements. I am trying to reconstruct differential geometry and the underlying analysis/topology/measure-integration theory without the axiom of choice. This may seem quixotic and foolhardy. But that's what I'm doing. (E.g. linear algebra looks very different in AC, and most functional analysis textbooks would contain only 10 pages if they did not assume AC.) I've said too much already. If you look up my name plus "differential geometry" in a search engine, something will show up. It has nothing to do with a course that I'm studying or teaching. It's a personal crusade! I only mentioned it because I wanted to emphasize that although I disagree strongly with a lot of what I read in the wikipedia logic and set theory pages, I just have to hold my tongue (or keyboard) because this is not a forum for original research. (I can't even add my personal researches regarding the Tawny frogmouth, even though I know that that page has factual errors.) Thanks for asking....
--Alan U. Kennington (talk) 04:59, 18 August 2014 (UTC)

Ah, I see you have a link to your book on your user page User:Alan U. Kennington. I should have looked there first. JRSpriggs (talk) 06:13, 18 August 2014 (UTC)

I was going to ask whether my comments on finite sets would be considered reliable, per WP:SPS, as I am a recognized expert on the axiom of choice and its negation, and I do have a couple of peer-reviewed papers on Dedekind finite (IV-finite) "cardinals". Alan does not appear to be. In any case, the following characterization of Ia-, Ib-, and II- finite may be of interest.

A set S is Ia-finite if any partition of S into I-infinite sets has at most 1 element.

A set S is Ib-finite if any partition of S into I-infinite sets is I-finite, and bounded.

A set S is Ic-finite if any partition of S into I-infinite sets is I-finite.

A set S is II-finite if no partition of S has an I-infinite linearly-ordered subset [without a largest element]. (I believe I can show that any I-infinite linearly-ordered set has a I-infinite linearly-ordered partition without largest element, which is sufficient to remove the bracketed text.

A set S is III-finite if no partition of S [into IV-infinite sets] is IV-infinite.

I consider Ic more interesting than Ib, but it's not obvious that Ic-finite implies II-finite. — Arthur Rubin (talk) 08:39, 20 August 2014 (UTC)

To Arthur: Regarding your note, why would not $F(x)=\{y\vert y\in X\land y\approx x\}$ work, since F:X→P(X) ? JRSpriggs (talk) 09:53, 20 August 2014 (UTC)

You're right. I was confusing ZFU with NBGU (or KMU). What I meant to say is that there isn't a "class function" F (in NBGU) (or property φ in ZFU where $(\forall x)(\exists !y)\varphi (x,y,p_{1},p_{2},\ldots ,p_{n})$, and we make the convention that $\varphi (x,F(x),p_{1},p_{2},\ldots ,p_{n})$) such that $(\forall x,y)(x\approx y\leftrightarrow F(x)=F(y)).$ — Arthur Rubin (talk) 14:12, 20 August 2014 (UTC)

Notes

Other types of finiteness with respect to ω

In the section "Other types of finiteness", it gives different definitions of "finiteness" for ZF without choice.
It specifically mentions that all these defintions are pure set-theoretic definitions that don't explicitly involve ordinals.
But in ZF without choice, it is still possible to construct ω.
Thus we can actually get two new definitions of finiteness:

• S is A-finite iff there exists an injection from S to ω but no bijection from S to ω. (i.e. the |S|<|ω| definition)
• S is B-finite iff there does not exist an injection from ω to S. (i.e. the ¬|S|≥|ω| definition)

I'm just wondering where these definitions fit on the list of the "other types of finiteness". Are they equivalent to any of the definitions there? If not, where do they each fit in the hierarchy? --AndreRD (talk) 09:41, 18 June 2019 (UTC)

See Talk:Finite set#Is it really true that I-finite does not imply T-finite in ZF? above.

I-finite at Finite set#Other concepts of finiteness is the same as Tarski's definition (see #6 at Finite set#Necessary and sufficient conditions for finiteness). Your A-finite is the same as finite (see #1). So I-finite and A-finite are equivalent.

Your B-finite is the same as Dedekind finite which is IV-finite. JRSpriggs (talk) 05:11, 19 June 2019 (UTC)

Problems with the claims about Kuratowski finite

It seems to me that the there are several problems with the claims made about Kuratowski-finite. First, the notion of an object having "all properties" of such-and-such a kind is not generally expressible in ZF set theory, in light of Tarski's theorem on the non-definability of truth. That is, the definition of Kuratowski finite seems explicitly to use a truth predicate, which is not available in ZF. But secondly, since it refers to provability, the notion would seem to trivialize in a model of ZF + ¬Con(ZF), since everything is thought to be provable in such a model. In such a model, there can be no finite sets at all, not even the empty set or singletons. JoelDavid (talk) 18:27, 7 July 2024 (UTC)

ਕੁਲਵਿੰਦਰ ਕੌਰ 30026kly

Jk 223.187.107.135 (talk) 15:51, 26 November 2022 (UTC)