What is the minimum size of the set and minimum power of a strict relation that can be used for a base case...

0

$begingroup$

Consider the strict order binary relation $xRy$ over the set $A$ with the following properties:

irreflexive $forall x in A neg (xRx$)

asymmetric $forall xy in A (xRy Rightarrow neg yRx)$

transitive $forall xyz in A (xRy land yRz Rightarrow xRz)$

Non Empty Set $A neq emptyset$

Non Empty Relation $R neq emptyset$

What is minimum size of the set $A$ over which the relation $R$ is defined?

I need to know the minimum size/power to use as a base case in an inductive proof of a strict order.

Here is my attempt to find the smallest set and relation with these properties.
Examining $leftvert{A}rightvert$ for values 1,2, and 3.

$leftvert{A}rightvert=1, A={a}$ and there is only possible relation is $R={(a,a)}$ which is not irreflexive

$leftvert{A}rightvert=2, A={a,b}$ and there are only two mutually exclusive possible relations $R={(a,b)}$ or $R={(b,a)}$ each of which gives a relation that is asymmetric, vacuously irreflexive and vacuously transitivity. It has power $R^1$

$leftvert{A}rightvert=3, A={a,b,c}$ then $R={(a,b),(b,c),(a,c)}$ which is asymmetric, irreflexive and transitivity

It seems to me $leftvert{A}rightvert=3$ is the only case where true (as opposed vacuous) transitivity holds. It has power $R^2$ or ($R circ R$). $xRy$ is intended to formally represent a relation IsOnTopOf where one object is physically placed on top of another. Which base case is best suited to this situation? I am not sure whether or not I can use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof

proof-writing relations

share|cite|improve this question

edited Jan 27 at 19:47

Patrick Browne

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There doesn't seem to be a question here. You've shown that the minimum size is $2$, but for some reason you don't like that, so you give an answer of size $3$. What is it that you want to know?
  $endgroup$
  – saulspatz
  Apr 12 '18 at 19:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I was was not sure whether or not I could use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof. Thanks for the clarification.
  $endgroup$
  – Patrick Browne
  Apr 12 '18 at 22:19
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Ah, I understand now. Just let me reiterate. People use a vacuous argument to establish the base for an induction all the time, and it's perfectly legitimate. All that matters is that you prove the base is true. How you prove it is up to you.
  $endgroup$
  – saulspatz
  Apr 12 '18 at 22:22
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  You have not assumed trichotomy so if $A$ has at least $2$ members $a,b$ you can let $R={(a,b)},$ regardless of whether $A$ has any other members.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 8:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Trichotomy is not implied by the other properties. For a familiar example, let $A=Bbb N$ and let $xRy$ iff $x$ is a proper divisor of $y$.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 18:55
  

  
  
  
  

 | 
show 1 more comment

0

$begingroup$

Consider the strict order binary relation $xRy$ over the set $A$ with the following properties:

irreflexive $forall x in A neg (xRx$)

asymmetric $forall xy in A (xRy Rightarrow neg yRx)$

transitive $forall xyz in A (xRy land yRz Rightarrow xRz)$

Non Empty Set $A neq emptyset$

Non Empty Relation $R neq emptyset$

What is minimum size of the set $A$ over which the relation $R$ is defined?

I need to know the minimum size/power to use as a base case in an inductive proof of a strict order.

Here is my attempt to find the smallest set and relation with these properties.
Examining $leftvert{A}rightvert$ for values 1,2, and 3.

$leftvert{A}rightvert=1, A={a}$ and there is only possible relation is $R={(a,a)}$ which is not irreflexive

$leftvert{A}rightvert=2, A={a,b}$ and there are only two mutually exclusive possible relations $R={(a,b)}$ or $R={(b,a)}$ each of which gives a relation that is asymmetric, vacuously irreflexive and vacuously transitivity. It has power $R^1$

$leftvert{A}rightvert=3, A={a,b,c}$ then $R={(a,b),(b,c),(a,c)}$ which is asymmetric, irreflexive and transitivity

It seems to me $leftvert{A}rightvert=3$ is the only case where true (as opposed vacuous) transitivity holds. It has power $R^2$ or ($R circ R$). $xRy$ is intended to formally represent a relation IsOnTopOf where one object is physically placed on top of another. Which base case is best suited to this situation? I am not sure whether or not I can use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof

proof-writing relations

share|cite|improve this question

edited Jan 27 at 19:47

