Ygtjki

How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?

Alignment of six matrices

"Oh no!" in Latin

PTIJ: Which Dr. Seuss books should one obtain?

How to test the sharpness of a knife?

Why does the Persian emissary display a string of crowned skulls?

Does Doodling or Improvising on the Piano Have Any Benefits?

Mimic lecturing on blackboard, facing audience

Sound waves in different octaves

What is the meaning of "You've never met a graph you didn't like?"

Can I cause damage to electrical appliances by unplugging them when they are turned on?

How were servants to the Kaiser of Imperial Germany treated and where may I find more information on them

The Digit Triangles

If the only attacker is removed from combat, is a creature still counted as having attacked this turn?

How much do grades matter for a future academia position?

Would this string work as string?

Why is participating in the European Parliamentary elections used as a threat?

Should I warn new/prospective PhD Student that supervisor is terrible?

Would a primitive species be able to learn English from reading books alone?

Ways of geometrical multiplication

Is there a distance limit for minecart tracks?

Did I make a mistake by ccing email to boss to others?

Are Captain Marvel's powers affected by Thanos breaking the Tesseract and claiming the stone?

What should be the ideal length of sentences in a blog post for ease of reading?

Can we expand “induction principle” to a partial order $(X, leq)$?

Induction on Real NumbersExistence of a well-ordered set with a special elementExamples of proofs by induction with respect to relations that are not strict total orders.Common Binary Relation that is not a partial orderMathematical structures with a canonical partial orderCan a partially ordered set always be partitioned by its chains?Are these partial order or total orders?Given a partial order $R$ on the set $A$, prove that there exists a total order $leq$ on $A$ such that $R subseteq le$Higher order partial orderPartially Ordered Set and Equivalence RelationshipCan mathematical induction be applied on any total order set?

3

1

$begingroup$

We know that every infinite can be made well-ordered with an unknown order.
Also we can expand the induction principle on any infinite set in
the sense that
it can made well ordered.
Now partially ordered set may not be a well ordered set with respect
to the partial order.
Let a partially ordered set $(X, leq)$ with respect to this particular
order $'leq'$ and suppose that this partial order $'leq '$ does not make the
set $X$ well-ordered.

My question is-

Can we expand "induction principle" to the partially order set $(X,leq)$ keeping
in mind that $(X,leq)$ is not well ordered?

I have great confusion here.

elementary-set-theory order-theory

share|cite|improve this question

edited 16 hours ago

user21820

39.7k543157

asked 21 hours ago

M. A. SARKARM. A. SARKAR

2,3971819

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
  $endgroup$
  – Marc van Leeuwen
  17 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MarcvanLeeuwen, I did not get you. Can you elaborate it?
  $endgroup$
  – M. A. SARKAR
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
  $endgroup$
  – Marc van Leeuwen
  1 hour ago
  

  
  
  
  

add a comment | 

3

1

$begingroup$

We know that every infinite can be made well-ordered with an unknown order.
Also we can expand the induction principle on any infinite set in
the sense that
it can made well ordered.
Now partially ordered set may not be a well ordered set with respect
to the partial order.
Let a partially ordered set $(X, leq)$ with respect to this particular
order $'leq'$ and suppose that this partial order $'leq '$ does not make the
set $X$ well-ordered.

My question is-

Can we expand "induction principle" to the partially order set $(X,leq)$ keeping
in mind that $(X,leq)$ is not well ordered?

I have great confusion here.

elementary-set-theory order-theory

share|cite|improve this question

edited 16 hours ago

user21820

39.7k543157

asked 21 hours ago

M. A. SARKARM. A. SARKAR

2,3971819

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Supposing the answer were "yes", why do you think one would have stated the principle for well-orders in the first place? Definitions and hypotheses usually have a reason.
  $endgroup$
  – Marc van Leeuwen
  17 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MarcvanLeeuwen, I did not get you. Can you elaborate it?
  $endgroup$
  – M. A. SARKAR
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For comparison, if the law says that you may drive car provided you have a valid driver's licence, and you ask whether more generally people can legally drive when they have no driver's licence, then you can expect a negative answer. If the answer were "yes", what would be the point of a driver's licence in the first place ?
  $endgroup$
  – Marc van Leeuwen
  1 hour ago
  

  
  
  
  

add a comment | 

$begingroup$

We know that every infinite can be made well-ordered with an unknown order.
Also we can expand the induction principle on any infinite set in
the sense that
it can made well ordered.
Now partially ordered set may not be a well ordered set with respect
to the partial order.
Let a partially ordered set $(X, leq)$ with respect to this particular
order $'leq'$ and suppose that this partial order $'leq '$ does not make the
set $X$ well-ordered.

My question is-

Can we expand "induction principle" to the partially order set $(X,leq)$ keeping
in mind that $(X,leq)$ is not well ordered?

I have great confusion here.

elementary-set-theory order-theory

share|cite|improve this question

edited 16 hours ago

user21820

39.7k543157

asked 21 hours ago

M. A. SARKARM. A. SARKAR

2,3971819

$endgroup$

share|cite|improve this question

edited 16 hours ago

user21820

39.7k543157

asked 21 hours ago

M. A. SARKARM. A. SARKAR

2,3971819

share|cite|improve this question

edited 16 hours ago

user21820

39.7k543157

asked 21 hours ago

M. A. SARKARM. A. SARKAR

2,3971819

edited 16 hours ago

user21820

39.7k543157

edited 16 hours ago

