Math Genius: n-ary generalizations of De Morgan’s Laws

Original Source Link

$a)$ State the n-ary generalizations of De Morgan’s Laws.

$b)$ Pick one of these generalizations and prove it by induction.

What does this even mean… I know what de morgan’s laws are but I have never heard of the $n$-ary generalizations.

de Morgan’s Laws express the negation duality between bivariate operators $lor$ and $land$. $$lnot(p_1land p_2)=lnot p_1lorlnot p_2\lnot(p_1lor p_2)=lnot p_1landlnot p_2$$

The n-ary extension of these Laws states that this duality also holds for n-tuple series of these operators.
$$lnotbigwedge_{k=1}^n p_k=bigvee_{k=1}^n lnot p_k\lnotbigvee_{k=1}^n p_k=bigwedge_{k=1}^n lnot p_k$$

Where $displaystyle{smallbigwedge_{k=1}^n} p_k = p_1wedge p_2wedge p_3wedgecdotswedge p_n$ and such.


Now it clearly the expressions shall hold for $n=1$.$$bigwedge_{k=1}^1 p_k=p_1qquad,qquadbigvee_{k=1}^1p_k=p_1qquad,qquad lnot(p_1)=lnot p_1$$

Also the expressions hold for $n=2$ because the 2-ary expressions are deMorgan’s laws.

Now you must prove that if they hold for any positive natural number $n$, they shall hold for its successor, $n+1$.
$$forall ninBbb N^+~left(left(lnotbigwedge_{k=1}^n p_k=bigvee_{k=1}^n lnot p_kright)toleft(lnotbigwedge_{k=1}^{n+1} p_k=bigvee_{k=1}^{n+1} lnot p_kright)right)\forall ninBbb N^+~left(left(lnotbigvee_{k=1}^n p_k=bigwedge_{k=1}^n lnot p_kright)toleft(lnotbigvee_{k=1}^{n+1} p_k=bigwedge_{k=1}^{n+1} lnot p_kright)right)$$

Tagged : / / / /

Math Genius: Doubt – Negation of “all” [duplicate]

Original Source Link

I am a high schooler just reading logic when this doubt popped up
Let’s take a statement
All balls are black.
Then the negation should be-
Some balls are not black.
But why can’t it be-
All balls are not black.

Because to prove that “All balls are black” is a lie, it is sufficient to find just one that isn’t. I don’t need to prove that every single ball is a colour other than black to disprove the assertion.

Furthermore, “All balls are not black” is not the negation of “All balls are black” because what if only half the balls are black? Then neither the statement nor its negation is true. That kind of logic isn’t very useful.

You can always use the method of interpretations to show that the given argument is invalid.

Render “It’s not the case that all balls are black” as $neg(forall x)(Bxrightarrow Cx)$, and “All balls are not black” as $(forall x)(Bxrightarrowneg Cx)$. Now we want to show that the latter formula is not a logical consequence of the former. Consider the set of all human beings, interpret $Bx$ as $x$ is a girl and $Cx$ as $x$ is blonde. Interpretation of the first formula says that it’s not the case that all girls are blonde which is true, and the second one that all girls are not blonde, which is false. So we have true antecedent and false conclusion meaning that the latter doesn’t follow from the former.

Unfortunately, “All X are not Y” is ambiguous in common English usage. It could mean “Not all X are Y”, or it could mean “No X are Y”.

Tagged : /

Linux HowTo: Curious tautological pattern on“p->p”

Original Source Link

I found something that boggles me ( I’m really a beginner in symbolic logic, so maybe it’s very trivial).

I was practicing with truth-tables, and I found that:

  1. “p->p” is a tautology

  2. “(p->p)->p” is not a tautology.

I decided to go further, and:

  1. “((p->p)->p)->p” is again a tautology, but

4.”(((p->p)->p)->p)-> p” is not, and it keeps alternating.

I checked with an online logic calculator, and it seems correct.

Now, do you know why is that? Is there any particular reason for this pattern?

Cheers

1) For any formula $p$, $p to p$ is a tautology.
2) For any tautology $T$, $T to p$ is logically equivalent to $p$. (Check it out with a truth table.)

