1
$\begingroup$

I'm new to the Math stack exchange community so my apologies in advance in making mistakes for putting my question into non-fitting categories and such.

Ultimate Question: When are you supposed to use n-ary predicate statements for proving any sort of proof-based questions? (In my context, any of the three inductions) In case there may be any confusion due to many different theories and notation for predicate logic n-ary as in... i.e. P(x, y) or P(x, y, z) or n-ary P(x_0, x_1, ... , x_n-1)

Sub-Question #1: I thought about this question myself and came up with sub-question like what the difference is between the two following predicates and I was not able to find the answer what the difference is searched online however no really specific and detailed answer but here it is:

Sub-Question #2: Does every variable that is used in the predicate sentence need to be bounded by a quantifier?

Consider, the two following question:

  1. Prove that for all natural numbers $n, k*n \ge n$ for any natural number $k \ge 2.$

I thought of two predicates and two separate claims that I have made for the above question as follows:

Define a set $S =\{s \in \mathbb {N}\}.$

Also, define set $Y = \{y \in \mathbb {N} \; | \; y\ge 2\}.$

Predicate and Claim #1

Define the predicate $P:S \rightarrow \{True, False\}$

and is defined as $P(n): "k*n \ge n"$

Claim #1: $ \forall \; n\in S, P(n)$ holds.

NOTE: The bounded variable in the predicate would be $n$ and the free variable would be the $k$ because it is not bounded by some quantifier. So a natural question to ask is, do I have to/neccessary to bound the free variable $k$ in proving this question?

Claim #2: $ \forall \; n \in S , \forall \; k \in Y, P(n)$ holds.

Predicate and Claim #2

Define the predicate $P: (S \times S) \rightarrow \{True, False\}$

and is defined as $P(n, k): \; "k*n \ge n"$

Claim: $\forall n \in S, \; \forall k \in Y, \; P(n, k)$ holds.

Sub-Question #3: (I just thought of this question while writing this post...) If I have some arbitrary predicate statement (and ONLY THE predicate statement) $P(n)$, is the $n$ considered to be a free variable?

So out all the this attempts are any of them correct and if not can anyone provide with a proper rigorously defined predicate for the above question? Also, it will be very appreciated if someone can point out what basic background I might lack in to have this problem and also suggest any sort of textbooks or any online material that can possibly help me strengthen my knowledge in this field! I personally find that defining a predicate is the basis of learning how to rigorously prove any mathematical or non-mathematical statements.

Thank you so much in advance! :)

EDIT #1: Thank you for both of your answers but I did not state explicitly what the question I had in my mind. (My apologies, it was quite late last night wasn't able to think very straight)

I want to ask what the difference between my Claim #1 and Claim #2 and the difference between both of the two predicates that I defined. From my perspective the only difference I can spot in the predicate is the very explicit view which is my first predicate is unary and second predicate is binary BUT do not understand what the mathematical difference is.

$\endgroup$
23
  • $\begingroup$ In claim #1 we have $k$ a constant term. Otherwise it is not well formed. In claim #2 $k$ is bounded because of the quantifier, so the claim is well formed predicate. For the statement $P(n)$, $n$ is free if and only if $n$ is not bounded to any quantifier, those terms are called quantifier free, and it is depends on the domain if this is well formed. Important note free variable, $n$, doesn't not implies $n$ is not bounded. For the ultimate question, n-ary is used if you have $n$ different variables, there may be how many constant terms in there, they may or may not be bounded or free $\endgroup$
    – ℋolo
    Apr 17 '18 at 5:50
  • $\begingroup$ Thank you but I was not clear enough so if you can kindly read my edit of the post will be appreciated! $\endgroup$
    – javacoder
    Apr 17 '18 at 16:06
  • $\begingroup$ #1: $k$ is a constant in the language. #2: $k$ is bounded variable. In Both cases $n$ is bounded variable. It is important to see that $k$ in $P$(I'm talking about #1) is not a free variable because unless you specific the language we are in. In which case $k$ is either a constant or a free variable $\endgroup$
    – ℋolo
    Apr 17 '18 at 16:17
  • $\begingroup$ So the difference is that $k$ is a constant in #1 and $k$ is a bounded variable in #2, so what is the difference between the two and how and why would we treat them differently later on in the proof (of the question)? So what language are you talking about specifically to make the variable $K$ either a constant or a free variable in fact even bounded? From my knowledge, I think the variable $k$ would be bounded if it is quantified but not sure when a variable is a free variable or a constant... And what would be the difference between the free variable and a constant? $\endgroup$
    – javacoder
    Apr 17 '18 at 16:38
  • $\begingroup$ What did you also mean by "well-formed"? Also, then what would make the difference between my first unary predicate and the binary predicate? Sorry for so many questions... this is a concept I've been wondering and none of my professors at school are capable of answering these questions unfortunately. $\endgroup$
    – javacoder
    Apr 17 '18 at 16:40
1
$\begingroup$

We have that :

"for all natural numbers $n, k n ≥ n$ for any natural number $k ≥ 2$"

is:

$\forall n \forall k \ (k \ge 2 \to kn \ge n)$.

Thus, both variables $n$ and $k$ are (universally) quantified.

We assume that the domain is $\mathbb N$ : thus we can omit the "specification" : $\in \mathbb N$.

If we want to set-up a typical inductive proof, we can consider the binary predicate $P(n,k) := kn \ge n$ and apply induction on $k$ :

(i) Basis : $k=2$.

We have that $2n = n+n \ge n$.

(ii) Induction step : assume that the property holds for $k \ge 2$ and prove for $k+1$.

If $k+1 \ge 2$ (and thus $k \ge 1$, ensuring that $kn \ne 0$), we have that $(k+1)n=kn+n \ge n+n \ge n$.

In conclusion, we have $P(n,2) \text{ and } \forall k (k \ge 2 \to (P(n,k) \to P(n,k+1)))$. Thus, we can apply induction to conclude with:

$\forall k \ (k \ge 2 \to P(n,k))$.

But the result holds for $n$ whatever; thus we can generalize it to:

$\forall n \ \forall k \ (k \ge 2 \to kn \ge n)$.

$\endgroup$
3
  • $\begingroup$ Thank you but I was not clear enough so if you can kindly read my edit of the post will be appreciated! $\endgroup$
    – javacoder
    Apr 17 '18 at 16:06
  • $\begingroup$ For your above set-up of the proof that you gave you would have to apply induction twice for $k$ and $n$ right? $\endgroup$
    – javacoder
    Apr 17 '18 at 16:28
  • $\begingroup$ @javacoder - Yes and no; both steps ultimately rely on the fact that $n+n \ge n$. In foraml arithmetic we usually define $m \ge n \text { iff } \exists k (m=n+k)$; if so, from $n+n=n+n$ we have imemdiately yields : $n + n \ge n$. But of course induction will work: $n+0 \ge n$ by axiom and so on. $\endgroup$ Apr 18 '18 at 5:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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