Patrick Browne

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There doesn't seem to be a question here. You've shown that the minimum size is $2$, but for some reason you don't like that, so you give an answer of size $3$. What is it that you want to know?
  $endgroup$
  – saulspatz
  Apr 12 '18 at 19:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I was was not sure whether or not I could use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof. Thanks for the clarification.
  $endgroup$
  – Patrick Browne
  Apr 12 '18 at 22:19
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Ah, I understand now. Just let me reiterate. People use a vacuous argument to establish the base for an induction all the time, and it's perfectly legitimate. All that matters is that you prove the base is true. How you prove it is up to you.
  $endgroup$
  – saulspatz
  Apr 12 '18 at 22:22
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  You have not assumed trichotomy so if $A$ has at least $2$ members $a,b$ you can let $R={(a,b)},$ regardless of whether $A$ has any other members.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 8:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Trichotomy is not implied by the other properties. For a familiar example, let $A=Bbb N$ and let $xRy$ iff $x$ is a proper divisor of $y$.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 18:55
  

  
  
  
  

 | 
show 1 more comment

0

0

0

$begingroup$

Consider the strict order binary relation $xRy$ over the set $A$ with the following properties:

irreflexive $forall x in A neg (xRx$)

asymmetric $forall xy in A (xRy Rightarrow neg yRx)$

transitive $forall xyz in A (xRy land yRz Rightarrow xRz)$

Non Empty Set $A neq emptyset$

Non Empty Relation $R neq emptyset$

What is minimum size of the set $A$ over which the relation $R$ is defined?

I need to know the minimum size/power to use as a base case in an inductive proof of a strict order.

Here is my attempt to find the smallest set and relation with these properties.
Examining $leftvert{A}rightvert$ for values 1,2, and 3.

$leftvert{A}rightvert=1, A={a}$ and there is only possible relation is $R={(a,a)}$ which is not irreflexive

$leftvert{A}rightvert=2, A={a,b}$ and there are only two mutually exclusive possible relations $R={(a,b)}$ or $R={(b,a)}$ each of which gives a relation that is asymmetric, vacuously irreflexive and vacuously transitivity. It has power $R^1$

$leftvert{A}rightvert=3, A={a,b,c}$ then $R={(a,b),(b,c),(a,c)}$ which is asymmetric, irreflexive and transitivity

It seems to me $leftvert{A}rightvert=3$ is the only case where true (as opposed vacuous) transitivity holds. It has power $R^2$ or ($R circ R$). $xRy$ is intended to formally represent a relation IsOnTopOf where one object is physically placed on top of another. Which base case is best suited to this situation? I am not sure whether or not I can use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof

proof-writing relations

share|cite|improve this question

edited Jan 27 at 19:47

Patrick Browne

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

$endgroup$

Consider the strict order binary relation $xRy$ over the set $A$ with the following properties:

irreflexive $forall x in A neg (xRx$)

asymmetric $forall xy in A (xRy Rightarrow neg yRx)$

transitive $forall xyz in A (xRy land yRz Rightarrow xRz)$

Non Empty Set $A neq emptyset$

Non Empty Relation $R neq emptyset$

What is minimum size of the set $A$ over which the relation $R$ is defined?

I need to know the minimum size/power to use as a base case in an inductive proof of a strict order.

Here is my attempt to find the smallest set and relation with these properties.
Examining $leftvert{A}rightvert$ for values 1,2, and 3.

$leftvert{A}rightvert=1, A={a}$ and there is only possible relation is $R={(a,a)}$ which is not irreflexive

$leftvert{A}rightvert=2, A={a,b}$ and there are only two mutually exclusive possible relations $R={(a,b)}$ or $R={(b,a)}$ each of which gives a relation that is asymmetric, vacuously irreflexive and vacuously transitivity. It has power $R^1$

$leftvert{A}rightvert=3, A={a,b,c}$ then $R={(a,b),(b,c),(a,c)}$ which is asymmetric, irreflexive and transitivity

It seems to me $leftvert{A}rightvert=3$ is the only case where true (as opposed vacuous) transitivity holds. It has power $R^2$ or ($R circ R$). $xRy$ is intended to formally represent a relation IsOnTopOf where one object is physically placed on top of another. Which base case is best suited to this situation? I am not sure whether or not I can use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof

proof-writing relations

proof-writing relations

share|cite|improve this question

edited Jan 27 at 19:47

Patrick Browne

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

share|cite|improve this question

edited Jan 27 at 19:47

Patrick Browne

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

share|cite|improve this question

share|cite|improve this question

edited Jan 27 at 19:47

Patrick Browne

edited Jan 27 at 19:47

Patrick Browne

edited Jan 27 at 19:47

Patrick Browne

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

asked Apr 12 '18 at 19:07

Patrick BrownePatrick Browne

578

