Talk:Finite set/Archive 1

1865:

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.

1247:

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! --

931:"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." 1990:

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.

1497:

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.

31: 1643:

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!)

2213:

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.

153:: 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 271:"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? 95:; 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. 2221:

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

1943:

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

1864:

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

955:

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

2212:

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

1642:

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

1604:

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.

1603:

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

1599:

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

1496:

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,

237:

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

1646:

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

1282:

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

1261:

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

2169: 1373:

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

1848:

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.

226:

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

1938:

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

1246:

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

1985:

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

1650:

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

1989:

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,

1969:

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

1423:

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

1947:

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

1427:

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

939:

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.

241:

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.

699:

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

1844:

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

1647:

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!

1590:

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

2216:

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

1283:

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!

1262:

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

1124:

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

2052: 1369:"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." 1993:

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

1627:

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.

1428:

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.

1048:

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.

1696:

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

1621:

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.

2039:

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

892:

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.

2014:

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.

1166:

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

1651:

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.

935:

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

134:

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.

1668:

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 "

1730:

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

112:

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 !

667:

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,

2164:{\displaystyle \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)))} 1886:

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.

2238: 1159: 889:. So by induction, this stronger property of partial orderings holds for all finite sets. So the last condition in the equivalence also holds. QED. 1939:

invokes existence of bijections to and from ω, and cofinite, which most readers know even less well than "finite", and presumably they came to the

1424:

Dedekind-finite but not finite. A concrete set of this kind would effectively prove that countable choice is false, not just independent of ZF.

257:

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. --

1300:

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

1303:

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

2017:

Some people are familiar with the filter of cofinite subsets or the ideal of finite subsets. I wanted to suggest that the powerset of

407: 1522:. That is, some of their subsets or functions involving their elements or subsets and functions of their powersets are missing from 721:

The condition about partial orderings is equivalent to saying the (seemingly stronger) statement that for every partial ordering of

197:, but lots of the links are not in fact about finite sets, but about other notions. There should really be a disambiguation page at 1624:

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

1685: 1883: 1170:

is finite, then a simple application of mathematical induction shows that its powerset is also finite since the powerset of

118:

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).

311: 2234: 2001: 1955: 1872: 1658: 1611: 1600:

a proof of the non-existence of equivalences between the various definitions. Those might be somewhat non-constructive.

1504: 1435: 1409: 1385: 1290: 1273: 1252: 1153: 38: 1704:, then we can get its rank and determine what its elements are and their elements, etc.. Thus the counter-example 364:

There is redundancy between the Basic Properties and Closure Properties sections. Perhaps they should be merged?

701: 672: 411: 1688:, one can do this by constructing a model. That is, one makes a series of choices about what the properties of 1069:

I do not think that model theory is necessary or helpful to interpret the paragraph which you quoted. Suppose

683:(which should both be there), I'd consider it proved, although I shouldn't add it as a reference, myself. — 2230: 2184: 1997: 1951: 1868: 1654: 1607: 1555: 1500: 1431: 1405: 1381: 1286: 1269: 1248: 1149: 1134: 1053: 945: 261: 298: 227:

strong realism, while simply making mention of an assumption gives a more neutral perspective, I think. --

1832: 980:

showed, this can be cut-down to a model of ZFC (in which there are no such sets). It is not the case that

960: 687: 401: 1568: 1130: 1049: 941: 2226: 369: 325: 102:

mention the other property should also be included! If you have any good ones, then please add them.

2200: 2192: 2026: 1975: 1891: 1854: 1773: 1761:. I recall reading that if Q is a finite subset of the axioms of ZF, then ZF ⊢ Consis(Q), so that 1721: 1632: 1531: 1486: 1355: 1236: 1211: 1114: 1027: 993: 972:

Suppose we are given a model of ZF containing a Dedekind-finite (Kuratowski-)infinite set, call it

897: 709: 657: 1222:

OK. Now I see that the axiom of choice may be needed to select the order in which the elements of

745:, this is easily proved by induction. For the empty set, it is vacuously true because there is no 1002:

That's true. However, the model might be contained (indeed, because AC is Platonistically true,

478: 1592: 2188: 2040: 1829: 957: 684: 397: 106: 347: 293:, in this article. This interesting section introduces infinite set theory, but the article 286: 228: 2222:

