Talk:Finite set

Does one really "find counterexamples" in ZF model theory?

My understanding of this subject is not at all expert, but from the little that I do know, I think that in model theory one rarely actually constructs concrete counterexamples. For example, I would dearly love to see just one set which is infinite, but not Dedekind-infinite. Or a set which is Dedekind-finite but not finite. A concrete set of this kind would effectively prove that countable choice is false, not just independent of ZF.

It seems to me that it is possibly misleading to say that one "finds counter-examples" in models for various non-theorems. Wouldn't it be more correct to say that one "demonstrates the existence of counter-examples"? That would be a better form of language if the counter-examples are non-constructible. But I would be happy (and grateful) if someone could give me a constructible infinite set which is not Dedekind-infinite. Then the Bolzano-Weierstraß theorem would bite the dust.
--Alan U. Kennington (talk) 12:17, 9 August 2014 (UTC)

If M is a model different from V and x∈M, the properties that x has as an element of M are not necessarily the same as the properties which it has as an element of V. So it could serve as a counter-example in M to some proposition while still satisfying that proposition in V. That is, properties are model dependent. JRSpriggs (talk) 13:56, 9 August 2014 (UTC)

Yes, that's true. So I don't exclude the possibility of finding a ZF constructible set which is infinite but not Dedekind-infinite due to the ZF model being non-AC. However, my point is still that I think this is somewhat rare, although not impossible. I think, unless I see examples to the contrary, that model theory most of the time just proves in some way that counterexamples exist without constructing them. If so, then the language "finding counterexamples" would be somewhat precarious relative to the language "demonstrating the existence of counterexamples". On the other hand, maybe the people who don't know about these things don't care, and the people who do know about these things will just skip over it because they know what the situation is.
--Alan U. Kennington (talk) 14:02, 9 August 2014 (UTC)

The counter-examples will all be infinite sets. But in M they will lack some of the superstructure which they have in V. That is, some of their subsets or functions involving their elements or subsets and functions of their powersets are missing from M. JRSpriggs (talk) 08:42, 10 August 2014 (UTC)

