Fdtxjr

How to explain the utility of binomial logistic regression when the predictors are purely categorical

What difference does it make using sed with/without whitespaces?

Computationally populating tables with probability data

Is it correct to say moon starry nights?

What happened in Rome, when the western empire "fell"?

Why don't programming languages automatically manage the synchronous/asynchronous problem?

Traduction de « Life is a roller coaster »

Does the Idaho Potato Commission associate potato skins with healthy eating?

Yu-Gi-Oh cards in Python 3

Can someone explain this formula for calculating Manhattan distance?

Would a grinding machine be a simple and workable propulsion system for an interplanetary spacecraft?

When "be it" is at the beginning of a sentence, what kind of structure do you call it?

Is it ok to trim down a tube patch?

Can Sneak Attack be used when hitting with an improvised weapon?

Does destroying a Lich's phylactery destroy the soul within it?

Players Circumventing the limitations of Wish

Help/tips for a first time writer?

Help understanding this unsettling image of Titan, Epimetheus, and Saturn's rings?

Calculate the Mean mean of two numbers

In the "Harry Potter and the Order of the Phoenix" video game, what potion is used to sabotage Umbridge's speakers?

Would a completely good Muggle be able to use a wand?

Which one is the true statement?

Purpose of level-shifter with same in and out voltages

Can I board the first leg of the flight without having final country's visa?

Necessary and sufficient condition for existence of a partial order

1

1

$begingroup$

I'm trying to find a necessary and sufficient condition for the existence of a partial order such that an arbitrary relation on a set X is a subset of the partial order.

So far all I have is that since a partial order is reflexive, transitive, and symmetric, the partial order must only have elements related to themselves in order for any relation to be a subset of it, since the relation in question may be symmetric. Any help would be appreciated.

combinatorics relations order-theory

share|cite|improve this question

asked Mar 19 at 19:52

EJJJJEJJJJ

456

$endgroup$

add a comment | 

1

1

$begingroup$

I'm trying to find a necessary and sufficient condition for the existence of a partial order such that an arbitrary relation on a set X is a subset of the partial order.

So far all I have is that since a partial order is reflexive, transitive, and symmetric, the partial order must only have elements related to themselves in order for any relation to be a subset of it, since the relation in question may be symmetric. Any help would be appreciated.

combinatorics relations order-theory

share|cite|improve this question

asked Mar 19 at 19:52

EJJJJEJJJJ

456

$endgroup$

add a comment | 

$begingroup$

I'm trying to find a necessary and sufficient condition for the existence of a partial order such that an arbitrary relation on a set X is a subset of the partial order.

So far all I have is that since a partial order is reflexive, transitive, and symmetric, the partial order must only have elements related to themselves in order for any relation to be a subset of it, since the relation in question may be symmetric. Any help would be appreciated.

combinatorics relations order-theory

share|cite|improve this question

asked Mar 19 at 19:52

EJJJJEJJJJ

456

$endgroup$

share|cite|improve this question

asked Mar 19 at 19:52

EJJJJEJJJJ

456

share|cite|improve this question

asked Mar 19 at 19:52

EJJJJEJJJJ

456

asked Mar 19 at 19:52

EJJJJEJJJJ

456

asked Mar 19 at 19:52

EJJJJEJJJJ

456

2 Answers
2

active

oldest

votes

1

$begingroup$

$R$ is a subset of a partial order if and only if for all lists $x_1,x_2,dots,x_n$ of elements in $R$, we have
$$
x_1defR,R,R x_2R x_3Rdots R x_nR x_1implies x_1=x_2=dots=x_n
$$

In graph theory terms, $R$ must be acyclic. This is a generalization of $R$ being anti-symmetric, which says that $x_1R x_2R x_1implies x_1=x_2$.

If $R$ is a subset of a partial order $le$, then $x_1defR,R,R x_2R x_3Rdots R x_nR x_1$ would imply $x_1le x_2le dotsle x_nle x_1$, which combined with transitivity and anti-symmetry implies all $x_i$ are equal.

Conversely, if that condition holds, then let $le$ be the transitive closure of $R$, where $xle y$ if there is a chain $xR z_1R z_2 RdotsR z_k R y$. Then $le$ is easily shown to be transitive (connect the chains), and the given condition allows you to show anti-symmetry.

share|cite|improve this answer

answered Mar 20 at 17:46

Mike EarnestMike Earnest

26.3k22151

$endgroup$

add a comment | 

0

$begingroup$

Assume R is a relation for S.

A necessary condition for R to be a subset of an order for S is:

there does not exist distinct x,y with xRy and yRx.

A sufficient condition for R to be a subset of an order for S is;

there does not exist distinct x,y with xTy and yTx,

where T is the reflexive and transitive closure of R.

share|cite|improve this answer

answered Mar 20 at 2:22

William ElliotWilliam Elliot

8,9232820

$endgroup$

add a comment | 

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%2f3154522%2fnecessary-and-sufficient-condition-for-existence-of-a-partial-order%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

$R$ is a subset of a partial order if and only if for all lists $x_1,x_2,dots,x_n$ of elements in $R$, we have
$$
x_1defR,R,R x_2R x_3Rdots R x_nR x_1implies x_1=x_2=dots=x_n
$$

