1
vote
3answers
86 views

Can a statement in FOL be equivalent to two separate independent statements?

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
1
vote
1answer
85 views

Arrows-only implication & disjunction in $\mathbf{Set}.$

Just before the truth-arrows in a topos subsection of Goldblatt's "Topoi: A Categorial Analysis of logic," descriptions of the truth functions $\Rightarrow$ and $\smallsmile$ are given in ...
4
votes
4answers
352 views

The standard role of intuitive numbers in the foundations of mathematics

In my career I've been formed mostly in the formal side of mathematics, that is, standard set theory and every classical branch of mathematics that uses set theory. However, I am not quite sure about ...
1
vote
2answers
96 views

Abstract Objects in Logic

I am confused on the concept of extensionality versus intensionality. When we say 2<3 is True, we say that 2<3 can be demonstrated by a mathematical proof. So, according to mathematical logic, ...
4
votes
3answers
247 views

P entails Q implies P

I have been looking at the following: P entails Q implies P And developed the proof as follows: ...
4
votes
4answers
97 views

Can't see the intuition behind the validity of this formula: $\exists x(\exists yP(x,y) → \forall z \exists wP(z,w))$

I know that $$\vdash_{\mathcal G}\exists x(\exists yP(x,y) → \forall z \exists wP(z,w))$$ (I have read and done a syntactic proof of this.) And therefore also $$\models \exists x(\exists yP(x,y) → ...
9
votes
1answer
139 views

A graph of all of mathematics

In mathematics, one often makes (proves) statements on the basis of: Previously proven statements Axioms I like to think of these dependencies as a directed graph, with edges from the accepted ...
1
vote
3answers
65 views

Show that “$\Gamma \models S \Rightarrow \Gamma \vdash S$” entails “if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable”

Show that "$\Gamma \models S \Rightarrow \Gamma \vdash S$" entails "if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable" I'm primarily confused with the notation being used here. In ...
4
votes
1answer
84 views

What is the intuition behind $\Delta_1^0$ sets and $\Delta_1^1$ sets?

In the context of first-order arithmetic, if $\phi$ is a formula with only bounded quantifiers, then if you put existential quantifiers in front it becomes a $\Sigma_1^0$ formula according to the ...
2
votes
3answers
38 views

Clarification on the definition of logical conjunction

First of all, I have never studied Logic seriously before. I am reading this article on Wikipedia. The definition is the following: Logical conjunction is an operation on two logical values, ...
2
votes
1answer
71 views

Equality and order in sets

Just started Baby Rudin and got struck in this. While defining order in sets, $<$ was introduced as a relation and for a set to be ordered the condition was: for all $x,y$ belonging to an ordered ...
5
votes
1answer
294 views

Intuition for Absorption and Distributive Laws in Elementary Logic

$P ∧ (Q ∨ R) \equiv (P ∧ Q) ∨ (P ∧ R) \tag{Distributive Law 1}$ $P ∨ (Q ∧ R) \equiv (P ∨ Q) ∧ (P ∨ R) \tag{Distributive Law 2}$ $P ∨ (P ∧ Q) \equiv P \tag{Absorption Law 1}$ $P ∧ (P ∨ Q) ...
1
vote
2answers
153 views

Why does it make sense to pair existence and uniqueness?

Edit. September 8th, 2013. I've added another another section to the question, which should hopefully constrain its scope. Please see below the horizontal line!! Lets write the statement 'there is at ...
3
votes
3answers
166 views

Are statements like “Every time I've done X, Y has happened” (vacuously) true if I've never done X?

I've recently been wondering about vacuous truths. I know a statement like "I've never been beaten in a race" is true if I've never been in a race, but what I'm wondering is if the following ...
6
votes
7answers
349 views

Intuition behind “If P then Q” = “Q or Not P ”

I understand with truth tables the Conditional Law: $[P \Longrightarrow Q] \equiv [\lnot P \vee Q]$. However, what's the intuition or a natural motivation? Source 1, all but intuitive, now appears as ...
18
votes
4answers
376 views

Associativity of $\iff$

In this answer, user18921 wrote that the $\iff$ operation is associative, in the sense that $(A\iff B)\iff C$ $A\iff (B\iff C)$ are equivalent statements. One can brute-force a proof fairly ...
1
vote
3answers
516 views

About NOT elimination/introduction and RAA rules on Natural Deduction

Can somebody explain the $\neg$-elimination rule in natural deduction?. Searching on books and the web, I found different definitions for it. For example, in my logic I course, the rule is: $A, ...
0
votes
2answers
54 views

Constraint satisfaction problem - Arc consistency

The Constraint satisfaction problem (CSP) is roughly speaking a formalism that defines a finite set of relations over a domain. The relations are simply defined by enlisting elements in certain ...
4
votes
4answers
382 views

the role of logic in math and education

My question is somewhat related to this discussion: Is Mathematics one big tautology? I have a computer science background and I have always approached math from the logic point of view ...
10
votes
5answers
747 views

Why König's lemma isn't “obvious”?

I keep facing König's lemma "Every finitely branching infinite tree over $\mathbb{N}$ has infinite branch". Why it is not taken "obvious" but needs a careful proof? It seems somewhat obvious, but I ...
5
votes
2answers
221 views

Intuition behind the Axiom of Choice

Why is it different to make one choice or many choices than to make infinite choices from a theoretical point of view in which indeed you are not going to do any? How could that be different from ...
2
votes
1answer
83 views

Maths branch of logics or vice versa?

Is it logics a branch of maths or vice versa? From a the point of view of the definition of a logical system, logics is a 'calculus' which has axioms and rules as any branch of maths. However it ...
0
votes
2answers
79 views

Non-isomorphic structures with equal cardinality

Let $\mathfrak{A}=(\mathbb{N},S,0)$ be a structure where $S$ is the sucessor function. Let $\mathfrak{B} =(\mathbb{N}\times \{0\} \cup \mathbb{Z} \times\{1\} ,S, 0)$ with $0 = (0,0)$ and $$ S(k,i) ...
16
votes
4answers
752 views

How did the ancients view *infinitesimals*?

With some category/topos theory we can now put infinitesimals on a rigorous ground, as in Bell's A Primer of Infinitesimal Analysis, where the author introduces $\epsilon$ satisfying \begin{equation} ...
4
votes
2answers
217 views

why does soundness seem to be less important than consistency for the structuralist?

If I am not wrong, many mathematicians (I believe this is not only restricted to structuralists) agree that an inconsistent formal system does not have any model. By model I mean some kind of set ...
2
votes
1answer
235 views

Free boolean algebra

Consider the following definition: Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X ...
1
vote
1answer
223 views

Confusion about proof that first order logic without equality is not contradictory

I am having a problem understanding a proof from the field of mathematical logic. Seems like my brain cannot digest concepts from logic very well. I will quickly define some terminology and then ...
4
votes
3answers
230 views

Theories and models

I apologize if my question is not well formed. The reason for it is that I don't understand the concepts enough to be able to ask a completely meaningful question. In the classes we said that a ...
3
votes
1answer
151 views

A Formal and Precise treatment of Simplification?

I am looking to gain a deeper understanding of, and increase my own skill in "Mathematical Simplification". But I've been finding the concept overly vague and haven't been able to find any good ...
5
votes
3answers
290 views

$\wedge,\cap$ and $\vee,\cup$ between Logic and Set Theory always interchangeable?

In "$\wedge,\cap,\times$ and $\vee,\cup,+$ are always interchangeable?" It has been shown that arithmetic shouldn't be included. So the new modified question is: The analogy of $\wedge,\cap$ and ...
5
votes
2answers
195 views

$\wedge,\cap,\times$ and $\vee,\cup,+$ are always interchangeable?

Update : Should have left the Arithmetic out of this question, the new modified question is posted here : $\wedge,\cap$ and $\vee,\cup$ between Logic and Set Theory always interchangeable? ...
2
votes
2answers
290 views

Propositional Logic Proof of $\vdash \lnot (p \supset q) \supset (p \land \lnot q)$

$\vdash \lnot (p \supset q) \supset (p \land \lnot q)$ I need to prove the above proposition via intuitionistic logic rules and/or natural logic rules. I guess it is not possible to prove with ...
2
votes
0answers
228 views

Statements about logic (=“metalogic”(??)) [closed]

Sometimes there are statements about logic e.g. "That's not logical" and I can neither prove nor disprove a statement about logic with no definition for logic itself. It's just a negation and it's ...
9
votes
3answers
923 views

What is the intuition behind the “par” operator in linear logic?

I'm $\DeclareMathOperator{\par}{\unicode{8523}}$ trying to wrap my mind around the $\par$ ("par") operator of linear logic. The other connectives have simple resource interpretations ($A\otimes B$ ...
3
votes
3answers
145 views

“Contradiction-free” in logic vs. “Contradiction-free” in plain mathematics

In our course we have defined a theory $T$ to be contradiction-free, if there are no formulas $\alpha_1,\ldots \alpha_n\in T$ such that $\neg ( \alpha_1 \& \ldots \ \& \alpha_n )$ is provable ...
2
votes
3answers
200 views

A question on logic - where intuition can fail

Suppose I have two predicates $P(x)$ and $Q(x)$, such that $\overline{P(x)\wedge Q(x)}$ holds for all $x$. Now, if $\displaystyle \bigwedge_{x\in A}P(x)$ for a set $A$, it must be certainly true, ...
13
votes
7answers
1k views

Why in an inconsistent axiom system every statement is true? (For Dummies)

I would like to know if someone can explain in a somehow down to earth (almost logic free) way why is it true that in an axiom system where there is some statement $P$ such that $P$ and its negation ...