So an even amount of occurrences of $p$ will give you tautologies (by 1)); appending another $p$ will give you something that behaves like p (by 2)). And if you take that $p$-equivalent proposition and append another $p$, you will, by 1), get the tautology again, etc.

The core answer to your question lies in 2).

I love @lemontree’s explanation (and @Manx’s terser version of the same point). It may be useful to see the point in a different way, though:

$(p rightarrow p) rightarrow p$ is equivalent to $neg (neg p lor p) lor p$, which by one of De Morgan’s laws is equivalent to $(neg neg p ,&, neg p) lor p$.

That last expression is equivalent to $(p ,&, neg p) lor p$.

The left disjunct of that expression is a contradiction, though; it’s always false, so the truth value of the whole expression is the same as the truth value of $p$.

lemontree’s answer shows that you can apply this conclusion to understand the longer expressions.

For example, $((p rightarrow p) rightarrow p) rightarrow p$ embeds the original 3-$p$ expression on the left side of the arrow, and we saw that that was equivalent to $p$, so the whole expression is equivalent to $p rightarrow p$.

Tagged : /

Math Genius: Why is a deductive closure an intersection of maximally consistent sets?

Original Source Link

Full Question:
Show that if $Delta(Gamma)$ is the deductive closure of a consistent $Gamma$ then $Delta(Gamma)$ is the intersection of all maximal consistent sets of formulas $Lambda$ with $Gamma subseteq Lambda$.

I’m really stuck with this question, I honestly don’t know how to even start. Can someone please provide some assistance?

You have two things to prove: (1) that $Delta(Gamma)$ is a subset of any maximal consistent superset of $Gamma$; (2) that if $phi notin Delta(Gamma)$ then there is a maximal consistent superset of $Gamma$ that does not contain $phi$.

For (1), if $chi in Delta(Gamma)$ and $Lambda$ is a consistent superset of $Gamma$, then so is $Lambda cup {chi}$. So if $Lambda$ is a maximal consistent superset, then $chi in Lambda$.

For (2), use Zorn’s lemma: consider the set $cal C$ of all consistent supersets of $Gamma$ that do not contain $phi$. There is at least one member of $cal C$, namely $Gamma$ itself. The union of a chain of elements of $cal C$ is also a member of $cal C$, so by Zorn’s lemma $cal C$ has a maximal element.

Tagged : /

Math Genius: First Order Logic: How to transform to prenex conjunctive normal form and Skolem form?

Original Source Link

This is the sentence that needs to be transformed: ∃x∀y(Ax → (Bxy ∨ ¬Cy)) → ∀x∃y(Py → Qyx)
I have gotten to the point where I eliminated all occurrences of → and imported all negations inside all other logical connectives. Which lead me here:

∃x∀y(Ax ∧ ¬Bxy ∧ Cy) ∨ ∀x∃y(Py ∧¬ Qyx)

But I can’t seem to pull the quantifiers in front.

I can’t seem to pull the quantifiers in front.

To pull out the quantifiers, we will need to apply some quantifier distributive laws such that
$$∀x(Px)∨∀x(Q)↔∀x(Px∨Q)tag{1}$$
$$∃y(Py)∨∃y(Qy)↔∃y(Py∨Qy)tag{2}$$
Then we start from
begin{align}
&forall xexists y(Axlandneg Bxyland Cy)lorforall xexists y(neg Py lor Qyx)\
=&forall x_1forall x_2(exists y(Ax_1landneg Bx_1yland Cy)lorexists y(neg Py lor Qyx_2))tag*{By $(1)$}\
=&forall x_1forall x_2exists y((Ax_1landneg Bx_1yland Cy)lor(neg Py lor Qyx_2))tag*{By $(2)$}\
end{align}

Now you can put them into conjunctive normal form.


Note : As @user400188 mentioned, to avoid unnecessary confusion, we could just replace $(1)$ with
$$forall x_1(Px_1)lorforall x_2(Qx_2)leftrightarrow forall x_1forall x_2(Px_1lor Qx_2)$$ or equivalently we can also apply the original $(1)$ twice.

Tagged : / / / /

Math Genius: Rigor behind choice of index for Cauchy squence in bounded function space.

Original Source Link