von-Neumann-style ordinals at all. (Nor any other kind of ordinal number representation.)

1581: 1398:. This is the right paper to look at! It's got all of the 8 definitions that I put in the 1082: 912: 676: 450: 383: 365: 272: 135: 47: 17: 1010:

is present, but is no longer Dedekind-finite. In the larger model, there is a map from

2196: 2022: 1971: 1887: 1850: 1717: 1628: 1543: 1527: 1482: 1351: 1232: 1226:

are added to the empty set and thus to determine the bijection between the powerset of

1207: 1110: 1023: 989: 893: 705: 653: 243: 212: 202: 142: 78: 1547: 1395: 1595:, of course, where a set can be both countable and not countable, etc. etc.) The set 977: 442: 351: 128: 1738:

of ZF (or ZFU) with the desired characteristics. If the desired characteristic is "

1676:

is II-finite". This is the same as showing that there is no deduction from ZF plus "

331: 258: 1105:

consisting of pairs of socks which have a nonempty intersection with the image of

1089:

is finite. Obviously this contradicts the axiom of choice. It also implies that ∪

2011:

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

318: 46:

If you wish to start a new discussion or revive an old one, please do so on the

2242: 2204: 2030: 2005: 1979: 1959: 1895: 1876: 1858: 1835: 1765:⊢ finite fragments of ZF + (desired propery) correspond to finite fragments of 1725: 1662: 1636: 1615: 1535: 1508: 1490: 1439: 1413: 1389: 1359: 1317:

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

1294: 1277: 1256: 1240: 1215: 1138: 1118: 1057: 1031: 997: 963: 949: 916: 901: 713: 690: 661: 386: 373: 354: 275: 246: 231: 215: 205: 176: 1940: 1399: 1263: 1163: 908: 680: 380: 294: 290: 194: 1934:

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

1469:

are not necessarily the same as the properties which it has as an element of

1402:

wiki page. The reverse implications are all disproved using Mostowski models.

1022:

is Dedekind-finite, because the original model does not contain this map. --

1692:

are, and also what the properties are of such other sets as must exist if

1374:

1954. This article has some info on Levy's contributions to this problem:

1006:

contained, assuming the model is wellfounded) in a larger model in which

124: 121: 92: 168:: empty set is finite, according to everybody, not just Knowledge. Yes, 1375: 1186:) is equivalent to the disjoint union of two copies of the powerset of 464:

To show that they are all equivalent, it is sufficient to show that if

304:

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

173: 115:

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

2041:

Axiom of infinity#Extracting the natural numbers from the infinite set

1101:

would allow one to define a choice function on the infinite subset of

198: 190: 182: 150: 82: 1314:, making that similar to the next two definitions in the subsection. 1849:

Calling them alternative definitions of finiteness is misleading.

1772:

For those confused by metamathematical paradoxes, I know that the

253:

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

2021:

is merely the union of that filter and that ideal in this case.

1769:⊢ ZF, so for any finite fragment of ZF + (desired property), ZF 1477:

to some proposition while still satisfying that proposition in

201:

that would point also to other notions of finite quantities. --

1145:

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

628:

is surjective but not injective. Let the partial ordering put

25: 1986:

numbers if the set of finite ordinal numbers does not exist.

1518:

they will lack some of the superstructure which they have in

753:. Let us make the inductive assumption that it is true for 189:

Adjectives make bad article titles. I've moved what was at

1419:

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

1202:) which is the same as the definition of T-finiteness of 489:. Using mathematical induction one can show that all the 1365:

The Howard/Rubin book is fairly unambiguous about this.

172:

is a sloppy notation for the empty set in this case. --

