0
$\begingroup$

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 = {{}, {{}}, {{}, {{}}}}
  • 1
    Can you include your answer for part (a) of this question?2012-11-04
  • 0
    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.2012-11-04
  • 0
    HINT: Have you noticed that by this definition $3=\{0,1,2\}$?2012-11-04
  • 0
    Is this an answer? $\forall y\in S(x\in y)$2012-11-04
  • 0
    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$.2012-11-04
  • 0
    $\forall y\in S(x\in y\wedge x\in S)$2012-11-04
  • 0
    That statement is self-contradictory: it implies that $x\in x$, which violates one of the axioms of set theory. I’ll give you another push: $$\operatorname{Min}(x,S)\leftrightarrow x\in S\land\forall y\in S(x\in y\lor\dots)\;.$$ Now replace the dots by a very simple statement. Remember, you want $x\le y$ for all $y\in S$, **not** $x.2012-11-05
  • 0
    Last try $$Min(x,S)\leftrightarrow x\in S\wedge \forall y\in S(x\in y\vee x=y)$$ If this is true, I have to ask why it's true... This assignment is due on Wednesday and I'm not doing so well in the class.2012-11-05
  • 0
    (I only just saw this: if you want it brought to my attention, you have to put `@Brian` somewhere in the comment.) Yes, now you’ve got it. To say that $x$ is the minimum element of $S$ you must say first that $x\in S$, which you’ve done, and then that $x$ is minimal. That means that $x$ is less than or equal to everything in $S$. Thus, for each $y\in S$, you want either $x, which means $x\in y$, or $x=y$. In some of your earlier attempts you were forgetting to allow for the $x=y$ possibility.2012-11-05

2 Answers 2

0

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\}$$

1

Hint:

You can notice either of the following observations:

  1. $n; 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).