Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $D(x) = \{y \in \mathbb N : y\text{ is a divisor of } x\}$ and let the relation $\Sigma$ be defined as follows:

$$\begin{aligned}x \Sigma y \Leftrightarrow D(x) \subseteq D(y) \end{aligned}$$

check $\Sigma$ is a partial order, if it is total and determine $\min(\mathbb N, \Sigma)$ and $\max(\mathbb N, \Sigma)$.

In order to prove $\Sigma$ to be a partial order I need to gain proof of its reflexivity, anti-simmetry and transitivity, so:

Reflexivity

$x \Sigma x \Leftrightarrow D(x) \subseteq D(x)$

$\{x\in \mathbb N : x \text{ is a divisor of } x\} \subseteq \{x\in \mathbb N : x \text{ is a divisor of } x\}$

Anti-symmetry

$x \Sigma y \land y\Sigma x \Rightarrow x= y$

$\{y \in \mathbb N : y \text{ is a divisor of } x\} \land \{x \in \mathbb N : x \text{ is a divisor of } y\}$

for the fundamental theorem of arithmetic $x = y$

Transitivity

$x \Sigma y \land y\Sigma z \Rightarrow x \Sigma z$

$\{y\in \mathbb N : y \text{ is a divisor of } x\} \land \{z \in \mathbb N : z \text{ is a divisor of } y\} \Rightarrow \{z \in \mathbb N : z \text{ is a divisor of } x\}$.

I should prove if $\Sigma$ is a total order, but I have no idea how I could do that, can it involve the fact that element $0 \in \mathbb N$ doesn't belong to this relation because $x\Sigma 0$ would mean $\{0 \text{ is a divisor of } x\}$ which is not possible? And my gut feeling tells me that $\max(\mathbb N, \Sigma) = 1$ and $\nexists\min(\mathbb N, \Sigma)$ but I don't know if I am right. Will you please give me a nudge in the right direction?

share|improve this question
1  
There are some errors in your arguing above: Reflexivity: $D(x)$ equals (by definition) $\{y \in \mathbb N : y \mid x\}$ (where $|$ means "is a divisor of") and not $\{x \in \mathbb N : x \mid x\} (= \mathbb N)$. Anti-Symmetry: What do you mean with a conjuction of sets? I'm sure you wanted to write $\{z \in \mathbb N : z \mid x\} = \{z \in \mathbb N : z \mid y\}$ (and so $x = y$ by the FTA). Transitivity: Again: What is a conjuction of sets? What does it mean that a set is implied by others? –  martini Jul 12 '12 at 9:03
    
@martini yes, I should have written $D(x)=\{y \in \mathbb N : y \mid x\}$! In regard to the misuse of $\land$ I thought it would connect two propositions so what I meant (paraphrasing from the ani-symmetry section) is "if $y \in \mathbb N$ are divisors of $x$ and $x \in \mathbb N$ are divisors of $y$ then...". My teacher has used this kind of notation in class so maybe I've wrongly assumed it is correct. –  haunted85 Jul 12 '12 at 9:48
    
BTW $x\Sigma y$ is equivalent to $x\mid y$, which is very frequently given as an example of a partial ordering, see e.g. Divides is Partial Ordering on Positive Integers at ProofWiki. –  Martin Sleziak Jul 12 '12 at 9:48
add comment

2 Answers

up vote 2 down vote accepted

For $\Sigma$ to be a total order every two elements need to be comparable.

However $D(2)=\{1,2\}$ and $D(3)=\{1,3\}$ so neither is a subset of the other. Therefore $\lnot(2\Sigma3\lor 3\Sigma2)$ and so this is not a total order.

For $\min$ and $\max$, as you noted every number is a divisor of $0$; while no number except $1$ is a divisor of $1$, so $D(1)=\{1\}$ and $D(0)=\mathbb N$. It remains to show that $1\Sigma x$ for all $x$, but $1$ divides every number so it holds.

share|improve this answer
add comment

To elaborate a little more on martini's comment:

  • Reflexivity: $D(x)\subseteq D(x)$ is obvious. ($A\subseteq A$ holds for any sets.)

  • Anti-symmetry: $D(x)\subseteq D(y) \land D(y)\subseteq D(x)$ implies $D(y)=D(x)$. It remains to check that if $D(x)=D(y)$ implies $x=y$ (for non-negative integers).

  • Transitivity: $D(x)\subseteq D(y)$ and $D(y)\subseteq D(z)$ imply $D(x)\subseteq D(z)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.