Reference Request-Discrete Mathematics

Question

Being a student of Graduate Level, we are learning some good pure mathematics nowdays. Studying Discrete Mathematics is somewhat different I thought.

We are said that Finite Set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting.

But what does finite mean here?

Instead Our professor defined finite as which is not infinite. where infinite set $A$ is a set such that there exists a bijection from some proper subset $B \subset A $ to A.

I tried to search library for some reference, but none are written from Pure Mathematics Point of view, hence I request you to suggest me a reference book with some sensible definitions(Pure Mathematics point of view) and some good amount of quality problems

I would like to learn the following topics(Problems Solving is more focused)

1- Finite-Infinite

2-Functions and Relations

3- Countable-Uncountable

4-Posets

Thanks

Answer 1

Since you're a graduate student and sets are not totally new to you, I suggest Enderton's Elements of Set Theory.

It starts with the very basics of set theory, without overlooking the axioms of ZFC (some axioms are introduced later in the book as they're not useful in the beginning). It even teaches you to justify that a given collection of elements is indeed a set (as there are collections that are not sets, for example the collection of all sets), so it does things in the rigour that you're looking for.

The book covers the topics you mentioned. It also explains the definition given by your professor: actually, the book gives a definition of finite sets, then defines infinite sets to be sets that are not finite. Then it gives the following in page 157:

Corollary 6P A set is infinite iff it is equinumerous to a proper subset of itself.

Hence, you'll understand why one can define an infinite set as your professor defined it, and then finite sets to be sets that are not infinite.

The book contains a lot of exercises varying in difficulty. You'll be able to cover all the topics you mentioned by reading chapters 1-6 (knowing that chapter 1 is a discussion about set theory, and chapter 5 is not required for any chapter in the book).

I find that the author explains really well. He also presents important notions like induction and recursive definition in a rigorous way, so it doesn't lack the pure mathematics viewpoint. The author also discusses sometimes the history of set theory and talks about the foundational issues related to it.

The book also covers in good rigour cardinal numbers (the size of sets, even infinite ones) and ordinal numbers (which represent the different well orderings you can have)in chapters 7 and 8. Ordinal numbers have nice applications like transfinite induction, which is more general than induction on $\mathbb N$. It can be used to solve some problems in topology and measure theory for example. Ordinal numbers and cardinal numbers are also important in studying infinite discrete structures. They're definitely crucial if you want to study infinite combinatorics and infinite graphs for example.

Finally, if you want more problem solving, you can work on additional exercises in Komjáth and Totik's Problems and Theorems in Classical Set Theory.

Answer 2

You are referring to the defintion of Dedekind infinite set.. There are several other definitions in the Wikipedia article finite set and they are technical. You may be interested in reading the textbook Naive Set Theory by Paul Halmos. There are more advanced textbooks but you have to start somewhere.

Answer 3

Without the Axiom of Choice (AC) you need caution for "finite" and "infinite". A set $X$ is Tarski-finite iff every non-empty family of subsets of $X$ has a $\subset$-minimal member. A set $X$ is Dedekind-finite iff there does not exist an injective $f:A\to B$ for any proper subset $B$ of $A.$ Without AC we can show that $X$ is Tarski-finite iff there is a bijection $g:X\to \{j:j<n\}$ for some (unique) $n\in \Bbb N$ and we can show that $Y$ is Dedekind-infinite iff there is an injection $g:\Bbb N\to Y$.

Without AC we can show that every Tarski-finite set is Dedekind-finite, but not vice-versa. AC implies that $X$ is Dedekind-finite iff $X$ is Tarski-finite.

As for references, other than the Halmos book (in another Answer), the book Set Theory:An Introduction To Independence Proofs by K. Kunen presents a thorough development of the basics of the subject from the Axioms, but also includes much advanced material. You can find a good deal of basic set theory, less formally, in Introduction To Topology And Modern Analysis by Simmons. For some fun, try Stories About Sets, by Vilenkin.

The word "poset" has different meanings in different contexts. In Kunen's book a poset is a set $X$ with a binary relation $\leq$ on $X$ which is reflexive and transitive, which is a very broad def'n.

Cautions: (1).An important and basic theorem in set theory is known variously as the Schroeder-Bernstein Theorem, the Cantor-Bernstein Theorem, and the Schroeder-Cantor-Bernstein Theorem. (2). The set-theoretic Axiom of Foundation is also called the Axiom of Regularity.(3). Some authors combine the axiom schemas (collections of axioms) known as the Comprehension schema and the Replacement schema into a single schema which they also call Replacement.