2
votes
1answer
103 views

Prove by induction on $n$ that any set of $n$ reals is bounded

Prove by induction on $n$ that any set of $n$ reals is bounded Working: I approached the problem by splitting it into three cases and proving each case, it seems a bit tedious to me how I did it, so ...
0
votes
1answer
45 views

Strong Induction Base Case

Is a base case needed ? In response to many questions on this subject I offer the clarification below.
4
votes
2answers
72 views

Induction without base case?

I'm doing a bit of research on set theory. So far it's quite interesting. Right now I'm reading about transfinite induction. The book states the following theorem about induction in a well-ordered ...
1
vote
1answer
77 views

Is this a correct proof by contradiction?

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$. I have attempted a proof by contradiction as ...
0
votes
1answer
78 views

Proving $A \times (B \cap C) = (A \times B) \cap (A \times C)$ using induction.

first question here. I need to prove that $A \times (B \cap C) = (A \times B) \cap (A \times C)$, using induction. The tactic sounds familiar for sequences, though, (Let $\alpha _n$ be a random ...
1
vote
2answers
42 views

Induction with sets: $\forall n \ge 1: \overline{\bigcap_{i=1}^nA_i}=\bigcup_{i=1}^n \overline{A_i}$

I know how to do induction with equations, but for this thing with sets: $$\forall n \ge 1: \overline{\bigcap\nolimits_{i=1}^nA_i}=\bigcup\nolimits_{i=1}^n \overline{A_i}$$ exactly I don't have an ...
0
votes
1answer
121 views

Prove that set is countable? [duplicate]

Show that the set N* of finite sequences of nonnegative integers is countable. Where do I start? I think I have to prove that there is a bijection between N* and N (set of natural numbers), but how ...
1
vote
0answers
64 views

How to solve a inductively defined set?

I'm new to induction. Right now iIm working on a task which I'm not sure if I've solved it correctly. Here is the task: Give an inductive definition of the given language below: ...
1
vote
1answer
89 views

Inductive definition of a given language

I'm having some difficulties solving a induction task. Here is the task i'm working on: Give an inductive definition of the given language below: $\{a^n,b^n\mid ...
1
vote
1answer
134 views

Proving that the Intersection of all Inductively Defined Sets is Inductive

In Avigad's lecture notes, we are given a set $U$, a subset $B \subseteq U$, and some functions $f_{1}, \dots, f_{k}$. Furthermore, following Enderton (p. 22) say a set is inductive if it contains $B$ ...
0
votes
1answer
112 views

A problem due to Halmos in Santos' number theory [duplicate]

I found this cool problem in Santos' number theory book, page 12, but he gives the credit to Halmos.Supposedly it must be solved by mathematical induction. Every man in a village knows instantly ...
1
vote
2answers
96 views

Proof of the principle of backwards induction

I have difficulty in neatly writing down a proof for the following: Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, ...
1
vote
1answer
546 views

Proof for Strong Induction Principle

I am currently studying analysis and I came across the following exercise. Proposotion 2.2.14 Let $m_0$ be a natural number and let $P(m)$ be a property pertaining to an arbitrary natural ...
0
votes
0answers
108 views

Induction proof of surjectivity

I have a problem. Let $A: S\to T$ be a surjective map between finite sets. Prove by induction that $|S|\geq|T|$ and that if $|S|=|T|$, then $A$ is bijective. Another way to phrase the question is: ...
4
votes
2answers
422 views

Well-Ordering and Mathematical Induction

Here is my attempt to prove the Well-ordering principle, i.e. Any non-empty subset of $\Bbb N$, the set of natural numbers has a minimum element. Proof: Suppose there exists a non-empty subset $S$ of ...
2
votes
1answer
229 views

Does mathematical induction assume that non-negative integers are infinite?

Does mathematical induction assume that the non-negative integers continue indefinitely? A friend of mine was attempting to show me that there are an infinite number of non-negative integers using ...
1
vote
2answers
1k views

A one-to-one function from a finite set to itself is onto - how to prove by induction?

I'm not sure if I can do this without knowing what f actually is? Let $X$ be a finite set with $n$ elements and $f: X \rightarrow X$ a one-to-one function. Prove by induction that $f$ is an onto ...
6
votes
4answers
536 views

Mathematical Induction: how do we know what applies to one thing also applies to another?

Background: I'm new to math. I'm learning about set theory. The book I'm reading (Schaum's Outline of Set Theory) covers mathematical induction. The book uses a common illustration and a common ...
7
votes
3answers
203 views

“If $n=0$ there is nothing to prove”

Suppose that I must prove a theorem by (strong) induction on $\mathbb N$. If the statement of the theorem has sense, for example, for $n\ge 1$, often as base case one chooses $n=0$ and says "for $n=0$ ...
3
votes
2answers
88 views

Proving the size of the unions of sets

How should one go about proving the following with induction? $$ \left| \bigcup_{i \in I} A_i \right| = \sum_{J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right| $$ I is just a finite ...
1
vote
1answer
680 views

Sets induction problem (complement of intersection equals union of complements)

Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$ ...
5
votes
2answers
214 views

troubles proving every subset of a finite set is finite with naive set theory

In a first undergraduate course in analysis, they have established a model of the natural numbers (without zero), proof by induction, recursive definition, injectivity, surjectivity, bijectivity of ...
1
vote
3answers
143 views

Prove that $\bigcap\limits_{i = 1}^n {\left( {{A_i} - B} \right)} = \bigcap\limits_{i = 1}^n {{A_i}} - B$

Prove that if $A_1, A_2, \ldots , A_n$ and $B$ are sets, then $$(A_1 − B) \cap (A_2 − B) \cap \cdots \cap (A_n − B) = (A_1 \cap A_2 \cap \cdots \cap A_n) − B.$$
2
votes
2answers
229 views

Inductive definition of a set

I'm a beginner in set theory and I have doubt regarding mathematical induction. I came across the following examples. Example 1: Find the set given by the following definition: 1) $ 3 \in P $ 2) ...
3
votes
4answers
270 views

Proving that there are infinite cardinal numbers >$\mathfrak{c}$

I was reading Simmons' book and he states that there are infinite cardinal numbers > $\mathfrak{c}$ where $\mathfrak{c}$ denotes the number of Real Numbers. For this, he states that we can construct ...
2
votes
2answers
170 views

$\wp^{(\omega)}(A)=?$

Let $A$ be a set, $$\wp^{(0)}(A)=A$$ $$\wp^{(n+1)}(A)=\wp(\wp^{(n)}(A))$$ But what sense does $\wp^{(\alpha)}(A)$ make where $\alpha$ is a limit ordinal number? The most natural way is let ...
1
vote
1answer
850 views

Inductive Proof of a countable set Cartesian product [duplicate]

Possible Duplicate: Proving $\mathbb{N}^k$ is countable I would like to prove that if S is countable then for any positive integer n the set $S^n$ (the n-fold Cartesian product of S with ...
1
vote
3answers
119 views

Finite set cardinality decreasing

Say I have a finite set $A$ and know its cardinality. How can I prove that, by repeatedly applying some algorithm, which removes a known number of elements from $A$ each time, its cardinality will ...
4
votes
3answers
616 views

What are the cases of not using (countable) induction?

In countably infinite union of countably infinite sets is countable the proof has been given, but when as a student I attempted the question, I tried using induction ( later to found it to be wrong ...
5
votes
3answers
512 views

noetherian induction

So I think I've misunderstood the principle of Noetherian induction as stated in the Hartshorne exercise II.3.16, or his statement is slightly incorrect. He says: "Let $X$ be a Noetherian topological ...
3
votes
2answers
1k views

Using induction to extend DeMorgan's law

I have an assignment in my text that asks me to "Show how induction can be used to conclude that $(A_1 \cup A_2 \cup \dots A_n )^c = A_1^c \cap A_2^c \cap \dots \cap A_n^c$. The issue I am facing is ...
3
votes
1answer
166 views

Question about base cases in induction

So when first developing the natural numbers in basic set theory, most properties are proven by induction. This is very convenient since $\omega$ is the smallest inductive set. I saw a proof of the ...
3
votes
1answer
464 views

Question related with partial order - finite set - minimal element

Prove by induction. Every partial order on a nonempty finite set has at least one minimal element. How can I solve that question ?
1
vote
3answers
440 views

Prove that the natural numbers are present on an inductive definition of another set

If I give you the following definition of the set $A$, how could you prove it is equal the set of the natural numbers without an explicit definiton for the latter? The set $A$ is inductively defined ...