We have a Cauchy sequence in the normed space of bounded functions $(f_n)_n subset B(Omega, mathbb{K})$. I have shown that $(f_n(omega))_n$ is a Cauchy squence for all $omega in Omega$. What’s the rigor behind being able to choose a natural number $N in mathbb{N}$ such that
$$|f_n(omega)- f_m(omega)| le |f_n- f_m|_{infty} < varepsilon text{, for all } omegain Omega text{ and } n,m ge N.$$

I mean, why exists $N = max_{omega in Omega}{N_{omega}}$ for $Omega$ arbitrary, where $N_{omega}$ is the corresponding Cauchy index for $(f_n(omega))_n$? I have a common foundation in logic.

I don’t understand what you mean with $N_omega$. As I understood, the task is to show that such a $N_omega$ exists.

So, let $omega in Omega$ be arbitrary and $varepsilon>0$. As the sequence $(f_n)_{n in mathbb{N}}$ is Cauchy (is suspect with the supremum norm, as it is the ”reasonable” one on the space of bounded functions) there exists $N in mathbb{N}$ such that

$$
|f_n-f_m|_infty<varepsilon
$$

for all $n,mgeq N$. As by definition of the supremum we have $|f_n(omega)-f_m(omega)|leq|f_n-f_m|_infty$ we get that also

$$
|f_n(omega)-f_m(omega)|<varepsilon
$$

holds for all $n,mgeq N$.

This shows that we can choose the same $N$ for all $omega$.

Tagged : / /

Math Genius: Proof of ⊨∃x(Px⇒∀xPx) (Drinker’s Paradox) [duplicate]

Original Source Link

⊨∃x(Px⇒∀xPx)
I was trying to solve the above drinker’s paradox by contradiction and came up with the below expression by negating the above expression –

⊨ ∀x ( Px ∧ ¬ ∀x Px )

This is where I got stuck because to distribute the universal quantifier I need all the variables inside the parenthesis to be bound variables but as x is a free variable I was not able to go further.
Is the approach correct considering that the universal set is not empty and what should I do next?

In your approach, you have not given an equivalent expression, but rather the negation of the expression.

You can however equivalenty write it as $models exists x (neg Px lor forall y Py)$

It should be quite clear why this is true. Just read it out. “There is an $x$ such that either $Px$ is false, or $Px$ is true for all $x$. This is evident by just considering the two cases of when $Px$ is true for all $x$ and when it is not.

Tagged : /

Math Genius: Investigate the validity of the argument

Original Source Link

If Tom wears a mask, then he will not be affected by COVID 19.
If Tom does not stay at home, then he will wear a mask.
But he has affected by COVID 19.
Therefore he must have stayed at home.

The problem with this reasoning is that “he will not be affected by COVID-19” is referring to the future, while “he has [been] affected by COVID-19” is referring to the past. These are not the same thing.

Tagged : /

Math Genius: Mathematical object described irrespective of a foundational system?

Original Source Link

Is there a mathematical discipline that studies mathematical objects based on their behavior rather than their encoding?

I ask because a group is classically defined as a set with a binary operation and a handful of axioms. But I am learning type theory, and I am able to define a group as a type with a binary function and some constraints. The set theoretic and type theoretic formulations have different encodings, and yet I still believe I am working with the same mathematical object despite different foundational systems.

Is category theory or some other discipline capable of abstracting away the details of how an object like a group is encoded and instead define them on the basis of behavior that should be encoding-irrelevant?

I would argue that type theory is precisely such a discipline, that is we can view type theory as a language designed to manipulate certain types of objects independently of their encoding.

Let me be precise in what I mean by encoding here. To do mathematics we in any case need a foundational system. That is a system which tells us how to construct valid mathematical objects in a consistent manner. Set theory does this very well, because it allows us to define objects of just about any complexity. Let us call set theory System S. Let me be very explicit and remark that in System S with an appropriate set theoretic universe $U$, we usually define the set of monoids (for simplicity) as the set

$$text{Mon}_S := {xin U | exists m,starintext{fun}(mtimes m,m),1in m. x = langle m,langle star,1rangleranglewedge phi(m,star,1)}$$