578

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There doesn't seem to be a question here. You've shown that the minimum size is $2$, but for some reason you don't like that, so you give an answer of size $3$. What is it that you want to know?
  $endgroup$
  – saulspatz
  Apr 12 '18 at 19:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I was was not sure whether or not I could use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof. Thanks for the clarification.
  $endgroup$
  – Patrick Browne
  Apr 12 '18 at 22:19
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Ah, I understand now. Just let me reiterate. People use a vacuous argument to establish the base for an induction all the time, and it's perfectly legitimate. All that matters is that you prove the base is true. How you prove it is up to you.
  $endgroup$
  – saulspatz
  Apr 12 '18 at 22:22
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  You have not assumed trichotomy so if $A$ has at least $2$ members $a,b$ you can let $R={(a,b)},$ regardless of whether $A$ has any other members.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 8:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Trichotomy is not implied by the other properties. For a familiar example, let $A=Bbb N$ and let $xRy$ iff $x$ is a proper divisor of $y$.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 18:55
  

  
  
  
  

 | 
show 1 more comment

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There doesn't seem to be a question here. You've shown that the minimum size is $2$, but for some reason you don't like that, so you give an answer of size $3$. What is it that you want to know?
  $endgroup$
  – saulspatz
  Apr 12 '18 at 19:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I was was not sure whether or not I could use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof. Thanks for the clarification.
  $endgroup$
  – Patrick Browne
  Apr 12 '18 at 22:19
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Ah, I understand now. Just let me reiterate. People use a vacuous argument to establish the base for an induction all the time, and it's perfectly legitimate. All that matters is that you prove the base is true. How you prove it is up to you.
  $endgroup$
  – saulspatz
  Apr 12 '18 at 22:22
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  You have not assumed trichotomy so if $A$ has at least $2$ members $a,b$ you can let $R={(a,b)},$ regardless of whether $A$ has any other members.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 8:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Trichotomy is not implied by the other properties. For a familiar example, let $A=Bbb N$ and let $xRy$ iff $x$ is a proper divisor of $y$.
  $endgroup$
  – DanielWainfleet
  Apr 14 '18 at 18:55
  

  
  
  
  

1

1

$begingroup$
There doesn't seem to be a question here. You've shown that the minimum size is $2$, but for some reason you don't like that, so you give an answer of size $3$. What is it that you want to know?
$endgroup$
– saulspatz
Apr 12 '18 at 19:18

$begingroup$
There doesn't seem to be a question here. You've shown that the minimum size is $2$, but for some reason you don't like that, so you give an answer of size $3$. What is it that you want to know?
$endgroup$
– saulspatz
Apr 12 '18 at 19:18

$begingroup$
I was was not sure whether or not I could use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof. Thanks for the clarification.
$endgroup$
– Patrick Browne
Apr 12 '18 at 22:19

$begingroup$
I was was not sure whether or not I could use the vacuously irreflexive and vacuously transitivity as a base case for an inductive proof. Thanks for the clarification.
$endgroup$
– Patrick Browne
Apr 12 '18 at 22:19

1

1

$begingroup$
Ah, I understand now. Just let me reiterate. People use a vacuous argument to establish the base for an induction all the time, and it's perfectly legitimate. All that matters is that you prove the base is true. How you prove it is up to you.
$endgroup$
– saulspatz
Apr 12 '18 at 22:22

$begingroup$
Ah, I understand now. Just let me reiterate. People use a vacuous argument to establish the base for an induction all the time, and it's perfectly legitimate. All that matters is that you prove the base is true. How you prove it is up to you.
$endgroup$
– saulspatz
Apr 12 '18 at 22:22

1

1

$begingroup$
You have not assumed trichotomy so if $A$ has at least $2$ members $a,b$ you can let $R={(a,b)},$ regardless of whether $A$ has any other members.
$endgroup$
– DanielWainfleet
Apr 14 '18 at 8:29

$begingroup$
You have not assumed trichotomy so if $A$ has at least $2$ members $a,b$ you can let $R={(a,b)},$ regardless of whether $A$ has any other members.
$endgroup$
– DanielWainfleet
Apr 14 '18 at 8:29

1

1

$begingroup$
Trichotomy is not implied by the other properties. For a familiar example, let $A=Bbb N$ and let $xRy$ iff $x$ is a proper divisor of $y$.
$endgroup$
– DanielWainfleet
Apr 14 '18 at 18:55

$begingroup$
Trichotomy is not implied by the other properties. For a familiar example, let $A=Bbb N$ and let $xRy$ iff $x$ is a proper divisor of $y$.
$endgroup$
– DanielWainfleet
Apr 14 '18 at 18:55

 | 
show 1 more comment

0

active

oldest

votes

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
});


}
});

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

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%2f2734400%2fwhat-is-the-minimum-size-of-the-set-and-minimum-power-of-a-strict-relation-that%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

0

active

oldest

votes

0

active

oldest

votes

active

oldest

votes

active

oldest

votes

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

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%2f2734400%2fwhat-is-the-minimum-size-of-the-set-and-minimum-power-of-a-strict-relation-that%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

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

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

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

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

This page is only for reference, If you need detailed information, please check here