All Questions
Tagged with natural-numbers elementary-set-theory
152
questions
14
votes
8
answers
2k
views
Why can't we define arbitrarily large sets yet after defining these axioms? (Tao's Analysis I)
In Tao's Analysis I I am very confused why he says we do not have the rigor to define arbitrarily large sets after defining the below 2 axioms:
Axiom 3.4 If $a$ is an object, then there exists a set
$...
- 2,119
1
vote
2
answers
142
views
proving the set of natural numbers is infinite (Tao Ex 2.6.3)
Tao's Analysis I 4th ed has the following exercise 3.6.3:
Let $n$ be a natural number, and let $f:\{i \in \mathbb{N}:i \leq i \leq n\} \to \mathbb{N}$ be a function. Show that there exists a natural ...
- 11
8
votes
6
answers
6k
views
Proving there is no natural number which is both even and odd
I've run into a small problem while working through Enderton's Elements of Set Theory. I'm doing the following problem:
Call a natural number even if it has the form $2\cdot m$ for some $m$. Call ...
- 6,099
-1
votes
1
answer
90
views
What is the intuitive meaning of natural numbers as constructed in ZF set theory?
My understanding is that in elementary set theory, the natural numbers are defined so that $0 = \emptyset$ and $n+1 = n \cup \{ n \}$. I understand that this gives us some very pleasant properties ...
- 483
127
votes
9
answers
76k
views
Produce an explicit bijection between rationals and naturals
I remember my professor in college challenging me with this question, which I failed to answer satisfactorily: I know there exists a bijection between the rational numbers and the natural numbers, but ...
- 115
2
votes
1
answer
33
views
Equivalent characterizations of finite sets
How can we show that the following notions of finiteness for a nonempty set $X$ are equivalent?
There exists $n \in \mathbb{N}$ such that there is an injection $X \hookrightarrow \{1, \ldots, n\}$
...
- 7,730
2
votes
0
answers
86
views
Is there a name for this set-theoretical definition of natural numbers, or has it been invented?
I'll call it the binary encoding with sets. I think it's nice and trivial, should have been discovered by many genius brains, but i can't find it by searching with efforts.
Prior arts are Zermelo's ...
- 109
0
votes
1
answer
136
views
Does Cantor’s theorem rely on the Empty Set being in the power set of a set?
As I understand, Cantor’s diagonal set can be empty, that is, there could be a mapping from the the Natural Numbers to the Power Set of the Natural Numbers in which the empty set is not mapped. The ...
4
votes
0
answers
115
views
Show that $f(a,b,c)=(a+b+c)^3+(a+b)^2+a$ is injective.
For a function $f : \mathbb{N} \times \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ defined by
$f(a,b,c)=(a+b+c)^3+(a+b)^2+a$
I want to show that $f$ is injective.
How can I show this?
I ...
- 41
0
votes
1
answer
163
views
Proving (rigorously) that the number of $m$ element subsets of an $n$ element set is ${n \choose m}$
I am trying to solve the following problem (Amann & Escher Analysis I, Exercise I.6.3):
Show that the number of $m$ element subsets of an $n$ element set is ${n \choose m}$.
I emphasize that the ...
- 9,866
0
votes
0
answers
40
views
Induction principle in its set formulation and in its property formulation: which one to use in a well-redacted Induction Step of an induction?
I have read this answer about the well ordering principle and the induction principle. It especially says that "any proper axiomatization of $\mathbb N$ in modern logic does not involve set-...
- 275k
0
votes
0
answers
32
views
Partitioning $\mathbb{N}$ into infinitely many infinite pairwise disjoint sets [duplicate]
Find an infinite collection of infinite sets $A_1,A_2,A_3\ldots$ such that $A_i\cap A_j=\emptyset$ for $i≠j$ and $$\bigcup_{i=1}^{\infty}A_i=\mathbb{N}.$$
My Attempt:
Let $p_i$ be the $i^{\textrm{th}}...
- 2,145
3
votes
1
answer
103
views
Bijection between $\mathbb{N}$ and the set of finite parts of $\mathbb{N}$
Let $\mathbb{N} = \{0,1,2,3,...\}$ be the set of natural numbers (with $0$) and $\mathbb{F}$ the set of finite parts of $\mathbb{N}$. I want to find a bijection, as simple as possible, between $\...
- 1,122
0
votes
0
answers
30
views
Elementary question regarding various definitions of the integers and naturals
So the question is as follows
We need to prove that $\mathbb{\mathbb{Z}}$ is the same set as the following three sets
(i) $\{x\in\mathbb{R}\hspace{0.1cm}|\hspace{0.1cm}x\in\mathbb{\mathbb{N}}\hspace{...
- 85
1
vote
0
answers
106
views
Can every bijection of natural numbers be defined with a closed form formula
I am interested in the existance of closed form formulas for bijections on natural numbers.
With the term closed form is lose. Any information on formulas that represent permutations on N are welcomed....
- 47