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.

Express the notion of a minimum of a set of number (where numbers are defined via sets). That is, define a relation Min(S,x) using logic and set-theoretic operations such that it is true whenever x is the minimum element in S.

  • I understand the definition of numbers in terms of sets. I did that in part a of this same question.
  • I understand what a function or relation is

    But I have no idea what this is asking, nor how to answer it.


Edit: My definition of a number is as follows:

0 = {}
$n+1 = n\cup \{n\}$

So :

  • 1 = {{}}
  • 2 = {{}, {{}}}
  • 3 = {{}, {{}}, {{}, {{}}}}
share|improve this question
1  
Can you include your answer for part (a) of this question? –  Benjamin Dickman Nov 4 '12 at 23:00
    
Try breaking it down into pieces: (1) How would you write '$x$ is a smaller number than $y$' as a logical expression involving sets? (2) How would you write '$x$ is the smallest number in the set $S$' as a logical expression involving the 'less-than' relation? Once you have those, all you need to do is piece them together. –  Steven Stadnicki Nov 4 '12 at 23:01
    
HINT: Have you noticed that by this definition $3=\{0,1,2\}$? –  Brian M. Scott Nov 4 '12 at 23:09
    
Is this an answer? $\forall y\in S(x\in y)$ –  agent154 Nov 4 '12 at 23:46
    
It’s almost part of one: it says that $x$ is less than each number in $S$. Unfortunately, this implies that $x\notin S$, which is not what you want. $\operatorname{Min}(x,S)\leftrightarrow x\in S\land \dots~$, where the missing part has to say in effect that for all $y\in S$, $x\le y$. –  Brian M. Scott Nov 4 '12 at 23:50

2 Answers 2

Hint:

You can notice either of the following observations:

  1. $n<m\iff n\in m$; and
  2. $n\leq m\iff n\subseteq m$.

Therefore if $S$ is a set of natural numbers, its minimum is the element which is either the member of everyone else; or a subset of everyone (including itself, of course).

share|improve this answer
up vote 0 down vote accepted

I'd like to thank Brian M. Scott above in the comments for helping me understand the problem and coax me to an answer.

As I understand it, the logic is as follows:

For a number to be the minimum number in a set of numbers, it must

  1. Be a member of the set, and
  2. Be a member of every other member of that set

For the first part, we have $$Min(S,x)\iff x\in S$$

For the second part, we have

$$Min(S,x)\iff \forall y\in S\{x\subseteq y\}$$

I've chosen $x\subseteq y$ instead of $x\in y\vee x=y$ because I like having less text, but both are equivalent. The reason why $x\subseteq y$ works is because x can legitimately be a subset of itself, but can only also be a subset of any natural number greater than it. So it'll return false only if there is a natural number less than x in the set S.

Putting 1 and 2 together now, we have:

$$Min(S,x)\iff x\in S\wedge \forall y\in S\{x\subseteq y\}$$

share|improve this answer

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.