In graph theory terms, $R$ must be acyclic. This is a generalization of $R$ being anti-symmetric, which says that $x_1R x_2R x_1implies x_1=x_2$.

If $R$ is a subset of a partial order $le$, then $x_1defR,R,R x_2R x_3Rdots R x_nR x_1$ would imply $x_1le x_2le dotsle x_nle x_1$, which combined with transitivity and anti-symmetry implies all $x_i$ are equal.

Conversely, if that condition holds, then let $le$ be the transitive closure of $R$, where $xle y$ if there is a chain $xR z_1R z_2 RdotsR z_k R y$. Then $le$ is easily shown to be transitive (connect the chains), and the given condition allows you to show anti-symmetry.

share|cite|improve this answer

answered Mar 20 at 17:46

Mike EarnestMike Earnest

26.3k22151

$endgroup$

add a comment | 

1

$begingroup$

$R$ is a subset of a partial order if and only if for all lists $x_1,x_2,dots,x_n$ of elements in $R$, we have
$$
x_1defR,R,R x_2R x_3Rdots R x_nR x_1implies x_1=x_2=dots=x_n
$$

In graph theory terms, $R$ must be acyclic. This is a generalization of $R$ being anti-symmetric, which says that $x_1R x_2R x_1implies x_1=x_2$.

If $R$ is a subset of a partial order $le$, then $x_1defR,R,R x_2R x_3Rdots R x_nR x_1$ would imply $x_1le x_2le dotsle x_nle x_1$, which combined with transitivity and anti-symmetry implies all $x_i$ are equal.

Conversely, if that condition holds, then let $le$ be the transitive closure of $R$, where $xle y$ if there is a chain $xR z_1R z_2 RdotsR z_k R y$. Then $le$ is easily shown to be transitive (connect the chains), and the given condition allows you to show anti-symmetry.

share|cite|improve this answer

answered Mar 20 at 17:46

Mike EarnestMike Earnest

26.3k22151

$endgroup$

add a comment | 

$begingroup$

$R$ is a subset of a partial order if and only if for all lists $x_1,x_2,dots,x_n$ of elements in $R$, we have
$$
x_1defR,R,R x_2R x_3Rdots R x_nR x_1implies x_1=x_2=dots=x_n
$$

In graph theory terms, $R$ must be acyclic. This is a generalization of $R$ being anti-symmetric, which says that $x_1R x_2R x_1implies x_1=x_2$.

If $R$ is a subset of a partial order $le$, then $x_1defR,R,R x_2R x_3Rdots R x_nR x_1$ would imply $x_1le x_2le dotsle x_nle x_1$, which combined with transitivity and anti-symmetry implies all $x_i$ are equal.

Conversely, if that condition holds, then let $le$ be the transitive closure of $R$, where $xle y$ if there is a chain $xR z_1R z_2 RdotsR z_k R y$. Then $le$ is easily shown to be transitive (connect the chains), and the given condition allows you to show anti-symmetry.

share|cite|improve this answer

answered Mar 20 at 17:46

Mike EarnestMike Earnest

26.3k22151

$endgroup$

share|cite|improve this answer

answered Mar 20 at 17:46

Mike EarnestMike Earnest

26.3k22151

answered Mar 20 at 17:46

Mike EarnestMike Earnest

26.3k22151

answered Mar 20 at 17:46

Mike EarnestMike Earnest

26.3k22151

0

$begingroup$

Assume R is a relation for S.

A necessary condition for R to be a subset of an order for S is:

there does not exist distinct x,y with xRy and yRx.

A sufficient condition for R to be a subset of an order for S is;

there does not exist distinct x,y with xTy and yTx,

where T is the reflexive and transitive closure of R.

share|cite|improve this answer

answered Mar 20 at 2:22

William ElliotWilliam Elliot

8,9232820

$endgroup$

add a comment | 

0

$begingroup$

Assume R is a relation for S.

A necessary condition for R to be a subset of an order for S is:

there does not exist distinct x,y with xRy and yRx.

A sufficient condition for R to be a subset of an order for S is;

there does not exist distinct x,y with xTy and yTx,

where T is the reflexive and transitive closure of R.

share|cite|improve this answer

answered Mar 20 at 2:22

William ElliotWilliam Elliot

8,9232820

$endgroup$

add a comment | 

$begingroup$

Assume R is a relation for S.

A necessary condition for R to be a subset of an order for S is:

there does not exist distinct x,y with xRy and yRx.

A sufficient condition for R to be a subset of an order for S is;

there does not exist distinct x,y with xTy and yTx,

where T is the reflexive and transitive closure of R.

share|cite|improve this answer

answered Mar 20 at 2:22

William ElliotWilliam Elliot

8,9232820

$endgroup$

share|cite|improve this answer

answered Mar 20 at 2:22

William ElliotWilliam Elliot

8,9232820

answered Mar 20 at 2:22

William ElliotWilliam Elliot

8,9232820

answered Mar 20 at 2:22

William ElliotWilliam Elliot

8,9232820