The 1956 paper by Lévy on finite sets (Lévy, Azriel (1958). "The independence of various definitions of finiteness" (PDF). Fundamenta Mathematicae. 46: 1–13. {{cite journal}}: Invalid |ref=harv (help)) uses the set K of atoms of a Mostowki ZFA model as the basis for all counter-examples. So in this sense, the basic example set is in fact a normal set (in fact countably infinite) within ZF, and not a normal set in a model where AC is false. (This is related to Skolem's paradox, of course, where a set can be both countable and not countable, etc. etc.) The set K of atoms has some relation to the set of rational numbers, but the paper presupposes an understanding of Mostowski models which I do not have. However, the actual choice of set to get the counter-example is not the only thing which is important here. It is the structures which are constructed to get a proof of the non-existence of equivalences between the various definitions. Those might be somewhat non-constructive.

I think my point still remains, though, that the idea of "finding counter-examples" sort of gives a false impression that these are counter-examples in the sense of standard ZF set theory, when in fact the "rules of the game" are quite different, and these counter-examples are in a different sort of set-universe to the usual ones. That's why I prefer to be a bit more fuzzy in my language about these things, and talk about proving non-equivalences rather than finding counter-examples. Anyway, that's my 2¢ worth on the matter. I think I've learned enough about finite sets now to last me till Xmas.
--Alan U. Kennington (talk) 10:12, 10 August 2014 (UTC)

Some of the independence results may be relative to ZF with urelements (ZFU) or with atoms (no regularity) as you say. So perhaps we should change the article to refer to ZFU rather than ZF.

Certainly some aspect of proof is involved — one must prove that a counter-example exists and that it is in fact a counter-example.

What bothered me about your wording was that when you talked about proof, you did not make it clear that you were talking about proving the non-provability rather than proving the reverse implication. JRSpriggs (talk) 10:35, 10 August 2014 (UTC)

Frankly I think there was no harm done at all in the changes you made to the wording. As I said before, the experts who know all about it will just ignore it if it's wrong in some small way, and for the non-experts, it has no real effect, except to perhaps create a slightly false idea that it's like finding counterexamples to the pseudo-theorem: "All continuous functions are differentiable almost everywhere." But really, I don't think anyone's going to start trying to build counter-examples within standard ZF on the basis of this wikipedia article. (I have myself tried to find concrete examples of infinite sets which are not Dedekind-infinite, and I was not surprised that I couldn't find any!)

Getting into model theory in any way, like discussing ZFU or ZFA or Fraenkel-Mostowski models is really at the edges of the scope of the article. I think it's best to just leave it all simple, with just an intriguing little look at 8 non-equivalent finiteness definitions in ZF, which are equivalent in ZF+AC. (I think the equivalences just need countable choice, but I can't swear to the truth of that.) After all, wikipedia is only an encyclopedia, not an academic journal. Readers have to read the references if they want to get real knowledge!

What I've read of the Lévy article is pretty much the discovery of counter-examples. So I'm happy to leave the wording as you have put it. But personally, I prefer not to get into model theory. I think it's all a bit of hocus-pocus and rabbits out of a hat. Model theorists use ZF and other set theories to construct models to make statements about ZF and other set theories. So it's all a bit circular, especially since the absolute consistency of ZF can't be proved.
--Alan U. Kennington (talk) 10:52, 10 August 2014 (UTC)

To show that the reverse implication (from III-finiteness to II-finiteness for example) is not provable, one needs to show that there is no deduction from ZF plus "x is III-finite" to "x is II-finite". This is the same as showing that there is no deduction from ZF plus "x is III-finite and x is not II-finite" to a contradiction. Following Gödel's completeness theorem, one can do this by constructing a model. That is, one makes a series of choices about what the properties of x are, and also what the properties are of such other sets as must exist if x exists. Sometimes these choices are wrong and we must back-track and take the other way. But eventually (if there is not a contradiction), we will get to a model where all the properties of x are specified. If we know the properties of x, then we can get its rank and determine what its elements are and their elements, etc.. Thus the counter-example x should actually exist in V. However, proving that may require assumptions (about V) far beyond just ZF. JRSpriggs (talk) 16:18, 10 August 2014 (UTC)

That is more complicated than necessary (or than commonly used by most set theorists). The standard approach is to assume you have a countable standard model M of ZF + V=L, and construct a model N of ZF (or ZFU) with the desired characteristics. If the desired characteristic is "c is III-finite and c is not II-finite", where c is a new constant symbol, then c_N is a counterexample in N. I recall reading that if Q is a finite subset of the axioms of ZF, then ZF ⊢ Consis(Q), so that N ⊢ finite fragments of ZF + (desired propery) correspond to finite fragments of M ⊢ ZF, so for any finite fragment of ZF + (desired property), ZF

For those confused by metamathematical paradoxes, I know that the compactness theorem implies (∀Q ⊆ ZF)(Q finite → Consis(Q)) ↔ Consis(ZF), but

• (∀Q ⊆ ZF)(Q finite → (ZF ⊢ Consis(Q))

is not the same as

• ZF ⊢ (∀Q ⊆ ZF)(Q finite → Consis(Q))

— Arthur Rubin (talk) 04:12, 11 August 2014 (UTC)

Countable choice and IV-finite (Dedekind finite) imply I-finite. So countable choice is enough to show that I, Ia, II, III, and IV are the same. After that, I think a stronger form of AxCh is needed to establish equivalence of those with V, VI, and VII.

This gets to something which has been bothering me about this section — it is really more about the axiom of choice (or the lack thereof) than it is about finite sets. Except for I-finite sets, none of these sets are really finite rather they are victims of the crippled models in which they live. Calling them alternative definitions of finiteness is misleading. JRSpriggs (talk) 12:08, 12 August 2014 (UTC)

The first paragraph is clearly true and objective. Yes, CC plus IV-finite implies I-finite. I don't think I can agree with anything in the second paragraph. The subject of different kinds of finiteness is not an axiom of choice matter. Calling the models crippled is an extreme value judgement which I can't understand. If you put it that way, then surely all of the models which show the independence of various versions of AC and CH are all crippled. So all of model theory is essentially crippled, unless you have some favourite models which you think are the only models. There is nothing misleading in what it written there. It is in the standard literature in peer-reviewed books and journals, like by Tarski, Mostowski, Lindenbaum, Howard, Rubin, Jech, Moore and many others. They all refer to them as definitions of finiteness. I don't think those authors (and many others) are misleading. Just because you can make lots of definitions equivalent by introducing some extra axioms doesn't mean that they are all the same. There's a lot of diversity in set theory. There is not one single consensus set theory (and one model) which is healthy and able-bodied, while all the rest are "crippled". If you take out the diversity, then a hundred years of set theory, proof theory and model theory have been a waste of time.
--Alan U. Kennington (talk) 12:21, 12 August 2014 (UTC)

VI→I is equivalent to ¬I→¬VI which by Tarski's theorem about choice is equivalent to the full axiom of choice. So VI and VII need the full axiom of choice to be equivalent to I. So the only one which is unclear is V. JRSpriggs (talk) 17:14, 12 August 2014 (UTC)

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)

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

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