where $phi(m,star,1)$ ensures the identity and associativity axioms $mathcal A$.

In particular, I prefer to think of the operations $text{fun}(cdot,cdot)$,$langlecdot,cdotrangle$ and $cdottimescdot$ as nothing but macros with the expansions
begin{align*}
langle x,yrangle &:= {x,{x,y}}\
xtimes y &:={win U | exists uin x,vin y. w = langle u,vrangle}\
text{fun}(A,B)&:={alphain mathcal P(Atimes B) | forall uin A. exists! vin B. langle u,vrangleinalpha}.
end{align*}

Let us now suppose we have a type theory System M with universe $text{Type}$, equality types $s =_A t$, dependent sums $Sigma_{x:A}B$, and arrow types $Ato B$. In this system we would simply define the type of monoids as
$$text{Mon}_M := Sigma_{M:Type}Sigma_{star:(Mtimes Mto M)}Sigma_{1:M}P(M,star,1)$$
where $P(M,star,1)$ are the type-theoretic monoid axioms.
$newcommand{llb}{[![}newcommand{rrb}{]!]}$

What is important here is that we can encode System M into System S as follows

  • For a suitable set universe $U$ we encode
    $$llb text{Type}rrb_sigma := U$$
  • The function space is encoded
    $$llb Ato Brrb_sigma := text{fun}(llb Arrb_sigma,llb Brrb_sigma)$$
  • Supposing $x:Avdash t:B$ we encode lambda abstractions as
    $$llb lambda x:A.trrb_sigma := {win llb Arrb_sigmatimes llb Brrb_sigma | forall uinllb Arrb_sigma, vinllb Brrb_sigma. w = (u,v)implies v = llb trrb_{sigma,xmapsto u}}$$
  • and a variable $x:A$ as
    $$llb xrrb_sigma := sigma(x).$$
  • Given a type family $B:Ato text{Type}$ (written this way for simplicity), we encode dependent sums as
    $$llbSigma_{x:A}Brrb_sigma :={zin llb Arrb_sigmatimesllb text{Type}rrb_sigma |
    forall xinllb Arrb_sigma,yinllb text{Type}rrb_sigma. z = (x,y)implies \ yin llb Brrb_sigma(x)}.$$
  • We can encode equality as
    $$llb s =_A trrb_sigma := {xin{emptyset} | llb srrb_sigma = llb trrb_sigma}$$
  • and a proof $p: s =_A t$ is encoded
    $$llb prrb_sigma := emptyset.$$

And of course, one should check that for every $t : A$, the encoding satisfies
$$llb trrb_{[]} in llb Arrb_{[]}qquadtext{(for $[]$ the empty valuation)}.$$

Now if we take $M:text{Mon}_M$, $llb Mrrb_{[]}$ is the encoding of the monoid $M$ in System S, although this encoding is a bit more complicated than the definition of a monoid directly in System S described by $text{Mon}_S$.

Now why should we bother going through all this effort? The reason is that the definition of a monoid in this type theory is much better behaved than that in set theory. What System M does is give a coarser abstraction layer above System S. So whereas it would make sense to ask a meaningless question such as whether $emptyset in llb Mrrb$ in System S, such a question cannot even be stated within System M. In fact, the only things that can be stated about $M$ are statements in the theory of monoids, unless we add assumptions about $M$. This explains how type theory gives us a way to talk about objects independently of their encoding.

Tagged : / / / /

Math Genius: If our axioms don’t describe everything why don’t we just add new ones?

Original Source Link

In reading https://mathoverflow.net/questions/1924/what-are-some-reasonable-sounding-statements-that-are-independent-of-zfc?page=2&tab=votes#tab-top I began to wonder: if our axioms don’t describe everything then why don’t we just add new ones?

Why are we no longer looking for axioms that could help us solve polynomials degree 5?

Why have we (mostly) given up on proving the continuum hypothesis only because it is independent of our axioms?

I’m sure there are many other problems like these. I’m puzzled because a solution to them would be extremely useful, and the purpose of mathematics is ultimately to solve problems (unless you are a game formalist, of course ;)).

Addition I know no axioms are complete, but certainly some systems are better than others.

This is a soft question.

Tagged : /