Tag: .999
Logic on Math StackExchange
- Maximum cardinality of a collection of sets of integers with pairwise finite intersections [duplicate] December 9, 2024Let $\mathcal{C}$ be a collection of subsets of $\mathbb{N}$ such that any two distinct $U,V\in\mathcal{C}$ have finite intersection $U\cap V$. Then what can be said about the cardinality of $\mathcal{C}$? I have a construction showing $|\mathcal{C}|=\aleph_1$ is possible, but I don’t know if $|\mathcal{C}|=|\mathbb{R}|$ is possible. My construction uses transfinite recursion and the axiom of […]SmileyCraft
- Is there a syntactic "higher-up" to derivations? December 9, 2024The question is likely to be illposed, but I was wondering whether there was some known syntactic "higher-up" to the notion of derivation of semi-exoteric use. By this I mean: when working in $\mathsf{PA}$, we make use of digitalization so as to encode finite structures such as: lists, trees, and —on the syntactic side of […]Sho
- "You cannot engage in argument unless you rely on the principle of non-contradiction" December 9, 2024A very good SEoP article "Aristotle on Non-contradiction" by Paula Gottlieb makes two interesting claims, one after the other: Claim 1: "Anyone asking for a deductive argument for PNC [the principle of non-contradiction], as Aristotle points out, is missing the point, or, rather, is asking for something that is impossible without using PNC." Claim 2. […]logiclearner
- Why does "p⊃q" instead of "q⊃p" mean "if p then q"? [closed] December 9, 2024The “if-then” sentence is called a conditional and will be symbolized as (p ⊃ q). The part to the left of the horseshoe is called the antecedent (what comes before), and the part to the right of the horseshoe is called the consequent (what comes after). So why does "p⊃q" instead of "q⊃p" mean "if […]陈海斌
- Do we need not need truth values to describe models in predicate logic? December 8, 2024I am reading Kirby's Model theory. In section 3.3, the following definition of interpretation is given: $\textbf{Definition 3.4 (Interpretation of formulas)}$ Let $\varphi$ be a formula of $L$ and $\bar{x} = (x_1, \dots, x_n)$ a list of variables containing every free variable of $\varphi$. We also write $\varphi(\bar{x})$ for the formula with the list of […]Brian
- Can proof by contradiction be used disprove a statement? December 8, 2024I'm currently taking an introductory proofs class. The textbook that we are using justifies proof by contradiction by stating that the statement $P$ is logically equivalent to the statement $(\neg P\implies(Q\land\neg Q)).$ The logic makes sense to me when we use the proof technique conventionally as follows: assume that $\neg P$ is true and then […]Learning Math
- Show law of excluded middle is valid December 7, 2024Example 1.12 from David Marker's An Invitation to Mathematical Logic (p. 10) shows $(\phi \vee \neg \phi)$ (that is, the law of excluded middle (LEM)) is valid in finitary model-theoretic FOL: For any $\mathcal{L}$-structure $\mathcal{M}$ and any assignment $\sigma: V \rightarrow M$, $$\mathcal{M} \models_\sigma \neg \phi \Leftrightarrow \mathcal{M} \not\models_\sigma \phi $$ Thus $\mathcal{M} \models \phi$ […]silly-little-guy
- How do you construct a While loop using propositional dynamic logic? December 7, 2024I am learning some modal logic from a textbook (Modal Logic from Blackburn, De Rijke and Venema) and they have an example about propositional dynamic logic (PDL). Here they explain that if $\pi$ is a program, then $\pi^*$ is also a program, and $\pi^*$ is an iteration of $\pi$ for a finite (possibly zero) number […]UnrulyTank
- Proof of Deduction Theorem in Hilbert-Calculus, Beginner friendly December 7, 2024Deduction Theorem: Let $ \Sigma$ be an axiom system, and let $ \psi, \varphi$ be $ L$-formulas. Then the following always holds: $ \Sigma, \psi \vdash \varphi \iff \Sigma \vdash \psi \rightarrow \varphi $ “$ \Rightarrow$” We prove by strong induction on the length of a proof $ n \geq 1$ that for arbitrary $ […]God
- Proof of the General Deduction Theorem December 6, 2024Theorem: For all axiom systems $\Sigma$ and all formulas $\varphi, \psi_1, \ldots, \psi_n$, it holds that: $ \Sigma, \psi_1, \ldots, \psi_n \vdash \varphi \iff \Sigma \vdash \psi_1 \to \ldots \to \psi_n \to \varphi$ Proof: $\Rightarrow$: We prove by complete induction. Initially, that is, for $n = 1$, it holds: Let $\Sigma, \psi_1 \vdash \varphi$, and […]God
Recent Comments