1712:. However, proving that may require assumptions (about 1548:"The independence of various definitions of finiteness" 1514:

The counter-examples will all be infinite sets. But in

468:

is infinite, then the other three conditions fail. Let

457:

Do you agree that it is obvious that the finiteness of

98:

That said, any interesting definitions of X or Y that

2055: 1396:

The independence of various definitions of finiteness

1970:

Necessary and sufficient conditions for finiteness.

1073:is an infinite set of pairs of socks and for every 346:You are invited to give your opinion about this in 2163: 1306:I notice that Dedekind finite is equivalent to 1+| 310:in a new separate article, such as, for instance, 1684:is not II-finite" to a contradiction. Following 1394:The Levy (1958) paper is available online here: 984:changes its character in this submodel. Rather 414:is sufficient to establish the equivalence of: 157:is finite iff every nonempty set of subsets of 511:∈ω} is a countable set of non-empty sets. Let 281:Moving section "Foundational issues" elsewhere 1018:. The original model can delude itself that 652:, then this ordering has no maximal element. 8: 1700:are specified. If we know the properties of 1473:. So it could serve as a counter-example in 285:After weeks of navigation in Knowledge (see 211:Done (but it should have lots more links) -- 2179:using ZF, even though the transitive model 1481:. That is, properties are model dependent. 560:which implies the Dedekind-infiniteness of 1164:Finite set#Other definitions of finiteness 252: 161:contains a maximal element wrt inclusion. 2054: 1093:is Dedekind-finite because any injection 596:+1) is injective but not surjective. Let 1162:) just added the interesting subsection 1965:I thought about saying "Each subset of 1918:is either finite or cofinite or both.", 1541:The 1956 paper by Lévy on finite sets ( 1198:) which would imply II-finiteness of P( 572:to itself unless it is in the range of 523:) be the first element in the image of 1882:VI→I is equivalent to ¬I→¬VI which by 1577: 1566: 907:Do you intend to add source material? 424:(Dedekind-finite) Every function from 44:Do not edit the contents of this page. 781:be the element which is maximal over 299:Basic concepts in infinite set theory 297:is not even included in the category 77:This encyclopedia defines the terms " 7: 829:which contradicts the maximality of 461:implies the other three conditions? 1734:of ZF + V=L, and construct a model 669:Consequences of the Axiom of Choice 334:(see suggestion by JRSpriggs below) 312:Introduction to infinite set theory 238:statement being true, not provable. 2107: 2077: 2065: 2056: 24: 923:Error in Dedekind-finite example? 410:) questioned whether ZF plus the 988:simply is not in this submodel. 29: 1750:is a new constant symbol, then 428:one-to-one into itself is onto. 2158: 2155: 2152: 2146: 2131: 2119: 2104: 2101: 2089: 2062: 1194:would imply I-finiteness of P( 902:23:53, 29 September 2009 (UTC) 714:00:43, 26 September 2009 (UTC) 691:15:27, 25 September 2009 (UTC) 662:11:35, 25 September 2009 (UTC) 1: 1884:Tarski's theorem about choice 1139:19:43, 1 September 2011 (UTC) 1109:. That is what it is saying. 737:which is greater or equal to 733:, there is a maximal element 1686:Gödel's completeness theorem 1127:Mathematical Intro. to Logic 675:is listed as implying every 536:) which is not equal to any 515:be its choice function. Let 289:), I have found the section 216:22:15, 26 October 2005 (UTC) 206:20:41, 25 October 2005 (UTC) 2243:07:21, 15 August 2014 (UTC) 2205:07:03, 15 August 2014 (UTC) 2031:10:46, 11 August 2014 (UTC) 2006:09:52, 11 August 2014 (UTC) 1980:09:42, 11 August 2014 (UTC) 1960:07:40, 11 August 2014 (UTC) 1896:17:14, 12 August 2014 (UTC) 1877:12:21, 12 August 2014 (UTC) 1859:12:08, 12 August 2014 (UTC) 1836:04:12, 11 August 2014 (UTC) 1726:16:18, 10 August 2014 (UTC) 1663:10:52, 10 August 2014 (UTC) 1637:10:35, 10 August 2014 (UTC) 1616:10:12, 10 August 2014 (UTC) 1536:08:42, 10 August 2014 (UTC) 1230:and its finite cardinality. 1119:06:27, 31 August 2011 (UTC) 1058:03:47, 31 August 2011 (UTC) 1032:09:14, 22 August 2011 (UTC) 998:02:31, 22 August 2011 (UTC) 964:00:06, 22 August 2011 (UTC) 950:23:39, 21 August 2011 (UTC) 568:which maps each element of 355:10:07, 31 August 2007 (UTC) 177:18:28, 14 August 2005 (UTC) 85:" in terms of each other!! 2260: 1922:whereas before there was: 1509:14:02, 9 August 2014 (UTC) 1491:13:56, 9 August 2014 (UTC) 1449:is a model different from 1440:12:17, 9 August 2014 (UTC) 1414:09:24, 9 August 2014 (UTC) 1390:09:01, 9 August 2014 (UTC) 1360:07:43, 9 August 2014 (UTC) 1295:03:41, 9 August 2014 (UTC) 1278:03:26, 9 August 2014 (UTC) 1257:08:24, 8 August 2014 (UTC) 1241:08:01, 8 August 2014 (UTC) 1216:07:54, 8 August 2014 (UTC) 1206:. What am I missing here? 849:is maximal over itself in 741:. For (Kuratowski) finite 556:is an injection from ω to 435:onto itself is one-to-one. 393:Countable choice is enough 387:10:34, 27 April 2009 (UTC) 374:04:26, 27 April 2009 (UTC) 344:Please do not answer here. 276:10:52, 1 August 2007 (UTC) 1746:is not II-finite", where 1708:should actually exist in 865:in which case there is a 702:axiom of countable choice 673:axiom of countable choice 412:axiom of countable choice 262:22:16, 13 July 2007 (UTC) 131:23:29, 19 Apr 2005 (UTC) 109:06:46, 25 Sep 2003 (UTC) 2047:is that predicate, then 837:. On the other hand, if 247:20:36, 12 May 2006 (UTC) 232:18:52, 12 May 2006 (UTC) 2185:axiom of extensionality 1757:is a counterexample in 1556:Fundamenta Mathematicae 1190:. Thus I-finiteness of 917:18:05, 6 May 2011 (UTC) 2165: 1799:finite → (ZF ⊢ Consis( 1716:) far beyond just ZF. 1461:, the properties that 1014:to a proper subset of 869:which is maximal over 2166: 1788:)) ↔ Consis(ZF), but 1465:has as an element of 644:(2)<... for every 337:just where it is now. 42:of past discussions. 2191:(which includes the 2053: 793:is still maximal in 725:, for every element 648:not in the range of 431:Every function from 326:Axiomatic set theory 185:should be a dab page 149:defined in terms of 70:Circular definition? 2193:axiom of regularity 1808:is not the same as 1774:compactness theorem 1672:is III-finite" to " 1376:Levy and set theory 1345:is Dedekind finite. 1331:is Dedekind finite. 809:must be maximal in 620:be the identity on 498:are non-empty. So { 479:injective functions 291:Foundational issues 2231:Alan U. Kennington 2189:axiom of induction 2183:may only obey the 2161: 1998:Alan U. Kennington 1952:Alan U. Kennington 1944:of various kinds. 1869:Alan U. Kennington 1742:is III-finite and 1680:is III-finite and 1655:Alan U. Kennington 1608:Alan U. Kennington 1501:Alan U. Kennington 1432:Alan U. Kennington 1406:Alan U. Kennington 1382:Alan U. Kennington 1287:Alan U. Kennington 1270:Alan U. Kennington 1249:Alan U. Kennington 1150:Alan U. Kennington 441:is empty or every 2246: 2229:comment added by 2175:can be proven in 1914:. Each subset of 1906:So now we have: 67: 66: 54: 53: 48:current talk page 2251: 2245: 2223: 2170: 2168: 2167: 2162: 1819:finite → Consis( 1784:finite → Consis( 1593:Skolem's paradox 1585: 1579: 1574: 1572: 1564: 1552: 927:With regard to: 881:is maximal over 624:otherwise, then 443:partial ordering 421:is a finite set. 287:Talk:Cardinality 74:Wait a minute!! 63: 56: 55: 33: 32: 26: 2259: 2258: 2254: 2253: 2252: 2250: 2249: 2248: 2224: 2051: 2050: 1904: 1755: 1586:) uses the set 1575: 1565: 1550: 1542: 1421: 1266:wikipedia page! 1147: 1083:choice function 925: 757:, and consider 677:Dedekind finite 535: 506: 497: 476: 451:maximal element 395: 362: 317:right here, in 283: 269: 255: 224: 222:Axiom of Choice 187: 72: 59: 30: 22: 21: 20: 18:Talk:Finite set 12: 11: 5: 2257: 2255: 2210: 2209: 2208: 2207: 2173: 2172: 2171: 2160: 2157: 2154: 2151: 2148: 2145: 2142: 2139: 2136: 2133: 2130: 2127: 2124: 2121: 2118: 2115: 2112: 2109: 2106: 2103: 2100: 2097: 2094: 2091: 2088: 2085: 2082: 2079: 2076: 2073: 2070: 2067: 2064: 2061: 2058: 2034: 2033: 2015: 2012: 1995: 1983: 1982: 1949: 1936: 1935: 1920: 1919: 1903: 1900: 1899: 1898: 1866: 1862: 1861: 1846: 1841: 1840: 1839: 1838: 1826: 1825: 1824: 1806: 1805: 1804: 1770: 1753: 1652: 1640: 1639: 1625: 1622: 1605: 1539: 1538: 1498: 1494: 1493: 1429: 1420: 1417: 1403: 1379: 1371: 1370: 1363: 1362: 1350:Any thoughts? 1348: 1347: 1346: 1332: 1315: 1304: 1301: 1284: 1267: 1244: 1243: 1146: 1143: 1142: 1141: 1067: 1066: 1065: 1064: 1063: 1062: 1061: 1060: 1039: 1038: 1037: 1036: 1035: 1034: 967: 966: 933: 932: 924: 921: 920: 919: 845:, then either 805:in which case 789:, then either 719: 718: 717: 716: 694: 693: 576:in which case 531: 502: 493: 477:be the set of 472: 455: 454: 436: 429: 422: 394: 391: 390: 389: 361: 358: 341: 340: 339: 338: 335: 328: 322: 315: 282: 279: 268: 265: 254: 251: 250: 249: 239: 223: 220: 219: 218: 186: 180: 143:natural number 79:natural number 71: 68: 65: 64: 52: 51: 34: 23: 15: 14: 13: 10: 9: 6: 4: 3: 2: 2256: 2247: 2244: 2240: 2236: 2232: 2228: 2220: 2214: 2206: 2202: 2198: 2194: 2190: 2186: 2182: 2178: 2174: 2149: 2143: 2140: 2137: 2134: 2128: 2125: 2122: 2116: 2113: 2110: 2098: 2095: 2092: 2086: 2083: 2080: 2074: 2071: 2068: 2059: 2049: 2048: 2046: 2042: 2038: 2037: 2036: 2035: 2032: 2028: 2024: 2020: 2016: 2013: 2010: 2009: 2008: 2007: 2003: 1999: 1991: 1987: 1981: 1977: 1973: 1968: 1964: 1963: 1962: 1961: 1957: 1953: 1945: 1942: 1933: 1929: 1925: 1924: 1923: 1917: 1913: 1909: 1908: 1907: 1901: 1897: 1893: 1889: 1885: 1881: 1880: 1879: 1878: 1874: 1870: 1860: 1856: 1852: 1847: 1843: 1842: 1837: 1834: 1831: 1827: 1822: 1818: 1814: 1810: 1809: 1807: 1802: 1798: 1794: 1790: 1789: 1787: 1783: 1779: 1775: 1771: 1768: 1764: 1760: 1756: 1749: 1745: 1741: 1737: 1733: 1729: 1728: 1727: 1723: 1719: 1715: 1711: 1707: 1703: 1699: 1695: 1691: 1687: 1683: 1679: 1675: 1671: 1667: 1666: 1665: 1664: 1660: 1656: 1648: 1644: 1638: 1634: 1630: 1626: 1623: 1620: 1619: 1618: 1617: 1613: 1609: 1601: 1598: 1594: 1589: 1583: 1570: 1562: 1558: 1557: 1549: 1545: 1537: 1533: 1529: 1525: 1521: 1517: 1513: 1512: 1511: 1510: 1506: 1502: 1492: 1488: 1484: 1480: 1476: 1472: 1468: 1464: 1460: 1456: 1452: 1448: 1444: 1443: 1442: 1441: 1437: 1433: 1425: 1418: 1416: 1415: 1411: 1407: 1401: 1397: 1392: 1391: 1387: 1383: 1377: 1368: 1367: 1366: 1361: 1357: 1353: 1349: 1344: 1340: 1336: 1333: 1330: 1326: 1322: 1319: 1318: 1316: 1313: 1309: 1305: 1302: 1299: 1298: 1297: 1296: 1292: 1288: 1280: 1279: 1275: 1271: 1265: 1259: 1258: 1254: 1250: 1242: 1238: 1234: 1231: 1229: 1225: 1220: 1219: 1218: 1217: 1213: 1209: 1205: 1201: 1197: 1193: 1189: 1185: 1181: 1177: 1173: 1169: 1165: 1161: 1158: 1155: 1151: 1144: 1140: 1136: 1132: 1131:TricksterWolf 1128: 1123: 1122: 1121: 1120: 1116: 1112: 1108: 1104: 1100: 1097:from ω into ∪ 1096: 1092: 1088: 1084: 1080: 1076: 1072: 1059: 1055: 1051: 1050:TricksterWolf 1047: 1046: 1045: 1044: 1043: 1042: 1041: 1040: 1033: 1029: 1025: 1021: 1017: 1013: 1009: 1005: 1001: 1000: 999: 995: 991: 987: 983: 979: 975: 971: 970: 969: 968: 965: 962: 959: 954: 953: 952: 951: 947: 943: 942:TricksterWolf 938: 930: 929: 928: 922: 918: 914: 910: 906: 905: 904: 903: 899: 895: 890: 888: 884: 880: 876: 872: 868: 864: 860: 856: 852: 848: 844: 840: 836: 832: 828: 824: 820: 816: 813:. Otherwise, 812: 808: 804: 800: 796: 792: 788: 784: 780: 776: 772: 768: 764: 760: 756: 752: 748: 744: 740: 736: 732: 728: 724: 715: 711: 707: 703: 698: 697: 696: 695: 692: 689: 686: 682: 678: 674: 670: 666: 665: 664: 663: 659: 655: 651: 647: 643: 639: 635: 631: 627: 623: 619: 615: 611: 607: 603: 599: 595: 591: 587: 583: 579: 575: 571: 567: 563: 559: 555: 551: 547: 543: 539: 534: 530: 526: 522: 518: 514: 510: 505: 501: 496: 492: 488: 484: 480: 475: 471: 467: 462: 460: 452: 448: 444: 440: 437: 434: 430: 427: 423: 420: 417: 416: 415: 413: 409: 406: 403: 399: 392: 388: 385: 382: 378: 377: 376: 375: 371: 367: 359: 357: 356: 353: 349: 345: 336: 333: 329: 327: 323: 320: 316: 313: 309: 308: 307: 306: 305: 302: 300: 296: 292: 288: 280: 278: 277: 274: 266: 264: 263: 260: 248: 245: 240: 236: 235: 234: 233: 230: 221: 217: 214: 210: 209: 208: 207: 204: 200: 196: 192: 184: 181: 179: 178: 175: 171: 170:{1,2,3,...,n} 167: 162: 160: 156: 152: 148: 144: 139: 137: 132: 130: 126: 122: 119: 116: 113: 110: 108: 103: 101: 96: 94: 89: 86: 84: 80: 75: 69: 62: 58: 57: 49: 45: 41: 40: 35: 28: 27: 19: 2225:— Preceding 2218: 2215: 2211: 2180: 2176: 2044: 2018: 1992: 1988: 1984: 1966: 1946: 1937: 1931: 1927: 1921: 1915: 1911: 1905: 1863: 1830:Arthur Rubin 1820: 1816: 1812: 1800: 1796: 1792: 1785: 1781: 1777: 1766: 1762: 1758: 1751: 1747: 1743: 1739: 1735: 1731: 1713: 1709: 1705: 1701: 1697: 1693: 1689: 1681: 1677: 1673: 1669: 1649: 1645: 1641: 1602: 1596: 1587: 1569:cite journal 1560: 1554: 1544:Lévy, Azriel 1540: 1523: 1519: 1515: 1495: 1478: 1474: 1470: 1466: 1462: 1458: 1454: 1450: 1446: 1426: 1422: 1393: 1372: 1364: 1342: 1338: 1334: 1328: 1324: 1320: 1311: 1307: 1281: 1260: 1245: 1227: 1223: 1221: 1203: 1199: 1195: 1191: 1187: 1183: 1179: 1175: 1171: 1167: 1156: 1148: 1126: 1106: 1102: 1098: 1094: 1090: 1086: 1081:which has a 1078: 1074: 1070: 1068: 1019: 1015: 1011: 1007: 1003: 985: 981: 973: 958:Arthur Rubin 936: 934: 926: 891: 886: 882: 878: 874: 870: 866: 862: 858: 854: 850: 846: 842: 838: 834: 830: 826: 822: 818: 814: 810: 806: 802: 798: 794: 790: 786: 782: 778: 774: 770: 766: 762: 758: 754: 750: 746: 742: 738: 734: 730: 726: 722: 720: 685:Arthur Rubin 668: 649: 645: 641: 637: 633: 629: 625: 621: 617: 613: 609: 605: 601: 597: 593: 589: 585: 581: 577: 573: 569: 565: 561: 557: 553: 549: 545: 541: 537: 532: 528: 524: 520: 516: 512: 508: 503: 499: 494: 490: 486: 482: 473: 469: 465: 463: 458: 456: 446: 438: 432: 425: 418: 404: 398:Arthur Rubin 396: 363: 343: 342: 332:Infinite set 303: 284: 270: 256: 225: 188: 169: 165: 163: 158: 154: 146: 140: 138:May 5, 2005 133: 120: 117: 114: 111: 107:Toby Bartels 104: 99: 97: 90: 87: 76: 73: 60: 43: 37: 1776:implies (∀ 449:contains a 319:Cardinality 295:finite sets 229:Fell Collar 91:This isn't 36:This is an 1941:finite set 1400:finite set 1264:finite set 978:Kurt Gödel 616:) and let 366:WardenWalk 360:Redundancy 350:. Regards, 273:Sam Staton 195:finite set 136:bananaclaw 2197:JRSpriggs 2023:JRSpriggs 1972:JRSpriggs 1948:I-finite. 1928:Ia-finite 1912:Ia-finite 1888:JRSpriggs 1851:JRSpriggs 1718:JRSpriggs 1629:JRSpriggs 1578:|ref=harv 1528:JRSpriggs 1483:JRSpriggs 1352:JRSpriggs 1341:)) where 1233:JRSpriggs 1208:JRSpriggs 1111:JRSpriggs 1024:Trovatore 990:JRSpriggs 956:here. — 894:JRSpriggs 877:and thus 706:JRSpriggs 671:; if the 654:JRSpriggs 348:this page 244:Trovatore 213:Trovatore 203:Trovatore 61:Archive 1 2239:contribs 2227:unsigned 2187:and the 1902:Cofinite 1576:Invalid 1546:(1958). 1327:) where 1160:contribs 704:(CC).". 564:, since 408:contribs 379:Done. — 352:Paolo.dL 267:Dedekind 93:Bourbaki 88:-- Anon 1994:matter. 1811:ZF ⊢ (∀ 1563:: 1–13. 1182:not in 1178:} (for 679:set is 640:(1)< 636:(0)< 552:. Then 259:Fsmoura 164:As for 141:First, 81:" and " 39:archive 2141:NatNum 2045:NatNum 2043:). If 1833:(talk) 1815:⊆ ZF)( 1795:⊆ ZF)( 1780:⊆ ZF)( 1310:|: --> 961:(talk) 777:, let 769:}. If 688:(talk) 681:finite 544:) for 485:+1 to 199:finite 191:finite 183:Finite 151:finite 83:finite 1551:(PDF) 1337:⊆P(P( 976:. As 909:Cliff 608:+1))= 481:from 100:don't 16:< 2235:talk 2201:talk 2027:talk 2002:talk 1976:talk 1956:talk 1892:talk 1873:talk 1855:talk 1845:VII. 1722:talk 1659:talk 1633:talk 1612:talk 1582:help 1532:talk 1505:talk 1487:talk 1453:and 1436:talk 1410:talk 1386:talk 1356:talk 1291:talk 1274:talk 1253:talk 1237:talk 1212:talk 1154:talk 1135:talk 1129:.) 1115:talk 1054:talk 1028:talk 994:talk 946:talk 913:talk 898:talk 710:talk 658:talk 632:< 548:< 402:talk 381:Emil 370:talk 129:Talk 2219:not 2195:). 1445:If 1323:⊆P( 937:not 885:in 873:in 853:or 833:in 797:or 785:in 749:in 729:of 588:))= 445:of 330:in 324:in 301:! 193:to 166:n=0 147:not 145:is 125:MFH 105:-- 2241:) 2237:• 2203:) 2144:⁡ 2138:⊨ 2132:⇔ 2129:ω 2126:∈ 2114:∈ 2108:∀ 2105:⇒ 2096:∈ 2084:∈ 2078:∀ 2072:∈ 2066:∀ 2057:∀ 2029:) 2004:) 1996:-- 1978:) 1958:) 1950:-- 1930:. 1894:) 1875:) 1867:-- 1857:) 1828:— 1823:)) 1803:)) 1791:(∀ 1724:) 1661:) 1653:-- 1635:) 1614:) 1606:-- 1573:: 1571:}} 1567:{{ 1561:46 1559:. 1553:. 1534:) 1526:. 1507:) 1499:-- 1489:) 1438:) 1430:-- 1412:) 1404:-- 1388:) 1380:-- 1358:) 1293:) 1285:-- 1276:) 1268:-- 1255:) 1239:) 1214:) 1174:∪{ 1137:) 1117:) 1085:, 1056:) 1030:) 1004:is 996:) 948:) 915:) 900:) 765:∪{ 712:) 660:) 384:J. 372:) 242:-- 174:EJ 127:: 123:— 2233:( 2199:( 2181:M 2177:V 2159:) 2156:) 2153:) 2150:n 2147:( 2135:M 2123:n 2120:( 2117:M 2111:n 2102:) 2099:M 2093:s 2090:( 2087:r 2081:s 2075:M 2069:r 2063:( 2060:M 2025:( 2019:S 2000:( 1974:( 1967:S 1954:( 1932:S 1926:" 1916:S 1910:" 1890:( 1871:( 1853:( 1821:Q 1817:Q 1813:Q 1801:Q 1797:Q 1793:Q 1786:Q 1782:Q 1778:Q 1767:M 1763:N 1759:N 1754:N 1752:c 1748:c 1744:c 1740:c 1736:N 1732:M 1720:( 1714:V 1710:V 1706:x 1702:x 1698:x 1694:x 1690:x 1682:x 1678:x 1674:x 1670:x 1657:( 1631:( 1610:( 1597:K 1588:K 1584:) 1580:( 1530:( 1524:M 1520:V 1516:M 1503:( 1485:( 1479:V 1475:M 1471:V 1467:M 1463:x 1459:M 1457:∈ 1455:x 1451:V 1447:M 1434:( 1408:( 1384:( 1378:. 1354:( 1343:D 1339:D 1335:S 1329:D 1325:D 1321:S 1312:S 1308:S 1289:( 1272:( 1251:( 1235:( 1228:S 1224:S 1210:( 1204:S 1200:S 1196:S 1192:S 1188:S 1184:S 1180:x 1176:x 1172:S 1168:S 1157:· 1152:( 1133:( 1113:( 1107:f 1103:S 1099:S 1095:f 1091:S 1087:B 1079:S 1077:⊆ 1075:B 1071:S 1052:( 1026:( 1020:D 1016:D 1012:D 1008:D 992:( 986:D 982:D 974:D 944:( 911:( 896:( 887:T 883:b 879:m 875:S 871:y 867:m 863:S 861:∈ 859:y 857:≤ 855:b 851:T 847:b 843:b 841:= 839:x 835:S 831:m 827:S 825:∈ 823:y 821:≤ 819:b 817:≤ 815:m 811:T 807:b 803:b 801:≤ 799:m 795:T 791:m 787:S 783:x 779:m 775:b 773:≠ 771:x 767:b 763:S 761:= 759:T 755:S 751:S 747:x 743:S 739:x 735:m 731:S 727:x 723:S 708:( 656:( 650:g 646:x 642:g 638:g 634:g 630:x 626:l 622:S 618:l 614:n 612:( 610:g 606:n 604:( 602:g 600:( 598:l 594:n 592:( 590:g 586:n 584:( 582:g 580:( 578:h 574:g 570:S 566:h 562:S 558:S 554:g 550:n 546:k 542:k 540:( 538:g 533:n 529:B 527:( 525:f 521:n 519:( 517:g 513:f 509:n 507:| 504:n 500:B 495:n 491:B 487:S 483:n 474:n 470:B 466:S 459:S 453:. 447:S 439:S 433:S 426:S 419:S 405:· 400:( 368:( 321:; 314:; 159:X 155:X 50:.

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index