1
vote
2answers
37 views

Proving by induction, if the base case fails to meet the main condition, what do we do?

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct. I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$. ...
1
vote
4answers
41 views

Prove that the power set of S contains $|2^n|$ elements

From the above explanation, I don't understand why the set that contains {a} will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$ The construction of a new set $S$ is the union of ...
3
votes
1answer
38 views

Direct proof of principle of transfinite induction

This is a problem from the book Set theory by You-Feng Lin. Principle of Transfinite Induction Let $(A,\le)$ be a well-ordered set. For each $x \in A$, let $p(x)$ be a statement about $x$. If for ...
2
votes
1answer
69 views

Equivalence between “mathematical induction” and “transfinite induction” for natural numbers?

The "principle of mathematical induction" says that for a subset $S$ of $\omega$ (where $\omega$ is the set of all natural numbers), if $0 \in S$ and $n \in S \implies n^+ \in S$, then $S = \omega$. ...
-4
votes
0answers
85 views

proof by mathematical induction that the total number of subsets of a set is $2^n$ [closed]

What is the proof by mathematical induction that the total number of subsets of a set is $2^n$?
2
votes
1answer
64 views

Use principle of mathematical induction to show a function defined recursively is uniquely determined.

I'm having difficulty with the following taken from "Elementary Number Theory And Its Applications" by Rosen section 1.1 questions. "Use the Principal Of Mathematical Induction to show that the value ...
0
votes
1answer
101 views

Is this a Correct Proof of the Principle of Complete Induction for Natural Numbers in ZF?

I have reviewed a number of previous posts on this subject without finding an answer to my own point of interest, which is a proof that is closely related to ZF axioms and doesn't pre-suppose results ...
0
votes
0answers
28 views

Proof by Induction on two languages [duplicate]

I have a question that states - Using proof by induction, prove formally that L(R*) = L((R*)*) -- Where R is a regular expression over a non-empty alphabet. I have am struggling to relate it back to ...
1
vote
1answer
300 views

induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
2
votes
1answer
125 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
102 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
85 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
84 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 ...
1
vote
2answers
75 views

Induction proof: if $n\in\mathbb{N}$, $f:I_n\to B$, and $f$ is onto, then $B$ is finite and $|B|\le n$

Prove that if $n\in\mathbb{N}$, $f:I_n\to B$, and $f$ is onto, then $B$ is finite and $|B|\le n$. Attempt at a proof: We use induction Base case: When $n=0, I_0=\varnothing$ and since $f$ is ...
0
votes
1answer
79 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
146 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
67 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
90 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
156 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$ ...
4
votes
2answers
262 views

Prove the principle of mathematical induction in $\sf ZFC $

How does one prove the principle of mathematical induction using the standard axioms of $\sf ZFC $?
0
votes
1answer
130 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
144 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
726 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
113 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
732 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
250 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
2k 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
646 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 ...
8
votes
3answers
215 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$ ...
1
vote
6answers
1k views

Prove by induction: For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $ 2^N $ subsets. [duplicate]

For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $ 2^N $ subsets. How do I prove this by induction?
3
votes
2answers
98 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
879 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
228 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
144 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
283 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
320 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
172 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
914 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
126 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
762 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
627 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
2k 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
175 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
500 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
499 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 ...