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
$...
- 3,019
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 ...
- 3,325
-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
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\}$
...
- 1,649
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 ...
- 1,143
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-...
- 1,231
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 $\...
- 576
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
2
votes
1
answer
186
views
Is the set of all linear orders on $\mathbb{N}$ linearly orderable?
In studying the issue of linear orders and well ordering in the context of ZF Set Theory (without the Axiom of Choice), I have recently been thinking about the following question:
Is the set of all ...
- 4,331
1
vote
1
answer
76
views
how many linear orderings on $\omega$ the are and how can we identify when 2 of them are in fact isomorphic.
how many linear orderings on $\omega$ the are and how can we identify when 2 of them are in fact isomorphic. I think that by instability argument there are $2^{\aleph_0}$ of them, but I do not know ...
- 3,978
0
votes
1
answer
125
views
What is the cardinality of non-singleton subsets of $\mathbb{N}$?
I am studying a course on ZF Set Theory (without the Axiom of Choice) and am currently looking at the cardinalities of infinite sets. One question that I came across is the following:
Determine the ...
- 4,331
3
votes
1
answer
490
views
Is this exercise from Tao's Analysis 1 erroneous?
On page 68 of the fourth edition of Tao's Analysis 1, is Exercise $3.5.12$, the first part of which I believe is erroneous. The exercise is stated as follows:
(Note: $n++$ refers to the successor of $...
- 469
0
votes
2
answers
120
views
Constructing the power set of natural numbers
Consider the set of Natural numbers, $\mathbb{N}$, and a particular natural number, $n$.
Consider $A_n$ to be the set of all subsets of $\mathbb{N}$ whose size is $\leq n$.
Now as we take $n$ to ...
1
vote
1
answer
75
views
How do you prove that there exists a highest element of any finite, nonempty subset of Natural Numbers? Is the following algorithmic proof valid?
Since the given set, $C \subset \mathbb{N}$ is non empty, hence by well ordering principle there exists $\alpha \in C$ which is the lowest element in C. Also, since the set $C$ is finite, $\quad \...
- 194
1
vote
1
answer
25
views
Function that generates 2 indexes for nested subsets
I'm doing a problem and looking for some way to create a specific bijection between $\mathbb{N}$ and my set $W$. $W$ is a set that contains infinite subsets $Y_n$. Each of these subsets contains every ...
- 121
0
votes
0
answers
24
views
How to count a number of elements in a set with subsequent natural numbers and why substracting the lowest number from the highest is wrong??
I just started learning math from 0 and looking for explanation
I have a set {18,...,32} and the task is to find its cardinality. I was thinking that substracting the lowest (18) from the highest (32) ...
4
votes
1
answer
115
views
Can One Discuss Induction without Sets?
The standard presentation of mathematical induction involves subsets having a certain property. Here is a typical formulation from Gallian's Contemporary Abstract Algebra, Ninth edition:
It seems to ...
- 515
0
votes
2
answers
78
views
Is this an adequate proof that any non-empty subset of N has a minimal element?
I am trying to improve my own standards for proof writing, but I cannot attend school, so I do not have the luxury of being able to speak to professors or peers to verify my attempts. In the proof ...
- 11
1
vote
1
answer
57
views
How do I define the proper subset $\bigcup\limits_{i=1}^\infty[n^2,n^2+1]$ of a set $\bigcup\limits_{i=1}^\infty[n,n+1]$
I have to determine if the set $T=\bigcup\limits_{i=1}^\infty[n^2,n^2+1]$ is bounded and find the supremum and infimum if they exist. Clearly, $T=\{[1,2], [4,5], [9,10]...\}$ it is clearly bounded ...
- 11
0
votes
1
answer
56
views
Describing $\mathbb{N}$ with multiples of $4\mathbb{N}$
Suppose we index subsets of the natural numbers in the following way.
$$\begin{matrix} X_2 = 4 \mathbb{N} &Y_2 = 8\mathbb{N} \\
X_3 = 16\mathbb{N} & Y_3 = 32\mathbb{N} \\
X_4 = 64\mathbb{N} &...
- 2,782
1
vote
1
answer
171
views
Unboundedness of infinite subsets of natural numbers
$\newcommand{\N}{\mathbb{N}}$
I am trying to show that every infinite subset of $\N$ is unbounded, that is,
$$
\forall A \subseteq \N: (|A| = |\N| \Rightarrow \forall m \in \N:\exists n \in A:m < n)...
- 2,617
2
votes
3
answers
134
views
How to show that this set is finite?
Let $m \in \mathbb{N}$
For $\alpha = (\alpha_{1},...,\alpha_{m}) \in \mathbb{N}_{0}^{m}$, let $|\alpha|:= \alpha_{1}+...+\alpha_{m}$
Is the set $\{\alpha \in \mathbb{N}_{0}^{m}: |\alpha|\leq k\}$ ...
- 296
0
votes
1
answer
41
views
Family set of subsets of $\Bbb N$
Let $g:\Bbb N\times\Bbb N \to\Bbb N$ biyective s.t. $g(n, m) = 2^{n-1}(2m-1)$. Show that there exists a famaily set $\{C_n : n \in\Bbb N\}$ of subsets of $\Bbb N$, infinites, disjoints pairwise and ...
- 3
1
vote
1
answer
1k
views
The set of Fibonacci numbers formalized in set-theoretic notation: did I do it correctly?
The set of Fibonacci numbers $= \displaystyle \{x_i \in \Bbb N_0 : x_i = x_{i-1} + x_{i-2} \ \forall \ i \in \Bbb N_2 : x_0 + x_1 =1, >\}$.
Is this correct notation? The $>$ at the end is ...
- 1,129
0
votes
2
answers
306
views
How to prove that there are $n$ natural numbers that are less or equal than $n$ and what properties are allowed to use in induction.
Let $n \in \mathbf{N}$. I wondered how to prove that there are exactly $n$ natural numbers that are smaller or equal than $n$. This seems somewhat circular which confuses me. I guess the way to do ...
- 389
1
vote
1
answer
55
views
Finiteness, finite sets and representing its elements.
A set $S$ is called finite if there exists a bijection from $S$ to $\{1,...,n\}$ for one $n \in \mathbf{N}$. It is then common to write its elements as $s_1,...,s_n$. I now wonder, why this is ...
- 389
0
votes
3
answers
258
views
Can the natural numbers contain an element that is not representable by a number?
I read the following document: https://www.math.wustl.edu/~freiwald/310peanof.pdf . In this document, the author wants to formalize that natural numbers, that are informally thought of as a collection ...
- 389
0
votes
2
answers
100
views
Directly proof $S$ is countable, where $S$ is set of function from $\{0, 1\}$ to $\mathbb{N}$
Suppose $S=\{f_1,f_2,f_3,f_4,f_5,........\}$ where $f_i$ is a function $f:\{0, 1\}\to\mathbb{N}.$ I have to prove $S$ is countable.Then need to prove direct one-to-one correspondence between $S$ and $\...
user976798
2
votes
1
answer
106
views
Why Cantor diagonalization theorem is failed to prove $S$ is countable, Where $S$ is set of finite subset of $\mathbb{N}$?
I have an given set $S$ where $S=$ set of finite subsets of $\mathbb{N}.$ We need to prove $S$ is countably infinite.
My approach: I need to prove there is one-to-one correspondence between $S$ and ${\...
user976798
-1
votes
1
answer
173
views
Why bijection between $\mathbb{N^2}$ and $\mathbb{N}$ is not possible directly?
To understand bijection between $\mathbb{N^2}$ and
$\mathbb{N}$ I found this pdf on internet. But have couple of confusion.
N.B: Here we take $0 \in \mathbb{N}.$
Confusion:1 Why directly proof of ...
- 1
0
votes
0
answers
209
views
Are odd natural numbers an inductive set?
The definition of inductive set my textbook gave is:
A set $T$ that is a subset of the integers is an inductive set
provided that for each integer $k$, if $k$ is an element in the set
$T$, then $k+1$ ...
- 53
0
votes
0
answers
103
views
Why is the principle of induction for natural numbers not "self-evident"? [duplicate]
The principle of induction can be stated, in first-order logic, as follows. Let $S\subseteq\mathbb N$, and suppose that
$0\in S$.
$\forall n:n\in S\to n+1\in S$.
Then, $S=\mathbb N$. Now, suppose ...
- 20.7k
-1
votes
1
answer
135
views
$X$ is infinite thus we have an injection from $\mathbb{N}$ to X [duplicate]
Hey guys I'm trying to prove the following:
$X=\emptyset \lor$ There is a surjection $g: \mathbb{N} \rightarrow X \implies X$ is finite $\lor$ there is a Bijection from $\mathbb{N}$ to X
I did case ...
- 385
2
votes
0
answers
128
views
Statement of Well-ordering principle
The statement of well ordering principle appears in different mode - on subsets of natural numbers, or well-ordering of every (non-empty) set. For the question below, I am considering it w.r.t. non-...
- 3,047
1
vote
0
answers
515
views
Adding a Fixed Value to Each Element in a Set (How to Denote)
To denote a set such as, for example, the set of every natural number that is 3 greater than a multiple of 5, would $5\mathbb{N}+3$ be generally understood as $\{8,13,18,23,28,33,\dots\}$? If not, how ...
- 11
3
votes
3
answers
187
views
Infinite natural numbers?
Only using the successor function $\nu$ and the other axioms, how do we guarantee that the "next" generated number is different from all the "previous" numbers (I am using ...
- 325
3
votes
1
answer
364
views
Showing that the natural numbers are totally ordered with respect to set membership
Working with the usual set theoretic construction of the natural numbers, denoted $\omega$ for now.
I am trying to show that $\omega$ is totally ordered with respect to set membership, that is, $n<...
- 3,612
0
votes
1
answer
85
views
In ZFC, do we use the set $\mathbb{N}$ in the definition of $\mathbb{N}$ recursively?
In ZFC set theory, we define the set of the natural numbers as follows: By the axiom of infinity, an inductive set exists. Let I be an inductive set. Then, $\mathbb{N}$ is defined as $\{ x\in I |\...
- 375
0
votes
0
answers
118
views
A Doubt about Well Ordering Principle and Principle of Mathematical Induction
I have had this lingering doubt in my mind for a very long time: One of the standard constructions of N starts by assuming the 5 Peano Axioms, proving that every non-zero is a successor and s(n) is ...
- 21
0
votes
1
answer
33
views
Defining $A \in \mathcal{P}(\Bbb N \times\Bbb N)$ such that it is not any member of a countable subset $M \subseteq \mathcal{P}(\Bbb N \times \Bbb N)$
$
\newcommand{\N}{\mathbb{N}}
\newcommand{\P}{\mathcal{P}(\N \times \N)}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\i}{^{(i)}}
\newcommand{\x}{^{[x]}}
\newcommand{\y}{^{[y]}}
\newcommand{\...
- 45.9k
0
votes
2
answers
105
views
Is there a specific symbol for $\mathbb{N}\cup\lbrace 0\rbrace$? [duplicate]
It is well known that natural numbers start in 1.
However, sometimes people work with a "widened set" of natural numeres plus zero, $\mathbb{N}\cup\lbrace 0\rbrace$. That is, all non-...
- 164
1
vote
2
answers
96
views
Is this the right way to view infinity in real analysis?
So, I've lately been having confusion on how to understand infinity, but I think I have progress in my intuition. So, I'd appreciate if someone would let me know if I'm on the right track, and which ...
- 1,093
0
votes
1
answer
79
views
Set of all finite subsets of $\mathbb{N}$ not equal to the to set of subsets of $\mathbb{N}$
I can kind of grasp why this is the case as if we take the union of all finite subsets of cardinality $i$ as $i$ runs through every natural number, we are listing finitely many elements each time.
...
- 459
0
votes
2
answers
231
views
Is the set of all natural numbers acctually a proper class?
I have been searching about the difference between a set and a class. The main definitions I found can be resumed in “all sets are classes, but not all classes are sets. If a class is not a set, then ...
user784856
4
votes
2
answers
176
views
Is my proof that the Sharkovsky Ordering is a total ordering, correct?
The Sharkovsky ordering is an ordering of the natural numbers $\mathbb{N}$, where
$3$ $\prec$ $5 $ $\prec$ $7 $ $\prec$ $9$ $\prec$ ...
$2*3$ $\prec$ $2*5$ $\prec$ $...
- 85