Usbrth

How to test the equality of two Pearson correlation coefficients computed from the same sample?

Can smartphones with the same camera sensor have different image quality?

Would an alien lifeform be able to achieve space travel if lacking in vision?

Why can't wing-mounted spoilers be used to steepen approaches?

Was credit for the black hole image misattributed?

How does ice melt when immersed in water

Did the new image of black hole confirm the general theory of relativity?

Can a 1st-level character have an ability score above 18?

Do working physicists consider Newtonian mechanics to be "falsified"?

Do warforged have souls?

verb not working in beamer even though I use [fragile]

how can a perfect fourth interval be considered either consonant or dissonant?

Can the DM override racial traits?

Make it rain characters

University's motivation for having tenure-track positions

system call string length limit

How is simplicity better than precision and clarity in prose?

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

The variadic template constructor of my class cannot modify my class members, why is that so?

Does the AirPods case need to be around while listening via an iOS Device?

Problems with Ubuntu mount /tmp

Difference between "generating set" and free product?

Why is superheterodyning better than direct conversion?

Arduino Pro Micro - switch off LEDs

Using mathematical induction on $X_n$ within the definition of $X_n$?

2

$begingroup$

Assume we have a domain $D$ with a property $phi(x)$ that is either true or false for any $xin D$. Also assume that there is a function $f:Phito Phi$, where $Phi = xin D:phi(x)$.

Consider the following construction:
Let $X_1$ be a set such that for all $xin X_1, phi(x)$ holds. And define:
$$X_n = yin D: exists xin X_n-1, f(x)=y $$

I am trying to prove by mathematical induction that for all $n, X_nsubseteq Phi$. This seems to me to be very obviously true and almost trivial, but I don't know how to actually prove it, since it seems we need the induction step to even define $X_n$. Strictly speaking, $f(x)$ within the definition of $X_n$ is undefined, since we don't know whether for arbitrary $xin X_n-1$, $xin Phi$. So it seems we need to use mathematical induction to prove that $X_nin Phi$ before we can even define $X_n$.

This seems messy, so what should I do to solve this?

EDIT:
Intuitively, if you think of defining $X_n$ as a procedure, we can simply do it like this:

Pseudocode:

i=1
prove X_1 subset of Phi 
while true
 Define X_i+1 using the fact that X_i is a subset of $Phi$
 Prove that X_i+1 is a subset of $Phi$.
 i++;

But this would be different from mathematical induction (afaik), and I'm not sure how to formalize it mathematically.

elementary-set-theory induction

share|cite|improve this question

edited Apr 9 at 6:37

user56834

asked Apr 8 at 11:55

user56834user56834

3,32521253

$endgroup$

add a comment | 

2

$begingroup$

Assume we have a domain $D$ with a property $phi(x)$ that is either true or false for any $xin D$. Also assume that there is a function $f:Phito Phi$, where $Phi = xin D:phi(x)$.

Consider the following construction:
Let $X_1$ be a set such that for all $xin X_1, phi(x)$ holds. And define:
$$X_n = yin D: exists xin X_n-1, f(x)=y $$

I am trying to prove by mathematical induction that for all $n, X_nsubseteq Phi$. This seems to me to be very obviously true and almost trivial, but I don't know how to actually prove it, since it seems we need the induction step to even define $X_n$. Strictly speaking, $f(x)$ within the definition of $X_n$ is undefined, since we don't know whether for arbitrary $xin X_n-1$, $xin Phi$. So it seems we need to use mathematical induction to prove that $X_nin Phi$ before we can even define $X_n$.

This seems messy, so what should I do to solve this?

EDIT:
Intuitively, if you think of defining $X_n$ as a procedure, we can simply do it like this:

Pseudocode:

i=1
prove X_1 subset of Phi 
while true
 Define X_i+1 using the fact that X_i is a subset of $Phi$
 Prove that X_i+1 is a subset of $Phi$.
 i++;

But this would be different from mathematical induction (afaik), and I'm not sure how to formalize it mathematically.

elementary-set-theory induction

share|cite|improve this question

edited Apr 9 at 6:37

user56834

asked Apr 8 at 11:55

user56834user56834

3,32521253