user21820

39.7k543157

asked 21 hours ago

M. A. SARKARM. A. SARKAR

2,3971819

asked 21 hours ago

M. A. SARKARM. A. SARKAR

2,3971819

2 Answers
2

active

oldest

votes

3

$begingroup$

We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.

One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.

share|cite|improve this answer

edited 16 hours ago

answered 21 hours ago

ArthurArthur

119k7118202

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
  $endgroup$
  – user647486
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @user, my question is for arbitrary poset
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
  $endgroup$
  – Peter LeFanu Lumsdaine
  17 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
  $endgroup$
  – Arthur
  16 hours ago
  
  

  
  
  
  

 | 
show 3 more comments

10

$begingroup$

Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.

For total orders, being well-founded is equivalent to being well-ordered.

Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).

share|cite|improve this answer

answered 21 hours ago

Daniel AhlsénDaniel Ahlsén

3165

New contributor

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

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So on totally ordered set , we can do induction
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
  $endgroup$
  – Daniel Ahlsén
  20 hours ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

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%2f3155166%2fcan-we-expand-induction-principle-to-a-partial-order-x-leq%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.

One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.

share|cite|improve this answer

edited 16 hours ago

answered 21 hours ago

ArthurArthur

119k7118202

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
  $endgroup$
  – user647486
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @user, my question is for arbitrary poset
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
  $endgroup$
  – Peter LeFanu Lumsdaine
  17 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
  $endgroup$
  – Arthur
  16 hours ago
  
  

  
  
  
  

 | 
show 3 more comments

3

$begingroup$

We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.

One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.

share|cite|improve this answer

edited 16 hours ago

answered 21 hours ago

ArthurArthur

119k7118202

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It is nice. I am talking that relation $rho$ which makes $X$ poset but well-ordered. Can we have induction on $X$ with respect to $rho$ ?
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Arthur You can do some inductions in some totally ordered sets that are not well-ordered. For example, on the reals. Therefore, your first and second sentences are false. The third sentence is also false, since you can also do induction in well-founded sets, which might not be totaly ordered.
  $endgroup$
  – user647486
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @user, my question is for arbitrary poset
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user647486: you can do induction on any set, if you are allowed to choose your own definition of “doing induction”. The “induction on real numbers” you link is a very nice principle, but it isn’t the most standard sense of “doing induction”, which (as this answer correctly says) fails over the reals and other non-well-founded orderings. The only shortcoming in this answer is its suggestion that well-foundedness and induction for partial orders are something novel or speculative — in fact they’re long-established and well-studied.
  $endgroup$
  – Peter LeFanu Lumsdaine
  17 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user647486 "no difference between the statement of induction on the reals and strong induction" seems a bit much. I agree that one can do induction-like arguments on the reals under certain conditions, but I think it's a bit of a stretch to say it's the same as conventional induction.
  $endgroup$
  – Arthur
  16 hours ago
  
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

We can't even do induction on a total order if it's not well-ordered. Like on $Bbb Q$ or $Bbb R$ with the standard order. So in general a partial order is out of the question.

One could impose a well-ordering-like requirement on the partial order (every non-empty subset of $X$ has a minimal element), and then it is called a well-founded partial order. In that case one can indeed induct on a partial order.

share|cite|improve this answer

edited 16 hours ago

answered 21 hours ago

ArthurArthur

119k7118202

$endgroup$

share|cite|improve this answer

edited 16 hours ago

answered 21 hours ago

ArthurArthur

119k7118202

answered 21 hours ago

ArthurArthur

119k7118202

answered 21 hours ago

ArthurArthur

119k7118202

10

$begingroup$

Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.

For total orders, being well-founded is equivalent to being well-ordered.

Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).

share|cite|improve this answer

answered 21 hours ago

Daniel AhlsénDaniel Ahlsén

3165

New contributor

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

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So on totally ordered set , we can do induction
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
  $endgroup$
  – Daniel Ahlsén
  20 hours ago
  

  
  
  
  

add a comment | 

10

$begingroup$

Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.

For total orders, being well-founded is equivalent to being well-ordered.

Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).

share|cite|improve this answer

answered 21 hours ago

Daniel AhlsénDaniel Ahlsén

3165

New contributor

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

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So on totally ordered set , we can do induction
  $endgroup$
  – M. A. SARKAR
  21 hours ago
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  No, not in general, since not all total orders are well-founded. The standard order on the integers is one example. Well-foundedness is equivalent to well-orderedness for total orders.
  $endgroup$
  – Daniel Ahlsén
  20 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Induction can be performed over any relation $R$ over a set $X$, provided the relation is well-founded: any subset $S subseteq X$ must have a minimal element with respect to $R$. A minimal element of $S$ is an element $m in S$ such that there is no $x in S$ with $x R m$.

For total orders, being well-founded is equivalent to being well-ordered.

Note: Assuming the axiom of dependent choice (a weaker form of the axiom of choice), one can show that a relation is well-founded if and only if there is no infinite descending chain of elements in $X$ (with respect to the relation $R$).

share|cite|improve this answer

answered 21 hours ago

Daniel AhlsénDaniel Ahlsén

3165

New contributor

Daniel Ahlsén 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 21 hours ago

Daniel AhlsénDaniel Ahlsén

3165

New contributor

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

answered 21 hours ago

Daniel AhlsénDaniel Ahlsén

3165

New contributor

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

answered 21 hours ago

Daniel AhlsénDaniel Ahlsén

3165