数学代写|Math557 Mathematical logic

MY-ASSIGNMENTEXPERT™可以为您提供 mcgill.ca/study Math557 Mathematical logic数理逻辑的代写代考和辅导服务！

Math557课程简介

Offered by: Mathematics and Statistics (Faculty of Science)

Overview
Mathematics & Statistics (Sci) : Sampling theory (including large-sample theory). Likelihood functions and information matrices. Hypothesis testing, estimation theory. Regression and correlation theory.

Terms: Winter 2023

Instructors: Asgharian, Masoud (Winter)

Winter

Prerequisite: MATH 556

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

Prerequisites 

Mathematical logic emerged in the mid-19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal philosophical logic and mathematics.[3] “Mathematical logic, also called ‘logistic’, ‘symbolic logic’, the ‘algebra of logic’, and, more recently, simply ‘formal logic’, is the set of logical theories elaborated in the course of the last Nineteenth Century with the aid of an artificial notation and a rigorously deductive method.”[4] Before this emergence, logic was studied with rhetoric, with calculationes,[5] through the syllogism, and with philosophy. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.

Math557 Mathematical logic HELP（EXAM HELP， ONLINE TUTOR）

Let $L$ be the language consisting of the identity predicate, $I$, and one additional binary predicate, $R$. A graph $G$ is a normal $L$-structure satisfying the $L$-sentences $\forall x \forall y(R x y \Leftrightarrow R y x)$ and $\forall x \neg R x x$. Thus
$$
G=\left(U_G, R_G, I_G\right)
$$
where $U_G={$ vertices of $G}, R_G=\left{\langle u, v\rangle \in\left(U_G\right)^2: u\right.$ is adjacent to $\left.v\right}$, and $I_G=\left{\langle v, v\rangle: v \in U_G\right}$

A graph $G$ is said to be connected if for any pair of vertices $u, v$ in $G$ there exists a path from $u$ to $v$, i.e., a finite sequence of vertices $u=$ $v_0, v_1, \ldots, v_n=v$ such that for each $i<n, v_i$ is adjacent to $v_{i+1}$. Here $n$ is the length of the path. The distance between $u$ and $v$ is the minimum length of a path from $u$ to $v$, if such a path exists, and $\infty$ otherwise. The diameter of $G$ is the supremum of the distances between vertices of $G$.

We will construct $C_n$ recursively for each positive integer $n$.

First, let $C_1$ be the sentence that states that the graph has at least two vertices and one edge between them: $$C_1 = \exists x \exists y (x \neq y \land E(x,y) \land \forall z (z = x \lor z = y \lor \neg E(x,z)))$$

For $n > 1$, let $C_n$ be the sentence that states that the graph is connected and that there exist vertices $u$ and $v$ with distance at most $n$ between them. To express the latter condition, we will use a new predicate symbol $P_{n-1}(x,y)$ that holds if the distance between vertices $x$ and $y$ is at most $n-1$.

The sentence $C_n$ can then be defined as follows: $$C_n = C_{n-1} \land \exists u \exists v (u \neq v \land P_{n-1}(u,v) \land \forall w (w = u \lor w = v \lor \neg P_{n-1}(u,w) \lor \neg P_{n-1}(w,v)))$$

The first conjunct, $C_{n-1}$, ensures that the graph is connected of diameter at most $n-1$, and the second conjunct states that there exist two vertices $u$ and $v$ with distance at most $n-1$ between them, but with no shorter path between them. This implies that the diameter of the graph is exactly $n$.

To define the predicate symbol $P_{n-1}(x,y)$, we can use a recursive definition: $$P_0(x,y) = E(x,y)$$ $$P_k(x,y) = \exists z (P_{k-1}(x,z) \land P_{k-1}(z,y)) \qquad (k > 0)$$

The base case $P_0(x,y) = E(x,y)$ simply states that there is an edge between $x$ and $y$. The recursive case $P_k(x,y) = \exists z (P_{k-1}(x,z) \land P_{k-1}(z,y))$ states that there is a path of length $k$ between $x$ and $y$ if there is a vertex $z$ such that there is a path of length $k-1$ between $x$ and $z$ and a path of length $k-1$ between $z$ and $y$.

Therefore, the sentence $C_n$ ensures that a graph is connected and has diameter at most $n$ by checking that there exist two vertices with distance at most $n$ between them, but with no shorter path between them.

Assume that $S$ is a set of $L$-sentences such that there exist connected graphs of arbitrarily large finite diameter satisfying $S$. We want to show that there exists a non-connected graph satisfying $S$.

Suppose for the sake of contradiction that every graph satisfying $S$ is connected. Let $n$ be a positive integer such that every graph satisfying $S$ has diameter at most $n$. Let $G$ be a connected graph of diameter greater than $n$. Such a graph exists by assumption.

Since $G$ is connected, it satisfies $S$. However, $G$ has diameter greater than $n$, so it cannot satisfy the $L$-sentence $C_n$ from the previous question. This is a contradiction, since $C_n$ is an $L$-sentence that characterizes graphs with diameter at most $n$. Therefore, our assumption that every graph satisfying $S$ is connected must be false.

Thus, there exists a non-connected graph satisfying $S$.

MY-ASSIGNMENTEXPERT™可以为您提供UNIVERSITY OF ILLINOIS URBANA-CHAMPAIGN MATH2940 linear algebra线性代数课程的代写代考和辅导服务！ 请认准MY-ASSIGNMENTEXPERT™. MY-ASSIGNMENTEXPERT™为您的留学生涯保驾护航。