$endgroup$

add a comment | 

$begingroup$

Assume we have a domain $D$ with a property $phi(x)$ that is either true or false for any $xin D$. Also assume that there is a function $f:Phito Phi$, where $Phi = xin D:phi(x)$.

Consider the following construction:
Let $X_1$ be a set such that for all $xin X_1, phi(x)$ holds. And define:
$$X_n = yin D: exists xin X_n-1, f(x)=y $$

I am trying to prove by mathematical induction that for all $n, X_nsubseteq Phi$. This seems to me to be very obviously true and almost trivial, but I don't know how to actually prove it, since it seems we need the induction step to even define $X_n$. Strictly speaking, $f(x)$ within the definition of $X_n$ is undefined, since we don't know whether for arbitrary $xin X_n-1$, $xin Phi$. So it seems we need to use mathematical induction to prove that $X_nin Phi$ before we can even define $X_n$.

This seems messy, so what should I do to solve this?

EDIT:
Intuitively, if you think of defining $X_n$ as a procedure, we can simply do it like this:

Pseudocode:

i=1
prove X_1 subset of Phi 
while true
 Define X_i+1 using the fact that X_i is a subset of $Phi$
 Prove that X_i+1 is a subset of $Phi$.
 i++;

But this would be different from mathematical induction (afaik), and I'm not sure how to formalize it mathematically.

elementary-set-theory induction

share|cite|improve this question

edited Apr 9 at 6:37

user56834

asked Apr 8 at 11:55

user56834user56834

3,32521253

$endgroup$

i=1
prove X_1 subset of Phi 
while true
 Define X_i+1 using the fact that X_i is a subset of $Phi$
 Prove that X_i+1 is a subset of $Phi$.
 i++;

share|cite|improve this question

edited Apr 9 at 6:37

user56834

asked Apr 8 at 11:55

user56834user56834

3,32521253

share|cite|improve this question

edited Apr 9 at 6:37

user56834

asked Apr 8 at 11:55

user56834user56834

3,32521253

asked Apr 8 at 11:55

user56834user56834

3,32521253

asked Apr 8 at 11:55

user56834user56834

3,32521253

1 Answer
1

active

oldest

votes

0

$begingroup$

Instead of saying $f(x) = y$ we can rollback to definition of function and write $langle x, yrangle in f$ in definition of $X_n$ - it's well defined for any $x, y$.

Then we can notice that as $f subset Phi times Phi$, $langle x, yrangle in f$ implies $y in Phi$.

share|cite|improve this answer

answered Apr 8 at 12:04

mihaildmihaild

80710

New contributor

mihaild is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3179534%2fusing-mathematical-induction-on-x-n-within-the-definition-of-x-n%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

Instead of saying $f(x) = y$ we can rollback to definition of function and write $langle x, yrangle in f$ in definition of $X_n$ - it's well defined for any $x, y$.

Then we can notice that as $f subset Phi times Phi$, $langle x, yrangle in f$ implies $y in Phi$.

share|cite|improve this answer

answered Apr 8 at 12:04

mihaildmihaild

80710

New contributor

mihaild is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

0

$begingroup$

Instead of saying $f(x) = y$ we can rollback to definition of function and write $langle x, yrangle in f$ in definition of $X_n$ - it's well defined for any $x, y$.

Then we can notice that as $f subset Phi times Phi$, $langle x, yrangle in f$ implies $y in Phi$.

share|cite|improve this answer

answered Apr 8 at 12:04

mihaildmihaild

80710

New contributor

mihaild is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

Instead of saying $f(x) = y$ we can rollback to definition of function and write $langle x, yrangle in f$ in definition of $X_n$ - it's well defined for any $x, y$.

Then we can notice that as $f subset Phi times Phi$, $langle x, yrangle in f$ implies $y in Phi$.

share|cite|improve this answer

answered Apr 8 at 12:04

mihaildmihaild

80710

New contributor

mihaild is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this answer

answered Apr 8 at 12:04

mihaildmihaild

80710

New contributor

mihaild is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered Apr 8 at 12:04

mihaildmihaild

80710

New contributor

mihaild is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered Apr 8 at 12:04

mihaildmihaild

80710