0

I have the following formula:

$(\exists x)(\forall y) r(x,y)$

Is this formula true in a model where r(x,y) is a binary predicate interpreted as "x is divisible by y" and the universe is all natural numbers except for zero? Why?

TKN
  • 757
  • Why would you think this is true? It's obviously false if we exclude $0$. But if we don't exclude $0$ it's not intuitively obvious (but easy) to see that $0$ would be the sole exception and only case where it could be true. – fleablood Feb 01 '20 at 17:41

1 Answers1

0

Why are you excluding $0$?

The statement is true for $0$ (because $x*0= 0$ is true for all $x$).

But for any $y\ne 0$ the statement, which is equivalent to state $\frac xy$ is an integer, is obviously false. What if $y > x$? Then if $x>0$ we have $0< \frac xy < 1$. What if $y = 2x$. The we have $\frac x{2x} = \frac 12$.

fleablood
  • 124,253
  • 3
    But if I understand it correctly, number zero is not divisible by all natural numbers (zero included in this case) since zero cannot be divided by zero, right? – TKN Feb 01 '20 at 17:42
  • 1
    Um...... I think divisibility means "There exists and integer $k$ so that $yk = x$" and not that that "$\frac xy$ is an integer". Algebraically $\frac xy$ means $x \cdot$ the multiplicative inverse of $y$ and doesn't really imply "dividing" $y$ into $x$. But you'll have to consult your text/teacher. I think it's save to say $0|0$ because $00 = 0$. but maybe you are correct. – fleablood Feb 01 '20 at 17:50
  • Also when you say "excluding 0" do you mean 1) there exist a number (that isn't zero) that is divisible by all numbers [definitely false] or 2) there exists a number that is divisible by all numbers (except zero) [true; that number is zero]? – fleablood Feb 01 '20 at 17:53
  • I mean an universe of discourse with all the natural numbers, meaning zero included/excluded. (there is not a consensus on that terminology so I explicitly state that just for sure) – TKN Feb 01 '20 at 17:55
  • 1
    Okay. If $\mathbb N = {1,2,3....}$ then the statement is false. If $\mathbb N={0,1,2,3.....}$ then the statement is true because $x0 = 0$ so $x|0$ for all $x$ and according to Niven&Zuckerman, for one, divisibility is defined as "there exists an $k$ so that $yk = x$ then $y|x$". As a consequence if $y\ne 0$ then $\frac xy$ is an integer. (And if $y=0$ then $x=0$... a trivial exception). – fleablood Feb 01 '20 at 18:01
  • Thank you for clarifying! – TKN Feb 01 '20 at 18:03
  • 1
    "I mean an universe of discourse with all the natural numbers, meaning zero included/excluded. " Ah.... well the statement is true if the universe includes $0$ and false if it doesn't. I figure you must have seen this in reference to a universe where $0$ was included. – fleablood Feb 01 '20 at 18:03