Discrete Mathematics Notation
I am having difficulty understanding the notation of discrete math.
Here (x | y) means “x evenly divides y” i.e. divides without a remainder.
∃S ⊆ Nat: (∀y ∈ S : (∀x ∈ Nat : (x | y ) ⇒ (x = y) ∨ (x = 1))))Can someone explain this equation to me in english?
$\endgroup$3 Answers
$\begingroup$There exists a subset $S$ of the set of natural numbers $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ (or not containing $0$, depending on your definition) such that whenever $y \in S$ and $x$ is any natural number that's a divisor of $y$, then $x = 1$ or $x = y$.
That is, if you choose an element $y$ of $S$ and a divisor $x$ of $y$, then $x$ is either $1$ or $y$.
In particular, this implies that $S$ is a set consisting only of prime numbers or $1$.
$\endgroup$ 2 $\begingroup$There exists a subset $S$ of the naturals such that for all elements $y$ in $S$ with the property that for all $x$ in the naturals with the property that $x$ evenly divides $y$ then $x$ is equal to $y$ or $x$ is equal to one.
Basically, You define a set $S$ in the naturals where every element in the subset has this property. Does this make sense?
$\endgroup$ $\begingroup$It's saying there is a set of natural numbers [∃S ⊆ Nat] that has the property that for every number y in S [∀y ∈ S], every divisor of x [(x | y)] is either y itself, or 1 [(x = y) ∨ (x = 1)]. You can probably guess that S is the set of prime numbers, and 1.
To get the composites, you can negate the inner phrase to get
∃S ⊆ Nat: (∀y ∈ S : (~∀x ∈ Nat : (x | y) ⇒ (x = y) ∨ (x = 1))))
which is equivalent by De Morgan's Law to
∃S ⊆ Nat: (∀y ∈ S : (∃x ∈ Nat : (x | y) ⇏ (x = y) ∨ (x = 1))))
which is in turn equivalent to
∃S ⊆ Nat: (∀y ∈ S : (∃x ∈ Nat : (x ≠ 1) ⋀ (x ≠ y) ⋀ (x | y))))
In English, this means there is a set where each member x has a divisor other than 1 or x, i.e the composites.
$\endgroup$
